Иерархия памяти и принцип локальности

Урок объясняет, почему память компьютера устроена как пирамида уровней, и какой принцип делает эту идею рабочей.

Иерархия памяти — расположение видов памяти слоями: маленькие и быстрые наверху (регистры, кэш), большие и медленные внизу (ОЗУ, диск). Принцип локальности — наблюдение, что программы обращаются к небольшому набору данных снова и снова.

Неразрешимый компромисс

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

Пирамида памяти

           ▲ быстрее, дороже, меньше
   ┌──────────────────┐
   │   Регистры       │  ~1 такт,   ~1 КБ
   ├──────────────────┤
   │   Кэш L1         │  ~4 такта,  ~64 КБ
   ├──────────────────┤
   │   Кэш L2         │  ~12 тактов, ~512 КБ
   ├──────────────────┤
   │   Кэш L3         │  ~40 тактов, ~32 МБ
   ├──────────────────┤
   │   ОЗУ (DRAM)     │  ~200 тактов, ~16 ГБ
   ├──────────────────┤
   │   SSD / диск     │  ~10^5-10^7 тактов, ТБ
   └──────────────────┘
           ▼ медленнее, дешевле, больше

Разрыв колоссален: обращение к ОЗУ медленнее обращения к регистру в сотни раз, а к диску — в миллионы. Если бы каждый доступ к данным шёл в ОЗУ, процессор простаивал бы почти всё время. Иерархию спасает локальность.

Два вида локальности

Локальность	Суть	Пример
Временная	к данным, использованным недавно, скоро обратятся снова	переменная цикла, счётчик
Пространственная	рядом с использованными данными скоро понадобятся соседние	обход массива по порядку

Как работает под капотом: цена промаха

Эффективное время доступа зависит от доли попаданий в быстрый уровень. Посчитаем, как сильно кэш ускоряет память, на модели «среднего времени доступа» (AMAT):

def amat(hit_time, miss_rate, miss_penalty):
    # среднее время = время попадания + штраф * доля промахов
    return hit_time + miss_rate * miss_penalty

cache_hit = 4         # такта на попадание в кэш
ram_penalty = 200     # такта на поход в ОЗУ при промахе

for miss in (0.50, 0.10, 0.02):
    t = amat(cache_hit, miss, ram_penalty)
    print(f"промахов {miss*100:4.0f}% -> среднее время {t:6.1f} такта")

Вывод:

промахов   50% -> среднее время  104.0 такта
промахов   10% -> среднее время   24.0 такта
промахов    2% -> среднее время    8.0 такта

Даже 2% промахов удваивают время относительно идеала — вот почему кэш так важен и почему «cache-friendly» код пишут аккуратно.

Локальность в коде: порядок обхода матрицы

Покажем пространственную локальность: обход матрицы по строкам (как она лежит в памяти) против обхода по столбцам. По строкам мы читаем соседние ячейки — кэш доволен. Сравним «попадания» в модели кэш-строк:

N = 4
matrix = [[r*N + c for c in range(N)] for r in range(N)]

def order_rows(m):
    seq = []
    for r in range(N):
        for c in range(N):
            seq.append(m[r][c])      # соседние в памяти
    return seq

def order_cols(m):
    seq = []
    for c in range(N):
        for r in range(N):
            seq.append(m[r][c])      # прыжки через N
    return seq

print("по строкам (locality+):", order_rows(matrix))
print("по столбцам (locality-):", order_cols(matrix))
print("по строкам адреса идут подряд -> кэш загружает строку и попадает")

Вывод:

по строкам (locality+): [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
по столбцам (locality-): [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
по строкам адреса идут подряд -> кэш загружает строку и попадает

Глубже в тему

За идеей иерархии памяти стоит фундаментальный физический и экономический конфликт, который инженеры так и не смогли разрешить напрямую за полвека. Быстрая память (статическая SRAM, из которой делают регистры и кэш) требует шести транзисторов на бит, дорога и греется, поэтому её можно позволить лишь килобайты-мегабайты. Ёмкая память (динамическая DRAM, из которой делают ОЗУ) — это один транзистор и конденсатор на бит, дёшево и плотно, но она медленнее в сотни раз и нуждается в постоянной регенерации. Диск и SSD ещё на порядки дешевле и медленнее. Никакая единая технология не даёт одновременно скорость, объём и низкую цену — это не недоработка, а свойство физики. Гениальность иерархии в том, что она не пытается победить этот конфликт, а ловко обходит его, складывая разные технологии слоями и автоматически перемещая «горячие» данные вверх.

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

Метрика AMAT (среднее время доступа к памяти) из урока — это рабочий инструмент архитектора, и её формула обманчиво проста. Среднее время равно времени попадания плюс произведение доли промахов на штраф за промах. Коварство в том, что штраф огромен: поход в ОЗУ при промахе L1 стоит сотни тактов против единиц при попадании. Поэтому даже скромные 2% промахов, как показывает расчёт, удваивают среднее время относительно идеала. Из этого вытекает неинтуитивный вывод: бороться нужно не столько за снижение времени попадания, сколько за снижение доли промахов, потому что штраф настолько велик, что доминирует. Именно поэтому индустрия строит трёх-четырёхуровневые иерархии кэшей: L2 ловит то, что промахнулось мимо L1, L3 — то, что промахнулось мимо L2, и каждый уровень снижает эффективный штраф для предыдущего.

Практический вывод для программиста — писать «cache-friendly» код, и пример с обходом матрицы из урока тут показателен. В языках вроде C матрица хранится построчно (row-major): элементы одной строки лежат в памяти подряд. Обход по строкам читает соседние адреса, и каждая загруженная кэш-строка (обычно 64 байта, то есть 16 четырёхбайтовых чисел) обслуживает сразу много обращений — сплошные попадания. Обход по столбцам, наоборот, прыгает через всю строку матрицы на каждом шаге, выбрасывая большую часть кэш-строки впустую, — отсюда замедление в разы на больших матрицах. Этот эффект настолько силён, что библиотеки линейной алгебры применяют блочную обработку (tiling), разбивая матрицы на куски, влезающие в кэш. Понимание иерархии памяти, таким образом, — не абстрактная теория, а прямой ключ к производительности реального кода: алгоритм с лучшей локальностью нередко обгоняет асимптотически такой же, но «недружелюбный» к кэшу.

Частые ошибки

Думать, что «больше ОЗУ = быстрее». Объём помогает не упереться в диск, но скорость даёт кэш и локальность доступа.
Игнорировать порядок обхода. Обход массива «не по памяти» рушит локальность и замедляет код в разы.
Считать диск и ОЗУ «одинаковой памятью». Между ними разрыв в тысячи раз — отсюда отдельный уровень.

Итог

Память — пирамида: быстро/мало/дорого наверху, медленно/много/дёшево внизу.
Иерархия работает благодаря локальности: временной (повторное обращение) и пространственной (соседние данные).
Даже малая доля промахов резко повышает среднее время доступа.