请注意:这个问题既不是关于代码质量的,也不是关于改进代码的方法的,更不是关于运行时差异的(in)意义的这是关于GCC以及为什么哪种编译器优化会降低性能的。
程序
以下代码统计到m
:的斐波那契素数的数量
int main() {
unsigned int m = 500000000u;
unsigned int i = 0u;
unsigned int a = 1u;
unsigned int b = 1u;
unsigned int c = 1u;
unsigned int count = 0u;
while (a + b <= m) {
for (i = 2u; i < a + b; ++i) {
c = (a + b) % i;
if (c == 0u) {
i = a + b;
// break;
}
}
if (c != 0u) {
count = count + 1u;
}
a = a + b;
b = a - b;
}
return count; // Just to "output" (and thus use) count
}
当使用g++.exe (Rev2, Built by MSYS2 project) 9.2.0
和无优化(-O0
)编译时,生成的二进制文件(在我的机器上)执行时间为1.9秒。使用-O1
和-O3
时,执行时间分别为3.3秒和1.7秒。
我试图通过查看汇编代码(godbolt.org)和相应的控制流图(hex-rays.com/products/ida)来理解生成的二进制文件,但我的汇编技能还不够。
其他观察结果
最里面的
if
中的显式break
使-O1
代码再次快速:if (c == 0u) { i = a + b; // Not actually needed any more break; }
正如";内联";循环的进度表达式:
for (i = 2u; i < a + b; ) { // No ++i any more c = (a + b) % i; if (c == 0u) { i = a + b; ++i; } else { ++i; } }
问题
哪种优化可以解释性能下降?
是否可以解释是什么触发了C++代码的优化(即,在没有深入了解GCC内部结构的情况下)?
同样,是否有一个高层次的解释来解释为什么替代方案(额外观察)明显阻止了流氓优化?
这里最重要的是循环携带的数据依赖性。
查看最内部循环的慢速变体的机器代码。我在这里展示了-O2
组件,-O1
的优化程度较低,但总体上具有类似的数据依赖性:
.L4:
xorl %edx, %edx
movl %esi, %eax
divl %ecx
testl %edx, %edx
cmove %esi, %ecx
addl $1, %ecx
cmpl %ecx, %esi
ja .L4
查看%ecx
中循环计数器的增量如何取决于前一条指令(cmov
),而前一条命令又取决于除法的结果,而除法的结果又取决于循环计数器的前一个值。
实际上,在计算%ecx
中的值时存在一个数据依赖链,该数据依赖链跨越整个循环,并且由于执行循环的时间占主导地位,因此计算该链的时间决定了程序的执行时间。
调整程序以计算分割数表明,它执行434044698条div
指令。在我的情况下,将程序占用的机器周期数除以这个数字得到26个周期,这与div
指令的延迟加上链中其他指令的大约3或4个周期(链为div
-test
-cmov
-add
)非常对应。
相比之下, 延迟限制最后,为您的问题提供具体答案: 1.哪种优化可以解释性能下降的原因 正如另一个答案所提到的,这是如果创建循环的转换在最初有控制依赖关系的地方携带数据依赖关系。当控制依赖关系对应于不可预测的分支时,控制依赖关系也可能代价高昂,但在这种情况下,分支很容易预测。 2.是否可以解释是什么触发了C++代码的优化(即,在没有深入了解GCC内部结构的情况下) 也许你可以想象将代码转换为的优化 其中在CPU上评估三元运算符,使得在计算出 3.同样,是否有高层解释为什么备选方案(额外观察)明显阻止了流氓优化 在这些变体中,代码不符合if转换的条件,因此没有引入有问题的数据依赖关系。-O3
代码没有这一依赖链,使其具有吞吐量限制而不是for (i = 2u; i < a + b; ++i) {
c = (a + b) % i;
i = (c != 0) ? i : a + b;
}
c
之前不知道i
的新值。
我认为问题出在-fif-conversion
中,它指示编译器执行CMOV
而不是TEST/JZ
进行一些比较。众所周知,CCD_ 28在一般情况下并不那么伟大。
据我所知,拆卸过程中有两点受到此标志的影响:
首先,第13行中的if (c == 0u) { i = a + b; }
被编译为:
test edx,edx //edx is c
cmove ecx,esi //esi is (a + b), ecx is i
其次,将if (c != 0u) { count = count + 1u; }
编译为
cmp eax,0x1 //eax is c
sbb r8d,0xffffffff //r8d is count, but what???
妙招!它是-1
到count
的减法,但带有进位,并且只有当c
小于1
时才设置进位,无符号意味着0
。因此,如果eax
为0,它将-1减去count
,但随后再次减去1:它不会改变。如果eax
不为0,则减去-1
,使变量递增。
现在,这避免了分支,但代价是错过了明显的优化,即如果c == 0u
,您可以直接跳到下一个while
迭代。这一点非常简单,甚至可以在-O0
中完成。
我相信这是由;有条件移动";编译器生成的指令(CMOVEcc),用于在使用-O1
和-O2
时替换分支。
当使用-O0
时,语句if (c == 0u)
被编译为跳转:
cmp DWORD PTR [rbp-16], 0
jne .L4
使用-O1
和-O2
:
test edx, edx
cmove ecx, esi
而-O3
产生跳跃(类似于-O0
):
test edx, edx
je .L5
gcc中存在一个已知的错误,其中";使用条件移动而不是比较和分支导致几乎2倍慢的代码";
正如rodrigo在他的评论中所建议的那样,使用标志-fno-if-conversion
告诉gcc不要用条件移动代替分支,从而防止了这个性能问题。