Раздел 32 · Системное программирование: Zig, ассемблер, Verilog

Технологии хранения и локальность

senior~130 мин

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

Технологии хранения и локальность

В прошлом уроке ты научился мерить: perf stat показал счётчики, callgrind нарисовал, где программа проводит время, а закон Амдала объяснил, за какой кусок браться первым. Почти в каждом таком отчёте самая тяжёлая строка одна и та же: процессор ждёт память. Сегодня мы разберём, чего именно он ждёт. Пройдём четыре технологии хранения от SRAM до магнитного диска, сведём их в одну таблицу с числами на 2026 год, посчитаем три вещи на калькуляторе (сколько тактов стоит один поход в память, сколько живёт SSD, сколько длится чтение с диска) и введём понятие, вокруг которого крутятся следующие четыре урока: локальность. А в конце напишем генератор трасс, который превращает обычную Zig-программу в список её обращений к памяти, и локальность станет видна глазами.

Цели урока

Знать четыре технологии хранения (SRAM, DRAM, флеш-память SSD, магнитный диск) и порядок их задержки, пропускной способности и цены за гигабайт.
Понимать, как устроен чип DRAM: матрица строк и столбцов, адрес в два приёма, буфер строки, обновление; что изменил DDR5.
Считать по формулам время доступа к диску, ресурс записи SSD, число выводов адреса у матрицы DRAM и цену одного промаха в тактах.
Различать временную и пространственную локальность, видеть обе в данных и в инструкциях.
Читать локальность по коду до запуска: шаг обращения, порядок вложенных циклов, массив структур против структуры массивов.
Собрать генератор трасс: обёртка над массивом пишет каждое своё обращение в формате valgrind lackey, и трассу можно сохранить в файл.
Считать по трассе две меры локальности: сколько блоков памяти задето и как часто обход переключается между ними.

Идея: четыре технологии, одна таблица

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

Таблица ниже это порядки величин на осень 2026 года. Цены на память в этом году скакали из-за спроса со стороны серверов для нейросетей, так что колонка с долларами верна с точностью до двух раз. Задержки и пропускная способность меняются куда медленнее, их запоминать стоит.

Технология	Где живёт	Задержка от ядра	Пропускная способность	Цена за гигабайт	Без питания
SRAM	кэши L1, L2, L3 на кристалле	около 1 нс в L1, около 10 нс в L3	сотни ГБ/с на ядро	отдельно не продаётся; по площади кристалла выходит порядка тысяч долларов	теряет данные
DRAM (DDR5)	модули памяти на плате	80 до 100 нс	40 до 80 ГБ/с на канал	единицы долларов	теряет данные
Флеш (SSD NVMe PCIe 5.0)	накопитель	20 до 100 мкс на чтение	10 до 14 ГБ/с последовательно	около десяти центов	хранит
Магнитный диск (7200 об/мин)	накопитель	5 до 10 мс	200 до 300 МБ/с	около двух центов	хранит

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

SRAM

DRAM

занимают верхние две строки, и разница между ними целиком объясняется тем, из чего сделана одна ячейка.

SRAM и DRAM: шесть транзисторов против одного конденсатора

Ячейка SRAM это триггер: два инвертора, замкнутые друг на друга, плюс два транзистора доступа. Шесть транзисторов на бит. Пока есть питание, триггер держит состояние сам, его не нужно ни обновлять, ни восстанавливать после чтения. Отвечает он за доли наносекунды. Платить за это приходится площадью: на той же площади кристалла DRAM уместит примерно вшестеро больше бит, поэтому кэш L1 меряется десятками килобайт, а не гигабайтами.

Ячейка DRAM это один конденсатор и один транзистор, который его подключает к шине. Заряд на конденсаторе означает единицу, отсутствие заряда ноль. Конденсатор крошечный, заряд с него утекает, и через десятки миллисекунд единица превратится в ноль сама собой. Отсюда две особенности, которых у SRAM нет.

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

Строки нужно обновлять. Каждая строка матрицы должна быть перечитана и записана обратно не реже, чем раз в 64 миллисекунды (при высокой температуре чипа вдвое чаще). Контроллер памяти выдаёт команду обновления примерно каждые 3.9 микросекунды, и на время обновления банк недоступен. Это несколько процентов пропускной способности, отданных за плотность.

Матрица, строки и столбцы

Ячейки DRAM в чипе сложены в матрицу из r строк и c столбцов, и каждая ячейка хранит не бит, а слово в 8 или 16 бит. Адрес ячейки подаётся в два приёма по одним и тем же выводам: сначала номер строки (команда RAS, row address strobe), потом номер столбца (CAS, column address strobe). Так чип экономит выводы: матрице 16 на 16 хватает четырёх адресных линий, хотя ячеек в ней 256.

Двухступенчатый адрес даёт побочный эффект, на котором стоит вся производительность DRAM. По команде RAS чип копирует целую строку матрицы во внутренний буфер строки. Дальнейшие обращения к столбцам той же строки обходятся одной командой CAS, они быстрые. Обращение к другой строке требует сначала закрыть текущую (записать буфер обратно в матрицу), потом открыть новую. Попадание в открытую строку против промаха мимо неё различается по времени вдвое, а то и втрое. Программа, которая идёт по памяти подряд, попадает в открытую строку почти всегда. Программа, которая прыгает, каждый раз платит за открытие.

Первая задача книги в этой главе про выводы адреса. Переформулируем её: матрица DRAM хранит 256 ячеек, и её можно сложить как 16 на 16, как 32 на 8 или как 256 на 1. Сколько адресных выводов нужно каждой раскладке? Выводов нужно под большее из двух чисел, потому что строка и столбец идут по очереди по одним линиям. Матрица 16 на 16 обходится четырьмя, 32 на 8 пятью, 256 на 1 восемью. Квадратная раскладка экономит выводы, зато у широкой длиннее строка, и буфер строки покрывает больше соседних адресов. Проектировщик чипа выбирает между ними, а мы увидим последствия в таблицах задержек. Расчёт в виде теста лежит ниже, вместе с остальными вычислениями урока.

DDR5

Оперативная память на плате в 2026 году это DDR5. Три вещи в нём стоит знать программисту.

Скорость передачи. Название вроде DDR5-6400 означает 6400 миллионов передач в секунду по каналу шириной 64 бита. Умножаем: 6400 миллионов на 8 байт это 51.2 ГБ/с на канал. У ноутбука обычно два канала, у сервера восемь или двенадцать. Это пиковая пропускная способность, которую программа получает только на длинном последовательном чтении.

Два подканала и пакет в 64 байта. DDR5 делит 64-битный канал на два независимых подканала по 32 бита, и каждая передача идёт пакетом из 16 слов (burst length 16). Шестнадцать слов по 32 бита это ровно 64 байта, размер линии кэша на x86-64 и на Apple Silicon. Память физически отдаёт данные линиями, отдельный байт из неё не заказать.

Задержка не уменьшилась. Со времён DDR2 время открытия строки и время выборки столбца стоят на месте: около 14 наносекунд каждое у обычных модулей, что даёт около 30 наносекунд внутри чипа и 80 до 100 наносекунд от ядра процессора с учётом контроллера, очередей и обхода кэшей. Росла только пропускная способность. Это главная асимметрия иерархии памяти: перекачать много подряд дёшево, сходить за одним словом дорого.

Флеш-память и SSD: ресурс записи

Накопитель SSD хранит данные в NAND-флеш, и у неё есть свойство, которого нет ни у SRAM, ни у DRAM: перезаписать ячейку на месте нельзя. Память разбита на страницы (4 до 16 КБ), страницы сложены в блоки (сотни страниц, единицы мегабайт). Читать можно постранично, за десятки микросекунд. Писать тоже постранично, за сотни микросекунд, но только в чистую страницу. Очистить страницу по отдельности нельзя, стирается сразу весь блок, и стирание длится миллисекунды.

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

TBW

это число из паспорта накопителя, по которому ресурс считается за минуту. Переформулируем задачу книги про износ. Возьмём SSD на 2 ТБ, для которого производитель обещает 1200 TBW (это 600 полных перезаписей ёмкости, с запасом ниже физического предела ячеек). Максимальная скорость записи 7 ГБ/с.

Обычный ноутбук пишет около 20 ГБ в день. Ресурса хватит на 1200 ТБ разделить на 20 ГБ, это 60 000 дней или около 164 лет. Накопитель устареет задолго до того, как износится.
Худший случай: запись на полной скорости без остановки. 1200 ТБ разделить на 7 ГБ/с это около 171 000 секунд, то есть 47.6 часа. Двое суток.

Оба числа верны, и вместе они показывают, что ресурс записи это не страшилка с форумов, а величина, которую делят на свой поток записи. Рабочая станция, которая пишет видеопоток или логи базы данных, живёт ближе ко второму случаю, чем к первому, и там TBW нужно смотреть.

Магнитный диск: геометрия и время доступа

Диск в 2026 году это уже не системный накопитель, а хранилище: архивы, резервные копии, холодные данные в облаке. Но на нём формула времени доступа видна невооружённым глазом, и она же в замаскированном виде пригодится для DRAM.

Диск это стопка пластин, у каждой две рабочие поверхности. Поверхность разбита на концентрические дорожки, дорожка на секторы фиксированного размера (сегодня 4096 байт). Дорожки с одинаковым номером на всех поверхностях образуют цилиндр. Ёмкость это произведение четырёх чисел. Переформулируем задачу книги: четыре пластины, 250 000 дорожек на поверхность, в среднем 3000 секторов на дорожке (ближе к краю секторов больше, ближе к центру меньше). Ёмкость это 8 поверхностей, умножить на 250 000 дорожек, умножить на 3000 секторов, умножить на 4096 байт: около 24.6 ТБ. Так и выглядят диски на полках в 2026 году.

Время доступа к одному сектору складывается из трёх частей.

Поиск. Головка перемещается на нужную дорожку. Среднее время поиска у настольного диска 4 до 9 мс.
Ожидание поворота. Головка ждёт, пока нужный сектор подъедет под неё. В среднем это половина оборота. При 7200 оборотах в минуту один оборот занимает 60 000 разделить на 7200, это 8.33 мс, половина 4.17 мс.
Передача. Сектор проезжает под головкой. Это один оборот, делённый на число секторов на дорожке: 8.33 мс разделить на 1000, около 8 микросекунд.

Возьмём поиск 6 мс и 1000 секторов на дорожке: 6 плюс 4.17 плюс 0.008, около 10.2 мс на сектор. Обрати внимание на пропорцию: передача данных занимает меньше десятой доли процента, всё остальное это механика. Отсюда следующая задача книги, которую тоже переформулируем: файл в 1 МБ это 256 секторов по 4 КБ. Если они лежат на диске подряд, платим за один поиск и одно ожидание поворота, дальше только передача: 6 плюс 4.17 плюс 256 умножить на 0.008, около 12.3 мс. Если те же секторы разбросаны по диску случайно, каждый стоит полных 10.2 мс, итого около 2.6 секунды. Один и тот же мегабайт, разница в двести раз, и вся она в порядке обращений. Запомни эту картину: то же самое, только в наносекундах, происходит между процессором и DRAM.

Что стоит одно ожидание

Переведём задержки в такты. Возьмём ядро на 4 ГГц: такт это четверть наносекунды.

Куда сходили	Задержка	Тактов простоя	Что успел бы процессор
L1	1 нс	4	пара сложений
DRAM	80 нс	320	цикл в сотню итераций
SSD	60 мкс	240 000	разбор небольшого JSON
Диск	8 мс	32 000 000	сборка небольшой программы

Простой в 320 тактов за одно чтение из DRAM это цена, которую платит любая программа, промахнувшаяся мимо кэшей. В уроке про машину и память ты видел эту таблицу как «числа, которые стоит знать наизусть», а в уроке про модель памяти железа как причину, по которой два потока не должны писать в одну линию. Здесь мы поворачиваем её другой стороной: раз ожидание настолько дорого, то вся производительность зависит от того, как часто программа его вызывает. А это уже свойство самой программы, и у него есть имя.

Все расчёты раздела собраны в один файл тестов: числа в нём те же, что в тексте, и тебе есть что поменять на свои.

//! Расчёты урока как тесты: стоимость промаха в тактах, ресурс записи SSD,
//! время доступа к диску. Числа в тестах те же, что в тексте.

const std = @import("std");

const ghz = 4.0;

/// Сколько тактов процессора на `ghz` ГГц простаивает за одно ожидание в `ns`.
fn cyclesLost(ns: f64) f64 {
    return ns * ghz;
}

test "во что обходится одно ожидание" {
    try std.testing.expectApproxEqAbs(4.0, cyclesLost(1.0), 0.01); // L1
    try std.testing.expectApproxEqAbs(320.0, cyclesLost(80.0), 0.01); // DRAM
    try std.testing.expectApproxEqAbs(240_000.0, cyclesLost(60_000.0), 1.0); // SSD, 60 мкс
    try std.testing.expectApproxEqAbs(32_000_000.0, cyclesLost(8_000_000.0), 1.0); // диск, 8 мс
}

/// Ресурс записи: `capacity_gb` гигабайт умножить на число циклов стирания.
fn tbwOf(capacity_gb: f64, cycles: f64) f64 {
    return capacity_gb * cycles / 1000.0;
}

test "ресурс записи SSD: годы против часов" {
    const tbw = tbwOf(2000, 600); // 2 ТБ, 600 циклов: 1200 ТБ
    try std.testing.expectApproxEqAbs(1200.0, tbw, 0.01);

    // Обычный ноутбук: 20 ГБ в день.
    const days = tbw * 1000.0 / 20.0;
    try std.testing.expectApproxEqAbs(164.4, days / 365.0, 0.1);

    // Худший случай: запись на полной скорости 7 ГБ/с без остановки.
    const seconds = tbw * 1000.0 / 7.0;
    try std.testing.expectApproxEqAbs(47.6, seconds / 3600.0, 0.1);
}

/// Среднее время доступа к диску: поиск, полоборота, передача сектора.
fn diskAccessMs(seek_ms: f64, rpm: f64, sectors_per_track: f64) f64 {
    const rotation_ms = 60_000.0 / rpm;
    const half_turn = rotation_ms / 2.0;
    const transfer = rotation_ms / sectors_per_track;
    return seek_ms + half_turn + transfer;
}

test "время доступа к диску 7200 об/мин" {
    const t = diskAccessMs(6.0, 7200, 1000);
    // 6 мс поиск + 4.17 мс полоборота + 0.008 мс передача.
    try std.testing.expectApproxEqAbs(10.17, t, 0.01);
    // 256 секторов по 4 КБ подряд: один поиск и один поворот, дальше только передача.
    const sequential_mb: f64 = 6.0 + 4.17 + 256.0 * (60_000.0 / 7200.0 / 1000.0);
    try std.testing.expectApproxEqAbs(12.3, sequential_mb, 0.1);
    // Те же 256 секторов вразброс: каждый со своим поиском и поворотом.
    const scattered: f64 = 256.0 * t;
    try std.testing.expectApproxEqAbs(2604.0, scattered, 1.0);
}

/// Число адресных выводов у матрицы DRAM r на c: адрес подаётся в два
/// приёма, строкой и столбцом, поэтому выводов нужно под большее из двух.
fn addressPins(rows: u32, cols: u32) u32 {
    return @max(std.math.log2_int_ceil(u32, rows), std.math.log2_int_ceil(u32, cols));
}

test "выводы адреса матрицы DRAM" {
    try std.testing.expectEqual(4, addressPins(16, 16));
    try std.testing.expectEqual(5, addressPins(32, 8));
    try std.testing.expectEqual(4, addressPins(8, 16));
    // 256 ячеек: 16 на 16 требует четыре вывода, 256 на 1 требовало бы восемь.
    try std.testing.expectEqual(8, addressPins(256, 1));
}

$ zig test calc.zig
1/4 calc.test.во что обходится одно ожидание...OK
2/4 calc.test.ресурс записи SSD: годы против часов...OK
3/4 calc.test.время доступа к диску 7200 об/мин...OK
4/4 calc.test.выводы адреса матрицы DRAM...OK
All 4 tests passed.

Одна деталь Zig по дороге. В тесте про диск переменные sequential_mb и scattered объявлены с явным типом f64. Без него выражение из одних литералов считается на этапе компиляции как comptime_float, а expectApproxEqAbs два таких значения сравнивать отказывается: ему нужен настоящий тип с плавающей точкой. Это не придирка, а напоминание, что литералы в Zig не имеют типа, пока ты его не назначил.

Локальность: временная и пространственная

Локальность

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

Временная локальность. К адресу, к которому обратились только что, скорее всего обратятся снова в ближайшее время. Переменная-счётчик, аккумулятор суммы, вершина стека, тело цикла.

Пространственная локальность. Если обратились к адресу, скорее всего обратятся к его соседям. Следующий элемент массива, следующее поле структуры, следующая инструкция.

Обе формы кэш эксплуатирует напрямую. Временную тем, что хранит недавно использованные данные и не выбрасывает их сразу. Пространственную тем, что приносит из памяти не байт, а линию: те самые 64 байта, которые DDR5 отдаёт одним пакетом. Если из линии понадобился один байт, остальные 63 приехали бесплатно, и вопрос только в том, воспользуется ли ими программа.

Ниже простейший цикл, и в нём есть обе формы сразу.

fn sumVec(v: []const i64) i64 {
    var sum: i64 = 0;
    for (v) |x| sum += x;
    return sum;
}

Переменная sum читается и пишется на каждой итерации: временная локальность в данных (компилятор, впрочем, держит её в регистре, и до памяти она не доходит, об этом ниже). Элементы v читаются по порядку, каждый следующий на 8 байт дальше предыдущего: пространственная локальность в данных. Тело цикла выполняется v.len раз: временная локальность в инструкциях. Инструкции тела лежат в памяти подряд: пространственная локальность в инструкциях.

Шаг обращения

Для пространственной локальности есть простая мера:

шаг обращения

(stride). Цикл sumVec идёт с шагом 1: обращения к соседним элементам. Линия в 64 байта вмещает восемь i64, значит один поход в память обслуживает восемь итераций. Обход с шагом 8 берёт из каждой линии ровно один элемент, и каждая итерация это отдельный поход. Шаг 8 при тех же операциях делает в восемь раз больше работы для памяти. Чем меньше шаг, тем выше пространственная локальность, и шаг 1 это лучшее, что бывает.

Порядок вложенных циклов задаёт шаг неявно, и это самая частая причина плохой локальности в коде, который выглядит правильно. Матрица в памяти лежит по строкам: элемент m[i][j] находится по смещению i * cols + j. Внешний цикл по i, внутренний по j дают шаг 1. Поменяй циклы местами, и шаг станет равен длине строки. Сумма та же, обращений столько же, а трасса другая, и ниже мы её увидим.

Читаем локальность по коду

Навык, ради которого написан этот раздел: посмотреть на цикл и до запуска сказать, какой у него шаг. Две задачи книги на этот навык, переформулированные.

Трёхмерный массив. Дана функция, суммирующая куб n на n на n:

fn sumArray3d(a: []const [16][16]i32) i64 {
    var sum: i64 = 0;
    for (0..16) |k| {
        for (0..16) |i| {
            for (0..16) |j| {
                sum += a[i][j][k];
            }
        }
    }
    return sum;
}

На первый взгляд всё в порядке: k это последний индекс, соседние k лежат рядом, и цикл по k в функции есть. Но внутренний цикл здесь по j, а не по k. Обращение идёт к a[i][j][k], в памяти это смещение (i * 16 + j) * 16 + k: цикл по k менял бы адрес на один элемент за итерацию, цикл по j на 16. Значит шаг 16 элементов, 64 байта: одна линия на обращение. Чтобы получить шаг 1, циклы нужно переставить в порядок i, j, k снаружи внутрь: самый быстрый цикл по последнему индексу. Правило общее: в массиве, лежащем по строкам, внутренний цикл должен идти по последнему индексу.

Массив структур. У каждой частицы три координаты скорости и три ускорения:

const Particle = struct { vel: [3]f32, acc: [3]f32 };

Три способа обнулить их у всех частиц.

fn clearA(ps: []Particle) void {
    for (ps) |*p| {
        p.vel = .{ 0, 0, 0 };
        p.acc = .{ 0, 0, 0 };
    }
}

fn clearB(ps: []Particle) void {
    for (ps) |*p| {
        for (0..3) |axis| {
            p.vel[axis] = 0;
            p.acc[axis] = 0;
        }
    }
}

fn clearC(ps: []Particle) void {
    for (0..3) |axis| {
        for (ps) |*p| {
            p.vel[axis] = 0;
            p.acc[axis] = 0;
        }
    }
}

clearA пишет 24 байта каждой структуры подряд, шаг 1 по байтам, лучшая локальность. clearB тоже проходит массив один раз, но внутри структуры прыгает: vel[0], acc[0], vel[1], acc[1]. Это прыжки на 12 байт внутри одной линии, кэш их почти не замечает, локальность чуть хуже. clearC проходит весь массив трижды, каждый раз трогая по два поля из шести: шаг 24 байта, и к каждой линии он возвращается через весь массив. Худший из трёх, и разница с первым тем больше, чем длиннее массив. Это тот самый обход, который в виджете ниже называется «массив структур, поле за полем».

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

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

Генератор трасс

Пока локальность это картинка в виджете. Сделаем её измеримой: научим обычную программу записывать каждое своё обращение к памяти. Формат возьмём готовый.

Трасса обращений

в формате инструмента lackey из valgrind выглядит так (снято на Linux x86-64 командой valgrind --tool=lackey --trace-mem=yes ./prog):

I  0400d7d4,8
 L 7ff000398,8
 S 7ff000390,8
 M 0421c7f0,4

Строка I это выборка инструкции, L чтение данных, S запись, M изменение (чтение и сразу запись по тому же адресу, как в x += 1). Дальше адрес в шестнадцатеричном виде и размер в байтах. Перед I пробела нет, перед остальными есть: так lackey отличает поток инструкций от потока данных, и симулятор кэша данных из урока про cachelab строки I пропускает.

Первый файл разбирает и печатает такие строки. Он маленький, но с ним мы будем работать четыре урока подряд, поэтому парсер честный: ошибки названы по месту, итератор помнит номер строки, пустые строки и комментарии с # пропускаются, чтобы трассу можно было подписать прямо в файле.

//! Трасса обращений к памяти в формате valgrind lackey.
//!
//! Каждая строка это одно обращение:
//!
//!   I  0400d7d4,8     выборка инструкции, кэш данных её не видит
//!    L 7ff000398,8    загрузка (load)
//!    S 7ff000390,8    сохранение (store)
//!    M 0421c7f0,4     модификация (modify): загрузка и сразу сохранение
//!
//! Адрес шестнадцатеричный, размер десятичный. Перед L, S и M lackey ставит
//! пробел, перед I нет; парсер принимает оба варианта и игнорирует пробелы.
//! Пустые строки и строки, начинающиеся с `#`, пропускаются: так удобно
//! подписывать эталонные трассы прямо в файле.

const std = @import("std");

/// Вид обращения. Значение это буква, которой оно записано в трассе.
pub const Kind = enum(u8) {
    instruction = 'I',
    load = 'L',
    store = 'S',
    modify = 'M',

    pub fn letter(kind: Kind) u8 {
        return @intFromEnum(kind);
    }

    /// Обращения к данным: всё, кроме выборки инструкций.
    pub fn isData(kind: Kind) bool {
        return kind != .instruction;
    }
};

/// Одна строка трассы.
pub const Entry = struct {
    kind: Kind,
    addr: u64,
    size: u32,

    pub fn load(addr: u64, size: u32) Entry {
        return .{ .kind = .load, .addr = addr, .size = size };
    }

    pub fn store(addr: u64, size: u32) Entry {
        return .{ .kind = .store, .addr = addr, .size = size };
    }

    pub fn modify(addr: u64, size: u32) Entry {
        return .{ .kind = .modify, .addr = addr, .size = size };
    }
};

pub const ParseError = error{
    BadKind,
    BadAddress,
    BadSize,
    MissingComma,
};

/// Разбирает одну строку. Пустая строка и комментарий дают `null`.
pub fn parseLine(line: []const u8) ParseError!?Entry {
    const trimmed = std.mem.trim(u8, line, " \t\r");
    if (trimmed.len == 0 or trimmed[0] == '#') return null;

    const kind = std.enums.fromInt(Kind, trimmed[0]) orelse return error.BadKind;
    const rest = std.mem.trimStart(u8, trimmed[1..], " \t");
    const comma = std.mem.indexOfScalar(u8, rest, ',') orelse return error.MissingComma;

    const addr = std.fmt.parseInt(u64, rest[0..comma], 16) catch return error.BadAddress;
    const size_text = std.mem.trim(u8, rest[comma + 1 ..], " \t");
    const size = std.fmt.parseInt(u32, size_text, 10) catch return error.BadSize;

    return .{ .kind = kind, .addr = addr, .size = size };
}

/// Построчный обход текста трассы. Помнит номер строки, чтобы ошибку можно
/// было показать пользователю с указанием места.
pub const Iterator = struct {
    lines: std.mem.SplitIterator(u8, .scalar),
    /// Номер последней прочитанной строки, с единицы.
    line_no: usize = 0,

    pub fn init(text: []const u8) Iterator {
        return .{ .lines = std.mem.splitScalar(u8, text, '\n') };
    }

    /// Следующее обращение или `null` в конце текста.
    pub fn next(it: *Iterator) ParseError!?Entry {
        while (it.lines.next()) |line| {
            it.line_no += 1;
            if (try parseLine(line)) |entry| return entry;
        }
        return null;
    }
};

/// Разбирает трассу целиком. Выборки инструкций остаются в результате:
/// решать, что с ними делать, будет тот, кто трассу проигрывает.
pub fn parse(gpa: std.mem.Allocator, text: []const u8) ![]Entry {
    var entries: std.ArrayList(Entry) = .empty;
    errdefer entries.deinit(gpa);

    var it: Iterator = .init(text);
    while (try it.next()) |entry| try entries.append(gpa, entry);
    return entries.toOwnedSlice(gpa);
}

/// Печатает одно обращение так, как это делает lackey.
pub fn writeEntry(w: *std.Io.Writer, entry: Entry) std.Io.Writer.Error!void {
    // Перед выборкой инструкции пробела нет, перед обращением к данным есть.
    if (entry.kind != .instruction) try w.writeByte(' ');
    try w.print("{c} {x},{d}\n", .{ entry.kind.letter(), entry.addr, entry.size });
}

/// Печатает трассу целиком.
pub fn write(w: *std.Io.Writer, entries: []const Entry) std.Io.Writer.Error!void {
    for (entries) |entry| try writeEntry(w, entry);
}

/// Трасса в виде строки, для тестов и файлов.
pub fn format(gpa: std.mem.Allocator, entries: []const Entry) ![]u8 {
    var out: std.Io.Writer.Allocating = .init(gpa);
    defer out.deinit();
    try write(&out.writer, entries);
    return out.toOwnedSlice();
}

test "разбор строк всех четырёх видов" {
    try std.testing.expectEqual(Entry{ .kind = .instruction, .addr = 0x0400d7d4, .size = 8 }, (try parseLine("I  0400d7d4,8")).?);
    try std.testing.expectEqual(Entry.load(0x10, 1), (try parseLine(" L 10,1")).?);
    try std.testing.expectEqual(Entry.store(0x18, 4), (try parseLine("S 18,4")).?);
    try std.testing.expectEqual(Entry.modify(0x7ff000398, 8), (try parseLine(" M 7ff000398,8\r")).?);
}

test "пустые строки и комментарии пропускаются" {
    try std.testing.expectEqual(null, try parseLine(""));
    try std.testing.expectEqual(null, try parseLine("   "));
    try std.testing.expectEqual(null, try parseLine("# hits:4 misses:5"));
}

test "ошибки разбора названы по месту" {
    try std.testing.expectError(error.BadKind, parseLine(" X 10,1"));
    try std.testing.expectError(error.MissingComma, parseLine(" L 10"));
    try std.testing.expectError(error.BadAddress, parseLine(" L zz,1"));
    try std.testing.expectError(error.BadSize, parseLine(" L 10,"));
}

test "печать и разбор обратны друг другу" {
    const entries = [_]Entry{
        .{ .kind = .instruction, .addr = 0x400, .size = 4 },
        .load(0x10, 1),
        .modify(0x20, 8),
        .store(0xff00, 2),
    };
    const text = try format(std.testing.allocator, &entries);
    defer std.testing.allocator.free(text);
    try std.testing.expectEqualStrings("I 400,4\n L 10,1\n M 20,8\n S ff00,2\n", text);

    const back = try parse(std.testing.allocator, text);
    defer std.testing.allocator.free(back);
    try std.testing.expectEqualSlices(Entry, &entries, back);
}

test "итератор считает строки, включая пустые" {
    var it: Iterator = .init("\n L 10,1\n\n# note\n S 18,1\n");
    _ = try it.next();
    try std.testing.expectEqual(@as(usize, 2), it.line_no);
    _ = try it.next();
    try std.testing.expectEqual(@as(usize, 5), it.line_no);
    try std.testing.expectEqual(null, try it.next());
}

$ zig test trace.zig
1/5 trace.test.разбор строк всех четырёх видов...OK
2/5 trace.test.пустые строки и комментарии пропускаются...OK
3/5 trace.test.ошибки разбора названы по месту...OK
4/5 trace.test.печать и разбор обратны друг другу...OK
5/5 trace.test.итератор считает строки, включая пустые...OK
All 5 tests passed.

Две мелочи, на которые стоит посмотреть. Kind объявлен как enum(u8) со значениями-буквами, поэтому буква из файла превращается в вид обращения одним вызовом std.enums.fromInt, а обратно одним @intFromEnum. И format собирает текст через std.Io.Writer.Allocating: это тот же интерфейс Writer, что у стандартного вывода, только пишет в растущий буфер. Одна функция write обслуживает и файл, и строку для теста.

Обёртка, которая записывает обращения

Теперь сам генератор. Идея такая: обращения к массиву идут не напрямую, а через обёртку Traced(T). Она выполняет чтение или запись по-настоящему и заодно записывает адрес и размер в Tracer. Получается та же трасса, что снял бы lackey, но без инструкций и без обращений к локальным переменным, которые компилятор всё равно держит в регистрах: только массивы, только то, что нас интересует.

Адреса в трассе виртуальные. У каждого массива есть base, который задаёт программа, и адрес элемента считается как base + index * @sizeOf(T). Настоящий адрес буфера в трассу не попадает нарочно: тогда она не зависит от того, куда аллокатор положил данные, и число промахов при проигрывании воспроизводится байт в байт на любой машине.

//! Генератор трасс из Zig-программы.
//!
//! Идея: обращения к массиву идут не напрямую, а через обёртку `Traced(T)`,
//! которая выполняет чтение или запись по-настоящему и заодно записывает
//! адрес и размер обращения в `Tracer`. Получается та же трасса, что снял бы
//! valgrind, только без инструкций и без обращений к локальным переменным,
//! которые компилятор всё равно держит в регистрах.
//!
//! Адреса в трассе виртуальные: у каждого массива свой `base`, который
//! задаёт программа. Так трасса не зависит от того, куда аллокатор положил
//! данные, и число промахов воспроизводится байт в байт.

const std = @import("std");
const trace = @import("trace.zig");

pub const Tracer = struct {
    gpa: std.mem.Allocator,
    entries: std.ArrayList(trace.Entry) = .empty,
    /// Сколько обращений не удалось записать из-за нехватки памяти.
    dropped: usize = 0,

    pub fn init(gpa: std.mem.Allocator) Tracer {
        return .{ .gpa = gpa };
    }

    pub fn deinit(t: *Tracer) void {
        t.entries.deinit(t.gpa);
        t.* = undefined;
    }

    /// Обёртки над массивами возвращают значения, а не ошибки, поэтому
    /// нехватка памяти здесь только считается; `slice` её потом покажет.
    pub fn record(t: *Tracer, kind: trace.Kind, addr: u64, size: u32) void {
        const entry: trace.Entry = .{ .kind = kind, .addr = addr, .size = size };
        t.entries.append(t.gpa, entry) catch {
            t.dropped += 1;
        };
    }

    pub fn slice(t: *const Tracer) error{OutOfMemory}![]const trace.Entry {
        if (t.dropped > 0) return error.OutOfMemory;
        return t.entries.items;
    }

    pub fn count(t: *const Tracer, kind: trace.Kind) usize {
        var n: usize = 0;
        for (t.entries.items) |entry| {
            if (entry.kind == kind) n += 1;
        }
        return n;
    }

    pub fn write(t: *const Tracer, w: *std.Io.Writer) !void {
        try trace.write(w, try t.slice());
    }
};

/// Массив элементов T, каждое обращение к которому попадает в трассу.
pub fn Traced(comptime T: type) type {
    return struct {
        const Self = @This();

        items: []T,
        /// Виртуальный адрес нулевого элемента в трассе.
        base: u64,
        tracer: *Tracer,

        pub fn init(tracer: *Tracer, base: u64, items: []T) Self {
            return .{ .items = items, .base = base, .tracer = tracer };
        }

        pub fn addrOf(self: Self, index: usize) u64 {
            return self.base + index * @sizeOf(T);
        }

        pub fn get(self: Self, index: usize) T {
            self.tracer.record(.load, self.addrOf(index), @sizeOf(T));
            return self.items[index];
        }

        pub fn set(self: Self, index: usize, value: T) void {
            self.tracer.record(.store, self.addrOf(index), @sizeOf(T));
            self.items[index] = value;
        }

        /// `x[i] += v`: одно обращение вида M, как его видит lackey.
        pub fn add(self: Self, index: usize, value: T) void {
            self.tracer.record(.modify, self.addrOf(index), @sizeOf(T));
            self.items[index] += value;
        }

        /// Чтение одного поля структуры: адрес и размер только у этого поля.
        pub fn getField(self: Self, index: usize, comptime field: []const u8) @FieldType(T, field) {
            const addr = self.addrOf(index) + @offsetOf(T, field);
            self.tracer.record(.load, addr, @sizeOf(@FieldType(T, field)));
            return @field(self.items[index], field);
        }

        pub fn setField(self: Self, index: usize, comptime field: []const u8, value: @FieldType(T, field)) void {
            const addr = self.addrOf(index) + @offsetOf(T, field);
            self.tracer.record(.store, addr, @sizeOf(@FieldType(T, field)));
            @field(self.items[index], field) = value;
        }
    };
}

/// Матрица rows на cols поверх трассируемого массива, построчно (row-major),
/// как двумерный массив в C: элемент (i, j) лежит по индексу i*cols + j.
pub fn Matrix(comptime T: type) type {
    return struct {
        const Self = @This();

        data: Traced(T),
        rows: usize,
        cols: usize,

        pub fn init(tracer: *Tracer, base: u64, items: []T, rows: usize, cols: usize) Self {
            std.debug.assert(items.len == rows * cols);
            return .{ .data = .init(tracer, base, items), .rows = rows, .cols = cols };
        }

        pub fn index(self: Self, i: usize, j: usize) usize {
            return i * self.cols + j;
        }

        pub fn get(self: Self, i: usize, j: usize) T {
            return self.data.get(self.index(i, j));
        }

        pub fn set(self: Self, i: usize, j: usize, value: T) void {
            self.data.set(self.index(i, j), value);
        }

        pub fn add(self: Self, i: usize, j: usize, value: T) void {
            self.data.add(self.index(i, j), value);
        }

        /// Прямой доступ без трассы: заполнить матрицу перед прогоном или
        /// проверить результат после.
        pub fn at(self: Self, i: usize, j: usize) *T {
            return &self.data.items[self.index(i, j)];
        }
    };
}

/// Сумма по строкам: внутренний цикл идёт вдоль строки, шаг между
/// соседними обращениями равен размеру элемента.
pub fn sumRows(m: Matrix(i32)) i64 {
    var sum: i64 = 0;
    var i: usize = 0;
    while (i < m.rows) : (i += 1) {
        var j: usize = 0;
        while (j < m.cols) : (j += 1) sum += m.get(i, j);
    }
    return sum;
}

/// Сумма по столбцам: те же обращения, но шаг между соседними равен
/// длине строки, и пространственная локальность пропадает.
pub fn sumCols(m: Matrix(i32)) i64 {
    var sum: i64 = 0;
    var j: usize = 0;
    while (j < m.cols) : (j += 1) {
        var i: usize = 0;
        while (i < m.rows) : (i += 1) sum += m.get(i, j);
    }
    return sum;
}

/// Обход массива с шагом: `count` чтений с индексами 0, stride, 2*stride ...
pub fn strideWalk(x: Traced(i64), stride: usize, count: usize) i64 {
    var sum: i64 = 0;
    var k: usize = 0;
    while (k < count) : (k += 1) sum += x.get(k * stride);
    return sum;
}

/// Сколько разных блоков по 2^b байт затронула трасса: мера пространственной
/// локальности. Чем меньше блоков на то же число обращений, тем она выше.
pub fn distinctBlocks(gpa: std.mem.Allocator, entries: []const trace.Entry, b: u6) !usize {
    var seen: std.AutoHashMapUnmanaged(u64, void) = .empty;
    defer seen.deinit(gpa);
    for (entries) |entry| {
        if (!entry.kind.isData()) continue;
        try seen.put(gpa, entry.addr >> b, {});
    }
    return seen.count();
}

test "обёртка пишет адрес и размер каждого обращения" {
    var tracer: Tracer = .init(std.testing.allocator);
    defer tracer.deinit();

    var items = [_]i32{ 1, 2, 3, 4 };
    const x: Traced(i32) = .init(&tracer, 0x1000, &items);
    try std.testing.expectEqual(@as(i32, 3), x.get(2));
    x.set(0, 10);
    x.add(1, 5);
    try std.testing.expectEqual(@as(i32, 7), items[1]);

    const expected = [_]trace.Entry{ .load(0x1008, 4), .store(0x1000, 4), .modify(0x1004, 4) };
    try std.testing.expectEqualSlices(trace.Entry, &expected, try tracer.slice());
}

test "поля структуры пишутся по своим смещениям" {
    const Pixel = extern struct { r: u8, g: u8, b: u8, a: u8 };
    var tracer: Tracer = .init(std.testing.allocator);
    defer tracer.deinit();

    var items = [_]Pixel{.{ .r = 0, .g = 0, .b = 0, .a = 0 }} ** 2;
    const p: Traced(Pixel) = .init(&tracer, 0x100, &items);
    p.setField(1, "b", 7);
    try std.testing.expectEqual(@as(u8, 7), p.getField(1, "b"));
    const expected = [_]trace.Entry{ .store(0x106, 1), .load(0x106, 1) };
    try std.testing.expectEqualSlices(trace.Entry, &expected, try tracer.slice());
}

$ zig test gen.zig
1/7 gen.test.обёртка пишет адрес и размер каждого обращения...OK
2/7 gen.test.поля структуры пишутся по своим смещениям...OK
3/7 trace.test.разбор строк всех четырёх видов...OK
4/7 trace.test.пустые строки и комментарии пропускаются...OK
5/7 trace.test.ошибки разбора названы по месту...OK
6/7 trace.test.печать и разбор обратны друг другу...OK
7/7 trace.test.итератор считает строки, включая пустые...OK
All 7 tests passed.

Тестов семь, а не два: gen.zig импортирует trace.zig, и zig test подхватывает тесты обоих файлов.

Разберём, что здесь сделано и почему.

Tracer.record не возвращает ошибку. Это осознанное решение: Traced(T).get возвращает значение элемента, и если бы запись в трассу могла провалиться, каждое чтение массива пришлось бы обвешивать try, а код обхода перестал бы быть похожим на обычный код обхода. Вместо этого нехватка памяти считается в dropped, а slice отказывается отдавать неполную трассу. Ошибка не потеряна, она просто отложена до того момента, когда её удобно обработать.

getField и setField записывают обращение не ко всей структуре, а к одному полю: адрес это адрес элемента плюс @offsetOf(T, field), размер это размер поля. Так трасса clearC из прошлого раздела покажет прыжки по 24 байта и обращения по 12, ровно как в железе. Поле выбирается на этапе компиляции, поэтому обёртка ничего не стоит по сравнению с прямым доступом.

Matrix(T) лежит по строкам: элемент (i, j) это индекс i * cols + j, как двумерный массив в C или срез срезов в Zig, уложенный в один буфер. at даёт прямой доступ без трассы, чтобы заполнить матрицу перед прогоном и не засорять трассу подготовкой.

distinctBlocks это первая мера локальности по трассе: сколько разных блоков по 2^b байт задето. При b = 6 блок это 64 байта, линия кэша. Функция сдвигает адрес вправо на b бит и складывает в множество, а std.AutoHashMapUnmanaged(u64, void) это и есть множество: значение пустое, аллокатор приходит в каждый вызов.

Локальность в трассе

Собираем всё в программу, которая обходит один массив с шагом 1 и с шагом 8, суммирует одну матрицу по строкам и по столбцам, и для каждого обхода считает две меры. Первая уже есть, это distinctBlocks. Вторая новая: сколько раз подряд идущие обращения попали в разные блоки. Число блоков говорит, сколько памяти задето, число переключений говорит, в каком порядке. Одну и ту же матрицу оба обхода задевают целиком, разница между ними только в порядке, и первая мера её не увидит.

//! Локальность видна в трассе: один и тот же массив обходится с шагом 1
//! и с шагом 8, одна и та же матрица суммируется по строкам и по столбцам.
//! Программа печатает трассы обращений в формате lackey и считает, сколько
//! блоков по 64 байта задело каждое из них.
//!
//!   zig run walk.zig
//!   zig run walk.zig -- --trace stride8 > stride8.trace

const std = @import("std");
const gen = @import("gen.zig");
const trace = @import("trace.zig");

const Tracer = gen.Tracer;

/// Что напечатать: короткий отчёт или полную трассу одного обхода.
const Mode = union(enum) { report, dump: []const u8 };

fn parseMode(args: []const []const u8) !Mode {
    if (args.len == 1) return .report;
    if (args.len == 3 and std.mem.eql(u8, args[1], "--trace")) return .{ .dump = args[2] };
    std.debug.print("usage: walk [--trace stride1|stride8|rows|cols]\n", .{});
    return error.BadUsage;
}

/// Сколько раз подряд идущие обращения попали в разные блоки по 2^b байт.
/// Число блоков говорит, сколько памяти задето, а число переключений
/// говорит, в каком порядке: это и есть пространственная локальность.
fn blockSwitches(entries: []const trace.Entry, b: u6) usize {
    var switches: usize = 0;
    var previous: ?u64 = null;
    for (entries) |entry| {
        const block = entry.addr >> b;
        if (previous != null and previous.? != block) switches += 1;
        previous = block;
    }
    return switches;
}

/// Один обход: имя, трасса, число блоков по 64 байта и переключений между ними.
const Walk = struct {
    name: []const u8,
    tracer: Tracer,
    blocks: usize,
    switches: usize,

    fn deinit(self: *Walk) void {
        self.tracer.deinit();
    }
};

const n = 16;
const stride = 8;
const side = 16;

fn walks(gpa: std.mem.Allocator) ![4]Walk {
    // Один и тот же буфер под все четыре обхода: важен не он, а адреса.
    var xs: [n * stride]i64 = undefined;
    for (&xs, 0..) |*x, i| x.* = @intCast(i);
    var cells: [side * side]i32 = undefined;
    for (&cells, 0..) |*c, i| c.* = @intCast(i);

    var out: [4]Walk = undefined;
    inline for (.{ "stride1", "stride8", "rows", "cols" }, 0..) |name, k| {
        var tracer: Tracer = .init(gpa);
        errdefer tracer.deinit();
        const x: gen.Traced(i64) = .init(&tracer, 0x10000, &xs);
        const m: gen.Matrix(i32) = .init(&tracer, 0x20000, &cells, side, side);
        const sum: i64 = switch (k) {
            0 => gen.strideWalk(x, 1, n),
            1 => gen.strideWalk(x, stride, n),
            2 => gen.sumRows(m),
            3 => gen.sumCols(m),
            else => unreachable,
        };
        std.debug.assert(sum >= 0);
        const entries = try tracer.slice();
        out[k] = .{
            .name = name,
            .tracer = tracer,
            .blocks = try gen.distinctBlocks(gpa, entries, 6),
            .switches = blockSwitches(entries, 6),
        };
    }
    return out;
}

pub fn main(init: std.process.Init) !void {
    const gpa = init.gpa;
    const args = try init.minimal.args.toSlice(init.arena.allocator());
    const mode = try parseMode(args);

    var all = try walks(gpa);
    defer for (&all) |*w| w.deinit();

    var buf: [4096]u8 = undefined;
    var stdout = std.Io.File.stdout().writer(init.io, &buf);
    const w = &stdout.interface;

    switch (mode) {
        .dump => |name| {
            for (&all) |*walk| {
                if (std.mem.eql(u8, walk.name, name)) try walk.tracer.write(w);
            }
        },
        .report => {
            try w.writeAll("обход     обращений   блоков  переключений\n");
            for (&all) |*walk| {
                const loads = walk.tracer.count(.load);
                try w.print("{s:<8} {d:>10} {d:>8} {d:>13}\n", .{ walk.name, loads, walk.blocks, walk.switches });
            }
        },
    }
    try w.flush();
}

$ zig run walk.zig
обход     обращений   блоков  переключений
stride1          16        2             1
stride8          16       16            15
rows            256       16            15
cols            256       16           255

Читаем таблицу. Шестнадцать чтений i64 с шагом 1 это 128 байт, два блока, одно переключение между ними: из каждого блока взяты все восемь элементов. Те же шестнадцать чтений с шагом 8 задевают шестнадцать блоков, по одному элементу из каждого, и переключаются на каждом шаге. Память сделала в восемь раз больше работы за тот же результат.

Матрица 16 на 16 из i32 занимает 1024 байта, шестнадцать блоков, и строка матрицы это ровно один блок. Обход по строкам переключает блок пятнадцать раз, на границах строк. Обход по столбцам переключает его на каждом обращении, 255 раз, потому что соседние по времени элементы лежат в соседних строках, через 64 байта. Число задетых блоков одинаковое, и это важно: пространственная локальность это не про то, сколько памяти тронули, а про то, в каком порядке.

Теперь сама трасса. Первые строки обхода с шагом 1 и с шагом 8:

$ zig run walk.zig -- --trace stride1 | head -4
 L 10000,8
 L 10008,8
 L 10010,8
 L 10018,8
$ zig run walk.zig -- --trace stride8 | head -4
 L 10000,8
 L 10040,8
 L 10080,8
 L 100c0,8

Адреса в первой трассе идут через 8, во второй через 0x40, то есть через 64 байта: ровно по блоку за шаг. И то же для матрицы:

$ zig run walk.zig -- --trace rows | head -4
 L 20000,4
 L 20004,4
 L 20008,4
 L 2000c,4
$ zig run walk.zig -- --trace cols | head -4
 L 20000,4
 L 20040,4
 L 20080,4
 L 200c0,4

Шаг обращения, который до сих пор был словами, стал разностью двух соседних чисел в файле. Сохрани эти четыре трассы в файлы той же командой с перенаправлением вывода, как в шапке walk.zig. Через два урока ты напишешь симулятор кэша, который прочитает их и назовёт точное число промахов для каждого. А для генератора нужна ещё одна деталь, которая появится вместе с симулятором: вместо того чтобы копить шесть миллионов строк трассы умножения матриц в памяти, Tracer сможет сразу скармливать каждое обращение кэшу.

Пара слов о Zig в walk.zig. inline for по кортежу строк разворачивается на этапе компиляции в четыре копии тела, и switch (k) внутри тоже сворачивается до одной ветки в каждой копии: имён обходов в собранной программе четыре, а таблицы диспетчеризации нет. Mode это тегированное объединение, и switch (mode) обязан разобрать обе ветки: забыть про .dump компилятор не даст. Список аргументов приходит через init.minimal.args.toSlice в арене, как в уроке про comptime и сборку.

Локальность инструкций

Всё это время мы говорили про данные. У инструкций локальность та же, и увидеть её проще всего в ассемблере. Возьмём две функции: обход с шагом 1 и обход с шагом stride.

//! Локальность инструкций: тело цикла лежит в памяти подряд и выполняется
//! много раз. `export fn` нужен, чтобы функцию не встроили и не убрали.
//!
//!   zig build-obj sum_asm.zig -O ReleaseSmall -femit-asm=sum_asm.s -fno-emit-bin -target x86_64-linux

export fn sum(xs: [*]const i64, n: usize) i64 {
    var total: i64 = 0;
    var i: usize = 0;
    while (i < n) : (i += 1) total +%= xs[i];
    return total;
}

export fn sumStride(xs: [*]const i64, n: usize, stride: usize) i64 {
    var total: i64 = 0;
    var i: usize = 0;
    while (i < n) : (i += 1) total +%= xs[i * stride];
    return total;
}

Собираем в ReleaseSmall, чтобы цикл остался циклом: в ReleaseFast компилятор развернёт его в восемь сложений на итерацию, и разбирать пришлось бы вдвое больше строк, а суть та же. Целевая платформа x86-64 Linux, синтаксис Intel, служебные директивы убраны.

sum:
        push    rbp
        mov     rbp, rsp
        xor     eax, eax
        xor     ecx, ecx
.LBB1_1:
        cmp     rsi, rcx
        je      .LBB1_3
        add     rax, qword ptr [rdi + 8*rcx]
        inc     rcx
        jmp     .LBB1_1
.LBB1_3:
        pop     rbp
        ret

sumStride:
        push    rbp
        mov     rbp, rsp
        shl     rdx, 3
        xor     eax, eax
.LBB0_1:
        sub     rsi, 1
        jb      .LBB0_3
        add     rax, qword ptr [rdi]
        add     rdi, rdx
        jmp     .LBB0_1
.LBB0_3:
        pop     rbp
        ret

Тело цикла sum это пять инструкций между .LBB1_1 и jmp, они лежат в памяти подряд и занимают меньше двадцати байт. Первая же выборка приносит всю эту линию в кэш инструкций, и следующие n итераций берут инструкции из неё: пространственная локальность в том, что они соседи, временная в том, что они повторяются. Прямолинейный код без циклов имеет только первую форму, код с прыжками по большому switch или по таблице виртуальных вызовов теряет и её.

Теперь посмотри, чего в ассемблере нет: обращений к total и i. Оба живут в rax и rcx, и в память ни разу не попадают. Это ответ на вопрос, почему Tracer из прошлого раздела не пишет обращения к локальным переменным: в собранной программе их тоже нет. Трасса lackey такие обращения покажет только в Debug, где компилятор честно кладёт каждую переменную на стек, и потому трассы отладочной и оптимизированной сборки одной программы различаются в разы. Когда будешь сравнивать свою трассу с чужой, сначала проверь, из какой сборки она снята.

И ещё одно различие между двумя функциями. В sum адрес считается на лету, [rdi + 8*rcx], а в sumStride компилятор заранее умножил шаг на восемь (shl rdx, 3) и прибавляет его к указателю. Для процессора это одинаково дёшево. Для памяти нет: sum идёт по линии, sumStride при stride >= 8 промахивается каждый раз. Одинаковые по числу инструкций циклы могут различаться по времени в разы, и ассемблер этой разницы не показывает. Её показывает трасса.

Практика

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

Сложи trace.zig, gen.zig и walk.zig в один каталог, прогони zig test trace.zig, zig test gen.zig и zig run walk.zig. Числа должны сойтись с таблицей выше.
Сохрани четыре трассы в файлы: stride1.trace, stride8.trace, rows.trace, cols.trace. В уроке про cachelab они станут первыми входами симулятора.
Добавь в walk.zig пятый обход: x[i] += 1 для каждого элемента через Traced.add. Убедись, что в трассе появились строки M, и посчитай, сколько блоков и переключений даёт этот обход с шагом 1 и с шагом 8.
Подпиши каждую трассу комментарием в первой строке: что за обход, какой шаг, сколько блоков ты ожидаешь. Парсер такие строки пропускает, а тебе через два урока будет с чем сверять.

Упражнения

CHK-1★

Ценовая колонка таблицы это порядок величины, но её тренд считается. Возьми DRAM по 4 доллара за гигабайт и предположи, что цена падает вдвое каждые пять лет, как в среднем за последние двадцать. Через сколько лет петабайт DRAM будет стоить тысячу долларов? Тот же вопрос для SSD по 10 центов и для диска по 2 цента при тех же темпах. Потом найди, какой была цена за гигабайт DRAM в 2021 году, и объясни, почему такая экстраполяция ненадёжна на горизонте в пять лет, хотя работает на горизонте в тридцать.

CHK-2★★

Перепиши sumArray3d из урока так, чтобы внутренний цикл шёл с шагом 1, а потом докажи это трассой: заведи Traced(i32) на 16 умножить на 16 умножить на 16 элементов, обходи его через get по индексу (i * 16 + j) * 16 + k в обоих порядках циклов и посчитай distinctBlocks и переключения блоков для каждого. Ответь на вопрос: почему число задетых блоков одинаковое, а число переключений различается в шестнадцать раз?

CHK-3★★

Три функции обнуления clearA, clearB, clearC перепиши поверх Traced(Particle) через setField (обнуляй по одной координате, чтобы обращения были по 4 байта) и сними три трассы для 64 частиц. Посчитай для каждой число блоков по 64 байта и число переключений и расставь функции по локальности. Совпал ли порядок с тем, что ты ожидал по коду? Обрати внимание на clearB: переключений у неё больше, чем у clearA, а блоков столько же. Объясни, почему кэш эту разницу почти не заметит.

CHK-4★★★

Массив это лучший случай локальности, связный список худший. Заведи узлы struct { value: i64, next: usize } в одном Traced массиве и обойди список по next через getField двумя способами: узлы лежат в порядке обхода (next равен index + 1) и узлы перемешаны случайной перестановкой. Сними обе трассы для 512 узлов и посчитай блоки и переключения. Потом уменьши узел до struct { value: i32, next: u32 } и повтори. Сформулируй, что даёт больший выигрыш: порядок узлов в памяти или их размер, и почему.

CHK-5★★

Повтори расчёт чтения мегабайта для SSD: время чтения одной страницы 4 КБ возьми 60 мкс, последовательную пропускную способность 12 ГБ/с. Сколько занимает мегабайт подряд и сколько 256 случайных страниц, если накопитель выполняет их по одной? Настоящий NVMe-накопитель держит в очереди сотни запросов одновременно и отвечает на 256 случайных чтений быстрее, чем за 256 умножить на 60 мкс. Найди в спецификации любого накопителя число операций в секунду при случайном чтении и посчитай, сколько запросов в среднем находится в работе одновременно.

CHK-6★★

Добавь к Tracer выборки инструкций. Заведи в walk.zig условный адрес начала тела цикла и перед каждым обращением к данным записывай I для каждой из пяти инструкций тела с их адресами, как в ассемблере sum (длины инструкций возьми из -femit-asm с ключом -fno-emit-bin, или примерно по 3 байта). Посчитай отдельно для инструкций и для данных, сколько блоков задето и сколько переключений, и объясни, почему кэш инструкций у настоящих процессоров отделён от кэша данных, хотя формат обращений у них один.

Итоги

Память программы собрана из четырёх технологий: SRAM в кэшах, DRAM в модулях, флеш в SSD, магнитный диск. Между соседями примерно два порядка по задержке и один по цене, отсюда лесенка вместо одной памяти на всё.
SRAM это шесть транзисторов на бит, без обновления и почти без задержки. DRAM это конденсатор и транзистор: плотнее в разы, но чтение разрушает бит, а строки нужно обновлять каждые 64 миллисекунды.
Чип DRAM это матрица строк и столбцов, адрес подаётся в два приёма по одним выводам, и открытая строка в буфере делает соседние обращения дешёвыми. DDR5 отдаёт данные пакетами по 64 байта, ровно по линии кэша, а его задержка не менялась со времён DDR2: росла только пропускная способность.
Флеш нельзя перезаписать на месте: страницы пишутся в чистые места, блоки стираются целиком, FTL раскладывает записи равномерно. Ресурс записи считается из TBW: 1200 ТБ это 164 года при 20 ГБ в день и двое суток при записи на полной скорости.
Время доступа к диску это поиск плюс полоборота плюс передача, и передача в нём меньше десятой доли процента. Мегабайт подряд читается за 12 мс, тот же мегабайт вразброс за 2.6 секунды.
Одно ожидание DRAM стоит около 320 тактов на 4 ГГц, SSD четверть миллиона, диск десятки миллионов. Поэтому производительность определяется тем, как часто программа промахивается мимо кэша, а это свойство программы.
Локальность бывает временная (тот же адрес снова) и пространственная (соседний адрес), и обе есть в данных и в инструкциях. Шаг обращения это мера пространственной локальности: шаг 1 берёт из линии все элементы, шаг в линию берёт один.
Порядок вложенных циклов задаёт шаг: в массиве, лежащем по строкам, внутренний цикл должен идти по последнему индексу. Массив структур, обходимый поле за полем, теряет локальность, потому что возвращается к каждой линии через весь массив.
Обёртка Traced(T) превращает обычную программу в генератор трассы формата lackey: вид обращения, адрес, размер. Адреса виртуальные, поэтому трасса воспроизводима. По трассе считаются две меры: число задетых блоков и число переключений между блоками, и вторая видит порядок там, где первая слепа.
Компилятор держит локальные переменные в регистрах, поэтому в трассе оптимизированной сборки их нет, а трасса Debug той же программы длиннее в разы. Тело цикла лежит в памяти подряд и повторяется: это локальность инструкций.

Дальше

Сегодня иерархия памяти была четырьмя технологиями и таблицей, а локальность свойством программы, которое видно в трассе. В следующем уроке между ними встанет кэш, и начнётся математика: адрес разделится на тег, индекс набора и смещение в блоке, три параметра S, E и B опишут любой кэш от учебного на четыре строки до L1 Apple M-серии, а промахи разложатся на три вида. Ты научишься по адресу сказать, в какой набор он попадёт, посчитаешь конфликтные промахи кэша прямого отображения на массиве из восьми элементов и разберёшь, чем ассоциативность их лечит и чего это стоит. Трассы, которые ты сохранил сегодня, дождутся своего часа: через урок ты напишешь симулятор, который их прочитает и назовёт точное число промахов для каждой.

домашка

Домашка

Опиши одну и ту же таблицу частиц как массив структур и как структуру массивов, сними обе трассы генератором урока и посчитай, сколько блоков по 64 байта задевает обнуление одной координаты у всех частиц в каждом случае.S
Найди характеристики памяти своей машины (частота передачи, число каналов, ширина канала) и посчитай пиковую пропускную способность и время передачи одной линии по 64 байта; сравни с задержкой доступа и объясни, почему второе не следует из первого.S
Прогони программу обхода с шагом через valgrind lackey в контейнере Linux x86-64 и сравни его трассу с трассой Tracer: найди обращения, которые lackey видит, а Tracer нет, и объясни, откуда они.L