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

Question

在试图了解一行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

为什么空循环使用的时间多于第二个有指令的时间？当然,我尝试了很多变种,但每次,空循环所需的时间多于单个指令.

请注意,我已尝试交换循环顺序并添加一些预热代码,但它根本没有改变我的问题.

我正在使用代码块作为IDE与GNU gcc编译器,linux ubuntu 14.04并且拥有2.3GHz的四核intel i5(我尝试在单核上运行程序,这不会改变结果).

Answer 1

假设您的代码使用32位整数int类型(您的系统可能会这样做),那么您的代码就无法确定任何内容.相反,它表现出不确定的行为.

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的内部程序集非常易读,所以我要展示一下.我会通过运行来生产它:

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

这是输出的相关部分(主要功能):

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 2

事实是现代处理器很复杂.执行的所有指令将以复杂和有趣的方式相互交互.感谢发布代码的"其他人".

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真的发生了!所以这可以在这里引入一个摊位.

这里的问题是条件跳转,addq导致条件存储,以及cmpq不确定从哪里获取数据,都非常非常接近.他们异常紧密地联系在一起.它们可能是如此接近,处理器此时无法弄清楚是i从存储指令获取还是从存储器中读取它.并从内存中读取它,这是较慢的,因为它必须等待商店完成.只添加一个就可以nop给处理器足够的时间.

通常你认为有RAM,并且有缓存.在现代英特尔处理器上,读取内存可以读取(从最慢到最快):

1. 记忆(RAM)
2. L3缓存(可选)
3. 二级缓存
4. L1缓存
5. 尚未写入L1缓存的先前存储指令.

那么处理器在短,慢循环内部做什么:

1. i从L1缓存中读取
2. 添加1到 i
3. 写入iL1缓存
4. 等到i写入L1缓存
5. i从L1缓存中读取
6. i与INT_MAX 比较
7. 分支到(1)如果它更少.

在漫长而快速的循环中,处理器可以:

1. 很多东西
2. i从L1缓存中读取
3. 添加1到 i
4. 执行将写入iL1缓存的"存储"指令
5. i直接从"store"指令读取而不触及L1缓存
6. i与INT_MAX 比较
7. 分支到(1)如果它更少.

Answer 3

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

稍后程序中的代码可能比早期代码执行得更快.

该clock()库函数可能造成的icache中读错过的定时器后,并在返回之前.这将在第一个测量间隔中产生一些额外的时间.(对于以后的调用,代码已经在缓存中).然而,这种影响很小,当然太小而clock()无法测量,即使它是一直到磁盘的页面错误.随机上下文切换可以添加到任一时间间隔.

更重要的是,你有一个i5 CPU,它具有动态时钟.当程序开始执行时,时钟速率很可能很低,因为CPU一直处于空闲状态.只运行程序会使CPU不再空闲,因此在短暂的延迟后,时钟速度将会增加.空闲和TurboBoosted CPU时钟频率之间的比率可能很大.(在我的超极本的Haswell i5-4200U上,前者的乘数为8,后者为26,使得启动代码的运行速度低于后期代码的30%!实现延迟的"校准"循环在现代计算机上是一个糟糕的想法! )

包括一个预热阶段(反复运行基准测试,抛出第一个结果)以获得更精确的计时,不仅适用于使用JIT编译器的托管框架!

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

我想这显示了对齐的重要性,但我恐怕不能具体说出如何:|