使用 GCC 针对 x86-64 计算前缀和的两种看似等效的方法之间存在显着的速度差异

Question

我尝试了两种几乎相同的计算前缀和的方法，发现它们编译后有显着差异。编译选项是-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);
}

在编译器资源管理器中

编译器中出现此异常的原因可能是什么？

Answer 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 中，类似的依赖关系也经历了edx内存而不是通过内存，这在每个 CPU 上都非常高效，让循环每次迭代执行接近 1.5 个周期。根据该效果，预计性能差异约为 4 倍。

在某些较新的 CPU 上，如果 CPU 在这种情况下可以使用内存重命名（零延迟存储到加载转发），那么情况可能不会那么糟糕。然而，关于英特尔 Ice Lake，Agner Fog 写道：

根据我的测试，快进在以下情况下不起作用：
...

• 读-修改-写指令

我们这里确实有一个读-修改-写指令，所以这可能不好。

对于 AMD 风格的内存重命名，显然内存操作数必须完全匹配（不仅仅是计算的地址，还有指定的方式），而我们这里没有，所以它可能也不好。

我不知道为什么GCC 会以如此不同的方式编译这两个版本。也许是有原因的，只是我想不到，但也许只是运气不好。