我正在对一个科学应用程序进行数值优化。我注意到的一件事是,GCC将通过将调用pow(a,2)编译为a*a来优化它,但调用pov(a,6)并没有优化,实际上会调用库函数pow,这会大大降低性能。(相比之下,可执行icc的“英特尔C++编译器”将消除对pow(a,6)的库调用。)

我好奇的是,当我使用GCC 4.5.1和选项“-O3-lm-funroll-loops-msse4”将pow(a,6)替换为a*a*a*a*a*a时,它使用了5条多指令:

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13

而如果我写(a*a*a)*(a*a*a),它将产生

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm13, %xmm13

这将乘法指令的数量减少到3。icc也有类似的行为。

为什么编译器不认识这种优化技巧?


当前回答

gcc实际上可以进行这种优化,即使对于浮点数也是如此。例如

double foo(double a) {
  return a*a*a*a*a*a;
}

变成

foo(double):
    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm1, %xmm0
    ret

使用-O-funcafe数学优化。但是,这种重新排序违反了IEEE-754,因此需要标记。

正如Peter Cordes在一篇评论中指出的,有符号整数可以在没有funsafe数学优化的情况下进行这种优化,因为它恰好在没有溢出的情况下有效,如果有溢出,则会出现未定义的行为。所以你得到

foo(long):
    movq    %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rax, %rax
    ret

只需-O。对于无符号整数,这更容易,因为它们是2的模幂,因此即使在溢出的情况下也可以自由地重新排序。

其他回答

这个问题已经有了一些很好的答案,但为了完整起见,我想指出C标准的适用部分是5.1.2.2.3/15(与C++11标准中的1.9/9节相同)。本节指出,只有当运算符真的是结合的或可交换的时,才能重新组合它们。

因为浮点数学不是关联的。浮点乘法中操作数的分组方式会影响答案的数值精度。

因此,大多数编译器对重新排序浮点计算非常保守,除非他们能够确定答案不变,或者除非你告诉他们你不在乎数值精度。例如:gcc的-fassociative math选项允许gcc重新关联浮点运算,或者甚至-fast math选项,允许更积极地权衡精度与速度。

gcc实际上可以进行这种优化,即使对于浮点数也是如此。例如

double foo(double a) {
  return a*a*a*a*a*a;
}

变成

foo(double):
    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm1, %xmm0
    ret

使用-O-funcafe数学优化。但是,这种重新排序违反了IEEE-754,因此需要标记。

正如Peter Cordes在一篇评论中指出的,有符号整数可以在没有funsafe数学优化的情况下进行这种优化,因为它恰好在没有溢出的情况下有效,如果有溢出,则会出现未定义的行为。所以你得到

foo(long):
    movq    %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rax, %rax
    ret

只需-O。对于无符号整数,这更容易,因为它们是2的模幂,因此即使在溢出的情况下也可以自由地重新排序。

Lambdageek正确地指出,由于关联性不适用于浮点数,所以a*a*a*a*a*a到(a*a**a)*(a*a*a)的“优化”可能会改变值。这就是C99不允许它的原因(除非用户通过编译器标志或pragma特别允许)。一般来说,假设程序员写的东西是有原因的,编译器应该尊重这一点。如果你想要(a*a*a)*(a*a*a),请写下。

不过,写起来可能会很痛苦;当你使用pow(a,6)时,编译器为什么不能做正确的事情?因为这样做是错误的。在一个拥有良好数学库的平台上,pow(a,6)比a*a*a*a*a*a或(a*a**a)*(a*a*a)要准确得多。为了提供一些数据,我在我的Mac Pro上做了一个小实验,测量了在评估所有[1,2)之间的单精度浮点数的^6时的最差误差:

worst relative error using    powf(a, 6.f): 5.96e-08
worst relative error using (a*a*a)*(a*a*a): 2.94e-07
worst relative error using     a*a*a*a*a*a: 2.58e-07

使用pow而不是乘法树可以将误差范围减少4倍。编译器不应该(通常也不会)进行增加错误的“优化”,除非获得用户的许可(例如通过-fast math)。

注意,GCC提供__builtin_powi(x,n)作为pow()的替代方案,pow应该生成内联乘法树。如果您想以精度换取性能,但不想启用快速数学,请使用该选项。

正如Lambdageek指出的那样,浮点乘法是不相关的,你可以得到更少的精度,但当获得更好的精度时,你可以反对优化,因为你想要一个确定性的应用程序。例如,在游戏模拟客户端/服务器中,每个客户端都必须模拟相同的世界,您希望浮点计算具有确定性。