Что значит «код дружелюбен к кэшу» и как это влияет на производительность C++?

Что такое кэш и почему он важен?

Современные процессоры работают на частотах в несколько гигагерц, а оперативная память (RAM) значительно медленнее — задержка доступа к RAM может составлять десятки и сотни наносекунд. Чтобы сгладить эту разницу, процессор использует кэш-память — небольшую, но очень быструю память, расположенную прямо на кристалле процессора. Типичная иерархия:

• L1 кэш — 32–64 КБ, задержка ~1–3 такта
• L2 кэш — 256–512 КБ, задержка ~5–10 тактов
• L3 кэш (общий) — 8–32 МБ, задержка ~30–50 тактов
• RAM — гигабайты, задержка ~100–300 тактов

Когда процессору нужно прочитать данные, он сначала проверяет L1, затем L2, затем L3, и только потом — RAM. Если данные найдены в кэше — это попадание (hit), если нет — промах (miss), и процессор вынужден ждать.

Локальность данных — ключевой принцип

Код считается cache-friendly, когда он использует два типа локальности:

1. Пространственная локальность — если мы обратились к адресу X, то с высокой вероятностью скоро понадобятся соседние адреса X+1, X+2 и т.д. Кэш загружает данные блоками (cache lines) — обычно по 64 байта. Обращение к одному int (4 байта) подтягивает целую строку.
2. Временная локальность — если мы обратились к данным, они скорее всего понадобятся снова в ближайшее время.

Почему обход по строкам быстрее?

В C++ двумерный массив int matrix[1000][1000] хранится в памяти по строкам (row-major order). Это значит, что все элементы первой строки идут подряд: matrix[0][0], matrix[0][1], ..., matrix[0][999], matrix[1][0], ...

Вариант 1 (по строкам):

for (int i = 0; i < 1000; ++i)
    for (int j = 0; j < 1000; ++j)
        sum += matrix[i][j];

Доступ последовательный: matrix[0][0] → matrix[0][1] → ... Каждое обращение к новому элементу — это, скорее всего, попадание в кэш, потому что соседние элементы уже загружены. На одну загрузку строки кэша (64 байта) мы получаем 16 int'ов. Коэффициент использования — почти 100%.

Вариант 2 (по столбцам):

for (int j = 0; j < 1000; ++j)
    for (int i = 0; i < 1000; ++i)
        sum += matrix[i][j];

Доступ прыгает: matrix[0][0] → matrix[1][0] → matrix[2][0] → ... Между matrix[0][0] и matrix[1][0] расстояние 1000 × 4 = 4000 байт! Каждый int из столбца находится в разных строках кэша. Процессор загружает строку кэша, использует только один int из 16, а остальные 15 игнорируются. При следующем обращении — снова промах. Это cache thrashing (пробуксовка кэша).

Как писать cache-friendly код?

• Следуйте порядку хранения данных. Для C/C++ — обходите многомерные массивы по последнему индексу во внутреннем цикле.
• Используйте структуры с учётом доступа. Если вы часто читаете поле x из массива структур, рассмотрите структуру массивов (SoA) вместо массива структур (AoS).
• Избегайте случайного доступа к большим данным. Связанные списки (std::list) — антипаттерн cache-friendly, т.к. узлы разбросаны по памяти.
• Работайте с блоками (tiling). Для матриц больше кэша разбивайте их на подблоки, которые помещаются в L1/L2.

Пример: структура массивов vs массив структур

// AoS — плохо для последовательного доступа к одному полю
struct Particle {
    float x, y, z, vx, vy, vz;
};
Particle particles[100000];

// SoA — хорошо
struct Particles {
    float x[100000];
    float y[100000];
    float z[100000];
    float vx[100000];
    float vy[100000];
    float vz[100000];
};

При обновлении только x в AoS мы используем 4 из 24 байт каждой структуры (если float — 4 байта). В SoA все x лежат подряд — идеальная пространственная локальность.

Вывод: cache-friendly код — это код, который максимально использует локальность данных, минимизируя промахи кэша. Понимание этого принципа даёт прирост производительности в разы, особенно на больших объёмах данных.

// Скомпилируйте с -O2 и запустите через cachegrind
// Результат для row-major:   D1mr (L1 read misses) ~ 0.1%
// Результат для column-major: D1mr ~ 99.9%