Производительность

Иерархия памяти: почему расстояние важнее числа операций

Суть L1 cache в 100 раз быстрее RAM. Array в 17 раз быстрее linked list при том же O(N). Это не детали — это фундамент, объясняющий, почему ''''медленный'''' алгоритм часто бьёт ''''быстрый'''' в production.

Высота — путь к senior

НольJuniorMiddleSenior

Ты на junior-высоте — поверхность

◷ 12 min

Два алгоритма, оба O(N). Один занимает 2 мс, другой — 35 мс. Код разный, но число операций идентично. Разница — только в том, где сидят данные.

Иерархия памяти

Современный CPU — не uniform memory machine. Данные живут на разных уровнях с кардинально разной latency:

Уровень	Размер	Latency	Циклы
L1 cache (per core)	32–64 KB	~1 нс	3–5
L2 cache (per core)	256 KB – 2 MB	~3 нс	10–15
L3 cache (shared)	4–64 MB	~10 нс	30–50
RAM (DDR5)	ГБ	~70–100 нс	200–300
SSD (NVMe)	ТБ	~100 мкс	~500 000

Gap между L1 и RAM — примерно 100x по latency. Это и есть рычаг: один cache miss стоит больше, чем 30 floating-point операций в регистрах.

Метафора: библиотека

Думай о памяти как о библиотеке:

L1 — 10 книг на твоём столе (мгновенный доступ).
L2 — 100 книг на ближайшей полке (несколько шагов).
L3 — 10 000 книг в той же комнате (поход по комнате).
RAM — 10 млн книг на складе в двух кварталах (едешь на склад).

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

Что такое cache line

Data не двигается между RAM и cache по одному байту. Единица transfer — cache line (64 байта на x86 и большинстве ARM).

Читаешь байт на адресе X — CPU грузит байты X до X+63 в cache, все сразу. Поэтому sequential access так быстр: первый read грузит 64 байта, следующие 7 reads той же строки — бесплатные L1-хиты.

Array vs linked list: канонический случай

Итерация std::vector из 1 млн int — около 2 мс.
Итерация std::list из 1 млн int — около 35 мс.

Тот же O(N). Разница в 17x.

Почему? Vector — одна contiguous аллокация. Prefetcher грузит L1 заранее. List nodes аллоцированы отдельно на heap; каждый .next — скорее всего cache miss; каждый шаг платит ~100 нс.

Умножи 1 млн раз: 100 нс × 1М = 100 мс для linked list vs 1 нс × 1М = 1 мс для array. Соотношение 17x — из-за частичных hits в cache у linked list, но порядок величины реальный.

Hardware prefetcher

Когда CPU видит 2–3 consecutive cache misses в одном направлении, он активирует hardware prefetcher — загружает следующие до 16 cache lines вперёд, пока CPU обрабатывает текущую.

Sequential iteration: следующая cache line уже в L1 к моменту, когда она нужна. Pointer chasing (linked list, tree): каждый следующий адрес зависит от предыдущего load — prefetcher не может предсказать, куда прыгнет следующий pointer.

Почему это работает

Big-O assume-ит, что каждая операция занимает constant time. На современном hardware — wild approximation. Cache hit стоит 1–15 циклов; cache miss стоит 100–300 циклов. Две операции с тем же «instruction count» могут различаться в 100x по wall-clock time. Big-O остаётся полезным для предсказания, как cost растёт с N — но constant factor, который он игнорирует, и есть разница между «влезает в L1» и «миссит каждую line».

Закончи аналогию

Заполни пропуск: когда memory accesses идут рядом друг с другом, hardware _______ CPU предсказывает и pre-load-ит следующие байты, делая доступ бесплатным.

Викторина

Почему O(N) array iteration может бить O(log N) tree traversal в реальных бенчмарках?

Викторина

Что такое cache line?

Расставь шаги по порядку

Поставь уровни памяти, к которым CPU обращается, от самого быстрого к самому медленному:

1 Register (внутри CPU core)
2 L1 cache (per core, ~1 нс)
3 L2 cache (per core, ~3 нс)
4 L3 cache (shared, ~10 нс)
5 Main memory / RAM (~70–100 нс)
6 SSD (~100 мкс)
7 Network или disk seek (~10 мс)

Вспомните перед уходом

01
В одном предложении: почему итерация linked list из 1 млн узлов в 17 раз медленнее array из 1 млн чисел, когда оба O(N)?

Итог

Современный CPU имеет многоуровневую иерархию памяти: L1 (~1 нс, 3–5 циклов) → L2 (~3 нс) → L3 (~10 нс) → RAM (~70–100 нс, 200–300 циклов). Gap между L1 и RAM — 100x по latency. Data двигается cache lines по 64 байта: один read грузит 64 байта, следующие 7 reads той же line — бесплатные hits. Sequential access кормит hardware prefetcher — он загружает следующие lines заранее. Pointer chasing defeat-ит prefetcher — каждый следующий адрес зависит от предыдущего результата. Array iteration бьёт linked list iteration в 17x при том же O(N) именно по этой причине.

Связанные уроки

открывает

углубляется в

встречается в159

Продолжить восхождение ↑Row-major vs column-major: порядок доступа и разрыв в 9x