优化长时间的内存读写
Optimizing Long Runs of Memory Reads and Writes
我有一个名为 reorder.cc 的源文件，如下所示：
void reorder(float *output, float *input) {
output[56] = input[0];
output[57] = input[1];
output[58] = input[2];
output[59] = input[3];
output[60] = input[4];
...
output[75] = input[19];
output[76] = input[20];
output[77] = input[21];
output[78] = input[22];
output[79] = input[23];
output[80] = input[24];
...
output[98] = 0;
output[99] = 0;
output[100] = 0;
output[101] = 0;
output[102] = 0;
output[103] = 0;
output[104] = 0;
output[105] = input[1];
output[106] = input[2];
output[107] = input[3];
output[108] = input[4];
output[109] = input[5];
output[110] = input[6];
output[111] = 0;
...
}
reorder 函数有一个非常长的从输入缓冲区到输出缓冲区的内存移动操作列表。输入到输出的对应关系很复杂，但一般有足够长的 运行 至少 10 个浮点数保证是连续的。 运行 被一个新的 运行 打断，该 运行 从任意输入索引开始，或者是“0”值。
带有 (g++-6 -march=native -Ofast -S reorder.cc) 的关联程序集文件 (.S) 生成以下程序集：
.file "reorder.cc"
.text
.p2align 4,,15
.globl _Z9optimizedPfS_
.type _Z9optimizedPfS_, @function
_Z9optimizedPfS_:
.LFB0:
.cfi_startproc
movss (%rsi), %xmm0
movss %xmm0, 32(%rdi)
movss 4(%rsi), %xmm0
movss %xmm0, 36(%rdi)
movss 8(%rsi), %xmm0
movss %xmm0, 40(%rdi)
movss 12(%rsi), %xmm0
movss %xmm0, 44(%rdi)
movss 16(%rsi), %xmm0
movss %xmm0, 48(%rdi)
movss 20(%rsi), %xmm0
movss %xmm0, 52(%rdi)
movss 28(%rsi), %xmm0
movss %xmm0, 60(%rdi)
movss 32(%rsi), %xmm0
movss %xmm0, 64(%rdi)
movss 36(%rsi), %xmm0
...
... 对应于每条装配线的单个移动单个标量 (fp32) 值。我认为编译器足够聪明，可以编译成更智能的指令，如 MOVDQU（移动未对齐的双四字，适用于 128 位字）足够长 运行s?
我正在考虑手写一个简单的解析器，它需要这么长的 运行s 并自动调用 movdqu，但我发现这很乏味、笨拙且容易出错。
是否有一个特殊的编译器标志可以自动检测这些长 运行 并生成高效指令？我是注定要使用内部函数来进一步优化这段代码，还是有一个聪明的技巧可以自动为我做这个簿记？
reorder.cc 大约是这些输入、输出对的 100,000 条指令，这是我正在处理的较小的测试用例。
此外，关于编译这些移动指令的 100K+ 行或更多行的大型源文件有什么技巧吗？对于 Macbook Pro i7 处理器，g++-6 -Ofast 在像这样的 1M 行文件上需要数小时。
首先，在其他函数中读取 input[] 时，可能（或可能不）值得在运行中执行此操作。如果洗牌有任何模式，那可能还不错。 OTOH，无论您将此数组提供给什么，它都可能会破坏预取。
您是否尝试过使用 __restrict__ 告诉编译器通过一个指针访问不能与通过另一个指针访问别名？如果它自己无法证明这一点，则不允许在源像这样交错时组合加载或存储。
restrict 是一个 C99 特性，它不包含在 ISO C++ 中，但是 the common C++ compilers support __restrict__ or __restrict as an extension。在 MSVC 上使用 CPP 宏 #define __restrict__ __restrict，或者在不支持任何等效项的编译器上使用空字符串。
gcc 在 load/store 合并方面很糟糕，但 clang 却没有。
这是 gcc 中长期存在的错误，它在合并 loads/stores 时很糟糕（请参阅 bugzilla link，但我想我记得更早以前看到过另一个错误报告，例如 gcc4。 0 或其他）。它更经常遇到结构复制（逐个成员生成loads/stores），但这里是同样的问题。
使用 __restrict__，clang 能够将示例函数中的大部分 loads/stores 合并为 xmm 或 ymm 向量 。它甚至生成最后三个元素的向量负载和标量 vpextrd！从 clang++3.8 -O3 -march=haswell.
查看 the Godbolt compiler explorer 上的代码 + asm 输出
使用相同的源代码，g++6.1 仍然完全无法合并任何内容，甚至是连续的零。 （尝试将编译器翻转到 gcc on godbolt）。即使我们使用 -march=haswell 进行编译，其中未对齐的向量非常便宜，它甚至在使用小 memcpy 时也做得很差，不使用 SIMD。 :/
如果有任何类型的模式，利用 reorder() 函数中的模式来节省代码大小将大有帮助。即使 loads/stores 合并为 SIMD 向量，您仍然会耗尽 uop 缓存和 L1 指令缓存。代码获取将与数据 load/store 竞争 L2 带宽。一旦您的数组索引对于 8 位位移变得太大，每条指令的大小将变得更大。 （操作码字节 + ModRM 字节 + disp32）。如果它不合并，gcc 没有将这些移动优化为 32 位 mov 指令（1 个操作码字节）而不是 movss (3 opcode bytes)
就太糟糕了
所以在这个函数 returns 之后，你的程序的其余部分将 运行 在很短的时间内比正常情况慢，因为 32kiB L1 指令缓存和更小的 uop 缓存将是冷的（充满了来自臃肿的重新排序功能的 mov 指令）。使用 perf 计数器查看 I-cache 未命中数。另见 x86 tag wiki to learn more about x86 performance, especially Agner Fog's guides.
正如您在评论中所建议的，calloc 是在您需要新的输出缓冲区时避免归零部分的好方法。它确实利用了这样一个事实，即来自 OS 的新页面无论如何都会从零开始（以避免信息泄漏）。不过，重用现有缓冲区比释放它并调用一个新缓冲区要好，因为旧缓冲区在缓存 and/or TLB 中仍然很热。至少页面仍然是有线的，而不是在你第一次触摸它们时出现故障。
使用 memcpy 和 memset 代替每个元素的赋值可能会有助于您的编译时间。 如果源代码非常重复，您可能可以用 perl（或您选择的文本操作语言）编写一些内容，将连续 运行 次复制转换为 memset 调用。
如果有任何大的 运行s（如 128 字节或更多），理想的 asm 在许多 CPU 上是 rep movsd（或 rep movsq），尤其是最近的 Intel。 gcc 通常将 memcpy 内联到 rep movs 而不是调用库 memcpy 当大小在编译时已知时，你甚至可以 tune the strategy (SIMD vs. rep movs) with -mstringop-strategy。如果没有可让您将其编码为循环的模式，那么代码大小的节省可能对您来说是一个重大的好处。
如果您的模式允许，可能值得复制一个更大的连续块，然后返回到零或将其他内容复制到几个元素中，因为 rep movs 具有显着的启动开销，但一旦它运行时性能非常好起来 运行ning。 （避免在 Intel CPU 上存储整个缓存行时读取所有权开销，甚至在 IvB 的快速 rep movsb 功能之前。）
如果你不能只用 clang 而不是 gcc 编译这个目标文件，也许你应该看看自己为它生成 asm。如果这会显着降低您的程序速度（并且复制那么多内存 + 取消指令缓存可能会这样做），那么一些文本处理可以将范围列表转换为设置 rsi、[=35 的 asm =]，ecx rep movsd。
按顺序读取输入可能比按顺序写入输出提供更好的性能。缓存未命中存储对管道的影响通常小于缓存未命中加载。 OTOH，一起为单个缓存行执行所有存储可能是一件好事。如果这是一个重大瓶颈，值得一试。
如果您确实使用了内在函数，那么对于覆盖整个缓存行（64B 大小，64B 对齐）的连续 运行 部分使用 NT 存储可能是值得的，如果您的数组真的很大。或者使用 NT 存储按顺序存储？
NT 加载可能是个好主意，但 IDK if the NT hint does anything at all on normal write-back memory。它们不是弱排序的，但有一些方法可以减少缓存污染（我的猜测参见 link）。
就地随机播放可能是个好主意，如果这对您的程序有用的话。由于输出包含一些 运行 的零，我假设它比输入长。在这种情况下，如果您从数组的末尾开始，就地执行它可能是最简单的。我怀疑就地洗牌不是你想要的，所以我不会说太多。
一个版本，例如使用 movups 或 movdqu，意味着有效地并行执行赋值，如果函数的参数可能有别名，这可能是不正确的。
如果他们不使用别名，您可以使用非标准 __restrict__ 关键字。
也就是说，gcc 仍将只矢量化循环，因此重写程序如下：
// #define __restrict__
void reorder(float * __restrict__ output, float * __restrict__ input) {
for (auto i = 0; i < 5; i++)
output[i+56] = input[i];
for (auto i = 0; i < 6; i++)
output[i+75] = input[i+19];
for (auto i = 0; i < 7; i++)
output[i+98] = 0;
for (auto i = 0; i < 6; i++)
output[i+105] = input[i+1];
output[111] = 0;
}
这个，用 -O2 -ftree-vectorize 编译，生成：
reorder(float*, float*):
movups xmm0, XMMWORD PTR [rsi]
movups XMMWORD PTR [rdi+224], xmm0
movss xmm0, DWORD PTR [rsi+16]
movss DWORD PTR [rdi+240], xmm0
movups xmm0, XMMWORD PTR [rsi+76]
movups XMMWORD PTR [rdi+300], xmm0
movss xmm0, DWORD PTR [rsi+92]
movss DWORD PTR [rdi+316], xmm0
movss xmm0, DWORD PTR [rsi+96]
movss DWORD PTR [rdi+320], xmm0
pxor xmm0, xmm0
movups xmm1, XMMWORD PTR [rsi+4]
movups XMMWORD PTR [rdi+392], xmm0
pxor xmm0, xmm0
movups XMMWORD PTR [rdi+420], xmm1
movss DWORD PTR [rdi+408], xmm0
movss DWORD PTR [rdi+412], xmm0
movss xmm1, DWORD PTR [rsi+20]
movss DWORD PTR [rdi+436], xmm1
movss xmm1, DWORD PTR [rsi+24]
movss DWORD PTR [rdi+416], xmm0
movss DWORD PTR [rdi+440], xmm1
movss DWORD PTR [rdi+444], xmm0
ret
不太理想，但仍然有一些动作是用一个 insn 完成的。
我有一个名为 reorder.cc 的源文件，如下所示：
void reorder(float *output, float *input) {
output[56] = input[0];
output[57] = input[1];
output[58] = input[2];
output[59] = input[3];
output[60] = input[4];
...
output[75] = input[19];
output[76] = input[20];
output[77] = input[21];
output[78] = input[22];
output[79] = input[23];
output[80] = input[24];
...
output[98] = 0;
output[99] = 0;
output[100] = 0;
output[101] = 0;
output[102] = 0;
output[103] = 0;
output[104] = 0;
output[105] = input[1];
output[106] = input[2];
output[107] = input[3];
output[108] = input[4];
output[109] = input[5];
output[110] = input[6];
output[111] = 0;
...
}
reorder 函数有一个非常长的从输入缓冲区到输出缓冲区的内存移动操作列表。输入到输出的对应关系很复杂，但一般有足够长的 运行 至少 10 个浮点数保证是连续的。 运行 被一个新的 运行 打断，该 运行 从任意输入索引开始，或者是“0”值。
带有 (g++-6 -march=native -Ofast -S reorder.cc) 的关联程序集文件 (.S) 生成以下程序集：
.file "reorder.cc"
.text
.p2align 4,,15
.globl _Z9optimizedPfS_
.type _Z9optimizedPfS_, @function
_Z9optimizedPfS_:
.LFB0:
.cfi_startproc
movss (%rsi), %xmm0
movss %xmm0, 32(%rdi)
movss 4(%rsi), %xmm0
movss %xmm0, 36(%rdi)
movss 8(%rsi), %xmm0
movss %xmm0, 40(%rdi)
movss 12(%rsi), %xmm0
movss %xmm0, 44(%rdi)
movss 16(%rsi), %xmm0
movss %xmm0, 48(%rdi)
movss 20(%rsi), %xmm0
movss %xmm0, 52(%rdi)
movss 28(%rsi), %xmm0
movss %xmm0, 60(%rdi)
movss 32(%rsi), %xmm0
movss %xmm0, 64(%rdi)
movss 36(%rsi), %xmm0
...
... 对应于每条装配线的单个移动单个标量 (fp32) 值。我认为编译器足够聪明，可以编译成更智能的指令，如 MOVDQU（移动未对齐的双四字，适用于 128 位字）足够长 运行s?
我正在考虑手写一个简单的解析器，它需要这么长的 运行s 并自动调用 movdqu，但我发现这很乏味、笨拙且容易出错。
是否有一个特殊的编译器标志可以自动检测这些长 运行 并生成高效指令？我是注定要使用内部函数来进一步优化这段代码，还是有一个聪明的技巧可以自动为我做这个簿记？
reorder.cc 大约是这些输入、输出对的 100,000 条指令，这是我正在处理的较小的测试用例。
此外，关于编译这些移动指令的 100K+ 行或更多行的大型源文件有什么技巧吗？对于 Macbook Pro i7 处理器，g++-6 -Ofast 在像这样的 1M 行文件上需要数小时。
首先，在其他函数中读取 input[] 时，可能（或可能不）值得在运行中执行此操作。如果洗牌有任何模式，那可能还不错。 OTOH，无论您将此数组提供给什么，它都可能会破坏预取。
您是否尝试过使用 __restrict__ 告诉编译器通过一个指针访问不能与通过另一个指针访问别名？如果它自己无法证明这一点，则不允许在源像这样交错时组合加载或存储。
restrict 是一个 C99 特性，它不包含在 ISO C++ 中，但是 the common C++ compilers support __restrict__ or __restrict as an extension。在 MSVC 上使用 CPP 宏 #define __restrict__ __restrict，或者在不支持任何等效项的编译器上使用空字符串。
gcc 在 load/store 合并方面很糟糕，但 clang 却没有。
这是 gcc 中长期存在的错误，它在合并 loads/stores 时很糟糕（请参阅 bugzilla link，但我想我记得更早以前看到过另一个错误报告，例如 gcc4。 0 或其他）。它更经常遇到结构复制（逐个成员生成loads/stores），但这里是同样的问题。
使用 __restrict__，clang 能够将示例函数中的大部分 loads/stores 合并为 xmm 或 ymm 向量 。它甚至生成最后三个元素的向量负载和标量 vpextrd！从 clang++3.8 -O3 -march=haswell.
使用相同的源代码，g++6.1 仍然完全无法合并任何内容，甚至是连续的零。 （尝试将编译器翻转到 gcc on godbolt）。即使我们使用 -march=haswell 进行编译，其中未对齐的向量非常便宜，它甚至在使用小 memcpy 时也做得很差，不使用 SIMD。 :/
如果有任何类型的模式，利用 reorder() 函数中的模式来节省代码大小将大有帮助。即使 loads/stores 合并为 SIMD 向量，您仍然会耗尽 uop 缓存和 L1 指令缓存。代码获取将与数据 load/store 竞争 L2 带宽。一旦您的数组索引对于 8 位位移变得太大，每条指令的大小将变得更大。 （操作码字节 + ModRM 字节 + disp32）。如果它不合并，gcc 没有将这些移动优化为 32 位 mov 指令（1 个操作码字节）而不是 movss (3 opcode bytes)
所以在这个函数 returns 之后，你的程序的其余部分将 运行 在很短的时间内比正常情况慢，因为 32kiB L1 指令缓存和更小的 uop 缓存将是冷的（充满了来自臃肿的重新排序功能的 mov 指令）。使用 perf 计数器查看 I-cache 未命中数。另见 x86 tag wiki to learn more about x86 performance, especially Agner Fog's guides.
正如您在评论中所建议的，calloc 是在您需要新的输出缓冲区时避免归零部分的好方法。它确实利用了这样一个事实，即来自 OS 的新页面无论如何都会从零开始（以避免信息泄漏）。不过，重用现有缓冲区比释放它并调用一个新缓冲区要好，因为旧缓冲区在缓存 and/or TLB 中仍然很热。至少页面仍然是有线的，而不是在你第一次触摸它们时出现故障。
使用 memcpy 和 memset 代替每个元素的赋值可能会有助于您的编译时间。 如果源代码非常重复，您可能可以用 perl（或您选择的文本操作语言）编写一些内容，将连续 运行 次复制转换为 memset 调用。
如果有任何大的 运行s（如 128 字节或更多），理想的 asm 在许多 CPU 上是 rep movsd（或 rep movsq），尤其是最近的 Intel。 gcc 通常将 memcpy 内联到 rep movs 而不是调用库 memcpy 当大小在编译时已知时，你甚至可以 tune the strategy (SIMD vs. rep movs) with -mstringop-strategy。如果没有可让您将其编码为循环的模式，那么代码大小的节省可能对您来说是一个重大的好处。
如果您的模式允许，可能值得复制一个更大的连续块，然后返回到零或将其他内容复制到几个元素中，因为 rep movs 具有显着的启动开销，但一旦它运行时性能非常好起来 运行ning。 （避免在 Intel CPU 上存储整个缓存行时读取所有权开销，甚至在 IvB 的快速 rep movsb 功能之前
如果你不能只用 clang 而不是 gcc 编译这个目标文件，也许你应该看看自己为它生成 asm。如果这会显着降低您的程序速度（并且复制那么多内存 + 取消指令缓存可能会这样做），那么一些文本处理可以将范围列表转换为设置 rsi、[=35 的 asm =]，ecx rep movsd。
按顺序读取输入可能比按顺序写入输出提供更好的性能。缓存未命中存储对管道的影响通常小于缓存未命中加载。 OTOH，一起为单个缓存行执行所有存储可能是一件好事。如果这是一个重大瓶颈，值得一试。
如果您确实使用了内在函数，那么对于覆盖整个缓存行（64B 大小，64B 对齐）的连续 运行 部分使用 NT 存储可能是值得的，如果您的数组真的很大。或者使用 NT 存储按顺序存储？
NT 加载可能是个好主意，但 IDK if the NT hint does anything at all on normal write-back memory。它们不是弱排序的，但有一些方法可以减少缓存污染（我的猜测参见 link）。
就地随机播放可能是个好主意，如果这对您的程序有用的话。由于输出包含一些 运行 的零，我假设它比输入长。在这种情况下，如果您从数组的末尾开始，就地执行它可能是最简单的。我怀疑就地洗牌不是你想要的，所以我不会说太多。
一个版本，例如使用 movups 或 movdqu，意味着有效地并行执行赋值，如果函数的参数可能有别名，这可能是不正确的。
如果他们不使用别名，您可以使用非标准 __restrict__ 关键字。
也就是说，gcc 仍将只矢量化循环，因此重写程序如下：
// #define __restrict__
void reorder(float * __restrict__ output, float * __restrict__ input) {
for (auto i = 0; i < 5; i++)
output[i+56] = input[i];
for (auto i = 0; i < 6; i++)
output[i+75] = input[i+19];
for (auto i = 0; i < 7; i++)
output[i+98] = 0;
for (auto i = 0; i < 6; i++)
output[i+105] = input[i+1];
output[111] = 0;
}
这个，用 -O2 -ftree-vectorize 编译，生成：
reorder(float*, float*):
movups xmm0, XMMWORD PTR [rsi]
movups XMMWORD PTR [rdi+224], xmm0
movss xmm0, DWORD PTR [rsi+16]
movss DWORD PTR [rdi+240], xmm0
movups xmm0, XMMWORD PTR [rsi+76]
movups XMMWORD PTR [rdi+300], xmm0
movss xmm0, DWORD PTR [rsi+92]
movss DWORD PTR [rdi+316], xmm0
movss xmm0, DWORD PTR [rsi+96]
movss DWORD PTR [rdi+320], xmm0
pxor xmm0, xmm0
movups xmm1, XMMWORD PTR [rsi+4]
movups XMMWORD PTR [rdi+392], xmm0
pxor xmm0, xmm0
movups XMMWORD PTR [rdi+420], xmm1
movss DWORD PTR [rdi+408], xmm0
movss DWORD PTR [rdi+412], xmm0
movss xmm1, DWORD PTR [rsi+20]
movss DWORD PTR [rdi+436], xmm1
movss xmm1, DWORD PTR [rsi+24]
movss DWORD PTR [rdi+416], xmm0
movss DWORD PTR [rdi+440], xmm1
movss DWORD PTR [rdi+444], xmm0
ret
不太理想，但仍然有一些动作是用一个 insn 完成的。