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

Предпосылки: процессор (конвейер, суперскалярность, внеочерёдное исполнение, IPC, ядро); хеш-таблица (хеш-функция, коллизия, бакет).

← Процессор | Устройство кеша | Когерентность →

Запустим наивный эксперимент. Программа выделяет массив на 10 миллионов чисел и читает его двумя способами: сначала подряд, от нулевого элемента к последнему, затем в случайном порядке — перемешав индексы. Количество обращений то же, данные те же, процессор тот же. Последовательный проход занимает около 10 миллисекунд, случайный — полсекунды. Разница в 30–50 раз.

Наивная модель говорит: «данные просто лежат в памяти, процессор к ним обращается». Если все обращения одинаковы, откуда такой разрыв? Первое объяснение, которое приходит в голову, — «кеш». Но кеш появляется как слово, за которым ещё не видно механизма: какой кеш, почему он быстрее памяти, почему он реагирует на порядок обращений. Чтобы увидеть механизм, придётся восстановить, что стоит между процессором и RAM.

Пять звеньев, на которых держится объяснение: физика памяти — почему быстрая и объёмная RAM в одном чипе невозможна; иерархия уровней — как регистры, L1/L2/L3 и RAM образуют лесенку из разных компромиссов; локальность — что реальные программы обращаются не случайно, и именно это делает маленький быстрый слой полезным; кеш-линия — почему память перемещается блоками по 64 байта, а не по одному байту; три типа промахов — какие ошибки попадают читателю в наблюдаемое замедление, и как они связаны с порядком обхода. Разрыв в 30–50 раз между последовательным и случайным проходом — следствие взаимодействия именно этих пяти.

Почему быстрая RAM физически невозможна

Конвейер и суперскалярное выполнение разгоняют процессор до 2–4 инструкций за такт. Эта скорость достижима, только если данные уже лежат в регистрах. Обращение к оперативной памяти (RAM, Random Access Memory — память произвольного доступа) занимает порядка 60–100 нс, а один такт процессора при частоте 3 ГГц — 0.33 нс. Это ~200–300 тактов простоя конвейера на каждом промахе: все стадии стоят и ждут, пока данные придут из RAM.

Очевидное решение — сделать саму RAM быстрее. Почему так не делают? У памяти два конкурирующих параметра: скорость (latency — задержка доступа) и объём (capacity — ёмкость). Физика не позволяет получить оба одновременно.

SRAM (Static RAM — статическая память) хранит бит в схеме, которая сама удерживает состояние, и поэтому быстрая. Цена — площадь на кристалле: на чип помещаются только десятки мегабайт.

DRAM (Dynamic RAM — динамическая память) хранит бит через заряд конденсатора. Заряд утекает, контроллер памяти постоянно его восстанавливает — и это занимает время. Плюс: один бит занимает минимум площади, на модуль помещаются гигабайты. Минус: задержка на порядок выше, чем у SRAM. Конкретные тайминги и арифметика — в оперативной памяти.

Стоимость тоже отличается на порядки. SRAM, из которой состоит кеш процессора, обходится примерно в 1000–3000 раз дороже DRAM на единицу объёма. Сделать 128 ГБ из SRAM — это кристалл площадью в несколько квадратных метров. Физически невозможно.

Между этими полюсами и зажата архитектура: нужна память со скоростью SRAM и объёмом DRAM. Единственный выход — многоуровневая система, где маленький и быстрый буфер из SRAM перехватывает большинство обращений, а медленная ёмкая DRAM обслуживает остальные. Этот буфер называется кеш (cache, буквально «тайник, запас»). Кеш из быстрой статической памяти перехватывает 95–99% обращений, и до медленной RAM доходят единицы процентов.

Иерархия: от регистров до оперативной памяти

Современный процессор организует память слоями. Каждый следующий слой больше по объёму, но медленнее по доступу.

              Объём         Задержка       Где / тип памяти
            -----------------------------------------------
Регистры      ~128 Б        ~0.25 нс       в ядре CPU
L1 кеш       32–64 КБ       ~1 нс          SRAM, в ядре
L2 кеш      256 КБ – 1 МБ   4–7 нс         SRAM, в ядре
L3 кеш       8–64 МБ        10–30 нс       SRAM, общий
RAM          8–128 ГБ       60–80 нс       DRAM, отдельные модули

Числа зависят от конкретного процессора, но порядок величин устойчив уже двадцать лет. У Intel Core i7-12700 (2022): L1 на ядро = 48 КБ, L2 на ядро = 1.25 МБ, L3 общий = 25 МБ. У Apple M2 (2022): L1 на ядро = 128 КБ, L2 общий = 16 МБ. У AMD EPYC 9654 (2022): L3 = 384 МБ, распределённый по чиплетам.

L1 и L2 — per-core (у каждого ядра свой), L3 — общий (shared) между всеми ядрами. Это пригодится в когерентности, где общие данные становятся источником трения.

Каждый слой перехватывает обращения к следующему. Когда CPU запрашивает адрес, запрос идёт сначала в L1. Если данные там — hit (попадание), задержка ~1 нс. Если нет — miss (промах), запрос уходит в L2 (+4–7 нс). Промах L2 — в L3 (+10–30 нс). Промах L3 — в RAM (+60–80 нс). Задержки складываются: промах по всем уровням стоит ~80–120 нс суммарно.

CPU запрашивает адрес 0x7FFF00012340
           |
           v
       [ L1 кеш ]  -- hit? --> данные за ~1 нс
           |
         miss (~4 нс штраф)
           |
           v
       [ L2 кеш ]  -- hit? --> данные за ~5 нс суммарно
           |
         miss (~10 нс штраф)
           |
           v
       [ L3 кеш ]  -- hit? --> данные за ~15 нс суммарно
           |
         miss (~70 нс штраф)
           |
           v
       [  RAM   ]  ----------> данные за ~80–120 нс суммарно

Механизм работает, потому что промахи редки. У типичного кода hit rate (доля попаданий) L1 держится на уровне 95–97%, у L2 — 80–95%. Даже если L3 перехватывает всего 70–80% оставшихся запросов, до RAM доходит 1–5% обращений. Средняя задержка для кода, где обращения концентрируются вокруг недавних и соседних адресов, — порядка 2–4 нс вместо 60–80 нс.

Но почему обращения концентрируются? Кеш полезен только тогда, когда программа приходит туда же повторно — иначе ничего перехватывать не получится.

Локальность данных: почему кеш вообще помогает

Программа обращается к памяти не случайно. За этим порядком стоят два устойчивых паттерна, которые в паре дают кешу шанс.

Временная локальность (temporal locality): если программа обратилась к адресу, она скорее всего обратится к нему снова в ближайшее время. Счётчик цикла i читается и пишется на каждой итерации — одна загрузка i в L1 обслуживает все тысячи обращений.

Пространственная локальность (spatial locality): если программа обратилась к адресу N, она скорее всего обратится к адресам N+1, N+2, N+3. Массив из 10 миллионов int32 (40 МБ) обходится поэлементно, элементы лежат в памяти подряд. Обращение к arr[0] подтягивает в кеш заодно arr[1]…arr[15], потому что кеш загружает данные не побайтно, а блоками.

Рассмотрим типичный цикл:

struct Point { float x, y, z; int flags; };  // 16 байт
struct Point points[1000000];                 // ~16 МБ
 
float sum = 0;
for (int i = 0; i < 1000000; i++)
    sum += points[i].x;                       // читаем только x

Временная локальность: sum и i живут в регистрах, обращений к памяти за ними нет. Пространственная локальность: элементы points лежат подряд, и каждая загрузка из памяти приносит сразу несколько соседних структур. Обе работают в паре — счётчик переиспользуется повторно, массив обходится по соседним адресам.

Локальность — не универсальное свойство программ, а свойство конкретного паттерна доступа. Матричное перемножение в наивном виде локальность ломает: внешний цикл перескакивает по столбцам, а столбцы в памяти разбросаны. Обход связного списка через указатели — каждый следующий узел лежит по случайному адресу. Поэтому два алгоритма одинаковой асимптотической сложности могут отличаться на порядки — не из-за числа операций, а из-за того, что один использует локальность, а другой — нет. Практические следствия этого (cache-aware layout, tiling, AoS vs SoA) разбираются отдельно.

Кеш-линия: минимальная единица обмена

Кеш опирается на пространственную локальность операционно: он не умеет загружать один байт или одно четырёхбайтовое слово. Минимальная единица, которую кеш читает из памяти и хранит у себя, — кеш-линия (cache line). На современных x86-64 и большинстве ARM размер кеш-линии — 64 байта. Проверить можно так:

getconf LEVEL1_DCACHE_LINESIZE    # выведет 64

Почему именно 64 байта? Это компромисс между тремя силами.

Слишком маленькая линия (16 байт) загружала бы только запрошенный элемент и ближайших соседей. Пространственная локальность работала бы слабо: для обхода массива int32 (4 байта) каждые 4 элемента вызывали бы новый запрос в память.

Слишком большая линия (256 байт) загружала бы много данных за раз. Первая цена — время: при пропускной способности соединения между L1 и L2 порядка 64 байт за такт, загрузка 256 байт занимает 4 такта вместо 1. Вторая — впустую потраченный объём: если программа обращается к одному int32 и больше не трогает окрестность, остальные 252 байта загружены зря, а из кеша вытеснена потенциально полезная линия. Третья — когерентность: при записи в любой байт линии нужно инвалидировать всю линию на других ядрах; чем больше линия, тем чаще возникает ложный конфликт (false sharing).

64 байта — точка баланса, найденная эмпирически и устоявшаяся с середины 2000-х: хватает для 16 элементов int32 или 8 элементов double, соединение не перегружается, false sharing терпимый.

Эффект кеш-линии легко наблюдать. Если обходить массив с шагом (stride — расстояние между обращениями), читая каждый N-й элемент, производительность зависит от соотношения шага и размера линии:

Шаг        Полезных элементов   Промахов на         Эффект
           в линии (64 Б)       16 обращений
---------------------------------------------------------------
4 Б        16 из 16             1                    вся линия полезна
64 Б       1 из 16              16                   каждое обращение — новая линия

При шаге 64 пропускная способность падает примерно в 16 раз по сравнению с шагом 4. Одна и та же программа обходит одинаковое число байт, но получает в 16 раз больше промахов.

Последовательный vs случайный обход: 30–50 раз

Вернёмся к исходному эксперименту. Массив из 10 миллионов int32 (40 МБ) не помещается в L3 (типичный L3 — 8–32 МБ), поэтому обход неизбежно нагружает RAM.

Последовательный обход (arr[0], arr[1], arr[2], …). Первое обращение к arr[0] промахивается по кешу и загружает линию с arr[0]…arr[15] (64 байта = 16 элементов по 4 байта). Следующие 15 обращений — попадания. Один промах на 16 обращений. Процессор, кроме того, замечает последовательный паттерн и заранее подтягивает следующие линии (аппаратная предвыборка, hardware prefetch; как она устроена — в устройстве кеша). Задержка RAM почти полностью скрыта. Итог: 5–10 мс на весь массив, пропускная способность 4–8 ГБ/с.

Случайный обход (в перемешанном порядке: arr[7392841], arr[284], arr[9104822], …). Каждое обращение — к случайному адресу. Вероятность, что нужная линия уже в кеше, мизерная (массив 40 МБ, кеш 8–32 МБ, данные из предыдущего обращения не помогают). Prefetch бесполезен: паттерна нет, предсказать следующий адрес невозможно. Каждый доступ — промах в RAM, ~100 нс. 10 миллионов × 100 нс = 1 секунда. На практике чуть быстрее за счёт параллелизма контроллера памяти (memory-level parallelism, MLP — способность контроллера обрабатывать несколько промахов одновременно, на современных процессорах до ~10 параллельных запросов): 200–500 мс. Пропускная способность падает до 80–200 МБ/с.

Разница — 30–50 раз при одной и той же алгоритмической сложности O(n). Это и есть ответ на наивную загадку из начала: данные не «просто лежат в памяти» — они доставляются блоками по 64 байта, и порядок обращений определяет, сколько полезных байт несёт каждая доставка.

Тот же эффект объясняет, почему массив часто обгоняет связный список даже там, где оба выполняют O(n) работы. Сдвиг массива — это копирование последовательных байт, попадающее в кеш-линии и prefetch. Обход списка — переход по указателям, разбросанным по памяти, с промахом на каждом узле. Асимптотика одинаковая, характер доступа — нет.

Три типа промахов

Промахи не все одинаковые. Когда кеш-профиль программы плохой, чинить нужно именно тот тип, который доминирует. У промахов три разные причины (три C, three Cs of cache misses), и каждая требует своей стратегии.

Compulsory miss

Обязательный промах, cold miss — первое обращение к линии. Данные никогда не были в кеше, промах неизбежен. Единственный способ уменьшить — предвыборка: загрузить данные заранее, до первого обращения.

Capacity miss

Промах ёмкости — рабочий набор данных (working set) не помещается в кеш. Линии вытесняются не из-за конфликтов, а потому что кеш физически меньше, чем данные. Обход массива 40 МБ при L3 = 8 МБ неизбежно вытесняет ранее загруженные линии. Способ борьбы — уменьшить рабочий набор: компактные структуры, блочные алгоритмы, отложенная обработка.

Conflict miss

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

На реальных нагрузках capacity и conflict часто пересекаются: когда рабочий набор чуть больше кеша, конфликтные промахи усиливают эффект. Мысленный приём для разделения: если заменить кеш на такой, где любая линия может занять любую позицию (того же размера), и промахи исчезают — это были conflict misses. Если промахи остаются — capacity misses. Если промахи возникают даже на бесконечном кеше — compulsory misses.

Диагностика: счётчики производительности процессора (hardware performance counters) через [[linux/infrastructure/tracing#perf-stat-аппаратные-счётчики-производительности|perf stat]] в Linux показывают количество L1/L2/L3 промахов. Команда perf stat -e L1-dcache-load-misses,LLC-load-misses ./program выдаёт абсолютные числа промахов по уровням.

Пропускная способность vs латентность

До сих пор речь шла о задержке одного обращения — сколько наносекунд уходит на промах. Но есть второй параметр: сколько байт в секунду система может доставить из RAM в кеш. Это пропускная способность (bandwidth). Оба параметра ограничивают производительность по-разному, и полезно видеть, где начинает упираться именно bandwidth.

Современная DDR5-5600 в двухканальной конфигурации даёт теоретический пик порядка 89 ГБ/с. На практике — 50–70 ГБ/с. Для DDR4-3200 в двух каналах — ~51 ГБ/с теоретического, ~35–40 ГБ/с реально.

Пропускная способность ограничивает не только RAM. Каждый уровень кеша имеет свой bandwidth. L1d на современном Intel обеспечивает пик ~192 ГБ/с на ядро (при полностью загруженном конвейере чтений), L2 — ~50–70 ГБ/с, L3 — ~150–300 ГБ/с суммарно, RAM — ~40–50 ГБ/с.

Если код упирается в bandwidth, а не в latency, увеличение кеша не поможет — данные просто не успевают приходить. Типичный пример: суммирование большого массива double (8 байт), не помещающегося в кеш. Каждый элемент читается один раз, все данные идут из RAM. Одно ядро при одном сложении за такт потребляет 3 ГГц × 8 байт = 24 ГБ/с — RAM (40 ГБ/с) справляется. Но четыре ядра с той же задачей потребляют 4 × 24 = 96 ГБ/с, а RAM по-прежнему выдаёт 40. Ядра простаивают, ожидая данных. Операция ограничена памятью (memory-bound): добавление пятого ядра не ускорит её, потому что узкое место — доставка данных, а не вычисления.

Последовательный vs случайный обход из предыдущего раздела — история про latency (со скрытым prefetch). Memory-bound сценарий с несколькими ядрами — про bandwidth. Эти два ограничения в реальных программах часто смешиваются, но лечатся по-разному: latency уменьшают локальностью и предвыборкой, bandwidth — уменьшением объёма данных, проходящих через память.

От наблюдаемого эффекта к устройству кеша

За 30–50-кратным разрывом между последовательным и случайным обходом стоит конкретный аппаратный механизм: кеш находит нужную линию за один такт среди сотен линий, политика замещения решает, какую вытеснить при полном кеше, предвыборщик угадывает, какую линию понадобится следующей. Его внутреннее устройство — тег, индекс, смещение, ассоциативность, store buffer, prefetch — разобрано в устройстве кеша.

Параллельно возникает другой вопрос. Пока ядро одно, кеш-линия живёт в его L1, и всё согласовано. Но в многоядерном процессоре у каждого ядра свой L1, и одна и та же линия может существовать в нескольких копиях. Когда два ядра пишут в один адрес, копии расходятся. Когерентность кешей объясняет, какой протокол поддерживает согласованность и какова её цена в наносекундах.

Два направления независимы. Устройство одного кеша можно понять, не зная про когерентность; когерентность можно изучать, пользуясь кеш-линией как готовым понятием. Порядок — на выбор.

Sources

John L. Hennessy, David A. Patterson, 2017, Computer Architecture: A Quantitative Approach — 6th edition, Chapter 2: Memory Hierarchy Design
Ulrich Drepper, 2007, What Every Programmer Should Know About Memory — Red Hat, Inc.
getconf LEVEL1_DCACHE_LINESIZE — размер cache line на текущей машине