Иерархия памяти: регистры, кэш, RAM, диск и почему это важно

В предыдущей статье трека мы разобрали процессор как машину, которая в цикле достаёт команду по адресу из PC, декодирует её и исполняет (Как работает процессор). В той модели память была одним ровным полем пронумерованных ячеек: сказал «дай ячейку N» — получил байт, и неважно, какой это N. Это удобная ложь. Она позволяет думать о программе, не отвлекаясь на железо, и почти во всём коде так и делают. Но именно в этой лжи прячется разница между кодом, который считает матрицу за секунду, и байт-в-байт таким же кодом, который считает её двадцать секунд.

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

Иллюзия плоской памяти и «стена памяти»

Модель «память — плоское поле» была почти правдой в 1980-х: процессор Intel 8086 работал на 5–10 МГц, а обращение к памяти занимало у него считанные такты. Память успевала за процессором. С тех пор частоты процессоров выросли примерно в тысячу раз, а задержка обращения к DRAM — всего в несколько раз. Разрыв рос десятилетиями и получил имя — стена памяти (memory wall).

Сегодня одно обращение к оперативной памяти — это порядка сотни тактов, в течение которых ядро на 3 ГГц могло бы выполнить сотни команд. Если бы каждое чтение шло прямо в RAM, современный процессор простаивал бы 90+ процентов времени, ожидая данные. Вся иерархия памяти существует ровно чтобы этого не допустить — расширить то самое «бутылочное горлышко фон Неймана», о котором шла речь в статье про процессор.

Почему нельзя сделать всю память быстрой

Первый вопрос новичка справедлив: если регистры такие быстрые, почему не сделать всю память из регистров? Ответ — на пересечении физики и экономики, и он фундаментален, а не «пока не придумали».

Физика. Быстрая память — это статическая память (SRAM): каждый бит хранят 6 транзисторов в виде защёлки, которая держит состояние, пока есть питание. Она быстрая, но занимает много места на кристалле и много ест. Ёмкая память — динамическая (DRAM): бит хранит один конденсатор и один транзистор; конденсатор крошечный, поэтому битов на площадь влезает в разы больше, но заряд утекает — его приходится периодически освежать (refresh), и чтение медленнее. Диск (магнитный HDD или флеш-SSD) хранит биты вообще без питания, плотность гигантская, но механика и физика флеш-ячеек делают доступ на порядки медленнее.

Есть и предел, который не обойти никакими транзисторами, — скорость света. За один такт 3-гигагерцевого процессора (треть наносекунды) свет проходит около 10 см. Чем больше памяти, тем она физически дальше от ядра, тем дольше сигнал идёт туда и обратно. Маленькое можно держать вплотную к АЛУ; большое неизбежно оказывается «на другом конце стола».

Экономика. Цена за байт различается на порядки, и держать всё в самой дорогой памяти никто не станет.

Никакая технология не попадает в правый верхний угол — «быстро и много» одновременно. Раз единого идеального носителя нет, инженеры сделали единственно возможное: собрали пирамиду из всех сразу и научили её вести себя как одна большая быстрая память.

Пирамида: уровни иерархии

Сверху вниз каждый уровень больше и медленнее предыдущего. Порядок величин (для типичного десктопа/ноутбука середины 2020-х) стоит просто запомнить — они объясняют почти всё поведение программ по скорости:

Обратите внимание на разрывы: от L1 до RAM — примерно ×100 по задержке, от RAM до SSD — ещё ×1000, от SSD до HDD-seek — ещё ×100. Именно поэтому уровней несколько, а не два: между «очень быстро» и «очень медленно» слишком большая пропасть, её приходится засыпать промежуточными ступенями.

Ключевая идея, которая делает пирамиду работоспособной: процессор всегда обращается только к самому верхнему уровню (регистры и L1), а нижние подтягивают данные вверх по мере надобности автоматически. Программа пишет x = a[i], как будто читает прямо из RAM, но по факту почти всегда получает данные из L1, куда их заранее принёс кэш. Насколько «почти всегда» — зависит от вас.

Задержки в человеческих масштабах

Числа в наносекундах ничего не говорят интуиции. Домножим их примерно на миллиард — так, чтобы один такт процессора превратился в одну секунду, — и получим масштаб, понятный человеку. Эту знаменитую табличку («Latency Numbers Every Programmer Should Know», популяризованную Джеффом Дином из Google) стоит один раз прочувствовать:

Вывод, который меняет мышление программиста: промах кэша, отправляющий за данными в RAM, — это для процессора не «чуть медленнее», а „сходить за кофе“ вместо мгновенного взгляда. А случайное чтение с диска — это «подождать сутки». Отсюда всё: почему базы данных так борются за то, чтобы горячие данные лежали в RAM; почему сеть кэшируют через CDN; почему один и тот же алгоритм на одних и тех же данных может работать в разы быстрее или медленнее в зависимости от того, как эти данные разложены в памяти.

Кэш: как медленную память притворяют быстрой

Кэш (cache) — это маленькая быстрая память, которая хранит копии недавно использованных кусков большой медленной памяти. Когда процессору нужен байт по адресу, он сначала смотрит в кэш. Если данные там (попадание, cache hit) — получает их за пару тактов. Если нет (промах, cache miss) — идёт на уровень ниже, платит его задержкой и заодно кладёт копию в кэш на будущее.

Первое, что удивляет: кэш обменивается с памятью не байтами, а блоками фиксированного размера — строками кэша (cache line), обычно 64 байта на x86-64 и ARM. Запросили один байт — в кэш приезжают все 64, к которым он принадлежит. Это не расточительство, а ставка: раз уж полезли в медленную память, тащим сразу окрестность — скорее всего, соседние байты понадобятся следом (об этом — в разделе про локальность).

Обращение к памяти — это каскад проверок сверху вниз, пока данные не найдутся:

Доля попаданий (hit rate) — главный показатель. При типичных 95–99 % попаданий средняя задержка обращения близка к скорости кэша, а не RAM. Но арифметика безжалостна: пусть попадание стоит 1 нс, промах — 100 нс. При hit rate 99 % средняя задержка = 0,99·1 + 0,01·100 ≈ 2 нс. При 90 % — уже 0,9·1 + 0,1·100 ≈ 11 нс, в пять с лишним раз хуже. Падение доли попаданий на несколько процентов кратно замедляет программу. Вот почему борьба идёт за каждый процент, а цель кода — «попадать в кэш».

Локальность — принцип, на котором всё держится

Кэш работал бы бесполезно, если бы программы обращались к памяти случайно: тогда каждое чтение было бы промахом. Но реальные программы обращаются к памяти предсказуемо, и это свойство называется локальностью (locality). Она бывает двух видов:

• Временна́я локальность (temporal): если к данным обратились сейчас, скорее всего обратятся к ним снова в ближайшее время. Пример — счётчик цикла, переменная-аккумулятор, часто вызываемая функция. Кэш держит такие данные под рукой.
• Пространственная локальность (spatial): если обратились к данным по адресу A, скорее всего скоро обратятся к соседним адресам. Пример — обход массива элемент за элементом, поля одной структуры. Именно на это работает строка кэша в 64 байта: подтягивая окрестность, кэш заранее готовит соседей.

Схема выше показывает суть на пальцах. При последовательном обходе массива первый элемент строки — промах (едем в RAM), но он подтягивает всю строку, и следующие 7–15 элементов оказываются попаданиями: один поход в память амортизируется на десяток обращений. При обходе с большим шагом (например, по столбцам матрицы, разложенной по строкам) каждый элемент попадает в новую строку — сплошные промахи, а подтянутые вместе с ним соседи так и не используются. Данные те же, число операций то же — а число походов в RAM отличается в разы.

Железо помогает локальности ещё и аппаратным упреждающим чтением (hardware prefetcher): процессор замечает, что вы читаете память с постоянным шагом, и начинает подтягивать следующие строки до того, как вы их запросили. Поэтому предсказуемый (линейный) доступ быстр вдвойне: и попадания растут, и упреждение работает. Случайный доступ лишает вас обоих подарков.

Устройство кэша: ассоциативность и вытеснение

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

• Отображение. В прямо отображаемом (direct-mapped) кэше каждый адрес памяти может лежать ровно в одной ячейке кэша (по остатку от деления адреса). Просто и быстро, но два «горячих» адреса, попавших в одну ячейку, вечно вытесняют друг друга (конфликтные промахи). Другая крайность — полностью ассоциативный кэш: строка может лежать где угодно, конфликтов нет, но искать дорого. Компромисс, который используют реально, — множественно-ассоциативный (N-way set-associative): кэш разбит на наборы по N ячеек, строка кладётся в свой набор в любую из N позиций. Типичный L1 — 8-канальный.
• Вытеснение. Когда набор заполнен, а нужна новая строка, кого-то выселяют. Идеал — выселить то, что дольше всего не понадобится, но будущего мы не знаем, поэтому приближают прошлым: LRU (least recently used) — выселяем давно не использованное. В железе применяют дешёвые приближения (pseudo-LRU).
• Запись. Что делать, когда процессор пишет? Сквозная запись (write-through) сразу дублирует запись в память — просто, но медленно. Отложенная запись (write-back) меняет только строку в кэше, помечает её «грязной» (dirty bit) и сбрасывает в память лишь при выселении — быстрее, ценой того, что кэш и память временно расходятся (это важно для многоядерности, см. ниже).

Все эти механизмы — часть железа и работают автоматически. Управлять ими напрямую из обычного кода нельзя, но можно писать код так, чтобы они работали на вас.

Почему это важно: код, дружелюбный к кэшу

Теперь главное для практика. Иерархия памяти невидима в исходнике, но кратно влияет на скорость. Классическая демонстрация — обход двумерного массива. В C и большинстве языков матрица лежит в памяти по строкам (row-major): сначала вся строка 0, затем строка 1 и т. д. Значит, соседние по строке элементы — соседи и в памяти.

#include <stdlib.h>

#define N 8192
static int a[N][N];  // 256 МБ — заведомо больше любого кэша

// Обход ПО СТРОКАМ: a[i][0], a[i][1]... — соседние адреса, дружит с кэшем
long sum_rows(void) {
    long s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            s += a[i][j];   // шаг 4 байта: 16 элементов на строку кэша
    return s;
}

// Обход ПО СТОЛБЦАМ: a[0][j], a[1][j]... — прыжки на N*4 байта
long sum_cols(void) {
    long s = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            s += a[i][j];   // каждый шаг — новая строка кэша, сплошные промахи
    return s;
}

Обе функции складывают одни и те же числа, выполняют одинаковое число сложений и обращений. Но sum_rows использует каждую подтянутую строку целиком (16 элементов по 4 байта на 64-байтную строку — 1 промах на 16 обращений), а sum_cols от каждой строки берёт по одному элементу и тут же её теряет — фактически промах на каждое обращение. На типичной машине разница 5–10 раз, а на больших матрицах ещё и вмешивается подсистема виртуальной памяти (промахи TLB), раздувая разрыв до 10–20 раз. Ни строчки логики не изменилось — только порядок обхода.

Отсюда набор практических приёмов, важных, когда скорость реально нужна:

• Обходите данные в том порядке, в котором они лежат в памяти. Линейный проход по массиву — золотой стандарт локальности.
• Предпочитайте непрерывные структуры. Массив (vector, array) лежит одним куском и идеален для кэша; связный список (linked list) — это разбросанные по памяти узлы, каждый переход по указателю рискует промахом («pointer chasing»). Именно поэтому на практике vector часто обгоняет list даже там, где по «классической» асимптотике список должен побеждать. Как это меняет выбор структуры — тема трека Структуры данных и обзорной статьи Как хранят данные.
• Структура массивов вместо массива структур. Если вы перебираете только одно поле у миллиона объектов, храните это поле отдельным массивом (SoA), а не внутри «толстых» структур (AoS) — тогда в строку кэша попадают только нужные значения, а не мусор из соседних полей.
• Big-O — не вся правда. Асимптотика считает операции, а не походы в память. Алгоритм с меньшим числом операций, но случайным доступом, легко проигрывает «более медленному», но кэш-дружелюбному. Об ограничениях модели сложности — в статье Что такое алгоритм и сложность.

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

Виртуальная память: ещё одна иллюзия поверх иерархии

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

Работает это через страницы (обычно 4 КБ): виртуальное пространство нарезано на страницы, и таблица страниц сопоставляет каждой виртуальной странице физическую (или отметку «на диске»). Когда данных страницы нет в RAM, возникает отказ страницы (page fault): процессор передаёт управление ОС, та подгружает страницу с диска (из области подкачки, swap) в RAM и возобновляет программу — а если RAM переполнена, вытесняет чью-то другую страницу на диск. Заметьте: это ровно тот же приём «кэша», только теперь RAM работает кэшем для диска, а роль «строки» играет страница.

И финальный штрих, замыкающий тему: сама трансляция «виртуальный адрес → физический» тоже кэшируется — в TLB (Translation Lookaside Buffer), кэше недавних переводов адресов. Промах TLB заставляет процессор идти читать таблицу страниц из памяти. То есть кэш есть даже у механизма адресации кэшей — принцип «горячее держи ближе» пронизывает систему на всех уровнях. Полностью виртуальная память, страницы и подкачка разбираются в статье Что делает операционная система и в треке Операционные системы.

Где эта абстракция протекает

«Одна большая быстрая память» — прекрасная модель, и большую часть времени её достаточно. Но, как всякая абстракция, она протекает, и в случае памяти протечки бывают дорогими и даже опасными.

Волатильность. Регистры, кэш и DRAM хранят данные, только пока есть питание. Выдернули шнур — всё, что было выше диска, исчезло. Именно поэтому существует отдельная забота о том, чтобы данные «пережили выключение»: запись на диск, fsync, журналы и транзакции баз данных. Разрыв между быстрой волатильной памятью и медленным энергонезависимым хранилищем — причина половины сложности систем хранения (трек Базы данных и обзор Как данные переживают выключение).

Когерентность кэшей. У каждого ядра свой L1 (а часто и L2). Если два ядра держат копии одной строки, а одно из них пишет — копия второго устаревает. Чтобы программы продолжали видеть согласованную память, железо гоняет между ядрами протокол когерентности (например, MESI): каждая строка в кэше находится в одном из состояний, и запись на одном ядре принудительно обесценивает копии на других.

Отсюда коварная ложная общность (false sharing): две переменные, которые правят разные потоки, случайно попали в одну 64-байтную строку. Логически они независимы, но с точки зрения кэша это одна строка — и она мечется между ядрами при каждой записи, обесценивая копии. Производительность падает в разы без всякой видимой причины в коде. Лечится выравниванием — разнести горячие переменные по разным строкам:

#include <stdalign.h>

// Плохо: два счётчика в одной строке кэша — потоки дерутся за неё
struct counters_bad { long a; long b; };

// Хорошо: каждый счётчик выровнен на свою строку кэша (64 байта)
struct counters_good {
    alignas(64) long a;
    alignas(64) long b;
};

Почему многоядерность делает такие вещи возможными и трудноуловимыми — тема статьи Многозадачность и параллелизм.

NUMA. В серверах с несколькими процессорами память физически «своя» у каждого сокета: обращение к чужой памяти дороже, чем к своей (Non-Uniform Memory Access). Плоская модель здесь протекает окончательно — приходится думать, на каком узле лежат данные и где считающий их поток.

Кэш как канал утечки. Раз попадание быстрее промаха, замерив время доступа, можно узнать, лежат ли данные в кэше, — а значит, что-то об их обработке. Именно на этом строятся атаки Spectre и Meltdown: спекулятивно исполненный код оставляет следы в кэше, и по таймингам из них достаётся то, к чему у программы не было доступа. Абстракция «память просто хранит байты» здесь протекает на уровень безопасности целой индустрии (см. Основы безопасности).

Типичные заблуждения

• «Память плоская, любое обращение стоит одинаково». Стоимость обращения различается на порядки в зависимости от того, на каком уровне иерархии сейчас данные. Именно это делает порядок доступа важнее, чем кажется.
• «Кэшем управляет программист». Аппаратными кэшами — нет, они автоматические. Вы влияете на них лишь косвенно — раскладкой данных и порядком доступа. (Кэши в приложениях — Redis, кэш браузера — это другое, «логическое» кэширование той же идеи.)
• «Меньше операций — всегда быстрее». Big-O игнорирует иерархию памяти. Кэш-дружелюбный алгоритм с большим числом операций регулярно обгоняет «оптимальный» с random-доступом.
• «Больше RAM — всегда быстрее». Помогает, только пока рабочий набор не влезал в память (убирает подкачку). Данные, влезающие в кэш, от лишней RAM быстрее не станут — их скорость определяет L1/L2/L3.
• «SSD быстрый, диск не важен». SSD в тысячи раз медленнее RAM. Для процессора чтение с SSD — это по-прежнему «подождать сутки» в человеческом масштабе.

Мини-итог

Память компьютера — не плоское поле, а пирамида: регистры, L1/L2/L3, ОЗУ, SSD, диск и сеть. Каждый уровень на порядки больше и медленнее предыдущего, потому что «быстро и много одновременно» невозможно ни физически (SRAM против DRAM против флеша, скорость света), ни экономически. Пирамида работает благодаря кэшу, который держит копии горячих данных ближе к ядру и обменивается с памятью строками по 64 байта, и благодаря локальности — свойству реальных программ обращаться к памяти предсказуемо (временна́я и пространственная). Отсюда практический вывод, ценный для любого программиста: код, который обходит данные так, как они лежат в памяти, и использует непрерывные структуры, попадает в кэш и работает в разы быстрее байт-в-байт идентичного по логике кода, который прыгает по памяти. А там, где «одна большая быстрая память» протекает — волатильность, когерентность кэшей и ложная общность на многих ядрах, NUMA, кэш-тайминговые атаки, — знание иерархии превращается из способа ускорить код в способ не написать опасный или необъяснимо медленный.

Источники, к которым стоит вернуться: Ulrich Drepper, «What Every Programmer Should Know About Memory» (2007, akkadia.org/drepper/cpumemory.pdf) — канонический разбор; Bryant & O’Hallaron, «Computer Systems: A Programmer’s Perspective», глава 6; Hennessy & Patterson, «Computer Architecture: A Quantitative Approach»; интерактивная таблица задержек Колина Скотта (colin-scott.github.io/personal_website/research/interactive_latency.html).

Что дальше

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

От кода к исполнению: компиляторы, интерпретаторы, ассемблер, машинный код