Кеш процессора

Материал проходит ревью.

НовичокФундамент ~24 мин

Границы темы

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

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

Перед статьёй полезно знать, зачем CPU нужны регистры.

Результаты обучения

После статьи читатель сможет:

1. расположить кеш между регистрами и RAM;
2. объяснить попадание и промах кеша;
3. описать смысл уровней L1, L2 и L3/LLC;
4. привести примеры локальности;
5. провести учебное сравнение двух порядков чтения массива.

Основная модель

CPU выполняет команды быстрее, чем RAM обычно успевает отдавать отдельные данные. Кеш уменьшает разрыв: хранит копии недавно и соседно использованных данных рядом с ядром.

Диаграмма

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

Это не кеш приложения

Аппаратный кеш CPU не равен Redis, кешу браузера или HTTP-кешу. Слово одно, потому что идея похожа — сохранить копию ближе к потребителю, — но владельцы, данные и правила совсем разные.

Основные термины

Термин	Простое определение
Попадание, cache hit	Нужные данные уже найдены на проверяемом уровне
Промах, cache miss	Данных нет, нужно идти на более далёкий уровень
Строка кеша	Блок соседних байтов, переносимый как единое целое
L1	Ближайший и небольшой уровень кеша
L2	Следующий, обычно более крупный уровень
LLC	Последний уровень перед оперативной памятью
Локальность	Склонность программы использовать близкие или недавние данные

End-to-end сценарий

Пусть программа читает numbers[100].

Диаграмма

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

Что происходит под капотом

Попадание и промах

При чтении CPU сначала проверяет ближайший уровень:

Диаграмма

Промах не является ошибкой. Это обычная ситуация, но частые промахи заставляют ядро дольше ждать данные.

Пространственная локальность

Если программа прочитала один элемент массива, скоро ей часто нужен следующий. Последовательный обход:

0 → 1 → 2 → 3 → 4 → 5

обычно использует принесённые строки лучше, чем случайный:

5 → 10000 → 2 → 800000 → 17

Это не правило языка программирования, а свойство расположения и доступа к данным.

Временная локальность

Если значение использовано сейчас, оно может понадобиться снова в ближайшее время. Например, небольшой справочник, читаемый в каждой итерации, способен оставаться в кеше.

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

Кеш команд и кеш данных

Ближайший уровень часто отдельно хранит машинные инструкции и данные. Это позволяет ядру одновременно получать следующий код и операнды. На общей схеме их часто объединяют, чтобы не усложнять первый разбор.

Запись

При изменении данных CPU обновляет кеш, а затем система должна согласовать изменение с более дальними уровнями. Конкретная политика может записывать дальше сразу или позже.

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

Минимальный воспроизводимый пример

Эксперимент сравнивает последовательный и перемешанный обход одного массива:

const size = 1_000_000;
const values = new Uint32Array(size);
const order = Uint32Array.from({ length: size }, (_, index) => index);

for (let index = size - 1; index > 0; index -= 1) {
  const other = (index * 48271) % (index + 1);
  [order[index], order[other]] = [order[other], order[index]];
}

function measure(label, valueAt) {
  let sum = 0;
  const started = performance.now();
  for (let round = 0; round < 10; round += 1) {
    for (let index = 0; index < size; index += 1) {
      sum += values[valueAt(index)];
    }
  }
  console.log(label, Math.round(performance.now() - started), sum);
}

measure("Последовательно, мс:", (index) => index);
measure("Вперемешку, мс:", (index) => order[index]);

Сохраните код в cache-locality.mjs и запустите:

node cache-locality.mjs

Ожидаемый результат

Обе строки заканчиваются контрольной суммой 0. На многих компьютерах перемешанный обход займёт больше времени. Точные числа и отношение не гарантируются: на них влияют CPU, Node.js, оптимизация кода и соседняя нагрузка.

Как диагностировать ошибку

• node не найден — установите Node.js или проверьте PATH;
• результаты сильно прыгают — повторите запуск несколько раз;
• времена почти равны — увеличьте round или size, но следите за объёмом RAM;
• сумма различается — варианты выполняют разную работу, сравнение некорректно;
• один случайный запуск противоречит ожиданию — не делайте вывод по одному измерению.

Ограничения и trade-offs

Подход к данным	Возможный эффект	Цена
Последовательный обход	Лучше использует соседние байты	Не подходит каждому алгоритму
Маленький рабочий набор	Больше повторных попаданий	Нужно уменьшить или разделить данные
Копирование в плотный массив	Удобный доступ	Дополнительная память и копирование
Случайные ссылки между объектами	Гибкая структура	Возможны частые промахи

Оптимизировать расположение данных стоит после измерения реальной программы. Более простой алгоритм часто важнее небольшой разницы в локальности.

Failure modes и типичные ошибки

• Кеш увеличивает объём доступной RAM. Он хранит копии, а не добавляет независимое рабочее пространство приложения.
• Попадание гарантировано после первого чтения. Строку могут вытеснить.
• L1, L2 и L3 одинаковы на всех CPU. Размеры и совместное использование зависят от модели.
• Последовательный доступ всегда быстрее при любом размере. Результат зависит от кода, данных и оптимизаций.
• Нужно вручную складывать обычные переменные в L1. Аппаратный кеш управляется CPU.
• HTTP cache miss и CPU cache miss — одно событие. Это разные уровни системы.

Различия времени кеша также используются в атаках по побочным каналам. Это важная, но отдельная продвинутая тема.

Практическое задание

Задача: выполните пример пять раз для двух размеров массива и сравните медианы.

Критерии готовности:

• оба варианта выполняют одинаковое число чтений;
• контрольная сумма одинакова;
• сохранены все результаты, а не только лучший;
• указаны размер массива и версия Node.js;
• вывод сформулирован как наблюдение для конкретной машины.

Подсказка

Попробуйте 100_000 и 2_000_000 элементов. Не ожидайте одинакового отношения: маленький и большой рабочие наборы по-разному взаимодействуют с кешами.

Проверка знаний

ИНТЕРАКТИВНАЯ ПРОВЕРКА

Аппаратный кеш CPU

0 / 4

01Зачем CPU нужен аппаратный кеш?

Сокращать ожидание часто нужных данных из RAMХранить пользовательские файлы навсегдаЗаменять кеш браузера и CDN

02Какие обращения обычно хорошо используют кеш?

Повторное чтение недавно использованных данныхЧтение соседних элементов массиваСлучайные чтения огромного набора без повторовРабота с небольшим набором данных

03Что происходит при чтении, если данных нет в ближайшем кеше?

1. CPU использует значение
2. Проверить ближайший кеш
3. Обратиться к следующему уровню или RAM
4. Поместить полученный блок в кеш

04Разработчик может считать, что выбранное значение всегда останется в L1.

ВерноНеверно

Проверено: 0 из 4

Самопроверка

1. Чем попадание отличается от промаха?
2. Почему чтение соседнего элемента массива часто дешевле?
3. Что такое временная локальность?
4. Почему приложение не может считать значение навсегда закреплённым в L1?

Ответы и критерии

1. При попадании данные уже есть на проверяемом уровне; при промахе нужен более далёкий уровень.
2. В кеш переносится блок соседних байтов, поэтому элемент может уже находиться в принесённой строке.
3. Недавно использованное значение скоро используется снова.
4. Кеш ограничен, управляется аппаратно, а его строки вытесняются другой работой.

Краткое резюме

• Кеш хранит копии данных между ядром и RAM.
• Ближайшие уровни меньше и быстрее.
• Попадание сокращает ожидание, промах требует более далёкого чтения.
• Кеш переносит строки соседних байтов.
• Последовательный и повторный доступ обычно создают полезную локальность.
• Производительность нужно измерять на реальных данных.

Следующие шаги

Следующая статья — «Оперативная память». Она объясняет основное рабочее хранилище, из которого кеш получает данные.

Источники

• Intel 64 and IA-32 Optimization Reference Manual — официальное описание иерархии кешей и влияния доступа к памяти.
• Intel VTune: CPU Metrics Reference — связь промахов последнего уровня с ожиданием DRAM и рекомендации по локальности.
• Arm: Introducing the Arm architecture — официальная общая модель процессорной системы и кешей.