Кэш-френдли код на C++: что это и почему это важно для скорости

Ваш код работает медленно, хотя алгоритм идеален? Возможно, он не «дружит» с кэшем

Вы когда-нибудь писали код на C++, который в теории должен работать молниеносно, а на практике тормозит? Или замечали, что обход двумерного массива по строкам и по столбцам дает разную скорость, хотя сложность алгоритма одинаковая? Если да — вы столкнулись с cache-friendly (кэш-френдли) и его противоположностью — cache-unfriendly кодом.

Сегодня разберем, что это значит на уровне железа, почему кэш — это не просто «еще одна память», а ключ к производительности, и как писать код, который процессор будет «любить». Без сложных абстракций — только C++ и понятные примеры.

Почему процессор не может просто читать из оперативной памяти?

Скорость процессора выросла в тысячи раз за последние десятилетия, а скорость оперативной памяти (DRAM) — всего в десятки. Представьте себе гонщика Формулы-1 (процессор), который вынужден каждую секунду останавливаться, чтобы получить топливо (данные) из грузовика, едущего со скоростью 30 км/ч (оперативная память). Грустно и медленно.

Решение — кэш процессора: маленькая, но очень быстрая память, встроенная прямо в чип. Она хранит копии часто используемых данных. Когда процессору нужны данные, он сначала проверяет кэш (L1 — самый быстрый, затем L2, L3). Только если данных там нет (cache miss, кэш-промах), он идет в медленную оперативную память.

Вот примерные задержки (в циклах процессора):

• L1 кэш: ~3-5 циклов
• L2 кэш: ~10-20 циклов
• L3 кэш: ~30-50 циклов
• Оперативная память: ~100-300 циклов

Разница между L1 и RAM — в 50-100 раз. Именно поэтому cache-friendly код на C++ может быть в разы быстрее «недружественного» аналога.

Принцип локальности: как кэш решает, что сохранить

Кэш не копирует один байт — он работает блоками (cache lines), обычно по 64 байта. Когда вы читаете одну переменную, процессор загружает весь блок, содержащий эту переменную. И делает ставку на два принципа:

• Пространственная локальность (Spatial locality): если вы читаете элемент массива arr[i], скорее всего, вам скоро понадобится arr[i+1].
• Временная локальность (Temporal locality): если вы прочитали данные сейчас, вероятно, вы обратитесь к ним снова в ближайшее время.

Cache-friendly код — это код, который максимально использует эти принципы. Давайте посмотрим, как это выглядит на практике.

Пример 1: Обход двумерного массива — классика жанра

Cache-unfriendly (плохой код)

const int SIZE = 1024;
int matrix[SIZE][SIZE];

// Обход по столбцам (column-major)
for (int j = 0; j < SIZE; ++j) {
    for (int i = 0; i < SIZE; ++i) {
        matrix[i][j] = i + j;
    }
}

В C++ массивы хранятся в row-major order (по строкам). То есть элементы строки matrix[0][0], matrix[0][1], matrix[0][2]... лежат в памяти последовательно. Внешний цикл по j (столбцам) заставляет процессор прыгать через всю строку при каждом шаге — каждый доступ к matrix[i][j] — это, скорее всего, cache miss. Процессор тратит время на подгрузку новых блоков, а предыдущие данные из кэша вытесняются.

Cache-friendly (хороший код)

// Обход по строкам (row-major)
for (int i = 0; i < SIZE; ++i) {
    for (int j = 0; j < SIZE; ++j) {
        matrix[i][j] = i + j;
    }
}

Теперь мы идем по памяти последовательно. Как только мы загрузили блок с matrix[0][0], следующие 15 элементов (при 4-байтовом int) уже в кэше! Это дает прирост скорости в 5-10 раз на больших матрицах. Вот что значит быть cache-friendly на C++.

Пример 2: Структуры данных и кэш

Плохой пример: массив указателей (AoS vs SoA)

struct Particle {
    float x, y, z;  // координаты
    float vx, vy, vz; // скорость
    float mass;
    int type;
};

std::vector<Particle*> particles; // массив указателей

Каждый Particle* может указывать на объект в произвольном месте памяти. Когда вы итерируетесь по массиву, процессор прыгает по разным адресам — низкая пространственная локальность. Каждый доступ — потенциальный cache miss.

Хороший пример: массив структур (SoA — Structure of Arrays)

struct Particles {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> mass;
    std::vector<int> type;
};

Particles particles;
// Обновляем только координаты — все данные лежат подряд
for (size_t i = 0; i < particles.x.size(); ++i) {
    particles.x[i] += particles.vx[i] * dt;
    particles.y[i] += particles.vy[i] * dt;
    particles.z[i] += particles.vz[i] * dt;
}

Теперь все x лежат в одном непрерывном векторе, все y — в другом. Если вам нужно обновить только координаты, кэш загружает только нужные данные, а не всю структуру целиком. Это особенно важно в игровых движках и симуляциях частиц, где оптимизация C++ под кэш может ускорить код на порядок.

Пример 3: Небольшие структуры и false sharing

Проблема: False sharing в многопоточном коде

struct alignas(64) ThreadData {
    int counter; // всего 4 байта
    // padding до 64 байт, чтобы каждый экземпляр был в своей cache line
};

ThreadData data[4];
// Потоки обновляют свои data[i].counter

Если два ThreadData находятся в одной cache line (64 байта), и два потока одновременно пишут в свои counter, процессор вынужден синхронизировать эту линию между ядрами. Это false sharing — кэш-промахи из-за ложного разделения, хотя данные