我如何确定程序的缓慢是否与CPU缓存有关（在Linux上）？

Question

我目前正在努力理解我一个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)语句应该没有作用，因为操作系统应该会在程序结束时自动关闭文件。但是我发现，当我包含了fclose语句时，程序运行需要2.5秒，而当我注释掉它时则需要5秒，相差了两倍！而且这不是由于程序开始或结束时的延迟所导致的：在有fclose语句的版本中，打印.的速度明显更快。

我怀疑这可能与某些内存对齐或缓存未命中问题有关。如果我将fclose替换为另一个函数（例如ftell），那么运行时间也是5秒；如果我将large_buffer的大小减小到<=8000个元素，则无论是否有fclose语句，程序总是以2.5秒的速度运行。

但我真的很想确定这种奇怪行为的罪魁祸首是什么。有没有可能在某种性能分析器或其他工具下运行我的程序，以便给我提供这些信息？到目前为止，我已经尝试使用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上编译我的代码时，它也变得更快，尽管生成的汇编代码相同。唯一的区别是开始处的调试信息和二进制文件的部分顺序不同。

- hugomg

---

操作系统应该在程序结束时自动关闭文件-在C中，这很乐观...它确实会释放fd等，但它可能不会像close()那样刷新缓冲数据。 - ThingyWotsit

@DanielJour: 很好的观点。 在程序的原始版本中，每个printf后都有一个fflush，我忘记在这个问题中包括它（我已经编辑包括了）。但即使如此，改变“large_buffer”数组的大小会影响运行时间的事实表明，这是某种内存问题，而不仅仅是输出缓冲区的结果。 我使用“/usr/bin/time”来测量每个程序运行所需的时间。 - hugomg

我不认为这与缓存或内存对齐有任何关系。fclose是一个库（系统）调用，肯定需要一定数量的周期才能完成。如果你的程序剩余部分恰好少于或等于这个循环计数，那么它看起来就像是2倍的改善。尝试将循环限制增加到10000。现在fclose 的效果不会是2倍！ - Isuru H

@IsuruH 好奇的是，这段代码在加入fclose之后运行速度更快，而不是更慢。 - Daniel Jour

我很想看看你如何执行 do_lots_of_stuff()。 - dbush

Answer 1

关键衡量指标

你的罪魁祸首是分支缺失：

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.4纳秒。 所以，0.4纳秒/周期×15个周期/错过的分支×（440,171,927-71,034,122）个分支预测错误= 2.2秒。这将取决于你确切的处理器和机器码，但这就解释了其中大部分的差异。

原因

不同芯片的分支预测算法是专有的，但是如果你在这里进行研究（http://www.agner.org/optimize/microarchitecture.pdf），你可以了解更多关于不同处理器及其限制的信息。实际上，你会发现某些处理器更好地避免在分支预测表中发生碰撞，这个表存储了有关分支是否被执行的预测。

那么，这与什么有关呢？ 好吧，最可能发生的是，通过微调程序略微改变了不同分支在内存位置方面的确切位置。 当映射到处理器的分支预测表中的同一个存储桶时，有太多的项会发生这种情况。 通过稍微更改可执行文件，这个问题就会消失。 你必须在两个分支点之间具有非常特定的距离才能触发此问题。 你很不幸地做到了。

简单解决方案

正如你所发现的，许多更改实际上将导致程序不会出现这种降级性能。 基本上，任何改变两个关键分支点之间距离的事情都会解决这个问题。 你可以通过在两者之间插入16个字节（或足以将分支点移动到不同的存储桶中）的机器码nop来完成这一点。 你也可以像你所做的那样，改变某些东西以破坏这种距离，使其达成非病态的情况。

深入挖掘

如果你想真正理解在这种情况下引起它的原因，你将需要动手。 很有趣！ 你需要选择其中一个工具来找到被误判的具体分支。 这是一种方法：如何在Linux上测量单个分支的错误预测？

在确定了被误判的分支之后，你可以弄清楚是否有方法可以消除该分支（几乎总是为了性能而很好的做法）。 如果没有，你可以为其提供提示，或者最坏情况下，只需移动事物以确保先前建议的相同条目不再共享。

更广泛的教训

程序员低估了分支的成本（当编译器无法在编译时删除分支时）。 正如你发现的那样，每个分支都会给处理器的分支预测缓冲区带来更大的

- Nick Apperson

---

谢谢你的数学计算！这真的是很好的证据，表明一直以来都是分支预测的问题。我进行了一些额外的测试（请参见我的编辑），确实表明这只是分支预测的问题，与内存局部性无关。 - hugomg

Answer 2

可见的变化是时间上的变化，因此您需要首先针对表现出和不表现出该行为的运行进行时间分析，以查看时间花费的位置发生了什么变化。如果幸运的话，您可以编译跟踪，并查看gprof可以输出什么内容而不影响行为。

如果您确实只有一个巨大的函数组成了大部分程序，则任何按函数进行时间汇总的东西都不会给出非常细粒度的结果。在这种情况下，您可以尝试将一个超级函数拆分成一组较小的函数网络，以便获取更精细的时间成本统计信息。

如果您不幸的话，并且编译用于分析使行为差异消失，则跳过对内核函数调用进行分析（可以动态完成），并查找与内核函数调用跟踪相关的时间差异，而不是用户函数调用跟踪。

一旦您知道时间去哪里了，您应该有更精确的问题要问，可能能够排除一些因素。此时，您可能需要使用perf-tools。

- Jeremy W. Sherman

---

我认为在这里分解成更小的函数不是一个选项。经过进一步分析，似乎这种奇怪的行为只会发生在 -O3 优化级别下，当我的代码几乎全部内联到主函数中时。无论如何，我在 perf-tools 下运行了我的代码，并将结果作为对我的问题的编辑发布了出来。你认为我们可以根据这些数字得出什么结论吗？ - hugomg

分支未命中在慢速运行情况下高达六倍。接下来的问题是，对于几乎相同的代码，哪些分支被错过了这么多次？实际上有多少运行时间归因于(a)未命中和(b)不同的代码路径。您可能能够从gprof中获取每行成本信息，这可能会清楚地显示时间花费在哪里。 - Jeremy W. Sherman

Answer 3

首先，您需要通过使用objdump -d进行反汇编，并进行比较来检查所有功能的健全性，确保唯一的区别在于main函数。您可以进行操作以便通过diff进行比较。

fclose的添加会引入一个新的符号（因此文件的一部分已经被修改），之后main函数也会被修改。这反过来会改变地址和偏移量。

因此，猜测是您会得到过多的缓存垃圾，而这在程序的先前版本中不存在。

在您的问题中，您声明已执行了cachegrind，但它报告为0%。这是不合理的。即使前面提到的怀疑是错误的，您仍然会遇到几个缺失。请粘贴两个结果。

Linux上玩耍的规范工具是perf（https://perf.wiki.kernel.org/index.php/Tutorial）。请确保运行多次，因为对于如此短的运行时间，您将获得很大的差异。

通过用注释标注它们，您可以显式地对齐两个变量和函数。

  __attribute__((aligned(64)))

玩转数字。

- user4822941

---

谢谢，我会在周一再次复现时进行检查。 - hugomg

更多的测试也揭示了这种奇怪的行为只会发生在 -O3 时，当所有东西都内联到主函数中。我仔细检查了生成的汇编代码，两种情况非常相似，只是其中一个程序在中间有一个额外的代码块用于 fclose。我在 perf 下运行了这些程序（感谢您的推荐，我之前不知道），并将结果发布在我的问题编辑中。明天，我会尝试做一些关于对齐的实验，还没有机会去做。 - hugomg

根据数据，几乎可以确定这是分支预测。您可以进行分析以查看哪些分支被错误预测以及频率如何。如果某个条件大部分时间都成立，您可以使用__builtin_expect((condition), 1)（或0）来注释它。真正的解决方法是减少分支（例如，可能在循环中有一个分支，但您可以将其移到外面，并有两个不同的主体变体）。 - user4822941

我可以使用什么来查找哪些分支预测错误？perf stat 只报告错误预测的总数。 - hugomg

@hugomg 使用 perf record 替代，然后使用 perf report --stdio。 - Art