Кашегринд: Почему так много кешей пропадает?
В настоящее время я изучаю различные утилиты для профилирования и повышения производительности под 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.
Решение
Важно сначала проверить сгенерированный ассемблерный код, потому что именно это будет имитировать 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 может либо значительно переоценить, либо недооценить количество промахов и попаданий.
Другие решения
Я подозреваю, что это происходит потому, что векторный буфер не выровнен по границе строки кэша. Это внезапный скачок кеша пропускает отметку точки, когда мы переходим к следующей строке. Так что предлагаю проверить v.data() значение.