gcc 优化标志 -O3 使代码比 -O2 慢

Question

我找到了这个主题 Why is it faster to process a sorted array than an unsorted array?。并尝试运行这段代码。我发现奇怪的行为。如果我用 -O3 优化标志编译这段代码，它需要 2.98605 sec 到运行。如果我用 -O2 编译它需要 1.98093 sec。我尝试运行在同一台机器上的同一环境中多次（5 或 6 次）此代码，我关闭了所有其他软件（chrome、skype 等）。

gcc --version
gcc (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

所以请你解释一下为什么会这样？我阅读了 gcc 手册，我看到 -O3 包括 -O2。谢谢你的帮助。

P.S. 添加代码

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Answer 1

gcc -O3 使用 cmov for the conditional, so it lengthens the loop-carried dependency chain to include a cmov (which is 2 uops and 2 cycles of latency on your Intel Sandybridge CPU, according to Agner Fog's instruction tables. See also the x86 tag wiki). This is one of the cases where cmov sucks.

如果数据甚至有点不可预测，cmov 可能会获胜，因此这是编译器做出的相当明智的选择。（然而，compilers may sometimes use branchless code too much。）

我 put your code on the Godbolt compiler explorer 查看 asm（突出显示并过滤掉不相关的行。不过，您仍然必须向下滚动所有排序代码才能到达 main()）。

.L82:  # the inner loop from gcc -O3
    movsx   rcx, DWORD PTR [rdx]  # sign-extending load of data[c]
    mov     rsi, rcx
    add     rcx, rbx        # rcx = sum+data[c]
    cmp     esi, 127
    cmovg   rbx, rcx        # sum = data[c]>127 ? rcx : sum
    add     rdx, 4          # pointer-increment
    cmp     r12, rdx
    jne     .L82

gcc 可以通过使用 LEA 而不是 ADD 来保存 MOV。

ADD->CMOV（3 个周期）延迟的循环瓶颈，因为循环的一次迭代使用 CMO 写入 rbx，而下一次迭代使用 ADD 读取 rbx。

该循环仅包含 8 个融合域微指令，因此它可以每 2 个周期发出一个。执行端口压力也不像 sum dep 链的延迟那么严重，但它很接近（Sandybridge 只有 3 个 ALU 端口，不像 Haswell 的 4 个）。

顺便说一句，将其写成 sum += (data[c] >= 128 ? data[c] : 0); 以将 cmov 从循环携带的 dep 链中取出可能很有用。仍然有很多指令，但每次迭代中的 cmov 是独立的。这个compiles as expected in gcc6.3 -O2 and earlier, but gcc7 de-optimizes into a cmov on the critical path (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82666)。（它还可以使用比 if() 编写方式更早的 gcc 版本进行自动矢量化。）

Clang 将 cmov 移出关键路径，即使是原始源也是如此。

gcc -O2 使用一个分支（适用于 gcc5.x 及更早的版本），它预测得很好，因为您的数据已排序。由于现代 CPU 使用分支预测来处理控制依赖性，因此循环携带的依赖性链更短：只有 add（1 个周期延迟）。

每次迭代中的比较和分支都是独立的，这要归功于分支预测 + 推测执行，它可以让执行在确定分支方向之前继续进行。

.L83:   # The inner loop from gcc -O2
    movsx   rcx, DWORD PTR [rdx]  # load with sign-extension from int32 to int64
    cmp     ecx, 127
    jle     .L82        # conditional-jump over the next instruction 
    add     rbp, rcx    # sum+=data[c]
.L82:
    add     rdx, 4
    cmp     rbx, rdx
    jne     .L83

有两个循环携带的依赖链：sum和循环计数器。 sum 是 0 或 1 个周期长，循环计数器总是 1 个周期长。然而，循环在 Sandybridge 上是 5 个融合域 uops，所以无论如何它不能以每次迭代 1c 的速度执行，所以延迟不是瓶颈。

它可能运行s 大约每 2 个周期迭代一次（分支指令吞吐量瓶颈），而 -O3 循环每 3 个周期迭代一次。下一个瓶颈是 ALU 微指令吞吐量：4 个 ALU 微指令（在未采用的情况下）但只有 3 个 ALU 端口。（ADD 可以运行在任何端口上）。

此流水线分析预测与 -O3 ~3 秒与 -O2 ~2 秒的时间安排非常匹配。

Haswell/Skylake 可以运行每 1.25 个周期一个未采用的情况，因为它可以在与采用的分支相同的周期中执行一个未采用的分支，并且有 4 个 ALU 端口。（或自以来略有减少）。

(刚刚测试：Skylake @ 3.9GHz 运行s整个程序的branchy版本在1.45s，或者branchless版本在1.68s。所以那里的差异要小得多。)

g++6.3.1 即使在 -O2 时也使用 cmov，但 g++5.4 仍然表现得像 4.9.2.

对于 g++6.3.1 和 g++5.4，使用 -fprofile-generate / -fprofile-use 即使在 -O3 时也会产生分支版本（使用 -fno-tree-vectorize） .

来自较新 gcc 的循环的 CMOV 版本使用 add ecx,-128 / cmovge rbx,rdx 而不是 CMP/CMOV。这有点奇怪，但可能不会减慢速度。 ADD 写入输出寄存器以及标志，因此对物理寄存器的数量造成更大压力。但只要不是瓶颈，应该差不多。

较新的 gcc 使用 -O3 自动矢量化循环，即使只有 SSE2，这也是一个显着的加速。（例如我的 i7-6700k Skylake 运行是矢量化版本在 0.74 秒内，大约是标量的两倍。或者 -O3 -march=native 在 0.35 秒内，使用 AVX2 256b 向量）。

矢量化版本看起来有很多指令，但还算不错，而且其中大部分都不是循环携带的 dep 链的一部分。它只需要在接近尾声时解包为 64 位元素。但是，它执行了 pcmpgtd 两次，因为它没有意识到当条件已经将所有负整数置零时它可以只进行零扩展而不是符号扩展。

gcc 优化标志 -O3 使代码比 -O2 慢

gcc optimization flag -O3 makes code slower than -O2

c++

optimization

gcc

cpu-architecture

compiler-optimization