c - 意外的运行时差

Question

考虑给定的两种情况，

在下面的这种情况下，我只是运行两个嵌套循环，它们都是从 0 初始化的并运行到 100000 .

int k = 100000;
for(i=0;i<k;i++)
    for(j=0;j<k;j++){
    // Do nothing
 }

time在我的系统上 = 22.6 seconds

我又在做同样的事情，只是递增一个变量 c里面。

int k = 100000, cnt=0;
for(i=0;i<k;i++)
    for(j=0;j<k;j++){
    cnt++;
 }

time在我的系统上 = 19.6 seconds

怎么会？？？为什么时间在case2 < case1 ??

Answer 1

我只是重现了结果，并问了自己与 OP 相同的问题。

代码如下:

>>>> test1.c
int
main ()
{
  long long int i;
  long long int j;
  long long int k = 100000;
  for(i=0;i<k;i++)
    for(j=0;j<k;j++)
      {
        // Do nothing
      }

  return 0;
}

.

>>>> test2.c
int
main ()
{
  long long int i;
  long long int j;
  long long int c = 0;

  long long int k = 100000;
  for(i=0;i<k;i++)
    for(j=0;j<k;j++)
      {
        c++;
      }

  return 0;
}

在 amd64 gentoo linux 机器上用 gcc -o testx testx.c -g 编译。运行时，我得到以下时间:

  test1: 0m32.000s
  test2: 0m28.307s

这个我测试了很多次，推导量小得惊人。

要了解此处发生的情况，我们必须查看反汇编。

>>>> test1
Dump of assembler code for function main:
   0x00000000004004fc <+0>:     push   %rbp
   0x00000000004004fd <+1>:     mov    %rsp,%rbp
   0x0000000000400500 <+4>:     movq   $0x186a0,-0x18(%rbp)
   0x0000000000400508 <+12>:    movq   $0x0,-0x8(%rbp)
   0x0000000000400510 <+20>:    jmp    0x400530 <main+52>
   0x0000000000400512 <+22>:    movq   $0x0,-0x10(%rbp)
   0x000000000040051a <+30>:    jmp    0x400521 <main+37>
   0x000000000040051c <+32>:    addq   $0x1,-0x10(%rbp)
   0x0000000000400521 <+37>:    mov    -0x10(%rbp),%rax
   0x0000000000400525 <+41>:    cmp    -0x18(%rbp),%rax
   0x0000000000400529 <+45>:    jl     0x40051c <main+32>
   0x000000000040052b <+47>:    addq   $0x1,-0x8(%rbp)
   0x0000000000400530 <+52>:    mov    -0x8(%rbp),%rax
   0x0000000000400534 <+56>:    cmp    -0x18(%rbp),%rax
   0x0000000000400538 <+60>:    jl     0x400512 <main+22>
   0x000000000040053a <+62>:    mov    $0x0,%eax
   0x000000000040053f <+67>:    pop    %rbp
   0x0000000000400540 <+68>:    retq   
End of assembler dump.

.

>>>> test2:
Dump of assembler code for function main:
   0x00000000004004fc <+0>:     push   %rbp
   0x00000000004004fd <+1>:     ov    %rsp,%rbp
   0x0000000000400500 <+4>:     movq   $0x0,-0x18(%rbp)
   0x0000000000400508 <+12>:    movq   $0x186a0,-0x20(%rbp)
   0x0000000000400510 <+20>:    movq   $0x0,-0x8(%rbp)
   0x0000000000400518 <+28>:    jmp    0x40053d <main+65>
   0x000000000040051a <+30>:    movq   $0x0,-0x10(%rbp)
   0x0000000000400522 <+38>:    jmp    0x40052e <main+50>
   0x0000000000400524 <+40>:    addq   $0x1,-0x18(%rbp)
   0x0000000000400529 <+45>:    addq   $0x1,-0x10(%rbp)
   0x000000000040052e <+50>:    mov    -0x10(%rbp),%rax
   0x0000000000400532 <+54>:    cmp    -0x20(%rbp),%rax
   0x0000000000400536 <+58>:    jl     0x400524 <main+40>
   0x0000000000400538 <+60>:    addq   $0x1,-0x8(%rbp)
   0x000000000040053d <+65>:    mov    -0x8(%rbp),%rax
   0x0000000000400541 <+69>:    cmp    -0x20(%rbp),%rax
   0x0000000000400545 <+73>:    jl     0x40051a <main+30>
   0x0000000000400547 <+75>:    mov    $0x0,%eax
   0x000000000040054c <+80>:    pop    %rbp
   0x000000000040054d <+81>:    retq   
End of assembler dump.

正如预期的那样，它看起来非常相似。

我在下面的 test2 注释版本中突出显示了代码的作用。装配线的缩进表示它们所处的循环级别或它们实现的级别。

>>>> test2:
Dump of assembler code for function main:
   // setup the stackframe
   0x00000000004004fc <+0>:     push   %rbp
   0x00000000004004fd <+1>:     ov    %rsp,%rbp
   // initialize variable c
   0x0000000000400500 <+4>:     movq   $0x0,-0x18(%rbp)
   // initialize variable k
   0x0000000000400508 <+12>:    movq   $0x186a0,-0x20(%rbp)
     // initialize variable i
     0x0000000000400510 <+20>:  movq   $0x0,-0x8(%rbp)
     // enter the outer loop
     0x0000000000400518 <+28>:  jmp    0x40053d <main+65>
       // initialize variable j
       0x000000000040051a <+30>:    movq   $0x0,-0x10(%rbp)
       // enter the inner loop
       0x0000000000400522 <+38>:    jmp    0x40052e <main+50>
         // increment variable c
         0x0000000000400524 <+40>:  addq   $0x1,-0x18(%rbp)
       // increment variable j
       0x0000000000400529 <+45>:    addq   $0x1,-0x10(%rbp)
       // check if the inner loop condition still holds
       0x000000000040052e <+50>:    mov    -0x10(%rbp),%rax
       0x0000000000400532 <+54>:    cmp    -0x20(%rbp),%rax
       // jump to the start of the inner loop, if true, else continue
       0x0000000000400536 <+58>:    jl     0x400524 <main+40>
     // increment variable i
     0x0000000000400538 <+60>:  addq   $0x1,-0x8(%rbp)
     // check if the outer loop condition still holds
     0x000000000040053d <+65>:  mov    -0x8(%rbp),%rax
     0x0000000000400541 <+69>:  cmp    -0x20(%rbp),%rax
     // jump to the start of the outer loop, if true, else continue
     0x0000000000400545 <+73>:  jl     0x40051a <main+30>
   // tear down and return to main
   0x0000000000400547 <+75>:    mov    $0x0,%eax
   0x000000000040054c <+80>:    pop    %rbp
   0x000000000040054d <+81>:    retq   
End of assembler dump.

可以看到，代码结构与实际的C代码非常相似，test1和test2的汇编差别很小。

test2 执行速度稍快的原因可能深深地隐藏在您的硬件规范中。我认为现代处理器可能已经为简单循环优化了指令缓存和流水线，因为它们在程序中很常见，并且优化不适用于空循环，因为它们 (1) 在实际程序中非常罕见(2) 运行时优化实际上对空循环并不重要，因为它们通常用于(忙)等待。

无论出于何种原因，它可能在学术上很有趣，但对实际软件的影响可能不存在 :)

我刚刚找到了英特尔发布的这份文件，如果您对细节感兴趣，那应该是一本有趣的书 http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&ved=0CFgQFjAD&url=http%3A%2F%2Fwww.agner.org%2Foptimize%2Fmicroarchitecture.pdf&ei=8-sVUtWyM8nPtAb4ooCQBQ&usg=AFQjCNGRPm4A8ixWqSSGOOtNPCxp1YRfQg&sig2=Qe6Nxmz4Lee5Oo8UOGwTJw&bvm=bv.51156542,d.Yms