c - gcc 简单算术循环性能

Question

问题:明显多出一行代码会使程序加速近两倍。

这个问题很难表述为原始问题，它来自边界检查消除算法。所以，只是一些我无法理解的简单测试。

明显多出一行代码会使程序加速近两倍。

有以下来源:

#include <stdlib.h>
#include <stdio.h>

int main(void)
{
   long i = 0, a = 0, x = 0;
   int  up = 200000000;

   int *values = malloc(sizeof(int)*up);

   for (i = 0; i < up ; ++i)
   {
        values[i]=i % 2;
   }
   for (i = 0; i < up  ; ++i)
   {
      x  =  (a & i);
#ifdef FAST
      x = 0;
#endif
      a += values[x];
   }
   printf ("a=%ld\n", a);
   return 0;
}/*main*/

在此示例中，“a”的值始终为 0。该行x = 0;是额外的。

但是，(看——没有任何优化!)
$gcc -O0 -o short short.c && time ./short
a=0
真正的0m2.808s
用户0m2.196s
系统 0m0.596s

$gcc -O0 -DFAST -o short short.c && time ./short
a=0
真实 0m1.869s
用户 0m1.260s
系统 0m0.608s

而且，这在许多编译器/优化选项和程序变体上是可重现的。

此外，除了将这个愚蠢的额外 0 放入某个寄存器之外，它们实际上产生了相同的汇编代码!例如:

gcc -S -O0 -DFAST short.c && mv short.s shortFAST.s
gcc -S -O0 short.c && mv short.s shortSLOW.s
diff shortFAST.s shortSLOW.s
55d54
< movq $0, -24(%rbp)

不久之后——对某些(所有我能够测试的)其他编译器/语言(包括 Java JIT)也产生了同样的影响。唯一共享的东西——x86-64 架构。在 Intel 和 AMD 处理器上进行了测试...

Answer 1

简短回答:存储 0 消除了其中一个循环中的先读后写依赖性。

详细信息:

我认为这是一个有趣的问题，虽然您关注的是 O0 优化级别，但在 O3 上也可以看到相同的加速。但是查看 O0 可以更容易地关注处理器正在做什么来优化代码而不是编译器，因为正如您所指出的那样，生成的汇编代码仅相差 1 条指令。

感兴趣的循环的汇编代码如下所示

  movq  $0, -32(%rbp)
  jmp .L4
.L5:     
  movq  -32(%rbp), %rax
  movq  -24(%rbp), %rdx
  andq  %rdx, %rax     
  movq  %rax, -16(%rbp)
  movq  $0, -16(%rbp)     ;; This instruction in FAST but not SLOW
  movq  -16(%rbp), %rax
  leaq  0(,%rax,4), %rdx
  movq  -8(%rbp), %rax  
  addq  %rdx, %rax      
  movl  (%rax), %eax    
  cltq                  
  addq  %rax, -24(%rbp) 
  addq  $1, -32(%rbp) 
.L4:                    
  movl  -36(%rbp), %eax 
  cltq                  
  cmpq  -32(%rbp), %rax 
  jg  .L5      

在我的系统上使用 perf stat 运行我得到以下结果:

慢速代码的结果

Performance counter stats for './slow_o0':

   1827.438670 task-clock                #    0.999 CPUs utilized          
           155 context-switches          #    0.085 K/sec                  
             1 CPU-migrations            #    0.001 K/sec                  
       195,448 page-faults               #    0.107 M/sec                  
 6,675,246,466 cycles                    #    3.653 GHz                    
 4,391,690,661 stalled-cycles-frontend   #   65.79% frontend cycles idle   
 1,609,321,845 stalled-cycles-backend    #   24.11% backend  cycles idle   
 7,157,837,211 instructions              #    1.07  insns per cycle        
                                         #    0.61  stalled cycles per insn
   490,110,757 branches                  #  268.195 M/sec                  
       178,287 branch-misses             #    0.04% of all branches        

   1.829712061 seconds time elapsed

快速代码的结果

 Performance counter stats for './fast_o0':

   1109.451910 task-clock                #    0.998 CPUs utilized          
            95 context-switches          #    0.086 K/sec                  
             1 CPU-migrations            #    0.001 K/sec                  
       195,448 page-faults               #    0.176 M/sec                  
 4,067,613,078 cycles                    #    3.666 GHz                    
 1,784,131,209 stalled-cycles-frontend   #   43.86% frontend cycles idle   
   438,447,105 stalled-cycles-backend    #   10.78% backend  cycles idle   
 7,356,892,998 instructions              #    1.81  insns per cycle        
                                         #    0.24  stalled cycles per insn
   489,945,197 branches                  #  441.610 M/sec                  
       176,136 branch-misses             #    0.04% of all branches        

   1.111398442 seconds time elapsed

因此您可以看到，即使“快速”代码执行的指令更多，它的停顿也更少。当乱序 CPU(如大多数 x64 架构)正在执行代码时，它会跟踪指令之间的依赖关系。如果操作数准备就绪，则等待指令可以被另一条指令绕过。

在这个例子中，关键点可能是这个指令序列:

  andq  %rdx, %rax
  movq  %rax, -16(%rbp)
  movq  $0, -16(%rbp)     ;; This instruction in FAST but not SLOW
  movq  -16(%rbp), %rax  
  leaq  0(,%rax,4), %rdx
  movq  -8(%rbp), %rax    

在快速代码中，movq -8(%rbp), %rax 指令将从 movq $0, -16(%rbp) 中获取结果转发给它它将能够更快地执行。而较慢的版本将不得不等待 movq %rax, -16(%rbp)，它在循环迭代之间具有更多的依赖性。

请注意，如果不了解更多有关特定微架构的信息，此分析可能过于简单。但我怀疑根本原因是这种依赖性，执行 0 的存储(movq $0, -16(%rbp) 指令)允许 CPU 在执行代码序列时执行更积极的推测。