hug*_*omg 11 c performance profiling cpu-cache cachegrind
我目前正试图在我的一个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_bufferto <= 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上编译我的代码时,它也变得更快,尽管生成的汇编代码是相同的.唯一的区别是开始时的调试信息以及二进制文件的各个部分的顺序不同.
关键指标
你的罪魁祸首是分支未命中:
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高速缓存或天堂帮助您,主存储器中则可以更多.此外,编译器无法跨分支进行所有优化.