空循环比C中的非空循环慢

当试图知道一行C代码执行多长时，我注意到这个奇怪的事情：

int main (char argc, char * argv[]) { time_t begin, end; uint64_t i; double total_time, free_time; int A = 1; int B = 1; begin = clock(); for (i = 0; i<(1<<31)-1; i++); end = clock(); free_time = (double)(end-begin)/CLOCKS_PER_SEC; printf("%f\n", free_time); begin = clock(); for (i = 0; i<(1<<31)-1; i++) { A += B%2; } end = clock(); free_time = (double)(end-begin)/CLOCKS_PER_SEC; printf("%f\n", free_time); return(0); } 

当执行时显示：

 5.873425 4.826874 

为什么空循环使用比第二个有更多的时间内有一个指令？ 当然，我已经尝试了很多变体，但是每次都是一个空循环比一个单独的指令需要更多的时间。

请注意，我尝试交换循环顺序，并添加一些热身代码，它并没有改变我的问题。

我使用GNU gcc编译器，linux ubuntu 14.04的IDE，并在2.3GHz有一个quadcore英特尔i5（我试过在单个核心上运行程序，这不会改变结果）。

Answer 1

事实是，现代处理器是复杂的。 所有执行的指令将以复杂而有趣的方式相互作用。 感谢“其他人”张贴代码。

OP和“另一个人”显然发现短循环需要11个循环，而长循环需要9个循环。 对于长循环来说，即使有很多操作，9个周期也是充足的时间。 对于短循环来说，由于短暂的原因必然会造成一些停顿，只是增加一个nop使得循环足够长，以避免失速。

有一件事情，如果我们看看代码：

 0x00000000004005af <+50>: addq $0x1,-0x20(%rbp) 0x00000000004005b4 <+55>: cmpq $0x7fffffff,-0x20(%rbp) 0x00000000004005bc <+63>: jb 0x4005af <main+50> 

我们读i并写回（ addq ）。 我们立即再读一遍，并比较它（ cmpq ）。 然后我们循环。 但循环使用分支预测。 所以在执行addq时，处理器并不确定是否允许向i写入（因为分支预测可能是错误的）。

然后我们和i比较。 处理器将尽量避免从内存中读取i ，因为阅读需要很长时间。 相反，一些硬件会记住，我们只是通过添加它来写给i ，而不是读取i ， cmpq指令从存储指令中获取数据。 不幸的是，我们现在还不确定写给i真的发生过！ 这样可以在这里引入一个摊位。

这里的问题是条件跳转，导致条件存储的cmpq以及不确定从哪里获取数据的cmpq都非常接近。 他们exception密切在一起。 这可能是因为它们非常接近，处理器现在无法弄清楚是从存储指令中取出i还是从存储器中读取它。 并从内存中读取，因为要等待商店完成，所以速度较慢。 只增加一个nop给处理器足够的时间。

通常你认为有RAM，有caching。 在现代英特尔处理器上，读取内存可以从（最慢到最快）读取：

1. 内存（RAM）
2. 三级caching（可选）
3. 二级caching
4. L1caching
5. 上一条尚未写入L1caching的存储指令。

那么处理器在短暂的，慢的循环中做了什么：

1. 从L1caching中读取i
2. 给i加1
3. 写i到一级caching
4. 等到i写入L1caching
5. 从L1caching中读取i
6. 比较i与INT_MAX
7. （1）如果less了，则分支。

处理器在漫长而快速的循环中做到：

1. 很多东西
2. 从L1caching中读取i
3. 给i加1
4. 做一个“存储”指令，将i写入L1caching
5. 直接从“store”指令中读取，而不需要触及L1caching
6. 比较i与INT_MAX
7. （1）如果less了，则分支。

Answer 2

假设你的代码使用了一个32位整数的inttypes（你的系统可能会这样做），那么你的代码就不能确定了。 相反， 它performance出未定义的行为。

 foo.c:5:5: error: first parameter of 'main' (argument count) must be of type 'int' int main (char argc, char * argv[]) { ^ foo.c:13:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow] for (i = 0; i<(1<<31)-1; i++); ^ foo.c:19:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow] for (i = 0; i<(1<<31)-1; i++) { ^ 

我们试着解决这个问题：

 #include <stdint.h> #include <stdio.h> #include <time.h> #include <limits.h> int main (int argc, char * argv[]) { time_t begin, end; uint64_t i; double total_time, free_time; int A = 1; int B = 1; begin = clock(); for (i = 0; i<INT_MAX; i++); end = clock(); free_time = (double)(end-begin)/CLOCKS_PER_SEC; printf("%f\n", free_time); begin = clock(); for (i = 0; i<INT_MAX; i++) { A += B%2; } end = clock(); free_time = (double)(end-begin)/CLOCKS_PER_SEC; printf("%f\n", free_time); return(0); } 

现在，我们来看看这个代码的汇编输出。 就我个人而言，我发现LLVM的内部程序集非常可读，所以我要certificate这一点。 我将通过运行生成它：

 clang -O3 foo.c -S -emit-llvm -std=gnu99 

以下是输出的相关部分（主要function）：

 define i32 @main(i32 %argc, i8** nocapture readnone %argv) #0 { %1 = tail call i64 @"\01_clock"() #3 %2 = tail call i64 @"\01_clock"() #3 %3 = sub nsw i64 %2, %1 %4 = sitofp i64 %3 to double %5 = fdiv double %4, 1.000000e+06 %6 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %5) #3 %7 = tail call i64 @"\01_clock"() #3 %8 = tail call i64 @"\01_clock"() #3 %9 = sub nsw i64 %8, %7 %10 = sitofp i64 %9 to double %11 = fdiv double %10, 1.000000e+06 %12 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %11) #3 ret i32 0 } 

请注意， 无论在哪种情况下 ， clock()的调用之间都没有任何操作。 所以他们都编译到完全一样的东西 。

Answer 3

这个答案假定你已经理解并解决了关于未定义行为的优点，沙尔特在他的答案中做了 。 他还指出编译器可能会在您的代码上玩的技巧。 您应该采取措施确保编译器不会将整个循环识别为无用。 例如，将迭代器声明更改为volatile uint64_t i; 将防止删除循环，并volatile int A; 将确保第二个循环实际上比第一个循环做更多的工作。 但即使你这样做，你仍然可以发现：

程序后面的代码可能比之前的代码更快地执行。

clock()库函数在读取计时器之后，在返回之前可能会导致icache未命中。 这会在第一个测量间隔中造成一些额外的时间。 （对于以后的调用，代码已经在caching中）。 然而，这个效果对于clock()来说很小，对于测量来说太小了，即使是一直到磁盘的页面错误。 随机上下文切换可以添加到任一时间间隔。

更重要的是，你有一个i5 CPU，它具有dynamic时钟。 当你的程序开始执行时，由于CPU空闲，时钟频率可能很低。 只要运行该程序，CPU就不再空闲，所以经过短暂的延迟后，时钟速度将会增加。 闲置和TurboBoosted CPU时钟频率之间的比率可能是显着的。 （在我的超级本的Haswell i5-4200U上，前乘法器是8，后者是26，使得启动代码与后面的代码一样快地运行不到30％！“实现延迟的”校准“循环在现代计算机上是一个可怕的想法！ ）

包括一个热身阶段（重复运行一个基准testing，抛出第一个结果）以获得更精确的时序不仅仅适用于带有JIT编译器的托pipe框架！

Answer 4

我可以用GCC 4.8.2-19ubuntu1重现这一点，没有优化：

 $ ./a.out 4.780179 3.762356 

这是空的循环：

 0x00000000004005af <+50>: addq $0x1,-0x20(%rbp) 0x00000000004005b4 <+55>: cmpq $0x7fffffff,-0x20(%rbp) 0x00000000004005bc <+63>: jb 0x4005af <main+50> 

这里是非空的：

 0x000000000040061a <+157>: mov -0x24(%rbp),%eax 0x000000000040061d <+160>: cltd 0x000000000040061e <+161>: shr $0x1f,%edx 0x0000000000400621 <+164>: add %edx,%eax 0x0000000000400623 <+166>: and $0x1,%eax 0x0000000000400626 <+169>: sub %edx,%eax 0x0000000000400628 <+171>: add %eax,-0x28(%rbp) 0x000000000040062b <+174>: addq $0x1,-0x20(%rbp) 0x0000000000400630 <+179>: cmpq $0x7fffffff,-0x20(%rbp) 0x0000000000400638 <+187>: jb 0x40061a <main+157> 

让我们在空循环中插入一个nop ：

 0x00000000004005af <+50>: nop 0x00000000004005b0 <+51>: addq $0x1,-0x20(%rbp) 0x00000000004005b5 <+56>: cmpq $0x7fffffff,-0x20(%rbp) 0x00000000004005bd <+64>: jb 0x4005af <main+50> 

他们现在跑得一样快：

 $ ./a.out 3.846031 3.705035 

我想这表明了alignment的重要性，但是我恐怕不能具体说一下：|