我正在开展一个项目,需要实现一个已被理论证明与缓存友好的算法。简单来说,如果输入为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 = 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
为什么这两个工具之间会有如此大的差异?