c - 我如何确定我的程序运行缓慢是否是 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;
}

理论上，main 函数末尾的 fclose(input) 行应该无关紧要，因为操作系统应该在程序末尾自动关闭文件。但是我观察到，当我包含 fclose 语句时我的程序运行了 2.5 秒，而当我将其注释掉时运行了 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,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 上编译我的代码时，它也变得更快，尽管生成的汇编代码是相同的。唯一的区别是开始时的调试信息和二进制文件的各个部分的顺序不同。

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.4ns。因此，0.4ns/周期 * 15 个周期/遗漏分支 * (440,171,927 - 71,034,122) 分支遗漏 = 2.2 秒。这将取决于您的确切处理器和机器代码，但这解释了那里的大部分差异。

原因

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

那么，为什么它是相关的？好吧，发生的事情(99% 的可能性)是，通过非常轻微地重新安排您的程序，您可以更改完全不同的分支在内存位置方面的位置。在处理器的分支预测表中有太多映射到同一个桶。通过稍微更改可执行文件，这个问题就消失了。您必须在两个分支点之间有一个非常特定的距离才能触发此问题。不幸的是，你做到了。

简单的解决方案

如您所见，许多更改实际上会导致程序无法达到这种降级性能。本质上，任何改变两个关键分支点之间距离的东西都可以解决问题。您可以通过在这两个位置之间的某处插入 16 个字节(或足以将分支点移动到不同的存储桶)的机器代码 nop 来完成此操作。您也可以像以前那样做，改变一些会破坏与非病理情况的距离的东西。

深入挖掘

如果您想真正了解导致这种情况的原因，您需要亲自动手。乐趣!您将需要从众多工具中选择一种来查找被错误预测的特定分支。这是一种方式:How to measure mispredictions for a single branch on Linux?

在识别出预测错误的分支后，您可以确定是否有办法删除该分支(无论如何，这几乎总是一个提高性能的好主意)。如果没有，您可以为其添加一个提示，或者，最坏的情况是，只是四处移动以确保不会像之前建议的那样共享相同的条目。

更广泛的类(class)

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