为什么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字节.我猜这必须是块的大小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 = 125000L3缓存未命中.

没有优化(否-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未命中.在Intel 64和IA-32架构开发人员手册中,这些事件描述为:

2EH 4FH LONGEST_LAT_CACHE.REFERENCE此事件计算源自引用最后一级缓存中的缓存行的核心的请求.

2EH 41H LONGEST_LAT_CACHE.MISS此事件计算对最后一级缓存的引用的每个缓存未命中条件.

这似乎没问题.所以问题出在其他地方.

这是我的再现数字,只是我将数组长度增加了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 report后perf record -e cache-references ./main1:

  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,我们只能轻松减少到用户空间集合:

$ 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.当我们的程序访问新页面时调用此方法.正如评论中所解释的,在允许访问之前,内核将新页面归零,因此缓存未命中已在此处发生.

这与您的分析混淆,因为您期望在内核空间中发生的缓存未命中的很大一部分.但是,您无法保证内核实际访问内存的确切情况,因此可能会偏离代码所期望的行为.

为了避免这种情况,在数组填充周围建立一个额外的循环.只有内部循环的第一次迭代才会产生内核开销.一旦访问了数组中的每个页面,就不会有任何贡献.这是我重复外循环的结果:

$ 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