如果我的程序缓慢是CPU缓存问题(在Linux上),我如何确定?

前端之家收集整理的这篇文章主要介绍了如果我的程序缓慢是CPU缓存问题(在Linux上),我如何确定?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我正在尝试在我的一个C程序中了解一些非常奇怪的行为.显然,在最后添加删除看似无关紧要的行显着影响了程序其余部分的性能.

我的程序看起来有点像这样:

int large_buffer[10000];

void compute(FILE * input) {
    for(int i=0; i<100; i++) {
        do_lots_of_stuff();
        printf(".");
        fflush(stdout);
    }
}

int main() {
    FILE *input = fopen("input.txt","r");
    compute(input);
    fclose(input); // <--- everything gets 2x slower if I comment this out (!)
    return 0;
}

理论上,主函数末尾的fclose(输入)行并不重要,因为操作系统应该在程序结束时自动关闭文件.但是我注意到,当我将fclose语句和5s的评论时,我的程序花了2.5秒才能运行.一个因素2差异!而这并不是由于程序开始或结束时的延迟:速度.打印出来的版本在fclose语句的版本中明显更快.

我怀疑这可能与一些内存对齐或缓存未命中的问题有关.如果我将fclose替换为另一个函数(如ftell),则还需要5秒运行,如果我将large_buffer的大小减小到< = 8000元素,那么总是运行2.5秒,无论是否存在fclose语句. 但我真的希望能够100%肯定这个奇怪的行为背后的罪魁祸首.是否可以运行我的程序在某种分析器或其他工具,将给我的信息?到目前为止,我尝试在valgrind –tool = cachegrind下运行两个版本,但它报告了我的程序的两个版本的缓存未命中(0%). 编辑1:在perf stat -d -d -d运行我的程序的两个版本后,我得到以下结果:

Performance counter stats for './no-fclose examples/bench.o':

       5625.535086      task-clock (msec)         #    1.000 cpus utilized          
                38      context-switches          #    0.007 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
                54      page-faults               #    0.010 K/sec                  
    17,851,853,580      cycles                    #    3.173 GHz                      (53.23%)
     6,421,955,412      stalled-cycles-frontend   #   35.97% frontend cycles idle     (53.23%)
     4,919,383,925      stalled-cycles-backend    #   27.56% backend cycles idle      (53.23%)
    13,294,878,129      instructions              #    0.74  insn per cycle         
                                                  #    0.48  stalled cycles per insn  (59.91%)
     3,178,485,061      branches                  #  565.010 M/sec                    (59.91%)
       440,171,927      branch-misses             #   13.85% of all branches          (59.92%)
     4,778,577,556      L1-dcache-loads           #  849.444 M/sec                    (60.19%)
           125,313      L1-dcache-load-misses     #    0.00% of all L1-dcache hits    (60.22%)
            12,110      LLC-loads                 #    0.002 M/sec                    (60.25%)
   <not supported>      LLC-load-misses                                             
   <not supported>      L1-icache-loads                                             
        20,196,491      L1-icache-load-misses                                         (60.22%)
     4,793,012,927      dTLB-loads                #  852.010 M/sec                    (60.18%)
               683      dTLB-load-misses          #    0.00% of all dTLB cache hits   (60.13%)
             3,443      iTLB-loads                #    0.612 K/sec                    (53.38%)
                90      iTLB-load-misses          #    2.61% of all iTLB cache hits   (53.31%)
   <not supported>      L1-dcache-prefetches                                        
            51,382      L1-dcache-prefetch-misses #    0.009 M/sec                    (53.24%)

       5.627225926 seconds time elapsed
Performance counter stats for './yes-fclose examples/bench.o':

       2652.609254      task-clock (msec)         #    1.000 cpus utilized          
                15      context-switches          #    0.006 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
                57      page-faults               #    0.021 K/sec                  
     8,277,447,108      cycles                    #    3.120 GHz                      (53.39%)
     2,453,903      stalled-cycles-frontend   #   29.64% frontend cycles idle     (53.46%)
     1,235,728,409      stalled-cycles-backend    #   14.93% backend cycles idle      (53.53%)
    13,296,127,857      instructions              #    1.61  insn per cycle         
                                                  #    0.18  stalled cycles per insn  (60.20%)
     3,177,698,785      branches                  # 1197.952 M/sec                    (60.20%)
        71,034,122      branch-misses             #    2.24% of all branches          (60.20%)
     4,790,733,157      L1-dcache-loads           # 1806.046 M/sec                    (60.20%)
            74,908      L1-dcache-load-misses     #    0.00% of all L1-dcache hits    (60.20%)
            15,289      LLC-loads                 #    0.006 M/sec                    (60.19%)
   <not supported>      LLC-load-misses                                             
   <not supported>      L1-icache-loads                                             
           140,750      L1-icache-load-misses                                         (60.08%)
     4,792,716,217      dTLB-loads                # 1806.793 M/sec                    (59.93%)
             1,010      dTLB-load-misses          #    0.00% of all dTLB cache hits   (59.78%)
               113      iTLB-loads                #    0.043 K/sec                    (53.12%)
               167      iTLB-load-misses          #  147.79% of all iTLB cache hits   (53.44%)
   <not supported>      L1-dcache-prefetches                                        
            29,744      L1-dcache-prefetch-misses #    0.011 M/sec                    (53.36%)

       2.653584624 seconds time elapsed

看起来在这两种情况下都没有数据缓存未命中,正如kcachegrind报道的那样,但较慢版本的程序具有较差的分支预测和更多的指令高速缓存未命中和iTLB负载.这些差异中的哪一个将最有可能对测试用例之间运行时的2x差异负责?

编辑2:有趣的事实,显然我仍然可以保持奇怪的行为,如果我用一个NOP指令替换“fclose”调用.

编辑3:我的处理器是Intel i5-2310(Sandy Bridge)

编辑4:结果,如果我通过编辑程序集文件来调整数组大小,它不会更快.当我更改C代码中的大小时,它的原因是更快,因为gcc决定重新排列二进制文件的顺序.

编辑5:更多的证据表明重要的是JMP指令的精确地址:如果我在代码开始添加一个NOP(而不是一个printf),它会变得更快.同样,如果我从我的代码开始删除一个无用的指令,它也会变得更快.当我在不同版本的gcc上编译我的代码时,尽管生成的汇编代码是相同的,但是它也变得更快.唯一的区别是开始时的调试信息,并且二进制文件的各个部分的顺序不同.

解决方法

关键指标

你的罪魁祸首是分支未命中:

440,927      branch-misses             #   13.85% of all branches

71,122      branch-misses             #    2.24% of all branches

我不知道你在运行哪个处理器,但如果您假设在Haswell上运行一个2.5 GHz的处理器,那么您将看到每个分支预测错误都花费大约15个周期(通常会因为其他的东西停顿)每个周期为0.4ns.所以,0.4ns /周期* 15个周期/错过的分支*(440,927 – 71,122)分支未命中= 2.2秒.它将取决于您的确切处理器和机器代码,但这解释了大部分的差异.

原因

不同芯片的分支预测算法是专有的,但如果您在此研究(http://www.agner.org/optimize/microarchitecture.pdf),您可以了解有关不同处理器的更多信息,并且存在局限性.本质上,您会发现某些处理器能够更好地避免分支预测表中存在的冲突,以便对已分支与否进行预测.

那么,为什么是相关的?那么发生了什么事情(99%的几率)就是通过重新排列你的程序,你改变了内存位置的不同分支.在处理器的分支预测表中,有太多映射到同一个数据桶.通过稍微更改可执行文件,这个问题就消失了.您必须在两个分支点之间有一个非常特定的距离来触发此问题.你已经不幸地设法做到这一点.

简单的解决方

正如您所发现的,许多更改实际上将导致程序不会影响这种降级的性能.基本上,改变两个关键分支点之间的距离的任何事情都会解决问题.您可以通过在两个地方之间的某处将字节插入16字节(或足够将分支点移动到不同的桶)来实现这一点.你也可以像你一样做,并改变一些会破坏这种距离到非病态的事情.

挖掘更深

如果你想真正了解在这种情况下是什么原因,你需要弄脏你的手.有趣!您将需要选择许多工具之一来查找被错误预测的特定分支.这是一种方式:How to measure mispredictions for a single branch on Linux?

在您识别错误的分支后,您可以确定是否有办法删除分支(几乎总是一个好的主意,无论如何).如果没有,您可以提供一个提示,或者最坏的情况下,只需移动一下,以确保相同的条目不会像以前建议的那样共享.

更广泛的课程

程序员低估分支的成本(编译器在编译时无法删除分支).如您所见,每个分支机构对处理器的分支预测缓冲区施加更多压力,并增加错误预测的机会.因此,即使是处理器100%可预测的分支机构,也可以通过减少可用于预测其他分支机构的资源来降低性能.此外,当一个分支错误预测时,它花费最少12-15个周期,如果所需的指令不在L1高速缓存,L2缓存,L3缓存或天堂帮助您,主要内存,则可能会更多.另外,编译器不能跨分支进行所有优化.

原文链接:https://www.f2er.com/linux/393884.html

猜你在找的Linux相关文章