c++ - 为什么 Perf 和 Papi 为 L3 缓存引用和未命中提供不同的值？

Question

我正在开展一个项目，我们必须实现一种理论上证明对缓存友好的算法。简单来说，如果 N 是输入，B 是每次缓存未命中时在缓存和 RAM 之间传输的元素数，算法将需要 O(N/B) 访问 RAM。

我想证明这确实是实践中的行为。为了更好地理解如何测量各种与缓存相关的硬件计数器，我决定使用不同的工具。一种是Perf另一个是PAPI图书馆。不幸的是，我使用这些工具越多，我就越不了解它们到底在做什么。

我正在使用 Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz，8 GB RAM，L1 缓存 256 KB，L2 缓存 1 MB，L3 缓存 6 MB。高速缓存行大小为 64 字节。我想这一定是 block 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

为什么这两个工具有这么大的区别？

Answer 1

您可以查看 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% 的缓存引用实际发生在用户空间中，其余的都是由内核引起的。

这就是问题所在。将此与 PAPI 结果进行比较是不公平的，因为默认情况下 PAPI 仅计算用户空间事件。然而，Perf 默认收集用户和内核空间事件。

对于性能，我们可以很容易地减少到仅用户空间收集:

$ 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 中。当我们的程序访问新页面时调用它。正如评论中解释的那样，新页面在允许访问之前被内核清零，因此缓存未命中已经发生在这里。

这会影响您的分析，因为您预期的大部分缓存未命中发生在内核空间中。但是，您无法保证内核实际访问内存的确切情况，因此这可能与您的代码预期的行为有所偏差。

为避免这种情况，请围绕您的数组填充循环构建一个额外的循环。只有内部循环的第一次迭代会产生内核开销。一旦数组中的每一页都被访问，就不应该有任何贡献了。这是我的外部循环重复 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 次，因此您的分析预计会有 1,250,000,000 次缓存未命中。现在已经很接近了。偏差主要来自内核在页面清除期间加载到缓存的第一个循环。

使用 PAPI，可以在计数器开始之前插入一些额外的预热循环，因此结果更符合预期:

$ ./main2 
L3 accesses: 1318699729
L3 misses: 1250684880
L3 miss/access ratio: 0.948423