提问人：platelet 提问时间：11/7/2023 最后编辑：platelet 更新时间：11/7/2023 访问量：142
使用 GCC 计算 x86-64 的前缀总和的两种看似等效的方法之间的显着速度差异
Significant speed difference between two seemingly-equivalent methods of calculating prefix sums with GCC for x86-64
问：
我尝试了两种几乎相同的前缀总和计算方法，发现它们在编译后有显着差异。编译选项为 。-O2
不同的编译结果导致它们的运行时间相差 4 倍。
第一个：
#include <numeric>
#include <algorithm>
int main() {
unsigned a[5000];
std::iota(a, a + 5000, 0);
for (int k = 0; k < 1'000'000; k++)
for (int i = 1; i < 5000; i++)
a[i] += a[i - 1];
return *std::min_element(a, a + 5000);
}
第二种：
#include <numeric>
#include <algorithm>
int main() {
unsigned a[5000];
std::iota(a, a + 5000, 0);
for (int k = 0; k < 1'000'000; k++)
for (int i = 0; i + 1 < 5000; i++)
a[i + 1] += a[i];
return *std::min_element(a, a + 5000);
}
编译器中出现此异常的原因可能是什么？
答：
4赞
harold
11/7/2023
#1
在版本 2 中，我们看到 GCC 已经做到了这一点，
.L4:
add edx, DWORD PTR [rax]
add rax, 4
mov DWORD PTR [rax-4], edx
cmp rcx, rax
jne .L4
因此，在 中累积值，在其中添加一个新元素并将累积的总和存储到内存中。这很好，这里没有问题。edx
在版本 1 中，我们看到 GCC 已经做到了这一点，
.L4:
mov edx, DWORD PTR [rax-4]
add DWORD PTR [rax], edx
add rax, 4
cmp rax, rcx
jne .L4
在这里，再次加载先前存储的部分总和，然后将其添加到当前元素中。
这不好，内存存在循环携带的依赖关系，将存储+重新加载的延迟放在关键路径上。在各种 CPU 上，每次迭代可能是 5 或 6 个周期。在版本 2 中，类似的依赖关系通过而不是通过内存，这在每个 CPU 上都非常有效，让循环以每次迭代接近 1.5 个周期的速度执行。基于这种影响，预计性能差异约为 4 倍。edx
在一些较新的 CPU 上，如果 CPU 在这种情况下可以使用内存重命名（零延迟存储来加载转发），它可能不会那么糟糕。然而，关于英特尔 Ice Lake，Agner Fog 写道：
快进在 以下情况，根据我的测试：
......
- 读-修改-写指令
我们这里确实有一个读取-修改-写入指令，所以这可能不好。
对于AMD风格的内存重命名，显然内存操作数必须完全匹配（不仅仅是计算地址，还有指定地址的方式），我们这里没有，所以它可能也不好。
我不知道为什么 GCC 会以如此不同的方式编译这两个版本。也许有一个原因，我只是想不出来，但也许它只是运气不好。
评论
3赞
NathanOliver
11/7/2023
FWIW，较新版本的 GCC 似乎已修复此问题。GCC12 和 13 都产生相同的组件。
下一个：如何找到最大乘积的总和？
评论