Linux perf报告caching未命中意外的指令

我试图将一些性能工程技术应用于Dijkstraalgorithm的实现。为了find（天真的和未优化的）程序中的瓶颈，我使用perf命令来loggingcaching未命中的次数。相关的代码片段如下，它find距离最小的未访问节点：

 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 $0x1,%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 $0x0,(%rdi,%rdx,1) ▒ 0.53 │ ↑ jne ff ▒ │ if (tmp == -1 || dist[i] < dist[tmp]) { ▒ 0.07 │ cmp $0xffffffff,%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指令产生如此多的caching未命中？如果我没有弄错的话，这条指令不应该从内存中取回任何东西。我认为这可能与指令caching未命中有关，但即使使用L1-dcache-load-misses miss仅测量L1数据caching未L1-dcache-load-misses ，也表明在该指令中存在大量的caching未命中。

这让我有些困惑。有谁能解释这个（在我眼中）奇怪的结果？先谢谢你。

关于你的例子：

在柜台前和柜台上有几个指示：

  │ 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”是取决于比较结果的条件跳转。

许多现代英特尔CPU（和AMD也可能）可以并将一些操作组合（realworldtech.com/nehalem/5“合并到一个单一的uop，CMP + JCC”）中，并将cmp +条件跳转到非常常见的指令要融合的组合（你可以用Intel IACA模拟工具检查它，使用2.1版本的CPU）。可能会在perf / PMUs / PEBS中错误地报告熔合线对，其中大部分事件偏向两条指令之一。

这个代码可能意味着表达式“dist [i] <dist [tmp]”产生两个存储器访问，并且这两个值被用在与jbe条件跳转（部分地？）融合的ucomis指令中。 dist [i]或dist [tmp]或这两个表达式都会产生大量的失误。任何这样的错误将阻止ucomis生成结果并阻止jbe给下一个指令执行（或退出预测的指令）。所以， jbe可能会获得所有高计数器的名声，而不是真正的内存访问指令（对于“远”事件，比如高速缓存响应，对上一个被阻塞的指令有一些偏差）。

你可以尝试将visited [N]和dist [N]数组合并到struct { int visited; float dist} array [N]中struct { int visited; float dist} 当您访问array[i].visited或者您可能尝试更改顶点访问顺序，或重新编号图顶点，或者为下一个或多个元素执行一些软件预取（ struct { int visited; float dist}以强制预取array[i].dist ？）

关于名称问题的通用perf事件和可能的uncore歪斜。

在Linux中， perf （perf_events）工具在调用perf list时使用预定义的一组事件，并且一些列出的硬件事件可能不能实现; 其他映射到当前的CPU功能（和一些映射不完全正确）。关于真正的PMU的一些基本信息在你的https://software.intel.com/sites/products/collateral/hpc/vtune/performance_analysis_guide.pdf （但它有更多关于Nehalem-EP变种的细节）。

对于Nehalem（Intel Core i5 750，L3缓存为8MB，不支持多CPU /多插槽/ NUMA），perf将映射标准（ “通用缓存事件” ）LLC- LLC-load-misses事件为“OFFCORE_RESPONSE.ANY_DATA .ANY_LLC_MISS“写入perf事件映射（唯一一个）的最佳文档 – 内核源代码

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管道将（无序）加载请求发布到缓存层次结构并执行其他指令。经过一段时间（大约10个周期到达并获得L2的响应， 40个周期到达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空间），实际上L3实际上将实现为本地内存访问，并且有一些这样的计数器…（ https： //software.intel.com/zh-cn/node/596851- “在这里丢失的任何内存请求必须由本地或远程DRAM提供服务”）。

有一些PMU事件清单给你的CPU：

英特尔官方的“英特尔®64和IA-32架构软件开发人员手册”（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“18.8基于英特尔®微处理器代码的处理器性能监测代码名称NEHALEM” 213“第3B卷第18-35卷”
- 3B： https : //software.intel.com/sites/default/files/managed/7c/f1/253669-sdm-vol-3b.pdf “19.8 – 基于英特尔®微体系架构代码名称Nehalem的处理器” “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列表，获得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
来自英特尔的perf开发人员Andi Kleen的ocperf工具，是他的pmu工具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 of perf`的perf and this package will download event description and any supported event name will be converted into correct raw encoding of 。

应该有关于ANY_LLC_MISS offcore PMU事件执行的一些信息，以及NMB的PEBS事件列表，但我现在找不到它。

我可以推荐你使用来自https://github.com/andikleen/pmu-tools的 ocperf与你的CPU的任何PMU事件，而不需要手动编码它们。在你的CPU中有一些PEBS事件，并且有某些内存访问分析的延迟分析/ perf mem （一些随机的perf mem pdfs： 2012 post“perf：add memory access sampling support” ， RH 2013 – pg26-30 ，仍然没有在2015年记录 – sowa pg19 ， ls /sys/devices/cpu/events ）。对于较新的CPU，有更新的工具，如ucevent 。

我也可以推荐你用kcachegrind GUI来kcachegrind valgrind程序的cachegrind profiler / cache模拟器工具来查看配置文件。基于Valgrind的分析器可以帮助您了解代码的工作原理：它们为每条指令收集确切的指令执行计数，而cachegrind也模拟一些抽象的多级缓存。但是真正的CPU每个周期会执行几条指令（所以，1条指令= 1个CPU时钟周期的callgrind / cachegrind代价模型给出了一些错误; cachegrind缓存模型与真实缓存逻辑不一样）。所有的valgrind工具都是动态的二进制工具，与原生运行相比，这会减慢程序20-30倍。

当您读取内存位置时，处理器将尝试预取相邻的内存位置并缓存它们。

如果您正在读取全部分配在连续块的内存中的对象的数组，那么这种方法效果很好。

但是，例如，如果你有一个活在堆中的指针数组，除非你正在使用某种专门为此设计的自定义分配器，否则你将不太可能迭代内存的连续部分。

因此，解引用应该被看作是某种成本。结构数组可以更有效地指向结构体的指针数组。

Herb Sutter（C ++委员会成员）在这个演讲中谈到了这个问题https://youtu.be/TJHgp1ugKGM?t=21m31s