如果我的程序运行缓慢是 CPU 缓存问题（在 Linux 上），我该如何确定？
How can I pinpoint if the slowness in my program is a CPU cache issue (on 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;
}
理论上，main 函数末尾的 fclose(input) 行应该无关紧要，因为 OS 应该会在程序末尾自动关闭文件。但是我观察到，当我包含 fclose 语句时，我的程序花费了 2.5 秒到 运行，而当我将其注释掉时，它花费了 5 秒。相差2倍！这不是由于程序开始或结束时的延迟：在带有 fclose 语句的版本中，. 的打印速度明显更快。
我怀疑这可能与某些内存对齐或缓存未命中问题有关。如果我将 fclose 替换为另一个函数，例如 ftell，它也需要 5s 到 运行，如果我将 large_buffer 的大小减少到 <= 8000 个元素，那么它总是 运行s 在 2.5 中秒，无论 fclose 语句是否存在。
但我真的很想 100% 确定这种奇怪行为背后的罪魁祸首是什么。是否有可能 运行 我的程序在某种探查器或其他工具下可以给我该信息？到目前为止，我在 valgrind --tool=cachegrind 下尝试了 运行ning 两个版本，但它报告了我程序的两个版本相同数量的缓存未命中 (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 上编译我的代码时，它也变得更快，尽管生成的汇编代码是相同的。唯一的区别是开始时的调试信息和二进制文件的各个部分的顺序不同。
首先，您想通过反汇编所有函数并确保唯一的区别在于 main 来进行健全性检查。您可以使用 objdump -d 进行反汇编并进行修改以与 diff 进行比较。
添加 fclose 会引入一个新的符号（因此文件的一部分已经被修改），然后主函数也被修改。这反过来会改变地址和偏移量。
所以怀疑您得到了以前版本的程序中不存在的过多缓存垃圾。
在您的问题中，您说 cachegrind 已执行，但报告为 0%。这不加起来。即使上述怀疑是不正确的，你也一定会错过几次。请粘贴两个结果。
在 linux 上使用的规范工具是 perf ( https://perf.wiki.kernel.org/index.php/Tutorial )。确保 运行 几次，因为如此短的 运行 次你会得到很大的差异。
您可以通过使用
注释来显式对齐变量和函数
__attribute__((aligned(64)))
玩转数字。
可见的变化是时间上的变化，因此您希望首先将时间分析器瞄准既表现出又不表现出行为的运行，以查看时间花费的地方发生了什么变化。如果幸运的话，您可以编译跟踪并查看 gprof 可以在不扰乱行为的情况下吐出什么。
如果您真的只有一个庞大的功能构成了您的大部分程序，那么任何按功能进行时间汇总的功能都不会给出非常精细的结果。在这种情况下，您可以尝试将一个大型功能分解为一个由较小功能组成的网络，以获得更精细的时间成本统计信息。
如果你不走运，为了分析而编译使得行为差异消失，那么跳到分析内核函数调用（可以动态完成）并查找与内核函数调用跟踪有关的时间差异而不是用户函数调用跟踪。
一旦您知道时间将流向何处，您应该可以提出更精确的问题，并且可能能够排除一些因素。到那时，您可能想要突破 perf-tools.
关键指标
你的罪魁祸首是分支未命中：
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 cycles/missed 分支 * (440,171,927 - 71,034,122) 分支未命中 = 2.2 秒。这将取决于您的确切处理器和机器代码，但这解释了那里的大部分差异。
原因
不同芯片的分支预测算法是专有的，但如果你在这里研究（http://www.agner.org/optimize/microarchitecture.pdf），你可以了解更多关于不同处理器的信息以及它们的局限性。本质上，您会发现某些处理器在避免它们存储的分支预测表中的冲突方面做得更好，这些预测表用于预测是否采用分支。
那么，为什么这很重要？好吧，发生的事情（99% 的可能性）是，通过非常轻微地重新安排您的程序，您可以更改完全不同的分支在内存位置方面的位置。在处理器的分支预测表中有太多映射到同一个桶。通过稍微更改可执行文件，这个问题就消失了。您必须在两个分支点之间有一个非常特定的距离才能触发此问题。不幸的是你做到了。
简单的解决方案
如您所见，许多更改实际上会导致程序无法达到这种降级性能。本质上，任何改变两个关键分支点之间距离的东西都可以解决问题。您可以通过在这两个位置之间的某处插入 16 个字节（或足以将分支点移动到不同的存储桶）的机器代码 nop 来完成此操作。你也可以像你一样做，改变一些会破坏这个距离的东西到非病理情况。
深入挖掘
如果您想真正了解导致这种情况的原因，您需要亲自动手。乐趣！您将需要 select 众多工具中的一种来查找被错误预测的特定分支。这是一种方法：How to measure mispredictions for a single branch on Linux?
在识别出预测错误的分支后，您可以确定是否有办法删除该分支（无论如何，这几乎总是一个提高性能的好主意）。如果没有，您可以为它添加一个提示，或者，最坏的情况是，只是四处移动以确保不会像之前建议的那样共享相同的条目。
更广泛的课程
程序员低估了分支的成本（当编译器无法在编译时删除分支时）。正如您所发现的，每个分支都会给处理器的分支预测缓冲区带来更多压力，并增加预测错误的可能性。因此，即使处理器 100% 可预测的分支也会通过减少可用于预测其他分支的资源来降低性能。此外，当一个分支被错误预测时，它至少需要 12-15 个周期，如果所需的指令不在 L1 缓存、L2 缓存、L3 缓存或天堂帮助你，主内存中，可能会更多。此外，编译器无法跨分支进行所有优化。
我目前正试图了解我的一个 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) 行应该无关紧要，因为 OS 应该会在程序末尾自动关闭文件。但是我观察到，当我包含 fclose 语句时，我的程序花费了 2.5 秒到 运行，而当我将其注释掉时，它花费了 5 秒。相差2倍！这不是由于程序开始或结束时的延迟：在带有 fclose 语句的版本中，. 的打印速度明显更快。
我怀疑这可能与某些内存对齐或缓存未命中问题有关。如果我将 fclose 替换为另一个函数，例如 ftell，它也需要 5s 到 运行，如果我将 large_buffer 的大小减少到 <= 8000 个元素，那么它总是 运行s 在 2.5 中秒，无论 fclose 语句是否存在。
但我真的很想 100% 确定这种奇怪行为背后的罪魁祸首是什么。是否有可能 运行 我的程序在某种探查器或其他工具下可以给我该信息？到目前为止，我在 valgrind --tool=cachegrind 下尝试了 运行ning 两个版本，但它报告了我程序的两个版本相同数量的缓存未命中 (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 上编译我的代码时，它也变得更快，尽管生成的汇编代码是相同的。唯一的区别是开始时的调试信息和二进制文件的各个部分的顺序不同。
首先，您想通过反汇编所有函数并确保唯一的区别在于 main 来进行健全性检查。您可以使用 objdump -d 进行反汇编并进行修改以与 diff 进行比较。
添加 fclose 会引入一个新的符号（因此文件的一部分已经被修改），然后主函数也被修改。这反过来会改变地址和偏移量。
所以怀疑您得到了以前版本的程序中不存在的过多缓存垃圾。
在您的问题中，您说 cachegrind 已执行，但报告为 0%。这不加起来。即使上述怀疑是不正确的，你也一定会错过几次。请粘贴两个结果。
在 linux 上使用的规范工具是 perf ( https://perf.wiki.kernel.org/index.php/Tutorial )。确保 运行 几次，因为如此短的 运行 次你会得到很大的差异。
您可以通过使用
注释来显式对齐变量和函数 __attribute__((aligned(64)))
玩转数字。
可见的变化是时间上的变化，因此您希望首先将时间分析器瞄准既表现出又不表现出行为的运行，以查看时间花费的地方发生了什么变化。如果幸运的话，您可以编译跟踪并查看 gprof 可以在不扰乱行为的情况下吐出什么。
如果您真的只有一个庞大的功能构成了您的大部分程序，那么任何按功能进行时间汇总的功能都不会给出非常精细的结果。在这种情况下，您可以尝试将一个大型功能分解为一个由较小功能组成的网络，以获得更精细的时间成本统计信息。
如果你不走运，为了分析而编译使得行为差异消失，那么跳到分析内核函数调用（可以动态完成）并查找与内核函数调用跟踪有关的时间差异而不是用户函数调用跟踪。
一旦您知道时间将流向何处，您应该可以提出更精确的问题，并且可能能够排除一些因素。到那时，您可能想要突破 perf-tools.
关键指标
你的罪魁祸首是分支未命中：
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 cycles/missed 分支 * (440,171,927 - 71,034,122) 分支未命中 = 2.2 秒。这将取决于您的确切处理器和机器代码，但这解释了那里的大部分差异。
原因
不同芯片的分支预测算法是专有的，但如果你在这里研究（http://www.agner.org/optimize/microarchitecture.pdf），你可以了解更多关于不同处理器的信息以及它们的局限性。本质上，您会发现某些处理器在避免它们存储的分支预测表中的冲突方面做得更好，这些预测表用于预测是否采用分支。
那么，为什么这很重要？好吧，发生的事情（99% 的可能性）是，通过非常轻微地重新安排您的程序，您可以更改完全不同的分支在内存位置方面的位置。在处理器的分支预测表中有太多映射到同一个桶。通过稍微更改可执行文件，这个问题就消失了。您必须在两个分支点之间有一个非常特定的距离才能触发此问题。不幸的是你做到了。
简单的解决方案
如您所见，许多更改实际上会导致程序无法达到这种降级性能。本质上，任何改变两个关键分支点之间距离的东西都可以解决问题。您可以通过在这两个位置之间的某处插入 16 个字节（或足以将分支点移动到不同的存储桶）的机器代码 nop 来完成此操作。你也可以像你一样做，改变一些会破坏这个距离的东西到非病理情况。
深入挖掘
如果您想真正了解导致这种情况的原因，您需要亲自动手。乐趣！您将需要 select 众多工具中的一种来查找被错误预测的特定分支。这是一种方法：How to measure mispredictions for a single branch on Linux?
在识别出预测错误的分支后，您可以确定是否有办法删除该分支（无论如何，这几乎总是一个提高性能的好主意）。如果没有，您可以为它添加一个提示，或者，最坏的情况是，只是四处移动以确保不会像之前建议的那样共享相同的条目。
更广泛的课程
程序员低估了分支的成本（当编译器无法在编译时删除分支时）。正如您所发现的，每个分支都会给处理器的分支预测缓冲区带来更多压力，并增加预测错误的可能性。因此，即使处理器 100% 可预测的分支也会通过减少可用于预测其他分支的资源来降低性能。此外，当一个分支被错误预测时，它至少需要 12-15 个周期，如果所需的指令不在 L1 缓存、L2 缓存、L3 缓存或天堂帮助你，主内存中，可能会更多。此外，编译器无法跨分支进行所有优化。