Кашегринд: Почему так много кешей пропадает? - PullRequest
Новая
       19

Кашегринд: Почему так много кешей пропадает?

0 голосов
/ 09 ноября 2018

В настоящее время я изучаю различные утилиты для профилирования и повышения производительности под Linux, в частности, valgrind / cachegrind.

У меня есть следующая игрушка: 

#include <iostream>
#include <vector>

int
main() {
    const unsigned int COUNT = 1000000;

    std::vector<double> v;

    for(int i=0;i<COUNT;i++) {
        v.push_back(i);
    }

    double counter = 0;
    for(int i=0;i<COUNT;i+=8) {
        counter += v[i+0];
        counter += v[i+1];
        counter += v[i+2];
        counter += v[i+3];
        counter += v[i+4];
        counter += v[i+5];
        counter += v[i+6];
        counter += v[i+7];
    }

    std::cout << counter << std::endl;
}

Компиляция этой программы с g++ -O2 -g main.cpp и запуск valgrind --tool=cachegrind ./a.out, тогда cg_annotate cachegrind.out.31694 --auto=yes дает следующий результат: 

    --------------------------------------------------------------------------------
-- Auto-annotated source: /home/andrej/Data/projects/pokusy/dod.cpp
--------------------------------------------------------------------------------
       Ir I1mr ILmr        Dr    D1mr    DLmr        Dw D1mw DLmw 

        .    .    .         .       .       .         .    .    .  #include <iostream>
        .    .    .         .       .       .         .    .    .  #include <vector>
        .    .    .         .       .       .         .    .    .  
        .    .    .         .       .       .         .    .    .  int
        7    1    1         1       0       0         4    0    0  main() {
        .    .    .         .       .       .         .    .    .      const unsigned int COUNT = 1000000;
        .    .    .         .       .       .         .    .    .  
        .    .    .         .       .       .         .    .    .      std::vector<double> v;
        .    .    .         .       .       .         .    .    .  
5,000,000    0    0 1,999,999       0       0         0    0    0      for(int i=0;i<COUNT;i++) {
3,000,000    0    0         0       0       0 1,000,000    0    0          v.push_back(i);
        .    .    .         .       .       .         .    .    .      }
        .    .    .         .       .       .         .    .    .  
        3    0    0         0       0       0         0    0    0      double counter = 0;
  250,000    0    0         0       0       0         0    0    0      for(int i=0;i<COUNT;i+=8) {
  250,000    0    0   125,000       1       1         0    0    0          counter += v[i+0];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+1];
  125,000    1    1   125,000       0       0         0    0    0          counter += v[i+2];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+3];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+4];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+5];
  125,000    0    0   125,000 125,000 125,000         0    0    0          counter += v[i+6];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+7];
        .    .    .         .       .       .         .    .    .      }
        .    .    .         .       .       .         .    .    .  
        .    .    .         .       .       .         .    .    .      std::cout << counter << std::endl;
       11    0    0         6       1       1         0    0    0  }

Что меня беспокоит, так это строка: 

125,000    0    0   125,000 125,000 125,000         0    0    0          counter += v[i+6];

Почему в этой строке так много промахов кэша? Данные находятся в непрерывной памяти, каждую итерацию я читаю по 64 байта данных (при условии, что строка кэша имеет длину 64 байта).

Я запускаю эту программу на Ubuntu Linux 18.04.1, ядро ​​4.19, g ++ 7.3.0. Компьютер AMD 2400G.

Ответы [ 2 ]

0 голосов
/ 09 ноября 2018

Важно сначала проверить сгенерированный ассемблерный код, потому что именно это будет имитировать cachegrind.Цикл, который вас интересует, компилируется в следующий код: 

.L28:
addsd xmm0, QWORD PTR [rax]
add rax, 64
addsd xmm0, QWORD PTR [rax-56]
addsd xmm0, QWORD PTR [rax-48]
addsd xmm0, QWORD PTR [rax-40]
addsd xmm0, QWORD PTR [rax-32]
addsd xmm0, QWORD PTR [rax-24]
addsd xmm0, QWORD PTR [rax-16]
addsd xmm0, QWORD PTR [rax-8]
cmp rdx, rax
jne .L28

На каждую итерацию имеется 8 обращений к чтению, каждый из которых имеет размер 8 байт.В C ++ гарантируется, что каждый элемент выровнен по 8 байтов, но за одну итерацию можно получить доступ к двум строкам кэша в зависимости от адреса массива вектора v.cachegrind использует динамические двоичные инструменты для получения адреса каждого доступа к памяти и применяет свою модель иерархии кеша, чтобы определить, является ли доступ удачным или нет на каждом уровне иерархии (хотя он поддерживает только L1 и LLC).В данном конкретном случае случается, что новая строка кэша доступна на counter += v[i+6];.Затем следующие 7 обращений будут к той же 64-байтовой строке кэша.Строка исходного кода, к которой осуществляется доступ к новой строке кэша, не влияет на общее количество ошибок, сообщенных cachegrind.Он просто скажет вам, что другая строка исходного кода вызывает столько пропусков.

Обратите внимание, что cachegrind имитирует очень упрощенную иерархию кэша, основанную на машине, на которой он работает.В данном случае это AMD 2400G, которая имеет размер строки 64 байта на всех уровнях кэша.Кроме того, размер L3 составляет 4 МБ.Но поскольку общий размер массива составляет 8 МБ, то следующий цикл: 

for(int i=0;i<COUNT;i++) {
    v.push_back(i);
}

оставит только вторую половину массива в LLC.Теперь в самой первой итерации второго цикла, в котором вычисляется counter, первая доступная строка не будет в L1 или LLC.Это объясняет 1 в D1mr и DLmr столбцах.Затем в counter += v[i+6]; осуществляется доступ к другой строке, что также является пропуском в обоих уровнях кэша.Тем не менее, в этом случае все следующие 7 обращений будут хитами.На данный момент, только доступ из counter += v[i+6]; будет пропущен, и существует 125 000 таких доступов (1 миллион / 8).

Обратите внимание, что cachegrind - это всего лишь симулятор, и то, что на самом деле происходит на реальном процессоре, может быть искорее всего, очень разные.Например, на моем процессоре Haswell при использовании perf общее количество пропущенных L1D по всему коду (оба цикла) составляет всего 65 796.Таким образом, cachegrind может либо значительно переоценить, либо недооценить количество промахов и попаданий.

0 голосов
/ 09 ноября 2018

Я подозреваю, что это происходит потому, что векторный буфер не выровнен по границе строки кэша. Это внезапный скачок кеша пропускает отметку точки, когда мы переходим к следующей строке. Поэтому я предлагаю проверить v.data() значение.

...