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

我找到这个话题为什么处理排序数组比处理未排序数组更快？ https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array?rq=1。并尝试运行这段代码。我发现奇怪的行为。如果我用以下代码编译这段代码-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;
}

gcc -O3 uses a cmov http://felixcloutier.com/x86/CMOVcc.html对于条件，因此它延长了循环携带的依赖链以包括cmov（根据 Intel Sandybridge CPU 的说法，这是 2 uop 和 2 个周期的延迟Agner Fog 的说明书 http://agner.org/optimize/。另请参阅x86 /questions/tagged/x86标签维基）。这是其中一种情况cmov sucks http://yarchive.net/comp/linux/cmov.html.

如果数据具有一定程度的不可预测性，cmov可能会是一个胜利，所以这对于编译器来说是一个相当明智的选择。 （然而，编译器有时可能会过多使用无分支代码 https://bugs.llvm.org/show_bug.cgi?id=33013.)

I 将您的代码放在 Godbolt 编译器资源管理器上 https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(j:1,source:'%23include+%3Calgorithm%3E%0A%23include+%3Cctime%3E%0A%23include+%3Ciostream%3E%0A%0Aint+main()%0A%7B%0A++++//+Generate+data%0A++++const+unsigned+arraySize+%3D+32768%3B%0A++++int+data%5BarraySize%5D%3B%0A%0A++++for+(unsigned+c+%3D+0%3B+c+%3C+arraySize%3B+%2B%2Bc)%0A++++++++data%5Bc%5D+%3D+std::rand()+%25+256%3B%0A%0A++++//+!!!!!!+With+this,+the+next+loop+runs+faster%0A++++std::sort(data,+data+%2B+arraySize)%3B%0A%0A++++//+Test%0A++++clock_t+start+%3D+clock()%3B%0A++++long+long+sum+%3D+0%3B%0A%0A++++for+(unsigned+i+%3D+0%3B+i+%3C+100000%3B+%2B%2Bi)%0A++++%7B%0A++++++++//+Primary+loop%0A++++++++for+(unsigned+c+%3D+0%3B+c+%3C+arraySize%3B+%2B%2Bc)%0A++++++++%7B%0A++++++++++++if+(data%5Bc%5D+%3E%3D+128)%0A++++++++++++++++sum+%2B%3D+data%5Bc%5D%3B%0A++++++++%7D%0A++++%7D%0A%0A++++double+elapsedTime+%3D+static_cast%3Cdouble%3E(clock()+-+start)+/+CLOCKS_PER_SEC%3B%0A%0A++++std::cout+%3C%3C+elapsedTime+%3C%3C+std::endl%3B%0A++++std::cout+%3C%3C+%22sum+%3D+%22+%3C%3C+sum+%3C%3C+std::endl%3B%0A%7D%0A'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:33.36599326802078,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g492,filters:(b:'0',commentOnly:'0',directives:'0',intel:'0'),options:'-O2+-std%3Dgnu%2B%2B11+-Wall+',source:1),l:'5',n:'0',o:'x86-64+gcc+4.9.2+(Editor+%231,+Compiler+%231)',t:'0')),k:32.731651559407744,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g492,filters:(b:'0',commentOnly:'0',directives:'0',intel:'0'),options:'-O3+-std%3Dgnu%2B%2B11+-Wall',source:1),l:'5',n:'0',o:'x86-64+gcc+4.9.2+(Editor+%231,+Compiler+%232)',t:'0')),k:33.90235517257147,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4查看 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 个周期可以发出一个。执行端口压力也不像执行端口的延迟那样是一个严重的瓶颈。sumdep 链，但很接近（Sandybridge 只有 3 个 ALU 端口，与 Haswell 的 4 个不同）。

顺便说一句，写成sum += (data[c] >= 128 ? data[c] : 0);采取cmov循环外携带的 dep 链可能很有用。仍然有很多说明，但是cmov每次迭代都是独立的。这在 gcc6.3 中按预期编译-O2和更早的 https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(j:1,source:'%23include+%3Calgorithm%3E%0A%23include+%3Cctime%3E%0A%23include+%3Ciostream%3E%0A%0Aint+main()%0A%7B%0A++++//+Generate+data%0A++++const+unsigned+arraySize+%3D+32768%3B%0A++++int+data%5BarraySize%5D%3B%0A%0A++++for+(unsigned+c+%3D+0%3B+c+%3C+arraySize%3B+%2B%2Bc)%0A++++++++data%5Bc%5D+%3D+std::rand()+%25+256%3B%0A%0A++++//+!!!!!!+With+this,+the+next+loop+runs+faster%0A++++std::sort(data,+data+%2B+arraySize)%3B%0A%0A++++//+Test%0A++++clock_t+start+%3D+clock()%3B%0A++++long+long+sum+%3D+0%3B%0A%0A++++for+(unsigned+i+%3D+0%3B+i+%3C+100000%3B+%2B%2Bi)%0A++++%7B%0A++++++++//+Primary+loop%0A++++++++for+(unsigned+c+%3D+0%3B+c+%3C+arraySize%3B+%2B%2Bc)%0A++++++++%7B%0A%23if+0%0A++++++++++++if+(data%5Bc%5D+%3E%3D+128)%0A++++++++++++++++sum+%2B%3D+data%5Bc%5D%3B%0A%23else%0A++++++++++++sum+%2B%3D+(data%5Bc%5D+%3E%3D+128+%3F+data%5Bc%5D+:+0)%3B%0A%23endif%0A++++++++%7D%0A++++%7D%0A%0A++++double+elapsedTime+%3D+static_cast%3Cdouble%3E(clock()+-+start)+/+CLOCKS_PER_SEC%3B%0A%0A++++std::cout+%3C%3C+elapsedTime+%3C%3C+std::endl%3B%0A++++std::cout+%3C%3C+%22sum+%3D+%22+%3C%3C+sum+%3C%3C+std::endl%3B%0A%7D%0A'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:33.36599326802078,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g63,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),libs:!(),options:'-O2+-std%3Dgnu%2B%2B11+-Wall+-mtune%3Dhaswell',source:1),l:'5',n:'0',o:'x86-64+gcc+6.3+(Editor+%231,+Compiler+%231)',t:'0')),k:32.731651559407744,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g63,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),libs:!(),options:'-O3+-std%3Dgnu%2B%2B11+-Wall+-mtune%3Dhaswell',source:1),l:'5',n:'0',o:'x86-64+gcc+6.3+(Editor+%231,+Compiler+%232)',t:'0')),k:33.90235517257147,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4，但是 gcc7 去优化为cmov在关键路径上（https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82666 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82666）。 （它还使用比 gcc 版本更早的版本自动矢量化if()的书写方式。）

即使使用原始源代码，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 个融合域微指令，因此无论如何它每次迭代都无法以 1c 的速度执行，因此延迟不是瓶颈。

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

此管道分析预测与 -O3 的 ~3 秒和 -O2 的 ~2 秒的时间几乎完全匹配。

Haswell/Skylake 可以每 1.25 个周期运行一次未采取的情况，因为它可以在与采取的分支相同的周期中执行未采取的分支，并且具有 4 个 ALU 端口。 （或者稍微少一点，因为5 uop 循环在每个周期 4 uop 时不太问题 https://stackoverflow.com/questions/39311872/is-performance-reduced-when-executing-loops-whose-uop-count-is-not-a-multiple-of).

（刚刚测试过：Skylake @ 3.9GHz 在 1.45 秒内运行整个程序的分支版本，或在 1.68 秒内运行无分支版本。因此差异要小得多。）

g++6.3.1 使用cmov即使在-O2，但 g++5.4 的行为仍然与 4.9.2 类似。

对于 g++6.3.1 和 g++5.4，使用-fprofile-generate / -fprofile-use即使在-O3 (with -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但两次，因为它没有意识到当条件已经将所有负整数归零时，它可以只进行零扩展而不是符号扩展。