Суть Читаешь реальные сниппеты — strided-цикл, AoS-структуру, padded-счётчик и pointer chain, предсказываешь поведение кэша и pipeline, выбираешь фикс с наибольшим рычагом.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на senior-высоте — в орбите
◷ 14 min
Проблемы кэша диагностируют в коде и профиле, а не в big-O. Прочитай каждый сниппет, предскажи, куда реально уходит wall-clock time, и выбери фикс, к которому senior-инженер тянется первым.
Цель
Отработай петлю, которую ты гоняешь в каждом инциденте производительности: прочитал горячий путь, нашёл дефект раскладки или паттерна доступа, который подтвердит профайлер, и выбрал фикс с наибольшим рычагом до SIMD-интринсиков и флагов компилятора.
Сниппет 1 — strided-сумма
double sum = 0;// матрица row-major: matrix[i][j] по смещению (i*N + j)*8 байтfor (int j = 0; j < N; j++) // внешний: индекс столбца for (int i = 0; i < N; i++) // внутренний: индекс строки sum += matrix[i][j];
Викторина
Completed
На матрице 10 000×10 000 double, почему этот цикл в ~9 раз медленнее, чем при перестановке двух циклов, и какой фикс?
Heads-up Floating-point add почти бесплатен; CPU простаивает в ожидании памяти. SIMD всё равно не загрузит strided-столбец эффективно — сначала исправь порядок доступа.
Heads-up Они обходят те же элементы, но в другом порядке памяти. Column-порядок на row-major хранении промахивается мимо кэша практически на каждом доступе; разрыв по wall-clock ~9x.
Heads-up Выравнивание не меняет шаг в 80 000 байт. Дефект — итерация поперёк раскладки хранения; переупорядочь циклы или сделай tiling матрицы.
Сниппет 2 — раскладка структуры
struct Particle { float x, y, z, vx, vy, vz; char name[40]; }; // 64 байтаParticle parts[1_000_000];float total_x = 0;for (int i = 0; i < 1_000_000; i++) total_x += parts[i].x; // читается только x
Викторина
Completed
Цикл читает только `x`, но профиль показывает высокий L3 miss rate. В чём дефект раскладки и фикс?
Heads-up Корень не в размере, а в потраченной bandwidth. SoA сжимает объём затронутых байт ~16x для этого цикла, поэтому гораздо больше данных остаётся резидентным в кэше, и prefetcher их стримит.
Heads-up Prefetch чуть помогает, но ты всё равно тянул бы 64 байта на элемент, чтобы использовать 4. Структурный фикс — SoA, который убирает потраченные 60 байт на линию.
Heads-up Она уже 64 байта без зазоров; packing ничего не меняет. Потери — это холодные поля (`y…name`), соседствующие с горячим, что чинит только struct-splitting/SoA.
Сниппет 3 — padded-счётчик
type paddedCounter struct { value uint64 _ [56]byte // паддинг до полной 64-байтной cache line}var counters [16]paddedCounterfunc worker(idx int) { // одна горутина на idx atomic.AddUint64(&counters[idx].value, 1)}
Викторина
Completed
Что покупает паддинг `[56]byte` и какой сбой он предотвращает?
Heads-up Атомарная инструкция не меняется. Паддинг убирает межъядерный трафик когерентности (инвалидации линий), а не стоимость отдельной инструкции.
Heads-up atomic.AddUint64 уже делает инкремент гонко-безопасным. Паддинг адресует проблему производительности (false sharing), а не корректности.
Heads-up Он делает обратное — раздувает каждый счётчик с 8 до 64 байт. Размен — память в обмен на устранение cache-line contention.
Сниппет 4 — pointer chain
// idx[] хранит следующий индекс для посещения; следование за ним data-dependentint i = start;for (int step = 0; step < N; step++) { process(data[i]); i = idx[i]; // следующий адрес зависит от результата этой загрузки}
Викторина
Completed
Даже когда `data` и `idx` влезают в L2, это работает намного медленнее последовательного сканирования тех же массивов. Почему и какой структурный фикс?
Heads-up Они влезают в L2 — с ёмкостью всё хорошо. Стоимость — цепочка зависимостей, сериализующая промахи; это проблема паттерна доступа, а не ёмкости.
Heads-up Простои — на dependent-загрузках `idx[i]`. Даже тривиальный process() оставляет цикл memory-latency-bound, потому что каждый шаг ждёт предыдущей загрузки.
Heads-up Рекурсия не разрывает зависимость по данным. Нужно материализовать порядок в независимые, последовательные доступы, чтобы MLP и prefetcher включились.
Итог
Каждый сниппет здесь — дефект в константном множителе, которого big-O не видит: column-порядок цикла на row-major хранении промахивается на каждом шаге (переупорядочь или tiling); AoS-структура тянет холодные поля в линию для цикла по одному полю (раздели на SoA); непадженные счётчики на поток пинг-понгуют cache lines (паддинг до 64 байт); а dependent pointer chain сериализует промахи и ломает и MLP, и prefetcher (предвычисли contiguous порядок). Читай паттерн доступа, назови причину, исправь раскладку — затем перепрофилируй для подтверждения.