CPU cache и локальность данных

CPU читает память через иерархию кэшей. Когда нужные данные уже близко к ядру, доступ обычно существенно дешевле обращения к DRAM; когда их нет — процессор ждёт данные. Поэтому порядок обхода и представление данных влияют на скорость даже при одинаковой Big O.

Зачем это на интервью

Тема показывает, что кандидат понимает разницу между асимптотикой и физической стоимостью памяти. В backend-разработке это помогает объяснить, почему компактный буфер, batch и последовательный обход иногда выигрывают у «удобной» структуры из множества указателей — и почему оптимизацию надо подтверждать профилем.

Минимум для E4

• Объяснять, что кэширует CPU и почему данные загружаются cache line, а не по одному байту.
• Различать temporal и spatial locality.
• Связывать случайный доступ и pointer chasing с cache misses.
• Не называть фиксированную задержку кэша без архитектуры и измерения.

Spatial locality означает использование соседних адресов: последовательный проход []T хорошо использует строку кэша. Temporal locality означает скорое повторное использование тех же данных: маленький рабочий набор имеет шанс оставаться в кэше. Связный список может иметь $O(1)$ переход к следующему элементу, но узлы часто разбросаны по heap; это ухудшает предвыборку и locality по сравнению с массивом.

Углубление для E5/Senior

Рабочий набор — данные, к которым нагрузка активно обращается в окне времени. Когда он не помещается в доступные уровни кэша, промахи и давление на память растут; на многосокетной системе добавляется NUMA: доступ к памяти другого узла может быть дороже локального. Точные размеры строк, уровней и задержки зависят от CPU, поэтому E5 профилирует целевой хост и избегает переносимых «магических чисел».

Выбор layout — trade-off. Array of structs удобен, когда операция использует все поля объекта; struct of arrays уменьшает трафик памяти, если проход читает одно поле многих объектов. Но раздробление данных усложняет API и может ухудшить другой запрос. При конкурентном обновлении соседних полей появляется false sharing: проблема когерентности, а не просто локальности.

Для диагностики сначала подтверждают CPU-bound характер и горячий путь через профиль. Затем сравнивают варианты на одинаковом распределении данных, смотрят elapsed time, allocation rate и, при доступности, hardware counters через perf stat. Счётчики cache misses — контекстный сигнал: их читают вместе с instructions, cycles и нагрузкой, а не как самостоятельный вердикт.

Ключевые понятия

• Cache line — минимальный блок, которым кэш обычно переносит данные между уровнями; размер зависит от архитектуры.
• Cache hit/miss — данные найдены в кэше или потребовалось получить их с более дальнего уровня памяти.
• Spatial locality — обращение к соседним адресам; temporal locality — повторное использование тех же данных вскоре.
• Working set — активно используемый набор данных в заданном интервале работы.
• Pointer chasing — последовательность разыменований указателей; адрес следующего элемента часто неизвестен до загрузки текущего.
• Prefetching — аппаратная или программная попытка заранее подгрузить предсказуемые данные; не гарантирует ускорение произвольного доступа.
• NUMA — архитектура, где стоимость доступа зависит от расположения памяти и CPU.

Типовые вопросы

1. Почему массив часто быстрее связного списка при одинаковом $O(n)$ обходе?
   • Элементы массива обычно лежат компактно, что улучшает spatial locality и предвыборку; узлы списка могут быть разбросаны и требуют зависимых загрузок.
2. Что такое cache line?
   • Блок данных, который кэш перемещает как единицу. Доступ к одному полю может принести в кэш и соседние байты.
3. Всегда ли struct of arrays быстрее array of structs?
   • Нет. SoA выигрывает при обработке подмножества однородных полей, но AoS лучше, когда нужны все поля одной сущности; измеряют конкретный доступ.
4. Почему случайный доступ хуже последовательного?
   • Его труднее предвыбирать, он хуже использует соседние данные и чаще ждёт дальнюю память.
5. Как проверить гипотезу о locality?
   • Сначала построить benchmark одинаковой семантики и данных, затем сравнить время и аллокации; на Linux при возможности дополнить perf stat счётчиками instructions, cycles и cache misses.
6. Решит ли больший кэш любую проблему памяти?
   • Нет. Большой или случайный working set всё равно вытесняет данные; также остаются пропускная способность DRAM, NUMA и синхронизация.

Практика

• Реализуйте суммирование поля для []Item и для списка узлов *Node с одинаковым числом элементов. Готово: тесты подтверждают одинаковую сумму, benchmark использует несколько размеров входа и не включает генерацию данных в измеряемый участок.
• Сравните AoS и SoA для прохода, читающего одно числовое поле. Готово: измерены ns/op, B/op, allocs/op; вывод ограничен измеренной машиной и сценарием.
• На Linux запустите perf stat для обоих вариантов. Готово: сохранены команда и окружение, приведены cycles, instructions и доступные cache-счётчики; отсутствие прав на счётчики отмечено, а не заменено догадкой.

Частые ошибки и ловушки

• Приписывать всем CPU одинаковый размер cache line и одинаковую latency.
• Объяснять любое замедление «кэшем» без CPU-профиля и воспроизводимого сравнения.
• Выбирать linked list как универсально дешёвую структуру из-за $O(1)$ вставки, игнорируя поиск позиции, аллокации и locality.
• Смешивать cache locality с false sharing: первое про полезные данные, второе — про конкурирующие записи и когерентность.
• Оптимизировать layout ценой сложного API, не подтвердив, что этот путь горячий.

Связанные темы

Производительность и память · Big O · False sharing · Аллокации и GC · Виртуальная память

Источники

• Ulrich Drepper, What Every Programmer Should Know About Memory.
• Intel, Intel 64 and IA-32 Architectures Optimization Reference Manual, разделы о памяти и кэшах.
• Brendan Gregg, Systems Performance, главы о CPU и памяти.
• Linux perf-stat manual page и документация Performance Events.
• Go project, документация пакета testing, раздел Benchmarks.