Кеш процессора и раскладка данных в C++: где теряются такты

Есть классический эксперимент: два вложенных цикла суммируют элементы квадратной матрицы 4096×4096 типа float. Тело цикла одно и то же, число сложений одинаковое — 16 миллионов. Единственная разница — порядок обхода: по строкам или по столбцам. На типичном x86-64 обход по столбцам оказывается в 5–8 раз медленнее. Компилятор тут ни при чём: ассемблер почти идентичен. Разница целиком в том, как данные ложатся в кеш процессора.

Разберём, откуда берётся этот множитель, что именно происходит на уровне линий кеша, и как расположение структур в памяти меняет производительность горячего кода. Материал — про механику, а не про -O2 против -O3. Замеры приведены с условиями, чтобы их можно было воспроизвести и не принимать на веру.

Почему промах кеша стоит так дорого

Процессор не читает память по одному байту. Он тянет целую линию кеша¹ — на большинстве современных x86-64 это 64 байта. Когда вы обращаетесь к одному float (4 байта), в кеш подтягивается ещё 15 соседних значений. Если следующий доступ попадает в те же 64 байта, он почти бесплатен: данные уже в L1.

Иерархия примерно такая (порядок величины, конкретные цифры зависят от микроархитектуры):

Точные задержки для конкретного процессора смотрите в его технической документации или измеряйте утилитами вроде lmbench. Порядок важнее числа: промах до DRAM стоит примерно в 25–50 раз дороже попадания в L1. Именно этот множитель и вылезает в эксперименте с матрицей.

Разбираем эксперимент с обходом матрицы

Матрица в C++ обычно хранится по строкам (row-major): элемент [i][j] лежит по адресу base + (i * N + j) * sizeof(T). Соседние по j элементы идут подряд в памяти, соседние по i — отстоят на целую строку.

// C++17, g++ 13, -O2
#include <vector>
#include <cstddef>

constexpr std::size_t N = 4096;

// Обход по строкам: доступ подряд, линия кеша используется целиком
double sum_row_major(const std::vector<float>& m) {
    double acc = 0.0;
    for (std::size_t i = 0; i < N; ++i)
        for (std::size_t j = 0; j < N; ++j)
            acc += m[i * N + j];
    return acc;
}

// Обход по столбцам: каждый шаг перепрыгивает на 4096*4=16 КБ вперёд
double sum_col_major(const std::vector<float>& m) {
    double acc = 0.0;
    for (std::size_t j = 0; j < N; ++j)
        for (std::size_t i = 0; i < N; ++i)
            acc += m[i * N + j];
    return acc;
}

В sum_row_major одна подтянутая линия обслуживает 16 подряд идущих float, промах случается раз в 16 обращений. В sum_col_major шаг между обращениями — 16 КБ, каждая линия используется на один элемент из 16, и к моменту возврата к соседнему элементу строки она уже вытеснена из кеша. Практически каждое обращение — промах.

Что покажет замер

Меряйте не std::chrono в наносекундах на глаз, а через повторные прогоны и с прогревом кеша. Минимальный честный бенчмарк:

// компиляция: g++ -O2 -std=c++17 bench.cpp
#include <chrono>
#include <cstdio>
#include <vector>

int main() {
    std::vector<float> m(N * N, 1.0f);
    volatile double sink = 0.0; // не даём оптимизатору выкинуть цикл

    auto bench = [&](auto fn) {
        auto t0 = std::chrono::steady_clock::now();
        sink += fn(m);
        auto t1 = std::chrono::steady_clock::now();
        return std::chrono::duration<double, std::milli>(t1 - t0).count();
    };

    std::printf("row: %.1f ms\n", bench(sum_row_major));
    std::printf("col: %.1f ms\n", bench(sum_col_major));
    return 0;
}

Абсолютные числа зависят от процессора, частоты и объёма L3, поэтому не привожу их как истину — снимите на своём железе. Устойчиво повторяется соотношение: столбцовый обход в разы медленнее строчного при том же N. Чтобы увидеть роль кеша напрямую, снимите perf stat -e cache-misses,cache-references ./bench на Linux — в столбцовом варианте промахов будет на порядок больше.

Число операций одинаковое. Число обращений к памяти одинаковое. Отличается только то, попадают ли обращения в уже загруженную линию кеша — и это меняет время выполнения в разы.

Раскладка структур: паддинг и группировка полей

Второй источник промахов — как поля лежат внутри структуры и как структуры идут в массиве. Компилятор выравнивает поля, из-за чего появляются дыры-паддинг. Классический пример:

// Плохая раскладка: sizeof == 24 из-за выравнивания
struct BadParticle {
    char  type;   // 1 байт + 7 паддинга
    double x;     // 8
    char  flag;   // 1 байт + 7 паддинга
};

// Хорошая раскладка: поля от больших к меньшим, sizeof == 16
struct GoodParticle {
    double x;     // 8
    char  type;   // 1
    char  flag;   // 1 + 6 паддинга в конце
};

Проверить размеры можно прямо в коде: static_assert(sizeof(GoodParticle) == 16);. На массиве в миллион элементов разница в 8 байт на структуру — это 8 МБ лишних данных, которые вытесняют из L3 что-то полезное и добавляют промахи на обходе.

AoS против SoA

Если горячий цикл трогает только одно поле из структуры, массив структур (AoS) заставляет тянуть в кеш и все остальные поля — они едут в той же линии, но не используются. Массив по полям (SoA) кладёт одинаковые поля подряд:

SoA — не всегда выигрыш. Если код обычно работает с объектом целиком (прочитал все поля, обновил, пошёл дальше), AoS быстрее и понятнее. Переходить на SoA стоит только когда профилировщик показывает, что горячий цикл трогает узкое подмножество полей на большом массиве.

Где подход ломается

• False sharing. Два потока пишут в разные переменные, но лежащие в одной линии кеша. Каждая запись инвалидирует линию у соседнего ядра, и производительность падает, хотя логической конкуренции нет. Лечится выравниванием на размер линии: alignas(64) для счётчиков в разных потоках. Отдельная большая тема — здесь только упоминаю.
• Предвыборка (prefetch). Процессор угадывает линейные и простые шаговые паттерны и подтягивает данные заранее. Столбцовый обход с постоянным большим шагом иногда частично спасается аппаратной предвыборкой — поэтому множитель не всегда ровно 16.
• Мелкие данные. Пока весь рабочий набор влезает в L2/L3, разница между раскладками минимальна. Эффекты кеша вылезают на объёмах, превышающих кеш последнего уровня. Оптимизировать раскладку на массиве из сотни элементов бессмысленно.
• Слишком раннее SoA. Переписав AoS в SoA до профилирования, вы получаете уродливый код и, возможно, замедление на путях, где объект читается целиком.

Что мерить и что делать дальше

Не оптимизируйте раскладку по интуиции. Порядок действий:

1. Найдите горячий цикл профилировщиком (perf record, vtune). Оптимизировать раскладку в холодном коде — потерянное время.
2. Снимите cache-misses и cache-references через perf stat. Высокое отношение промахов к обращениям на горячем цикле — сигнал, что виновата память, а не арифметика.
3. Проверьте порядок обхода: доступ должен идти вдоль непрерывной памяти, а не поперёк. Для матриц это означает совпадение порядка циклов с раскладкой хранения.
4. Проверьте sizeof горячих структур и наличие паддинга. Утилита pahole на Linux показывает дыры в структурах явно.
5. SoA и alignas(64) против false sharing применяйте точечно, только после того как замеры указали на проблему.

Дальше стоит почитать про блочный (tiled) обход матриц — он разбивает данные на куски, влезающие в L2, и снимает часть промахов даже при неудобном порядке. И про то, как включённая векторизация меняет требования к выравниванию данных: это уже отдельный разговор.

¹ Линия кеша — минимальный блок данных, который процессор перемещает между уровнями памяти. Обращение к любому байту внутри блока подтягивает весь блок целиком; на большинстве x86-64 его размер 64 байта, узнать точно можно из /sys/devices/system/cpu/cpu0/cache/ на Linux.