Linux perf 报告缓存未命中意外指令
Linux perf reporting cache misses for unexpected instruction
我正在尝试将一些性能工程技术应用到 Dijkstra 算法的实现中。为了找到（原始和未优化的）程序中的瓶颈，我使用 perf 命令来记录缓存未命中的次数。相关的代码片段如下，它找到距离最小的未访问节点：
for (int i = 0; i < count; i++) {
if (!visited[i]) {
if (tmp == -1 || dist[i] < dist[tmp]) {
tmp = i;
}
}
}
对于 LLC-load-misses 指标，perf report 显示程序集的以下注释：
│ for (int i = 0; i < count; i++) { ▒
1.19 │ ff: add [=12=]x1,%eax ▒
0.03 │102: cmp 0x20(%rsp),%eax ▒
│ ↓ jge 135 ▒
│ if (!visited[i]) { ▒
0.07 │ movslq %eax,%rdx ▒
│ mov 0x18(%rsp),%rdi ◆
0.70 │ cmpb [=12=]x0,(%rdi,%rdx,1) ▒
0.53 │ ↑ jne ff ▒
│ if (tmp == -1 || dist[i] < dist[tmp]) { ▒
0.07 │ cmp [=12=]xffffffff,%r13d ▒
│ ↑ je fc ▒
0.96 │ mov 0x40(%rsp),%rcx ▒
0.08 │ movslq %r13d,%rsi ▒
│ movsd (%rcx,%rsi,8),%xmm0 ▒
0.13 │ ucomis (%rcx,%rdx,8),%xmm0 ▒
57.99 │ ↑ jbe ff ▒
│ tmp = i; ▒
│ mov %eax,%r13d ▒
│ ↑ jmp ff ▒
│ } ▒
│ } ▒
│ }
那么我的问题是：为什么 jbe 指令会产生如此多的缓存未命中？如果我没记错的话，这条指令根本不需要从内存中检索任何东西。我认为这可能与指令缓存未命中有关，但即使使用 L1-dcache-load-misses 仅测量 L1 数据缓存未命中也表明该指令中有很多缓存未命中。
这让我有点难过。谁能解释这个（在我眼中）奇怪的结果？提前谢谢你。
关于你的例子：
在高位计数器之前和处有几条指令：
│ movsd (%rcx,%rsi,8),%xmm0
0.13 │ ucomis (%rcx,%rdx,8),%xmm0
57.99 │ ↑ jbe ff
"movsd" 将 (%rcx,%rsi,8) 中的字（某些数组访问）加载到 xmm0 寄存器中，并且 "ucomis" 从 (%rcx,%rdx,8) 中加载另一个字并将其与刚刚加载的值进行比较xmm0 寄存器。 "jbe"是条件跳转，取决于比较结果。
许多现代 Intel CPUs（可能还有 AMD）可以并且将会融合（组合）一些运算组合（realworldtech.com/nehalem/5 "into a single uop, CMP+JCC"），以及 cmp +条件跳转非常常见的指令组合被融合（你可以用Intel IACA模拟工具检查它，你的CPU使用ver 2.1）。融合对可能会在 perf/PMUs/PEBS 中错误地报告，大多数事件偏向于两条指令之一。
这段代码可能意味着表达式 "dist[i] < dist[tmp]" 产生了两次内存访问，并且这两个值都用于 ucomis 指令中，该指令（部分？）与 jbe 条件跳转融合。 dist[i] 或 dist[tmp] 或两个表达式都会产生大量未命中。任何此类未命中都将阻止 ucomis 生成结果，并阻止 jbe 给出下一条要执行的指令（或退出预测的指令）。因此，jbe 可能会以高计数器而不是真正的内存访问指令而闻名（并且对于 "far" 缓存响应之类的事件，有一些偏向最后阻塞的指令）。
您可以尝试将 visited[N] 和 dist[N] 数组合并到 struct { int visited; float dist} 的数组 [N] 中，以在您访问 array[i].visited 时强制预取 array[i].dist 或者您可能会尝试更改顶点访问顺序，或重新编号图形顶点，或对下一个或多个元素进行一些软件预取 (?)
关于通用 perf 事件名称问题和可能的非核心偏差。
perf (perf_events) Linux 中的工具在调用 perf list 时使用预定义的事件集，一些列出的硬件事件无法实现；其他映射到当前 CPU 功能（有些映射不完全正确）。关于真实 PMU 的一些基本信息在你的 https://software.intel.com/sites/products/collateral/hpc/vtune/performance_analysis_guide.pdf 中（但它有更多关于相关 Nehalem-EP 变体的详细信息）。
对于您的 Nehalem（Intel Core i5 750，具有 8MB 的 L3 高速缓存且没有 multi-CPU/multi-socket/NUMA 支持）perf 会将标准 ("Generic cache events") LLC-load-misses 事件映射为 .. "OFFCORE_RESPONSE.ANY_DATA.ANY_LLC_MISS" 写在性能事件映射的最佳文档中（唯一的）-内核源代码
http://elixir.free-electrons.com/linux/v4.8/source/arch/x86/events/intel/core.c#L1103
u64 nehalem_hw_cache_event_ids ...
[ C(LL ) ] = {
[ C(OP_READ) ] = {
/* OFFCORE_RESPONSE.ANY_DATA.LOCAL_CACHE */
[ C(RESULT_ACCESS) ] = 0x01b7,
/* OFFCORE_RESPONSE.ANY_DATA.ANY_LLC_MISS */
[ C(RESULT_MISS) ] = 0x01b7,
...
/*
* Nehalem/Westmere MSR_OFFCORE_RESPONSE bits;
* See IA32 SDM Vol 3B 30.6.1.3
*/
#define NHM_DMND_DATA_RD (1 << 0)
#define NHM_DMND_READ (NHM_DMND_DATA_RD)
#define NHM_L3_MISS (NHM_NON_DRAM|NHM_LOCAL_DRAM|NHM_REMOTE_DRAM|NHM_REMOTE_CACHE_FWD)
...
u64 nehalem_hw_cache_extra_regs
..
[ C(LL ) ] = {
[ C(OP_READ) ] = {
[ C(RESULT_ACCESS) ] = NHM_DMND_READ|NHM_L3_ACCESS,
[ C(RESULT_MISS) ] = NHM_DMND_READ|NHM_L3_MISS,
我认为这个事件不准确：cpu 管道将 post（无序）加载请求到缓存层次结构并将执行其他指令。一段时间后 (around 10 cycles to reach and get response from L2 and 40 cycles to reach L3)，对应的（offcore？）PMU 中会出现带有未命中标志的响应，以增加计数器。在此计数器溢出时，将从该 PMU 生成分析中断。在几个 cpu 时钟周期内它将到达流水线以中断它，perf_events 子系统的处理程序将通过注册当前（中断）EIP/RIP 指令指针来处理此问题并将 PMU 计数器重置回某个负值（例如，-100000 表示每计数 100000 次 L3 未命中获得中断；使用 perf record -e LLC-load-misses -c 100000 设置精确计数或 perf 将自动调整限制以获得一些默认频率）。注册的EIP/RIP不是加载命令的IP，也可能不是要使用加载数据的命令的EIP/RIP。
但是如果你的 CPU 是系统中唯一的套接字并且你访问普通内存（不是一些映射的 PCI-express space），L3 miss 实际上将被实现为本地内存访问并且有一些计数器... (https://software.intel.com/en-us/node/596851 - "Any memory requests missing here must be serviced by local or remote DRAM").
您的 CPU 有一些 PMU 事件列表：
英特尔官方 "Intel® 64 and IA-32 Architectures Software Developer Manuals" (SDM)：https://software.intel.com/en-us/articles/intel-sdm，第 3 卷，附录 A
- 3B：https://software.intel.com/sites/default/files/managed/7c/f1/253669-sdm-vol-3b.pdf 第 213 页的“18.8 基于英特尔® 微体系结构代号 NEHALEM 的处理器性能监控”"Vol 3B 18-35"
- 3B：https://software.intel.com/sites/default/files/managed/7c/f1/253669-sdm-vol-3b.pdf“19.8 - 基于英特尔® 微体系结构代号 Nehalem 的处理器”来自第 365 页和 "Vol. 3B 19-61")
- Offcore 响应编码的其他卷？卷。 3A 18-26?
来自 oprofile http://oprofile.sourceforge.net/docs/intel-corei7-events.php
- 来自 libpfm4 的
showevtinfo http://www.bnikolic.co.uk/blog/hpc-prof-events.html（注意，此页面包含 Sandy Bridge 列表，请在您的 PC 上获取 libpfm4 ant 运行 以获取您的列表）。 libpfm4 中还有 check_events 工具，可帮助您将事件编码为原始 perf。
- 来自 VTune 文档：http://www.hpc.ut.ee/dokumendid/ips_xe_2015/vtune_amplifier_xe/documentation/en/help/reference/pmw_sp/events/offcore_response.html
- 来自 Nehalem PMU 指南：https://software.intel.com/sites/default/files/m/5/2/c/f/1/30320-Nehalem-PMU-Programming-Guide-Core.pdf
ocperf 来自 Intel 的 perf 开发人员 Andi Kleen 的工具，是他的 pmu-tools https://github.com/andikleen/pmu-tools 的一部分。 ocperf 只是 perf and this package will download event description and any supported event name will be converted into correct raw encoding ofperf` 的包装。
应该有一些关于 ANY_LLC_MISS offcore PMU 事件实现和 Nhm 的 PEBS 事件列表的信息，但我现在找不到。
我可以建议您将 https://github.com/andikleen/pmu-tools 中的 ocperf 与 CPU 的任何 PMU 事件一起使用，而无需手动对它们进行编码。您的 CPU 中有一些 PEBS 事件，并且有延迟分析 / perf mem 用于某种内存访问分析（一些随机性能内存 pdf：2012 post "perf: add memory access sampling support",RH 2013 - pg26-30, 2015 年仍未记录 - sowa pg19 、ls /sys/devices/cpu/events）。对于较新的 CPUs，有较新的工具，例如 ucevent.
我也可以推荐您尝试使用 kcachegrind GUI 的 valgrind 程序的 cachegrind profiler/cache simulator tool 来查看配置文件。基于 Valgrind 的分析器可以帮助您了解代码如何工作的基本概念：它们收集每条指令的准确指令执行计数，并且 cachegrind 还模拟一些抽象的多级缓存。但是真正的 CPU 每个周期会执行几条指令（因此，callgrind/cachegrind 1 条指令的成本模型 = 1 cpu 时钟周期给出了一些错误；cachegrind 缓存模型没有与真实缓存相同的逻辑）。所有 valgrind 工具都是动态二进制检测工具，与原生 运行.
相比，它们会使您的程序速度降低 20-30 倍
当您读取一个内存位置时，处理器将尝试预取相邻的内存位置并缓存它们。
如果您正在读取一个对象数组，这些对象都分配在内存中的连续块中，那么效果很好。
但是，例如，如果您有一个位于堆中的指针数组，除非您使用某种专门为此设计的自定义分配器，否则您不太可能迭代内存的连续部分。
正因为如此，取消引用应该被视为某种成本。结构数组比结构指针数组更有效。
Herb Sutter（C++ 委员会成员）在本次演讲中谈到了这一点 https://youtu.be/TJHgp1ugKGM?t=21m31s
我正在尝试将一些性能工程技术应用到 Dijkstra 算法的实现中。为了找到（原始和未优化的）程序中的瓶颈，我使用 perf 命令来记录缓存未命中的次数。相关的代码片段如下，它找到距离最小的未访问节点：
for (int i = 0; i < count; i++) {
if (!visited[i]) {
if (tmp == -1 || dist[i] < dist[tmp]) {
tmp = i;
}
}
}
对于 LLC-load-misses 指标，perf report 显示程序集的以下注释：
│ for (int i = 0; i < count; i++) { ▒
1.19 │ ff: add [=12=]x1,%eax ▒
0.03 │102: cmp 0x20(%rsp),%eax ▒
│ ↓ jge 135 ▒
│ if (!visited[i]) { ▒
0.07 │ movslq %eax,%rdx ▒
│ mov 0x18(%rsp),%rdi ◆
0.70 │ cmpb [=12=]x0,(%rdi,%rdx,1) ▒
0.53 │ ↑ jne ff ▒
│ if (tmp == -1 || dist[i] < dist[tmp]) { ▒
0.07 │ cmp [=12=]xffffffff,%r13d ▒
│ ↑ je fc ▒
0.96 │ mov 0x40(%rsp),%rcx ▒
0.08 │ movslq %r13d,%rsi ▒
│ movsd (%rcx,%rsi,8),%xmm0 ▒
0.13 │ ucomis (%rcx,%rdx,8),%xmm0 ▒
57.99 │ ↑ jbe ff ▒
│ tmp = i; ▒
│ mov %eax,%r13d ▒
│ ↑ jmp ff ▒
│ } ▒
│ } ▒
│ }
那么我的问题是：为什么 jbe 指令会产生如此多的缓存未命中？如果我没记错的话，这条指令根本不需要从内存中检索任何东西。我认为这可能与指令缓存未命中有关，但即使使用 L1-dcache-load-misses 仅测量 L1 数据缓存未命中也表明该指令中有很多缓存未命中。
这让我有点难过。谁能解释这个（在我眼中）奇怪的结果？提前谢谢你。
关于你的例子：
在高位计数器之前和处有几条指令：
│ movsd (%rcx,%rsi,8),%xmm0
0.13 │ ucomis (%rcx,%rdx,8),%xmm0
57.99 │ ↑ jbe ff
"movsd" 将 (%rcx,%rsi,8) 中的字（某些数组访问）加载到 xmm0 寄存器中，并且 "ucomis" 从 (%rcx,%rdx,8) 中加载另一个字并将其与刚刚加载的值进行比较xmm0 寄存器。 "jbe"是条件跳转，取决于比较结果。
许多现代 Intel CPUs（可能还有 AMD）可以并且将会融合（组合）一些运算组合（realworldtech.com/nehalem/5 "into a single uop, CMP+JCC"），以及 cmp +条件跳转非常常见的指令组合被融合（你可以用Intel IACA模拟工具检查它，你的CPU使用ver 2.1）。融合对可能会在 perf/PMUs/PEBS 中错误地报告，大多数事件偏向于两条指令之一。
这段代码可能意味着表达式 "dist[i] < dist[tmp]" 产生了两次内存访问，并且这两个值都用于 ucomis 指令中，该指令（部分？）与 jbe 条件跳转融合。 dist[i] 或 dist[tmp] 或两个表达式都会产生大量未命中。任何此类未命中都将阻止 ucomis 生成结果，并阻止 jbe 给出下一条要执行的指令（或退出预测的指令）。因此，jbe 可能会以高计数器而不是真正的内存访问指令而闻名（并且对于 "far" 缓存响应之类的事件，有一些偏向最后阻塞的指令）。
您可以尝试将 visited[N] 和 dist[N] 数组合并到 struct { int visited; float dist} 的数组 [N] 中，以在您访问 array[i].visited 时强制预取 array[i].dist 或者您可能会尝试更改顶点访问顺序，或重新编号图形顶点，或对下一个或多个元素进行一些软件预取 (?)
关于通用 perf 事件名称问题和可能的非核心偏差。
perf (perf_events) Linux 中的工具在调用 perf list 时使用预定义的事件集，一些列出的硬件事件无法实现；其他映射到当前 CPU 功能（有些映射不完全正确）。关于真实 PMU 的一些基本信息在你的 https://software.intel.com/sites/products/collateral/hpc/vtune/performance_analysis_guide.pdf 中（但它有更多关于相关 Nehalem-EP 变体的详细信息）。
对于您的 Nehalem（Intel Core i5 750，具有 8MB 的 L3 高速缓存且没有 multi-CPU/multi-socket/NUMA 支持）perf 会将标准 ("Generic cache events") LLC-load-misses 事件映射为 .. "OFFCORE_RESPONSE.ANY_DATA.ANY_LLC_MISS" 写在性能事件映射的最佳文档中（唯一的）-内核源代码
http://elixir.free-electrons.com/linux/v4.8/source/arch/x86/events/intel/core.c#L1103
u64 nehalem_hw_cache_event_ids ...
[ C(LL ) ] = {
[ C(OP_READ) ] = {
/* OFFCORE_RESPONSE.ANY_DATA.LOCAL_CACHE */
[ C(RESULT_ACCESS) ] = 0x01b7,
/* OFFCORE_RESPONSE.ANY_DATA.ANY_LLC_MISS */
[ C(RESULT_MISS) ] = 0x01b7,
...
/*
* Nehalem/Westmere MSR_OFFCORE_RESPONSE bits;
* See IA32 SDM Vol 3B 30.6.1.3
*/
#define NHM_DMND_DATA_RD (1 << 0)
#define NHM_DMND_READ (NHM_DMND_DATA_RD)
#define NHM_L3_MISS (NHM_NON_DRAM|NHM_LOCAL_DRAM|NHM_REMOTE_DRAM|NHM_REMOTE_CACHE_FWD)
...
u64 nehalem_hw_cache_extra_regs
..
[ C(LL ) ] = {
[ C(OP_READ) ] = {
[ C(RESULT_ACCESS) ] = NHM_DMND_READ|NHM_L3_ACCESS,
[ C(RESULT_MISS) ] = NHM_DMND_READ|NHM_L3_MISS,
我认为这个事件不准确：cpu 管道将 post（无序）加载请求到缓存层次结构并将执行其他指令。一段时间后 (around 10 cycles to reach and get response from L2 and 40 cycles to reach L3)，对应的（offcore？）PMU 中会出现带有未命中标志的响应，以增加计数器。在此计数器溢出时，将从该 PMU 生成分析中断。在几个 cpu 时钟周期内它将到达流水线以中断它，perf_events 子系统的处理程序将通过注册当前（中断）EIP/RIP 指令指针来处理此问题并将 PMU 计数器重置回某个负值（例如，-100000 表示每计数 100000 次 L3 未命中获得中断；使用 perf record -e LLC-load-misses -c 100000 设置精确计数或 perf 将自动调整限制以获得一些默认频率）。注册的EIP/RIP不是加载命令的IP，也可能不是要使用加载数据的命令的EIP/RIP。
但是如果你的 CPU 是系统中唯一的套接字并且你访问普通内存（不是一些映射的 PCI-express space），L3 miss 实际上将被实现为本地内存访问并且有一些计数器... (https://software.intel.com/en-us/node/596851 - "Any memory requests missing here must be serviced by local or remote DRAM").
您的 CPU 有一些 PMU 事件列表：
英特尔官方 "Intel® 64 and IA-32 Architectures Software Developer Manuals" (SDM)：https://software.intel.com/en-us/articles/intel-sdm，第 3 卷，附录 A
- 3B：https://software.intel.com/sites/default/files/managed/7c/f1/253669-sdm-vol-3b.pdf 第 213 页的“18.8 基于英特尔® 微体系结构代号 NEHALEM 的处理器性能监控”"Vol 3B 18-35"
- 3B：https://software.intel.com/sites/default/files/managed/7c/f1/253669-sdm-vol-3b.pdf“19.8 - 基于英特尔® 微体系结构代号 Nehalem 的处理器”来自第 365 页和 "Vol. 3B 19-61")
- Offcore 响应编码的其他卷？卷。 3A 18-26?
来自 oprofile http://oprofile.sourceforge.net/docs/intel-corei7-events.php
- 来自 libpfm4 的
showevtinfohttp://www.bnikolic.co.uk/blog/hpc-prof-events.html（注意，此页面包含 Sandy Bridge 列表，请在您的 PC 上获取 libpfm4 ant 运行 以获取您的列表）。 libpfm4 中还有check_events工具，可帮助您将事件编码为原始perf。 - 来自 VTune 文档：http://www.hpc.ut.ee/dokumendid/ips_xe_2015/vtune_amplifier_xe/documentation/en/help/reference/pmw_sp/events/offcore_response.html
- 来自 Nehalem PMU 指南：https://software.intel.com/sites/default/files/m/5/2/c/f/1/30320-Nehalem-PMU-Programming-Guide-Core.pdf
ocperf来自 Intel 的 perf 开发人员 Andi Kleen 的工具，是他的 pmu-tools https://github.com/andikleen/pmu-tools 的一部分。ocperf只是perf and this package will download event description and any supported event name will be converted into correct raw encoding ofperf` 的包装。
应该有一些关于 ANY_LLC_MISS offcore PMU 事件实现和 Nhm 的 PEBS 事件列表的信息，但我现在找不到。
我可以建议您将 https://github.com/andikleen/pmu-tools 中的 ocperf 与 CPU 的任何 PMU 事件一起使用，而无需手动对它们进行编码。您的 CPU 中有一些 PEBS 事件，并且有延迟分析 / perf mem 用于某种内存访问分析（一些随机性能内存 pdf：2012 post "perf: add memory access sampling support",RH 2013 - pg26-30, 2015 年仍未记录 - sowa pg19 、ls /sys/devices/cpu/events）。对于较新的 CPUs，有较新的工具，例如 ucevent.
我也可以推荐您尝试使用 kcachegrind GUI 的 valgrind 程序的 cachegrind profiler/cache simulator tool 来查看配置文件。基于 Valgrind 的分析器可以帮助您了解代码如何工作的基本概念：它们收集每条指令的准确指令执行计数，并且 cachegrind 还模拟一些抽象的多级缓存。但是真正的 CPU 每个周期会执行几条指令（因此，callgrind/cachegrind 1 条指令的成本模型 = 1 cpu 时钟周期给出了一些错误；cachegrind 缓存模型没有与真实缓存相同的逻辑）。所有 valgrind 工具都是动态二进制检测工具，与原生 运行.
当您读取一个内存位置时，处理器将尝试预取相邻的内存位置并缓存它们。
如果您正在读取一个对象数组，这些对象都分配在内存中的连续块中，那么效果很好。
但是，例如，如果您有一个位于堆中的指针数组，除非您使用某种专门为此设计的自定义分配器，否则您不太可能迭代内存的连续部分。
正因为如此，取消引用应该被视为某种成本。结构数组比结构指针数组更有效。
Herb Sutter（C++ 委员会成员）在本次演讲中谈到了这一点 https://youtu.be/TJHgp1ugKGM?t=21m31s