为什么 Perf 和 Papi 对 L3 缓存引用和未命中给出不同的值？
Why does Perf and Papi give different values for L3 cache references and misses?
我正在开展一个项目，我们必须实施一种在理论上被证明对缓存友好的算法。简单来说，如果 N 是输入，而 B 是每次缓存未命中时在缓存和 RAM 之间传输的元素数量，则算法将需要 O(N/B)访问 RAM。
我想证明这确实是实践中的行为。为了更好地理解如何测量各种缓存相关的硬件计数器，我决定使用不同的工具。一个是 Perf and the other is the PAPI 图书馆。不幸的是，我使用这些工具的次数越多，我就越不了解它们到底做了什么。
我使用的是 Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz，内存为 8 GB，一级缓存 256 KB，二级缓存 1 MB，三级缓存 6 MB。高速缓存行大小为 64 字节。我猜那一定是块的大小 B.
让我们看下面的例子：
#include <iostream>
using namespace std;
struct node{
int l, r;
};
int main(int argc, char* argv[]){
int n = 1000000;
node* A = new node[n];
int i;
for(i=0;i<n;i++){
A[i].l = 1;
A[i].r = 4;
}
return 0;
}
每个节点需要 8 个字节，这意味着一个缓存行可以容纳 8 个节点，所以我应该预计大约 1000000/8 = 125000 次 L3 缓存未命中。
没有优化（没有 -O3），这是 perf 的输出：
perf stat -B -e cache-references,cache-misses ./cachetests
Performance counter stats for './cachetests':
162,813 cache-references
142,247 cache-misses # 87.368 % of all cache refs
0.007163021 seconds time elapsed
这与我们的预期非常接近。现在假设我们使用 PAPI 库。
#include <iostream>
#include <papi.h>
using namespace std;
struct node{
int l, r;
};
void handle_error(int err){
std::cerr << "PAPI error: " << err << std::endl;
}
int main(int argc, char* argv[]){
int numEvents = 2;
long long values[2];
int events[2] = {PAPI_L3_TCA,PAPI_L3_TCM};
if (PAPI_start_counters(events, numEvents) != PAPI_OK)
handle_error(1);
int n = 1000000;
node* A = new node[n];
int i;
for(i=0;i<n;i++){
A[i].l = 1;
A[i].r = 4;
}
if ( PAPI_stop_counters(values, numEvents) != PAPI_OK)
handle_error(1);
cout<<"L3 accesses: "<<values[0]<<endl;
cout<<"L3 misses: "<<values[1]<<endl;
cout<<"L3 miss/access ratio: "<<(double)values[1]/values[0]<<endl;
return 0;
}
这是我得到的输出：
L3 accesses: 3335
L3 misses: 848
L3 miss/access ratio: 0.254273
为什么这两个工具有这么大的区别？
您可以查看 perf 和 PAPI 的源文件，找出它们实际将这些事件映射到哪个性能计数器，但事实证明它们是相同的（假设这里使用 Intel Core i）：事件 2E 与 umask 4F 用于参考和 41 用于未命中。在 the Intel 64 and IA-32 Architectures Developer's Manual 中，这些事件被描述为：
2EH 4FH LONGEST_LAT_CACHE.REFERENCE This event counts requests originating from the core that reference a cache line in the last level cache.
2EH 41H LONGEST_LAT_CACHE.MISS This event counts each cache miss condition for references to the last level cache.
好像还可以。所以问题出在其他地方。
这是我重现的数字，只是我将数组长度增加了 100 倍。（我注意到计时结果有很大的波动，并且长度为 1,000,000 的数组几乎仍然适合您的 L3 缓存）。 main1 这是你的第一个没有 PAPI 的代码示例，main2 你的第二个有 PAPI 的代码示例。
$ perf stat -e cache-references,cache-misses ./main1
Performance counter stats for './main1':
27.148.932 cache-references
22.233.713 cache-misses # 81,895 % of all cache refs
0,885166681 seconds time elapsed
$ ./main2
L3 accesses: 7084911
L3 misses: 2750883
L3 miss/access ratio: 0.388273
这些显然不匹配。让我们看看我们实际计算 LLC 引用的位置。这是perf record -e cache-references ./main1之后的perf report的前几行：
31,22% main1 [kernel] [k] 0xffffffff813fdd87 ▒
16,79% main1 main1 [.] main ▒
6,22% main1 [kernel] [k] 0xffffffff8182dd24 ▒
5,72% main1 [kernel] [k] 0xffffffff811b541d ▒
3,11% main1 [kernel] [k] 0xffffffff811947e9 ▒
1,53% main1 [kernel] [k] 0xffffffff811b5454 ▒
1,28% main1 [kernel] [k] 0xffffffff811b638a
1,24% main1 [kernel] [k] 0xffffffff811b6381 ▒
1,20% main1 [kernel] [k] 0xffffffff811b5417 ▒
1,20% main1 [kernel] [k] 0xffffffff811947c9 ▒
1,07% main1 [kernel] [k] 0xffffffff811947ab ▒
0,96% main1 [kernel] [k] 0xffffffff81194799 ▒
0,87% main1 [kernel] [k] 0xffffffff811947dc
所以你在这里可以看到实际上只有 16.79% 的缓存引用实际发生在用户 space 中，其余的都是由于内核。
问题就在这里。将此与 PAPI 结果进行比较是不公平的，因为默认情况下 PAPI 仅计算用户 space 事件。然而，Perf 默认收集用户和内核 space 事件。
对于 perf 我们可以很容易地减少到用户 space 集合：
$ perf stat -e cache-references:u,cache-misses:u ./main1
Performance counter stats for './main1':
7.170.190 cache-references:u
2.764.248 cache-misses:u # 38,552 % of all cache refs
0,658690600 seconds time elapsed
这些看起来很相配。
编辑：
让我们仔细看看内核做了什么，这次使用调试符号和缓存未命中而不是引用：
59,64% main1 [kernel] [k] clear_page_c_e
23,25% main1 main1 [.] main
2,71% main1 [kernel] [k] compaction_alloc
2,70% main1 [kernel] [k] pageblock_pfn_to_page
2,38% main1 [kernel] [k] get_pfnblock_flags_mask
1,57% main1 [kernel] [k] _raw_spin_lock
1,23% main1 [kernel] [k] clear_huge_page
1,00% main1 [kernel] [k] get_page_from_freelist
0,89% main1 [kernel] [k] free_pages_prepare
正如我们所见，大多数缓存未命中实际上发生在 clear_page_c_e 中。当我们的程序访问新页面时调用它。正如评论中所解释的，新页面在允许访问之前被内核清零，因此缓存未命中已经发生在这里。
这会打乱您的分析，因为您预期的大部分缓存未命中发生在内核 space 中。但是，您无法保证内核实际访问内存的具体情况，因此这可能与您的代码预期的行为存在偏差。
为避免这种情况，围绕您的数组填充循环构建一个额外的循环。只有内部循环的第一次迭代会导致内核开销。一旦数组中的每一页都被访问，就应该没有任何贡献了。这是我重复 100 次外循环的结果：
$ perf stat -e cache-references:u,cache-references:k,cache-misses:u,cache-misses:k ./main1
Performance counter stats for './main1':
1.327.599.357 cache-references:u
23.678.135 cache-references:k
1.242.836.730 cache-misses:u # 93,615 % of all cache refs
22.572.764 cache-misses:k # 95,332 % of all cache refs
38,286354681 seconds time elapsed
数组长度为 100,000,000，迭代次数为 100,000,000，因此根据您的分析，您预计会有 1,250,000,000 次缓存未命中。现在已经很接近了。偏差主要来自内核在页面清除期间加载到缓存的第一个循环。
使用 PAPI，可以在计数器开始之前插入一些额外的预热循环，因此结果更符合预期：
$ ./main2
L3 accesses: 1318699729
L3 misses: 1250684880
L3 miss/access ratio: 0.948423
我正在开展一个项目，我们必须实施一种在理论上被证明对缓存友好的算法。简单来说，如果 N 是输入，而 B 是每次缓存未命中时在缓存和 RAM 之间传输的元素数量，则算法将需要 O(N/B)访问 RAM。
我想证明这确实是实践中的行为。为了更好地理解如何测量各种缓存相关的硬件计数器，我决定使用不同的工具。一个是 Perf and the other is the PAPI 图书馆。不幸的是，我使用这些工具的次数越多，我就越不了解它们到底做了什么。
我使用的是 Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz，内存为 8 GB，一级缓存 256 KB，二级缓存 1 MB，三级缓存 6 MB。高速缓存行大小为 64 字节。我猜那一定是块的大小 B.
让我们看下面的例子：
#include <iostream>
using namespace std;
struct node{
int l, r;
};
int main(int argc, char* argv[]){
int n = 1000000;
node* A = new node[n];
int i;
for(i=0;i<n;i++){
A[i].l = 1;
A[i].r = 4;
}
return 0;
}
每个节点需要 8 个字节，这意味着一个缓存行可以容纳 8 个节点，所以我应该预计大约 1000000/8 = 125000 次 L3 缓存未命中。
没有优化（没有 -O3），这是 perf 的输出：
perf stat -B -e cache-references,cache-misses ./cachetests
Performance counter stats for './cachetests':
162,813 cache-references
142,247 cache-misses # 87.368 % of all cache refs
0.007163021 seconds time elapsed
这与我们的预期非常接近。现在假设我们使用 PAPI 库。
#include <iostream>
#include <papi.h>
using namespace std;
struct node{
int l, r;
};
void handle_error(int err){
std::cerr << "PAPI error: " << err << std::endl;
}
int main(int argc, char* argv[]){
int numEvents = 2;
long long values[2];
int events[2] = {PAPI_L3_TCA,PAPI_L3_TCM};
if (PAPI_start_counters(events, numEvents) != PAPI_OK)
handle_error(1);
int n = 1000000;
node* A = new node[n];
int i;
for(i=0;i<n;i++){
A[i].l = 1;
A[i].r = 4;
}
if ( PAPI_stop_counters(values, numEvents) != PAPI_OK)
handle_error(1);
cout<<"L3 accesses: "<<values[0]<<endl;
cout<<"L3 misses: "<<values[1]<<endl;
cout<<"L3 miss/access ratio: "<<(double)values[1]/values[0]<<endl;
return 0;
}
这是我得到的输出：
L3 accesses: 3335
L3 misses: 848
L3 miss/access ratio: 0.254273
为什么这两个工具有这么大的区别？
您可以查看 perf 和 PAPI 的源文件，找出它们实际将这些事件映射到哪个性能计数器，但事实证明它们是相同的（假设这里使用 Intel Core i）：事件 2E 与 umask 4F 用于参考和 41 用于未命中。在 the Intel 64 and IA-32 Architectures Developer's Manual 中，这些事件被描述为：
2EH 4FH LONGEST_LAT_CACHE.REFERENCE This event counts requests originating from the core that reference a cache line in the last level cache.
2EH 41H LONGEST_LAT_CACHE.MISS This event counts each cache miss condition for references to the last level cache.
好像还可以。所以问题出在其他地方。
这是我重现的数字，只是我将数组长度增加了 100 倍。（我注意到计时结果有很大的波动，并且长度为 1,000,000 的数组几乎仍然适合您的 L3 缓存）。 main1 这是你的第一个没有 PAPI 的代码示例，main2 你的第二个有 PAPI 的代码示例。
$ perf stat -e cache-references,cache-misses ./main1
Performance counter stats for './main1':
27.148.932 cache-references
22.233.713 cache-misses # 81,895 % of all cache refs
0,885166681 seconds time elapsed
$ ./main2
L3 accesses: 7084911
L3 misses: 2750883
L3 miss/access ratio: 0.388273
这些显然不匹配。让我们看看我们实际计算 LLC 引用的位置。这是perf record -e cache-references ./main1之后的perf report的前几行：
31,22% main1 [kernel] [k] 0xffffffff813fdd87 ▒
16,79% main1 main1 [.] main ▒
6,22% main1 [kernel] [k] 0xffffffff8182dd24 ▒
5,72% main1 [kernel] [k] 0xffffffff811b541d ▒
3,11% main1 [kernel] [k] 0xffffffff811947e9 ▒
1,53% main1 [kernel] [k] 0xffffffff811b5454 ▒
1,28% main1 [kernel] [k] 0xffffffff811b638a
1,24% main1 [kernel] [k] 0xffffffff811b6381 ▒
1,20% main1 [kernel] [k] 0xffffffff811b5417 ▒
1,20% main1 [kernel] [k] 0xffffffff811947c9 ▒
1,07% main1 [kernel] [k] 0xffffffff811947ab ▒
0,96% main1 [kernel] [k] 0xffffffff81194799 ▒
0,87% main1 [kernel] [k] 0xffffffff811947dc
所以你在这里可以看到实际上只有 16.79% 的缓存引用实际发生在用户 space 中，其余的都是由于内核。
问题就在这里。将此与 PAPI 结果进行比较是不公平的，因为默认情况下 PAPI 仅计算用户 space 事件。然而，Perf 默认收集用户和内核 space 事件。
对于 perf 我们可以很容易地减少到用户 space 集合：
$ perf stat -e cache-references:u,cache-misses:u ./main1
Performance counter stats for './main1':
7.170.190 cache-references:u
2.764.248 cache-misses:u # 38,552 % of all cache refs
0,658690600 seconds time elapsed
这些看起来很相配。
编辑：
让我们仔细看看内核做了什么，这次使用调试符号和缓存未命中而不是引用：
59,64% main1 [kernel] [k] clear_page_c_e
23,25% main1 main1 [.] main
2,71% main1 [kernel] [k] compaction_alloc
2,70% main1 [kernel] [k] pageblock_pfn_to_page
2,38% main1 [kernel] [k] get_pfnblock_flags_mask
1,57% main1 [kernel] [k] _raw_spin_lock
1,23% main1 [kernel] [k] clear_huge_page
1,00% main1 [kernel] [k] get_page_from_freelist
0,89% main1 [kernel] [k] free_pages_prepare
正如我们所见，大多数缓存未命中实际上发生在 clear_page_c_e 中。当我们的程序访问新页面时调用它。正如评论中所解释的，新页面在允许访问之前被内核清零，因此缓存未命中已经发生在这里。
这会打乱您的分析，因为您预期的大部分缓存未命中发生在内核 space 中。但是，您无法保证内核实际访问内存的具体情况，因此这可能与您的代码预期的行为存在偏差。
为避免这种情况，围绕您的数组填充循环构建一个额外的循环。只有内部循环的第一次迭代会导致内核开销。一旦数组中的每一页都被访问，就应该没有任何贡献了。这是我重复 100 次外循环的结果：
$ perf stat -e cache-references:u,cache-references:k,cache-misses:u,cache-misses:k ./main1
Performance counter stats for './main1':
1.327.599.357 cache-references:u
23.678.135 cache-references:k
1.242.836.730 cache-misses:u # 93,615 % of all cache refs
22.572.764 cache-misses:k # 95,332 % of all cache refs
38,286354681 seconds time elapsed
数组长度为 100,000,000，迭代次数为 100,000,000，因此根据您的分析，您预计会有 1,250,000,000 次缓存未命中。现在已经很接近了。偏差主要来自内核在页面清除期间加载到缓存的第一个循环。
使用 PAPI，可以在计数器开始之前插入一些额外的预热循环，因此结果更符合预期：
$ ./main2
L3 accesses: 1318699729
L3 misses: 1250684880
L3 miss/access ratio: 0.948423