GCC x86-64下两种近似等价前缀和计算方法为何性能差4倍？

两种代码逻辑完全一致，都是对数组重复执行100万次前缀和计算，但经-O2编译后性能差距显著，核心原因是编译器对两个循环的优化策略不同：

代码对比 #

第一种实现 #

#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);
}

核心优化差异分析 #

• 循环展开程度不同
  GCC在-O2级别会自动对适合的循环进行循环展开，减少循环控制指令（如cmp、jne）的执行开销，同时利用CPU的指令级并行能力提升效率。第一种循环的索引形式（i从1开始，直接访问当前元素与前一个元素）更符合编译器循环展开的识别规则，被进行了多轮展开；而第二种循环的索引形式（i从0开始，通过i+1访问下一个元素）未被编译器进行同等程度的展开，导致每次循环的控制开销占比更高，整体执行效率更低。

• 寄存器重用策略不同
  第一种循环中，编译器能识别出前缀和的链式依赖关系——每次迭代的结果依赖前一个元素的更新值，因此将前一个元素的值保存在寄存器（如eax）中，避免了每次迭代从内存重新加载前一个元素的开销；而第二种循环中，编译器未优化出这种寄存器重用逻辑，每次迭代都需要从内存加载当前元素，增加了内存访问的延迟。

这两个优化差异叠加，最终导致两种实现的运行时间相差4倍。

内容的提问来源于stack exchange，提问作者platelet