3

考虑给定的两种情况，

在下面的这种情况下，我只是运行两个嵌套循环，它们都从初始化0并运行 upto 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？？

4

4 回答 4

5

我只是复制了结果，并问了自己与 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;
}

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

  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=4.bYms.

于 2013-08-22T10:32:45.860 回答
3

如今，当 CPU 设计人员考虑性能时，他们试图很好地了解他们的处理器将要运行的代码，然后他们设计他们的芯片以在该工作负载上尽可能快地运行。在他们所在的联赛中，这意味着做出权衡。因此，更常见的代码运行得更快，从而提高了整体性能。

于 2013-08-21T21:51:22.133 回答
0

如果正如上面@JesseJ 评论的那样，重复试验产生相同的结果，那么编译器优化代码的方式很可能有所不同。如果您在关闭优化的情况下进行编译，您可能会得到预期的结果 ( case2 > case1)。随着优化器的开启，所有的赌注都关闭了。

于 2013-08-21T21:49:21.323 回答
0

可能是因为您的编译器进行了优化。

现代编译器非常擅长优化循环。

实际上我很惊讶第一种情况花了这么长时间，大多数编译器优化器会看到你的循环什么都不做并且直接影响i=j=k^2而没有将它编译为一个充满跳转（汇编程序中的 JNZ）指令的空循环的负担，第二种情况会可能也只是影响cnt=10e8（可能溢出），因为编译器足够聪明，知道这将是循环的最终结果，并且循环不会做任何其他事情并且不会触发任何其他副作用，因此可以跳过.

尝试再次运行测试-O0以关闭编译器优化。实际上你没有提到你用来执行测试的编译器和编译器选项，所以到目前为止任何结论都是无用的。

于 2013-08-21T21:50:11.033 回答