问题 如何确定我的程序中的缓慢是否是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(input) 主函数末尾的行无关紧要,因为OS无论如何都应该在程序结束时自动关闭文件。但是我观察到,当我将fclose语句包含在内时,我的程序需要2.5秒才能运行。差异2倍!这不是因为程序开始或结束时的延迟:速度 . 使用fclose语句打印出来的版本明显更快。

我怀疑这可能与某些内存对齐或缓存未命中问题有关。如果我用ftell等另一个函数替换fclose,它也需要5s来运行,如果我减小了它的大小 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,171,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加载。哪些差异最有可能导致测试用例之间运行时间的2倍差异?


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


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


编辑4:事实证明,如果我通过编辑汇编文件来调整数组大小  加快速度。当我在C代码中改变它们的大小时,它变得更快的原因是因为gcc决定重新排列二进制文件中的东西的顺序。


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


3399
2018-04-05 21:24


起源

'操作系统应该在程序结束时自动关闭文件' - 在C中,这是乐观的...它将释放fd等,当然,但它可能不会像close()那样刷新缓冲数据。 - ThingyWotsit
@DanielJour:好点。在该程序的原始版本中,每个printf之后都有一个fflush,我忘了在这个问题中包含(我编辑现在包括它)。但即便如此,改变大小的事实 large_buffer 数组在运行时有效,表明这是某种内存问题,而不仅仅是输出缓冲工件。我用了 /usr/bin/time 衡量每个程序运行的时间。 - hugomg
我认为这与缓存或内存对齐无关。 fclose是一个库(系统)调用,肯定需要一定数量的周期才能完成。如果你的程序的其余部分恰好小于或等于这个循环计数,它看起来像是2倍的改进。尝试将循环限制增加到10000.现在fclose的效果不会是2X! - Isuru H
@IsuruH的好奇心似乎是代码运行得更快 同 该 fclose,不要慢。 - Daniel Jour
我有兴趣看你怎么样 do_lots_of_stuff() - dbush


答案:


关键指标

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

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

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

我不确定你的哪个处理器正在运行,但是如果你假设在Haswell上运行一个2.5 GHz处理器,你会发现每个分支预测错过大约15个周期(通常多一点因为其他东西也停止),每个周期为0.4ns。因此,0.4ns /周期* 15周期/错过分支*(440,171,927 - 71,034,122)分支未命中= 2.2秒。这取决于您的确切处理器和机器代码,但这解释了那里的大部分差异。

原因

不同芯片的分支预测算法是专有的,但如果你在这里研究( http://www.agner.org/optimize/microarchitecture.pdf)您可以了解有关不同处理器的更多信息以及这些限制从本质上讲,您会发现某些处理器可以更好地避免它们存储的分支预测表中的冲突,以便对是否采用分支进行预测。

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

简单解决方案

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

深层发掘

如果你想真正理解在这种情况下导致它的原因,你需要弄清楚。有趣!您需要选择许多工具之一来查找错误预测的特定分支。这是一种方式: 如何衡量Linux上单个分支的误预测?

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

更广泛的课程

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


9
2018-04-12 22:58



谢谢你的数学!这是一个很好的证据,它一直是分支预测。我做了一些额外的测试(参见我的编辑)确实表明它只是分支预测而且内存局部性与它无关。 - hugomg


首先,您需要通过拆卸所有功能来确保检查,并确保唯一的区别在于主要功能。您可以使用objdump -d进行反汇编并进行黑客攻击以与diff进行比较。

添加fclose会拉入一个新符号(因此文件的一部分已经被修改),之后主func也被修改。这又会改变地址和偏移量。

所以怀疑是你在程序的早期版本中没有出现过多的缓存垃圾。

在您的问题中,您声明cachegrind已执行,但它报告了0%。这并没有加起来。即使前面提到的怀疑是不正确的,你仍然会得到几次失误。请粘贴两个结果。

在linux上使用的规范工具是perf( https://perf.wiki.kernel.org/index.php/Tutorial )。确保运行几次,因为如此短的运行时间,你会得到很多变化。

您可以通过使用注释对变量和函数进行显式对齐

  __attribute__((aligned(64)))

玩数字。


3
2018-04-09 10:40



谢谢,我会在星期一检查这个,我可以再次重现这个。 - hugomg
更多测试还表明,奇怪的行为只发生在-O3上,当所有内容都在主函数内部进行内联时。我仔细检查了生成的程序集,两种情况非常相似,只是其中一个程序在fclose的中间有一个额外的代码块。我在下面运行程序 perf (感谢您的推荐,我没有意识到这一点)并将结果发布到我的问题的编辑上。明天,我会尝试做对齐的一些实验,但还没有机会做到这一点。 - hugomg
鉴于数据,这几乎肯定是分支预测。您可以剖析以查看哪些分支机构被错误预测以及发生频率。如果绝大多数时间都是某种情况,您可以通过将条件置于__builtin_expect((condition),1)(或0)内来对其进行注释。真正的修复包括尽可能少的分支(例如,你可能在一个循环中有一个分支,但你可以将它移到外面并改为使用2个变体)。 - employee of the month
我可以用什么来找出哪些分支被错误预测? perf stat 仅报告错误预测的总数。 - hugomg
@hugomg使用 perf record 相反,那么 perf report --stdio - Art


可见的变化是时间的变化,因此您需要首先在运行中瞄准时间分析器,这些运行既展示又不展示行为,以查看花费时间的变化。如果你很幸运,你可以编译进行跟踪,看看gprof可以吐出什么而不会扰乱行为。

如果你真正只有一个庞大的功能组成你的大部分程序,任何按功能累积时间的东西都不会给出非常精细的结果。在这种情况下,您可以尝试将一个超级功能分解为较小功能的网络,以获得更精细的时间成本统计。

如果你运气不好,并且编译进行性能分析会使行为差异消失,那么跳过分析内核函数调用(可以动态完成)并查找内核函数调用跟踪而不是用户函数的时间差异呼叫追踪。

一旦你知道时间在哪里,你应该有更准确的问题要问,并且可能能够排除一些因素。那时,你可能想爆发 穿孔 - 工具


3
2018-04-09 23:12



我不认为闯入较小的功能是一种选择。在进一步分析之后,似乎这种奇怪的行为只发生在-O3优化级别上,而几乎整个代码都在内部函数中内联。无论如何,我在perf-tools下运行我的代码并将结果发布为我的问题的编辑。你认为我们可以根据这些数字得出结论吗? - hugomg
在慢速运行的情况下,分支未命中率高出六倍。接下来的问题是,对于几乎相同的代码,分支机构被错过了多少。运行时间实际上可归因于(a)未命中和(b)不同的代码路径。您可以从gprof中获取行级别成本信息,这可能会清楚地显示时间花费的时间。 - Jeremy W. Sherman