这个for循环中发生了哪些GCC优化?

7

使用gcc 4.6和-O3,我使用简单的time命令计时了以下四个代码

#include <iostream>
int main(int argc, char* argv[])
{
  double val = 1.0; 
  unsigned int numIterations = 1e7; 
  for(unsigned int ii = 0;ii < numIterations;++ii) {
    val *= 0.999;
  }
  std::cout<<val<<std::endl;
}

案例1运行时间为0.09秒

#include <iostream>
int main(int argc, char* argv[])
{
  double val = 1.0;
  unsigned int numIterations = 1e8;
  for(unsigned int ii = 0;ii < numIterations;++ii) {
    val *= 0.999;
  }
  std::cout<<val<<std::endl;
}

案例2在17.6秒内运行

int main(int argc, char* argv[])
{
  double val = 1.0;
  unsigned int numIterations = 1e8;
  for(unsigned int ii = 0;ii < numIterations;++ii) {
    val *= 0.999;
  }
}

第三个案例运行时间为0.8秒。

#include <iostream>
int main(int argc, char* argv[])
{
  double val = 1.0;
  unsigned int numIterations = 1e8;
  for(unsigned int ii = 0;ii < numIterations;++ii) {
    val *= 0.999999;
  }
  std::cout<<val<<std::endl;
}

第4个案例运行时间为0.8秒。

我的问题是为什么第二个案例比其他所有案例都要慢得多?案例3表明,去除cout会使运行时间恢复到预期水平。案例4表明,改变乘数也大大降低了运行时间。在第2个案例中没有发生哪些优化或优化?

更新:

当我最初运行这些测试时,没有单独的变量numIterations,该值是硬编码在for循环中的。通常情况下,硬编码此值会使事情比这里给出的情况运行得更慢。对于Case 3来说尤其如此,使用上面显示的numIterations变量几乎立即运行,表明James McNellis正确地指出了整个循环被优化掉了。我不确定为什么将1e8硬编码到for循环中会防止在Case 3中删除循环,或者为什么会使其他案例变慢,但是,第2个案例显著较慢的基本前提是正确的。

比较上述案例的汇编输出结果如下:

案例2和案例1:
movl $100000000, 16(%esp)


movl $10000000, 16(%esp)

案例2和案例4:
.long -652835029
.long 1072691150


.long -417264663
.long 1072693245


1
你运行了每个案例多少次?运行时间必须从多次运行中取平均值,同时在平均计算中最好不要使用太大的结果。 - osgx
@osgx 是的,我运行了每个测试用例多次。 - user334066
请确认一下:在你的平台上,int 至少有32位吗? - Oliver Charlesworth
可能与您实际的问题无关,但情况1比其他三种情况短十倍。 - Dennis Zickefoose
@Dennis:我认为这就是重点所在。第2种情况很慢,其他三种情况只有一个小改变并且运行速度快了10倍以上。 - Ben Voigt
@oli 根据 numeric_limits,最大的无符号整数是 4294967295。 - user334066
4个回答

8

René Richter在处理下溢时走上了正确的道路。最小的正规化数约为2.2e-308。使用f(n)=0.999**n,大约需要708,148次迭代才能达到这个限制。剩余的迭代将使用未规格化的计算。

这就解释了为什么1亿次迭代所需的时间比执行1千万次多10倍左右。前700,000次使用浮点硬件完成。一旦遇到非规格化数字,浮点硬件就会放弃;乘法将在软件中完成。

请注意,如果重复计算正确地计算0.999**N,则不会出现这种情况。最终,乘积将达到零,并且从那时起,乘法再次将使用浮点硬件完成。但事实并非如此,因为0.999 *(最小的非规格化数字)是最小的非规格化数字。继续的乘积最终会到达底部。

我们可以改变指数。指数为0.999999将使持续的乘积在7.08亿次迭代内保持在规格化数的范围内。利用这一点,

Case A  : #iterations = 1e7, exponent=0.999, time=0.573692 sec
Case B  : #iterations = 1e8, exponent=0.999, time=6.10548 sec
Case C  : #iterations = 1e7, exponent=0.999999, time=0.018867 sec
Case D  : #iterations = 1e8, exponent=0.999999, time=0.189375 sec

在这里,您可以轻松地看到浮点硬件与软件仿真相比有多快。


根据IEEE 754,2.2e-308是double类型的下溢限制,但在FPU计算期间,gcc在Intel架构上使用80位长double,直到结果从FPU复制回来,其中下溢发生在约3e-4951。Visual C++使用double,因此计时结果应该有所不同。 - René Richter
2
首先,user334066并没有使用Visual C++。一开始就说明了编译器是gcc 4.6。其次,这些计算结果存储在double中,而不是long double。无论使用哪种编译器,这些计算都需要从/转换为IEEE 754双精度浮点数。程序在大约708,500次迭代后仍然会遇到双精度下溢问题。 - David Hammen
这很有道理,因为它不是像我最初想的那样受到gcc优化的影响。谢谢。 - user334066

8
使用选项-S进行编译并查看生成的汇编输出(文件名为*.s)。
编辑:
在程序3中,循环被删除,因为结果没有被使用。
对于情况1、2和4,让我们做一些数学运算: 情况1的基数10对数是1e7*log10(0.999)=-4345(大约)。 对于情况2,我们得到1e8*log10(0.999)=-43451。 对于情况4,它是1e8*log10(0.9999)=-4343。 结果本身是pow(10, logarithm)。
浮点单元在x86/x64 cpu上内部使用80位长双精度。当数字变小于1.9E-4951时,会出现浮点下溢,如@James Kanze指出的那样。这只发生在情况2中。我不知道为什么这比规范化的结果要慢,也许有人能解释一下。

那超出了我的经验范围,但我会进行一些谷歌搜索并尝试一下。 - user334066
@user334066:你不必有汇编的经验,但你会看到任何差异。 - René Richter
这是最明智的做法,而且也非常容易。gcc -S -o prog.s prog.cpp等。 - Kerrek SB
@user:如果您将结果发布在问题中,我们将帮助您弄清楚任何不清楚的地方。 - Ben Voigt
@René:您走在正确的道路上,但您的指数不正确。下溢发生在约2.2e-308。X86/x64使用IEEE 754。完整的答案有点长,无法放在评论中。请查看我的回答。 - David Hammen
显示剩余2条评论

1

我在64位Linux上运行g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3。我像你一样使用了-O3。

这是我进行测试时的时间结果:

  • Case 2: 6.81秒
  • Case 3: 0.00秒
  • Case 4: 0.20秒

我查看了所有三个测试的汇编代码。

Case 3很快,因为GCC确实优化掉了整个for循环。主函数只是(删除标签和.cfi*语句后):

main:
        xorl    %eax, %eax
        ret

Case 2和Case 3的汇编唯一的区别是常量,这个常量可能代表0.999或0.999999:

$ diff case2.s case4.s
121,122c121,122
<   .long   3642132267
<   .long   1072691150
---
>   .long   3877702633
>   .long   1072693245

这是汇编中唯一的区别。GCC对Case 2和Case 4执行了相同的优化,但Case 2所需时间是Case 4的30倍。我的结论是,在x64架构上的浮点数乘法必须根据您要乘的值而变化。这不应该是一个令人惊讶的说法,但如果有人更了解x64,能够向我们解释为什么是这样就好了。

我没有仔细研究Case 1,因为你只进行了1e7次迭代,而不是1e8次,所以当然需要更少的时间。


需要不同时间的是将程序加载到内存中,执行启动程序所需的上下文切换等操作。 - David Hammen
@David 对于第三种情况的混淆我很抱歉,我上面的更新解释了时间上的差异。关于第一种情况,除了for循环的大小之外,其他所有东西都相同,Case 2不应该比Case 1慢50倍而是10倍吗? - user334066
1
我刚刚为你的测试用例添加了计时功能,但是在程序内部执行。我得到了以下结果:第一组测试用例用时0.57秒,第二组测试用例用时6.1秒,第三组和第四组测试用例用时均为0秒。第二组测试用例的执行时间大约是第一组测试用例的10倍。 - David Hammen
哈哈,在每个Linux上(包括glibc中)都有一个软件浮点计算,有时会被激活。 - osgx

1

就这个问题而言,我对所有四个版本进行了一些测试,以下是测试结果:

  • 首先,我和你一样发现速度存在差异。基本上:我使用的机器较慢,并且在测试1、3和4之间看到明显的差异。但它们仍然比测试2快两个数量级以上。

  • 第三次测试远远是最快的:查看生成的代码显示,g++确实删除了循环,因为结果没有被使用。

  • 测试1的速度只比测试4的速度慢十分之一左右。大致符合预期。

  • 而测试1、3和4之间唯一的区别就是常数。循环中绝对没有任何区别。

所以,这种差异不是编译器优化的问题。我只能猜测这与下溢处理有关。 (但是,我也会预期循环1的速度下降。)


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接