Я работаю над проектом, в котором мы должны реализовать алгоритм, который теоретически доказал свою совместимость с кешем. Проще говоря, если N
- это вход, а B
- это количество элементов, которые передаются между кешем и ОЗУ каждый раз, когда у нас происходит промах кеша, алгоритм потребует O(N/B)
обращений к ОЗУ.
Я хочу показать, что это действительно так на практике. Чтобы лучше понять, как можно измерить различные аппаратные счетчики, связанные с кешем, я решил использовать разные инструменты. Один - Perf, а другой - PAPI библиотеки. К сожалению, чем больше я работаю с этими инструментами, тем меньше понимаю, что именно они делают.
Я использую процессор Intel (R) Core (TM) i5-3470 @ 3,20 ГГц с 8 ГБ ОЗУ, кэш L1 256 КБ, кеш L2 1 МБ, кеш L3 6 МБ. Размер строки кэша составляет 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
Почему такая большая разница между двумя инструментами?