11

我目前正试图了解我的一个 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 秒。相差2倍!这不是由于程序开始或结束时的延迟:在.使用 fclose 语句的版本中,打印出来的速度明显更快。

我怀疑这可能与某些内存对齐或缓存未命中问题有关。如果我用另一个函数(例如 ftell)替换 fclose,它也需要 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 上编译我的代码时,它也变得更快,尽管生成的汇编代码是相同的。唯一的区别是开始时的调试信息,并且二进制文件的各个部分的顺序不同。

4

3 回答 3

9

关键指标

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

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/cycle * 15 个周期/missed branch * (440,171,927 - 71,034,122) 分支未命中 = 2.2 秒。这将取决于您的确切处理器和机器代码,但这解释了那里的大部分差异。

原因

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

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

简单的解决方案

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

深层发掘

如果您想真正了解导致这种情况的原因,您需要亲自动手。乐趣!您将需要从众多工具中选择一种来查找被错误预测的特定分支。这是一种方法:如何测量 Linux 上单个分支的错误预测?

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

更广泛的课程

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

于 2017-04-12T22:58:23.643 回答
3

首先,您想通过反汇编所有 func 并确保唯一的区别在于 main 来进行完整性检查。您可以使用 objdump -d 反汇编并四处破解以与 diff 进行比较。

fclose 的添加引入了一个新符号(因此文件的一部分已被修改),之后主函数也被修改。这反过来又改变了地址和偏移量。

所以怀疑是你得到了以前版本的程序中不存在的过度缓存垃圾。

在您的问题中,您声明 cachegrind 已执行,但报告为 0%。这不加起来。即使上述怀疑是不正确的,你也一定会错过几次。请粘贴两个结果。

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

您可以通过使用注释来明确变量和函数的对齐方式

  __attribute__((aligned(64)))

玩数字。

于 2017-04-09T10:40:55.390 回答
3

可见的变化是时间上的变化,因此您希望首先将时间分析器瞄准显示和不显示行为的运行,以查看时间花费的变化。如果幸运的话,您可以编译以进行跟踪,并查看 gprof 可以在不干扰行为的情况下吐出什么。

如果你真的只有一个庞大的函数构成了程序的大部分,那么任何按函数进行时间汇总的东西都不会给出非常精细的结果。在这种情况下,您可以尝试将一个大型功能分解为一个由较小功能组成的网络,以获得更精细的时间成本统计信息。

如果你不走运,并且为分析进行编译使得行为差异消失了,那么跳到分析内核函数调用(可以动态完成)并查找关于内核函数调用跟踪而不是用户函数的时间差异呼叫跟踪。

一旦你知道时间要去哪里,你应该有更精确的问题要问,并且可能能够排除一些因素。那时,您可能想要打破perf-tools

于 2017-04-09T23:12:13.140 回答