Mik*_*aev 18 c++ optimization gcc
我发现这个主题为什么处理排序数组比未排序数组更快？.并尝试运行此代码.而且我发现了奇怪的行为.如果我使用-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.谢谢你的帮助.
PS添加代码
#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;
}
Pet*_*des 31
gcc -O3使用cmov作为条件,因此它延长了循环携带的依赖链,包括a cmov(根据Agner Fog的指令表,你的Intel Sandybridge CPU有2个uop和2个周期的延迟.另请参阅x86标签wiki).这是糟糕的案例之一cmov.
如果数据甚至是中等不可预测的,cmov那么可能是一个胜利,所以这对于编译器来说是一个相当明智的选择.(但是,编译器有时可能会使用无分支代码.)
我把你的代码放在Godbolt编译器资源管理器上以查看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个周期)延迟的循环瓶颈,因为循环的一次迭代将rbx写入CMO,下一次迭代使用ADD读取rbx.
该循环仅包含8个融合域uop,因此它可以每2个循环发出一次.执行端口压力也不像sumdep链的延迟那样是一个瓶颈,但它很接近(Sandybridge只有3个ALU端口,不像Haswell的4).
顺便说一句,写它sum += (data[c] >= 128 ? data[c] : 0);以取出cmov循环携带的dep链可能是有用的.仍然有很多指令,但cmov每次迭代都是独立的.这在gcc6.3 -O2及更早版本中按预期编译,但gcc7 cmov在关键路径上取消优化(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个融合域uops,因此无论如何它不能以每次迭代1c执行,因此延迟不是瓶颈.
它可能每2个周期运行大约一次迭代(分支指令吞吐量瓶颈),而-O3循环每3个循环运行一次.下一个瓶颈是ALU uop吞吐量:4个ALU uops(在未采用的情况下)但只有3个ALU端口.(ADD可以在任何端口上运行).
这个管道分析预测几乎完全匹配-O3约为3秒的时间与-O2时约为2秒.
Haswell/Skylake可以每1.25个周期运行一次未采用的情况,因为它可以在与采用分支相同的周期内执行未采用的分支,并具有4个ALU端口.(或者稍微少一点,因为5个uop循环在每个循环4个uop时不会发出相当大的问题).
(刚刚测试过: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两次,因为当条件已经将所有负整数归零时,它没有意识到它只能零延伸而不是符号扩展.