Раздел 32 · Системное программирование: Zig, ассемблер, Verilog
Гора памяти
открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти
Гора памяти
В прошлом уроке ты переставлял циклы умножения матриц, резал транспонирование на блоки и считал промахи в симуляторе. Каждый раз ответ был одним числом: столько-то промахов, во столько-то раз быстрее. Сегодня мы снимем не число, а ландшафт. Одна программа читает массив с разным размером и разным шагом, и из её замеров вырастает поверхность, на которой видно всё, что мы разбирали в уроках про иерархию памяти: границы L1 и L2 как обрывы, длину линии как излом склона, предвыборку как ровный хребет там, где по всем расчётам должен быть провал. Гору ты снимешь на своём железе, и в конце урока будешь читать по ней размеры кэшей, не заглядывая в документацию. А потом заглянешь и сверишь.
Цели урока
- Понять гору памяти как функцию двух аргументов: размер рабочего набора отвечает за временную локальность, шаг обхода за пространственную.
- Написать ядро замера на Zig и объяснить каждую его деталь: четыре аккумулятора,
noinline,doNotOptimizeAway, разогрев, повторы и минимум из попыток. - Знать, что ломает замер: сборка в
Debug, загруженная машина, чужое ядро, короткий цикл, и как каждую из этих поломок увидеть в числах. - Читать срез по размеру: находить обрывы программой и переводить их в размеры кэшей, а потом сверять с
sysctlиlscpu. - Читать срез по шагу: видеть длину линии и работу предвыборки, и объяснять, почему граница L2 не видна на шаге 1.
- Сравнить гору Core i7 Haswell из книги с горой Apple M4 Max и назвать, что у них общего, а что различается.
- Найти на горе всё из уроков про иерархию памяти: где на ней живут порядки циклов, блочное разбиение и симулятор кэша.
Идея: две ручки и одна функция
Если программа читает n байт за s секунд, её пропускная способность чтения равна n / s. Число само по себе мало что говорит: оно зависит от того, что именно читали и в каком порядке. Но если читать одно и то же в плотном цикле и менять только два параметра, пропускная способность превращается в измерительный прибор.
Первый параметр это размер рабочего набора: сколько байт мы читаем, прежде чем пойти по кругу. Пока рабочий набор влезает в L1, все чтения обслуживает L1. Когда он перестаёт влезать, каждое чтение по кругу вытесняет что-то, что понадобится на следующем круге, и обращения уходят в L2. Размер это ручка временной локальности.
Второй параметр это шаг: сколько слов мы пропускаем между двумя чтениями. Шаг 1 читает соседние слова, и одна линия кэша кормит восемь чтений подряд. Шаг 8 при линии в 64 байта трогает каждую линию ровно один раз. Шаг это ручка пространственной локальности.
Гора памяти это функция throughput(size, stride), снятая на сетке: размеры от 16 КБ до 128 МБ с удвоением, шаги от 1 до 15 слов. Четырнадцать размеров, пятнадцать шагов, двести десять точек. Из урока про локальность ты знаешь, чего ждать: чем меньше размер и чем меньше шаг, тем выше. Интереснее, где именно поверхность ломается.
Ядро замера
Функция, которую мы измеряем, читает первые data.len слов массива с шагом stride и складывает их. Сложение здесь не ради результата: если ничего не делать с прочитанным, компилятор имеет полное право не читать. Сумма это доказательство, что чтения были.
const std = @import("std");
/// Один проход по массиву с шагом. `noinline`, чтобы компилятор не
/// подставил цикл в замер и не сложил повторы в один.
pub noinline fn readPass(data: []const i64, stride: usize) i64 {
var acc: [4]i64 = .{ 0, 0, 0, 0 };
const step = stride * 4;
var i: usize = 0;
while (i + step <= data.len) : (i += step) {
acc[0] +%= data[i];
acc[1] +%= data[i + stride];
acc[2] +%= data[i + 2 * stride];
acc[3] +%= data[i + 3 * stride];
}
while (i < data.len) : (i += stride) acc[0] +%= data[i];
return (acc[0] +% acc[1]) +% (acc[2] +% acc[3]);
}
test "проход с шагом складывает ровно те слова, что нужно" {
var data: [10]i64 = undefined;
for (&data, 0..) |*x, i| x.* = @intCast(i + 1);
try std.testing.expectEqual(@as(i64, 55), readPass(&data, 1));
// Индексы 0, 3, 6, 9: значения 1, 4, 7, 10.
try std.testing.expectEqual(@as(i64, 22), readPass(&data, 3));
try std.testing.expectEqual(@as(i64, 1), readPass(&data, 20));
}Четыре аккумулятора вместо одного это не украшение. В уроке про развёртывание ты видел границу задержки: цепочка сложений в один регистр не может идти быстрее одного сложения за такт, потому что каждое ждёт предыдущего. На M4 Max это ровно 1.00 такта на целочисленное сложение, то есть не больше одного слова за такт, восемь байт за такт. А L1 умеет отдавать больше двух слов за такт. С одним аккумулятором мы измерили бы не память, а сумматор, и вершина горы оказалась бы плоской по вине арифметики. Четыре независимых цепочки снимают это ограничение: книга по той же причине разворачивает цикл 4×4.
+%= это сложение с заворачиванием. В ReleaseFast проверок переполнения и так нет, но в ReleaseSafe обычный += вставил бы проверку после каждого чтения, и мы измеряли бы её. Сумма нам нужна только как контрольная, переполнение ей не мешает.
noinline запрещает подставить тело функции в место вызова. Без него компилятор видит цикл повторов вокруг одного и того же прохода, замечает, что результат не меняется, и оставляет один проход вместо тысячи. С noinline каждый вызов это честный вызов, а результат уходит в std.mem.doNotOptimizeAway, чтобы и его нельзя было счесть ненужным.
Что цикл действительно остался циклом из четырёх загрузок, видно в ассемблере. Соберём функцию под x86-64 с export, иначе она встроится и исчезнет:
// zig build-exe readpass_asm.zig -O ReleaseFast -femit-asm=readpass.s -fno-emit-bin -target x86_64-linux
export fn readPass(data: [*]const i64, len: usize, stride: usize) i64 {
var acc: [4]i64 = .{ 0, 0, 0, 0 };
const step = stride * 4;
var i: usize = 0;
while (i + step <= len) : (i += step) {
acc[0] +%= data[i];
acc[1] +%= data[i + stride];
acc[2] +%= data[i + 2 * stride];
acc[3] +%= data[i + 3 * stride];
}
while (i < len) : (i += stride) acc[0] +%= data[i];
return (acc[0] +% acc[1]) +% (acc[2] +% acc[3]);
}
pub fn main() void {}Главный цикл из readpass.s, остальное отрезано:
.LBB3_6:
add rcx, qword ptr [rdi + 8*r10]
add r9, qword ptr [r15 + 8*r10]
add rax, qword ptr [rbx + 8*r10]
add r8, qword ptr [r14 + 8*r10]
add r10, r11
lea r12, [r11 + r10]
cmp r12, rsi
jbe .LBB3_6Четыре add с операндом из памяти в четыре разных регистра, один шаг индекса, сравнение и переход. Ни одной векторной инструкции: шаг известен только во время выполнения, и собрать четыре слова в один регистр компилятору нечем. Ровно то, что мы хотели измерить.
Как снимать честно
Замер одной точки горы устроен так: разогреть, повторить много раз, засечь время, взять лучшую из нескольких попыток.
const std = @import("std");
pub const Measurer = struct {
io: std.Io,
/// Буфер не меньше самого большого размера, уже заполненный.
data: []const i64,
/// Сколько чтений набрать в одной попытке, чтобы таймер не мерил шум.
min_accesses: usize = 1 << 23,
tries: u32 = 5,
/// Пропускная способность в МБ/с для массива `size_bytes` и шага.
pub fn throughput(m: Measurer, size_bytes: usize, stride: u32) f64 {
const data = m.data[0 .. size_bytes / @sizeOf(i64)];
const accesses = (data.len + stride - 1) / stride;
const reps = @max(1, m.min_accesses / accesses);
// Разогрев: первый проход тянет данные в кэш и не считается.
std.mem.doNotOptimizeAway(readPass(data, stride));
var best_ns: f64 = std.math.inf(f64);
var attempt: u32 = 0;
while (attempt < m.tries) : (attempt += 1) {
const started = std.Io.Clock.awake.now(m.io);
var rep: usize = 0;
while (rep < reps) : (rep += 1) std.mem.doNotOptimizeAway(readPass(data, stride));
const elapsed = started.durationTo(std.Io.Clock.awake.now(m.io));
const ns: f64 = @floatFromInt(elapsed.toNanoseconds());
best_ns = @min(best_ns, ns / @as(f64, @floatFromInt(reps)));
}
const bytes: f64 = @floatFromInt(accesses * @sizeOf(i64));
return bytes * 1000.0 / best_ns;
}
};
pub noinline fn readPass(data: []const i64, stride: usize) i64 {
var acc: [4]i64 = .{ 0, 0, 0, 0 };
const step = stride * 4;
var i: usize = 0;
while (i + step <= data.len) : (i += step) {
acc[0] +%= data[i];
acc[1] +%= data[i + stride];
acc[2] +%= data[i + 2 * stride];
acc[3] +%= data[i + 3 * stride];
}
while (i < data.len) : (i += stride) acc[0] +%= data[i];
return (acc[0] +% acc[1]) +% (acc[2] +% acc[3]);
}
test "замер даёт конечное положительное число" {
const data = try std.testing.allocator.alloc(i64, 2048);
defer std.testing.allocator.free(data);
for (data, 0..) |*x, i| x.* = @intCast(i & 0xff);
const m: Measurer = .{ .io = std.testing.io, .data = data, .min_accesses = 1 << 12, .tries = 2 };
const mbs = m.throughput(16 * 1024, 1);
try std.testing.expect(std.math.isFinite(mbs) and mbs > 0);
}Каждая строка здесь закрывает одну известную дыру.
Разогрев. Первый проход по массиву приносит данные в кэш и, если страницы ещё не тронуты, вызывает сбои страниц. Ни то, ни другое не относится к пропускной способности чтения, поэтому первый проход мы выбрасываем. Заполняющий цикл в main делает то же для страниц: к моменту замера все 128 МБ уже отображены.
Повторы. Один проход по 16 КБ с шагом 15 это 137 чтений, меньше микросекунды. Таймер с разрешением в десятки наносекунд на таком отрезке даёт мусор. min_accesses задаёт, сколько чтений набрать в одной попытке: для маленьких массивов повторов тысячи, для 128 МБ один.
Минимум, а не среднее. Другой процесс, прерывание, миграция потока на другое ядро могут только замедлить наш цикл, ускорить его они не могут. Поэтому из пяти попыток берётся лучшая: она ближе всего к тому, что делает железо, когда ему не мешают. Среднее смешало бы замер с чужим шумом, и это одна из ловушек, разобранных в уроке про бенчмарки.
Часы. std.Io.Clock.awake это монотонные часы, считающие время бодрствования системы. Часы реального времени для замеров не годятся: синхронизация по сети может перевести их посреди попытки.
Три вещи, которые кодом не закрыть, а только дисциплиной.
Режим сборки. Гора собирается только в ReleaseFast. В Debug каждое data[i] это проверка индекса и переход, и она стоит дороже самого чтения. Вот первые строки той же программы в Debug, снятые на том же M4 Max:
размер s1 s2 s3 s4 s5 s6 s7 s8
16K 1108 1077 1072 869 1113 1157 897 621
128K 603 1017 1306 1295 1074 1039 1104 1074
256K 988 1029 1036 1185 1131 1352 1163 1073Около одного гигабайта в секунду везде, в девяносто раз ниже L1, и ни одного обрыва: гора превратилась в равнину, потому что узкое место теперь не память, а проверки.
Тихая машина. Вот та же программа в ReleaseFast, но запущенная, пока на машине одновременно шли одиннадцать сборок Zig (2026-09-13):
размер s1 s2 s4 s8 s15
128K 22691 27676 35279 19527 24163
256K 35032 22067 9233 7107 4763
131072K 4108 2154 5886 1422 1487На тихой машине четырьмя днями раньше строка 128 КБ давала 89578 на шаге 1, здесь 22691, и 256 КБ на шаге 1 внезапно выше, чем 128 КБ. Минимум из пяти попыток не спасает, когда все пять попыток шумные. Перед замером закрой браузер, останови сборки и индексаторы, и не запускай гору из-под нагрузки.
Чьё ядро. На Apple Silicon ядер два сорта. У ядра производительности M4 Max L1d на 128 КБ, у ядра экономии на 64 КБ, и планировщик macOS сам решает, куда посадить поток. Обычно долгий вычислительный цикл уезжает на ядро производительности, но гарантии нет, и гора, снятая на ядре экономии, покажет обрыв на 64 КБ. Первое, что стоит сделать перед чтением горы, это узнать, что на машине вообще есть:
sysctl hw.perflevel0 hw.perflevel1 hw.l1dcachesize hw.l2cachesize hw.cachelinesizehw.perflevel0.l1icachesize: 196608
hw.perflevel0.l1dcachesize: 131072
hw.perflevel0.l2cachesize: 16777216
hw.perflevel0.cpusperl2: 6
hw.perflevel0.name: Performance
hw.perflevel1.l1dcachesize: 65536
hw.perflevel1.l2cachesize: 4194304
hw.perflevel1.cpusperl2: 4
hw.perflevel1.name: Efficiency
hw.l1dcachesize: 65536
hw.l2cachesize: 4194304
hw.cachelinesize: 128Здесь ловушка: hw.l1dcachesize без префикса уровня отвечает за ядро экономии и говорит 64 КБ. Правильный ответ для ядра производительности лежит в hw.perflevel0.*: L1d 128 КБ, L2 16 МБ на кластер из шести ядер. Общего L3 в привычном смысле у M4 нет, есть системный кэш, который sysctl не показывает вовсе.
На Linux x86-64 то же самое читается из lscpu и из /sys. Форма вывода такая (значения для Core i7 Haswell из книги, машина из этого урока их снять не может):
$ lscpu | grep -i cache
L1d cache: 32 KiB (1 instance)
L1i cache: 32 KiB (1 instance)
L2 cache: 256 KiB (1 instance)
L3 cache: 8 MiB (1 instance)
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64На Linux можно ещё и прибить поток к ядру: taskset -c 2 ./mountain. На macOS такого инструмента нет, остаётся тихая машина и вера в планировщик.
Программа целиком
Соберём всё в одну программу. Она печатает таблицу по мере снятия, чтобы при долгом замере было видно, что происходит, и по ключу --out пишет JSON в форме, которую понимает виджет ниже и программа чтения обрывов из следующего раздела.
//! Гора памяти: пропускная способность чтения в зависимости от размера
//! массива и шага обхода. Собирать только в ReleaseFast: в Debug проверка
//! индекса стоит дороже самого чтения, и гора превращается в равнину.
//!
//! zig build-exe mountain.zig -O ReleaseFast
//! ./mountain # таблица в stdout
//! ./mountain --out mountain.json # плюс JSON для виджета
const std = @import("std");
pub const min_size: usize = 16 * 1024;
pub const max_size: usize = 128 * 1024 * 1024;
pub const max_stride: u32 = 15;
/// Размеры от 16 КБ до 128 МБ, каждый следующий вдвое больше.
pub const sizes = blk: {
var list: [14]usize = undefined;
var size = min_size;
for (&list) |*slot| {
slot.* = size;
size *= 2;
}
std.debug.assert(size == max_size * 2);
break :blk list;
};
/// Шаги от 1 до 15 слов по 8 байт.
pub const strides = blk: {
var list: [max_stride]u32 = undefined;
for (&list, 1..) |*slot, stride| slot.* = stride;
break :blk list;
};
/// Один проход по массиву с шагом. `noinline`, чтобы компилятор не
/// подставил цикл в замер и не сложил повторы в один.
pub noinline fn readPass(data: []const i64, stride: usize) i64 {
var acc: [4]i64 = .{ 0, 0, 0, 0 };
const step = stride * 4;
var i: usize = 0;
while (i + step <= data.len) : (i += step) {
acc[0] +%= data[i];
acc[1] +%= data[i + stride];
acc[2] +%= data[i + 2 * stride];
acc[3] +%= data[i + 3 * stride];
}
while (i < data.len) : (i += stride) acc[0] +%= data[i];
return (acc[0] +% acc[1]) +% (acc[2] +% acc[3]);
}
pub const Measurer = struct {
io: std.Io,
/// Буфер не меньше `max_size` байт, уже заполненный.
data: []const i64,
/// Сколько чтений набрать в одной попытке, чтобы таймер не мерил шум.
min_accesses: usize = 1 << 23,
tries: u32 = 5,
/// Пропускная способность в МБ/с для массива `size_bytes` и шага.
pub fn throughput(m: Measurer, size_bytes: usize, stride: u32) f64 {
const data = m.data[0 .. size_bytes / @sizeOf(i64)];
const accesses = (data.len + stride - 1) / stride;
const reps = @max(1, m.min_accesses / accesses);
// Разогрев: первый проход тянет данные в кэш и не считается.
std.mem.doNotOptimizeAway(readPass(data, stride));
var best_ns: f64 = std.math.inf(f64);
var attempt: u32 = 0;
while (attempt < m.tries) : (attempt += 1) {
const started = std.Io.Clock.awake.now(m.io);
var rep: usize = 0;
while (rep < reps) : (rep += 1) std.mem.doNotOptimizeAway(readPass(data, stride));
const elapsed = started.durationTo(std.Io.Clock.awake.now(m.io));
const ns: f64 = @floatFromInt(elapsed.toNanoseconds());
best_ns = @min(best_ns, ns / @as(f64, @floatFromInt(reps)));
}
const bytes: f64 = @floatFromInt(accesses * @sizeOf(i64));
return bytes * 1000.0 / best_ns;
}
};
/// Снятая гора: та же форма, что у JSON рядом с виджетом.
pub const Mountain = struct {
hardware: []const u8,
date: []const u8,
sizes: []const usize,
strides: []const u32,
/// Строка на размер, в ней значение на каждый шаг, МБ/с.
throughput: []const []const f64,
};
pub fn main(init: std.process.Init) !void {
const arena = init.arena.allocator();
const args = try init.minimal.args.toSlice(arena);
const out_path: ?[]const u8 = if (args.len == 3 and std.mem.eql(u8, args[1], "--out")) args[2] else null;
var out_buf: [4096]u8 = undefined;
var stdout = std.Io.File.stdout().writerStreaming(init.io, &out_buf);
const out = &stdout.interface;
defer out.flush() catch {};
// Буфер под самый большой массив; заполнение заодно трогает все страницы.
const data = try std.heap.page_allocator.alloc(i64, max_size / @sizeOf(i64));
defer std.heap.page_allocator.free(data);
for (data, 0..) |*x, i| x.* = @intCast(i & 0xff);
const measurer: Measurer = .{ .io = init.io, .data = data };
const started = std.Io.Clock.awake.now(init.io);
var table: [sizes.len][strides.len]f64 = undefined;
try out.print("{s:>8}", .{"размер"});
for (strides) |stride| try out.print(" s{d:<6}", .{stride});
try out.writeAll("\n");
for (sizes, &table) |size, *row| {
try out.print("{d:>6}K ", .{size / 1024});
for (strides, row) |stride, *cell| {
const mbs = measurer.throughput(size, stride);
cell.* = @round(mbs * 10) / 10;
try out.print(" {d:<7.0}", .{mbs});
}
try out.writeAll("\n");
try out.flush();
}
const elapsed = started.durationTo(std.Io.Clock.awake.now(init.io));
const elapsed_s = @as(f64, @floatFromInt(elapsed.toNanoseconds())) / 1e9;
try out.print("замер занял {d:.1} с\n", .{elapsed_s});
if (out_path) |path| {
var rows: [sizes.len][]const f64 = undefined;
for (&rows, &table) |*slot, *row| slot.* = row;
const result: Mountain = .{
.hardware = "своя машина",
.date = "сегодня",
.sizes = &sizes,
.strides = &strides,
.throughput = &rows,
};
var json: std.Io.Writer.Allocating = .init(arena);
try json.writer.print("{f}\n", .{std.json.fmt(result, .{ .whitespace = .indent_2 })});
try std.Io.Dir.cwd().writeFile(init.io, .{ .sub_path = path, .data = json.written() });
try out.print("JSON записан в {s}\n", .{path});
}
}
test "проход с шагом складывает ровно те слова, что нужно" {
var data: [10]i64 = undefined;
for (&data, 0..) |*x, i| x.* = @intCast(i + 1);
try std.testing.expectEqual(@as(i64, 55), readPass(&data, 1));
// Индексы 0, 3, 6, 9: значения 1, 4, 7, 10.
try std.testing.expectEqual(@as(i64, 22), readPass(&data, 3));
try std.testing.expectEqual(@as(i64, 1), readPass(&data, 20));
}
test "таблица размеров начинается с 16 КБ и кончается 128 МБ" {
try std.testing.expectEqual(min_size, sizes[0]);
try std.testing.expectEqual(max_size, sizes[sizes.len - 1]);
try std.testing.expectEqual(@as(u32, 1), strides[0]);
try std.testing.expectEqual(max_stride, strides[strides.len - 1]);
}Две детали, на которые стоит посмотреть. sizes и strides вычисляются на этапе компиляции: blk: с break :blk это обычный способ собрать таблицу в comptime, и assert внутри проверяет, что удвоений ровно столько, сколько надо. Массив под данные берём у page_allocator, а не у DebugAllocator: 128 МБ это ровно один mmap, и никакой учёт нам не нужен. Вывод идёт через writerStreaming, а не writer: когда stdout перенаправлен в файл, обычный писатель файла ведёт позицию сам, и при печати из разных мест строки могут лечь одна поверх другой.
Снятие занимает минуту с небольшим: на тихой машине двести десять точек по пять попыток, каждая не короче восьми миллионов чтений.
Прогон: гора Apple M4 Max
Ниже фрагмент таблицы, снятой этой программой на Apple M4 Max (aarch64, macOS), Zig 0.16.0, ReleaseFast, 2026-09-09, на тихой машине. Полная сетка из четырнадцати размеров и пятнадцати шагов лежит внутри виджета ниже, здесь только опорные столбцы. Единицы: мегабайты в секунду.
| размер | шаг 1 | шаг 2 | шаг 4 | шаг 8 | шаг 15 |
|---|---|---|---|---|---|
| 16 КБ | 44789 | 49196 | 56497 | 70182 | 90549 |
| 32 КБ | 88074 | 85890 | 83712 | 71755 | 89998 |
| 64 КБ | 88739 | 88108 | 86078 | 75150 | 77266 |
| 128 КБ | 89578 | 87901 | 83438 | 73807 | 84113 |
| 256 КБ | 79876 | 55905 | 36083 | 20841 | 28296 |
| 512 КБ | 81620 | 56473 | 33956 | 18703 | 17033 |
| 1 МБ | 81794 | 56600 | 33848 | 17658 | 14958 |
| 4 МБ | 78705 | 55443 | 32352 | 17109 | 13547 |
| 16 МБ | 78505 | 54436 | 32083 | 16050 | 13515 |
| 64 МБ | 77523 | 49357 | 27890 | 14757 | 10278 |
| 128 МБ | 76032 | 46756 | 26572 | 13848 | 9304 |
Первое, что бросается в глаза: вершина около 90 ГБ/с, дно около 9 ГБ/с, разница в десять раз. У книжной горы Core i7 Haswell вершина 14 ГБ/с, дно 900 МБ/с, разница в пятнадцать. Форма похожа, масштаб другой.
Второе: строка 16 КБ на маленьких шагах занижена, 44789 против 88074 у 32 КБ. Это не свойство памяти, а свойство замера. Проход по 16 КБ с шагом 1 это две тысячи чтений, и вызов функции, установка цикла и хвост из четырёх сложений занимают заметную долю такого прохода. С ростом шага чтений в проходе ещё меньше, но и повторов больше, и доля накладных расходов ведёт себя не монотонно. Отсюда правило: самой маленькой строке горы не верь, читай обрывы по строкам, где проход длинный.
Третье, и это главное: на шаге 8 между 128 КБ и 256 КБ полоса падает с 73807 до 20841, в три с половиной раза. На шаге 1 между теми же строками падение с 89578 до 79876, на двенадцать процентов. Одна и та же граница кэша на одном срезе выглядит обрывом, на другом почти не видна. Дальше мы разберём оба среза по отдельности.
Срез по размеру: обрывы и размеры кэшей
Зафиксируем шаг и пройдём по размерам. Это тот же срез, что книга рисует для шага 8 на своём Core i7: четыре области слева направо, L1, L2, L3 и основная память, с провалом на каждой границе. Чтобы не искать обрывы глазами, напишем программу, которая читает JSON и находит их сама. Обрыв здесь это падение больше чем в полтора раза между соседними размерами, а последний размер перед обрывом это оценка размера кэша.
//! Чтение горы с диска: где на срезе с заданным шагом пропускная
//! способность обрывается, и какие размеры кэшей из этого следуют.
//!
//! zig build-exe cliffs.zig -O ReleaseSafe
//! ./cliffs mountain.json 8 # обрывы на срезе с шагом 8
//! zig test cliffs.zig # тесты на синтетической горе
const std = @import("std");
/// Та же форма, что у JSON, который пишет программа горы.
pub const Mountain = struct {
hardware: []const u8 = "",
date: []const u8 = "",
sizes: []const usize,
strides: []const u32,
throughput: []const []const f64,
/// Разбор JSON. Строки и массивы живут в `arena`.
pub fn parse(arena: std.mem.Allocator, text: []const u8) !Mountain {
const m = try std.json.parseFromSliceLeaky(Mountain, arena, text, .{ .ignore_unknown_fields = true });
try m.validate();
return m;
}
pub fn validate(m: Mountain) error{BadShape}!void {
if (m.sizes.len == 0 or m.strides.len == 0) return error.BadShape;
if (m.throughput.len != m.sizes.len) return error.BadShape;
for (m.throughput) |row| {
if (row.len != m.strides.len) return error.BadShape;
}
}
pub fn strideIndex(m: Mountain, stride: u32) ?usize {
return std.mem.indexOfScalar(u32, m.strides, stride);
}
};
/// Обрыв: между двумя соседними размерами пропускная способность упала.
pub const Cliff = struct {
/// Последний размер, который ещё помещался.
from: usize,
/// Первый размер, который уже не помещается.
to: usize,
/// Во сколько раз упало: throughput(from) / throughput(to).
ratio: f64,
};
/// Обрывы на срезе горы с одним шагом. Обрывом считается падение больше
/// чем в `min_ratio` раз между соседними размерами.
pub fn findCliffs(gpa: std.mem.Allocator, m: Mountain, stride: u32, min_ratio: f64) ![]Cliff {
const column = m.strideIndex(stride) orelse return error.UnknownStride;
var cliffs: std.ArrayList(Cliff) = .empty;
errdefer cliffs.deinit(gpa);
var i: usize = 0;
while (i + 1 < m.sizes.len) : (i += 1) {
const before = m.throughput[i][column];
const after = m.throughput[i + 1][column];
if (after <= 0) continue;
const ratio = before / after;
if (ratio >= min_ratio) {
try cliffs.append(gpa, .{ .from = m.sizes[i], .to = m.sizes[i + 1], .ratio = ratio });
}
}
return cliffs.toOwnedSlice(gpa);
}
/// Размеры кэшей, которые читаются с горы: последний размер перед каждым
/// обрывом. Первый обрыв это L1, второй L2 и так далее.
pub fn levelSizes(cliffs: []const Cliff, out: []usize) []usize {
const n = @min(cliffs.len, out.len);
for (cliffs[0..n], out[0..n]) |cliff, *slot| slot.* = cliff.from;
return out[0..n];
}
pub fn main(init: std.process.Init) !void {
const arena = init.arena.allocator();
const args = try init.minimal.args.toSlice(arena);
if (args.len != 3) {
std.debug.print("usage: cliffs <mountain.json> <stride>\n", .{});
return error.BadUsage;
}
const stride = try std.fmt.parseInt(u32, args[2], 10);
const text = try std.Io.Dir.cwd().readFileAlloc(init.io, args[1], arena, .limited(1 << 20));
const m = try Mountain.parse(arena, text);
var buf: [1024]u8 = undefined;
var stdout = std.Io.File.stdout().writerStreaming(init.io, &buf);
const out = &stdout.interface;
const cliffs = try findCliffs(arena, m, stride, 1.5);
try out.print("{s}, {s}, шаг {d}\n", .{ m.hardware, m.date, stride });
if (cliffs.len == 0) try out.writeAll("обрывов нет: падения меньше, чем в 1.5 раза\n");
for (cliffs) |cliff| {
try out.print("обрыв между {d} КБ и {d} КБ: падение в {d:.2} раза\n", .{ cliff.from / 1024, cliff.to / 1024, cliff.ratio });
}
var slots: [3]usize = undefined;
const names = [_][]const u8{ "L1", "L2", "L3" };
for (levelSizes(cliffs, &slots), 0..) |size, level| {
try out.print("{s} по горе: {d} КБ\n", .{ names[level], size / 1024 });
}
try out.flush();
}
/// Синтетическая гора: три плато, 100, 40 и 10, обрывы после 64 КБ и 1 МБ.
fn syntheticMountain() Mountain {
const S = struct {
const sizes = [_]usize{ 16 << 10, 32 << 10, 64 << 10, 128 << 10, 256 << 10, 512 << 10, 1 << 20, 2 << 20, 4 << 20 };
const strides = [_]u32{ 1, 8 };
// Со strides.len столбцов; на шаге 1 предвыборка прячет второй обрыв.
const rows = [_][2]f64{
.{ 100, 100 }, .{ 100, 100 }, .{ 100, 100 },
.{ 95, 40 }, .{ 95, 40 }, .{ 95, 40 },
.{ 95, 40 }, .{ 90, 10 }, .{ 90, 10 },
};
const table = blk: {
var t: [rows.len][]const f64 = undefined;
for (&t, &rows) |*slot, *row| slot.* = row;
break :blk t;
};
};
return .{ .sizes = &S.sizes, .strides = &S.strides, .throughput = &S.table };
}
test "обрывы на срезе с шагом 8 стоят после 64 КБ и 1 МБ" {
const cliffs = try findCliffs(std.testing.allocator, syntheticMountain(), 8, 1.5);
defer std.testing.allocator.free(cliffs);
try std.testing.expectEqual(@as(usize, 2), cliffs.len);
try std.testing.expectEqual(@as(usize, 64 << 10), cliffs[0].from);
try std.testing.expectEqual(@as(usize, 128 << 10), cliffs[0].to);
try std.testing.expectEqual(@as(usize, 1 << 20), cliffs[1].from);
try std.testing.expectApproxEqAbs(@as(f64, 2.5), cliffs[0].ratio, 1e-9);
var slots: [3]usize = undefined;
const levels = levelSizes(cliffs, &slots);
try std.testing.expectEqualSlices(usize, &.{ 64 << 10, 1 << 20 }, levels);
}
test "на срезе с шагом 1 обрывов нет" {
const cliffs = try findCliffs(std.testing.allocator, syntheticMountain(), 1, 1.5);
defer std.testing.allocator.free(cliffs);
try std.testing.expectEqual(@as(usize, 0), cliffs.len);
try std.testing.expectError(error.UnknownStride, findCliffs(std.testing.allocator, syntheticMountain(), 3, 1.5));
}
test "JSON с неровной таблицей не проходит проверку формы" {
var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
defer arena.deinit();
const good =
\\{"sizes":[16384,32768],"strides":[1,2],"throughput":[[10,9],[5,4]],"extra":true}
;
const m = try Mountain.parse(arena.allocator(), good);
try std.testing.expectEqual(@as(?usize, 1), m.strideIndex(2));
const bad =
\\{"sizes":[16384,32768],"strides":[1,2],"throughput":[[10,9]]}
;
try std.testing.expectError(error.BadShape, Mountain.parse(arena.allocator(), bad));
}std.json.parseFromSliceLeaky разбирает JSON прямо в нашу структуру: имена полей совпадают с ключами, срезы становятся массивами, а ignore_unknown_fields разрешает файлу содержать больше, чем мы читаем (у JSON виджета есть ещё поле caches). Память под строки и массивы уходит в арену и освобождается вместе с ней. validate проверяет, что таблица прямоугольная: без этого m.throughput[i][column] мог бы выйти за границу на кривом файле.
Прогоним на горе M4 Max для трёх шагов:
$ ./cliffs mountain.json 8
Apple M4 Max (aarch64, macOS), Zig 0.16.0, ReleaseFast, 2026-09-09, шаг 8
обрыв между 128 КБ и 256 КБ: падение в 3.54 раза
L1 по горе: 128 КБ
$ ./cliffs mountain.json 1
Apple M4 Max (aarch64, macOS), Zig 0.16.0, ReleaseFast, 2026-09-09, шаг 1
обрывов нет: падения меньше, чем в 1.5 раза
$ ./cliffs mountain.json 15
Apple M4 Max (aarch64, macOS), Zig 0.16.0, ReleaseFast, 2026-09-09, шаг 15
обрыв между 128 КБ и 256 КБ: падение в 2.97 раза
обрыв между 256 КБ и 512 КБ: падение в 1.66 раза
L1 по горе: 128 КБ
L2 по горе: 256 КБТри вывода, три урока.
Шаг 8 даёт правильный L1. 128 КБ по горе, 131072 в hw.perflevel0.l1dcachesize. Это и есть чтение размера кэша с графика: не из документации, а из поведения. Совпадение заодно говорит, что поток сидел на ядре производительности, а не экономии.
Шаг 1 не даёт ничего. Падения меньше полутора раз на всём срезе, от 16 КБ до 128 МБ. Это работа предвыборки: при чтении подряд процессор видит закономерность и тянет следующие линии заранее, пока считываются текущие. Промахи никуда не деваются, но их задержка перекрывается, и полоса держится около 80 ГБ/с через все уровни, вплоть до 128 МБ, которые ни в какой кэш не влезают. Книга видит на своём Haswell то же самое: ровный хребет на 12 ГБ/с вдоль шага 1 через границы L1 и L2.
Шаг 15 врёт про L2. Второй обрыв программа нашла между 256 КБ и 512 КБ и подписала его как L2. Но L2 у M4 Max это 16 МБ, и между 16 и 32 МБ на срезе никакого обрыва нет. Падение 256 к 512 это не граница кэша, а продолжение первого обрыва: за границей L1 полоса не падает мгновенно до нового плато, а сползает ещё пару строк. Правило «второй обрыв это L2» работает только там, где второй обрыв есть. На M4 его нет ни на одном шаге: с 16 МБ до 128 МБ полоса на шаге 15 сползает с 13515 до 9304, на тридцать процентов, без ступени. Причин по меньшей мере три: предвыборка по постоянному шагу подтягивает и такие обращения, между L2 и памятью стоит системный кэш, а сама память у M4 Max очень широкая. Так что программа обрывов это подсказка, а не оракул: то, что она нашла, ты обязан сверить с тем, что говорит система, и с тем, что видно на соседних шагах. Книга, кстати, тоже честно пишет, что провалы на левых краях своих рёбер L2 и L3 объяснить не может без детального моделирования.
Отсюда рабочий порядок чтения горы: обрывы ищем на шаге не меньше длины линии, где предвыборке нечего угадывать; первый обрыв это L1 почти всегда; каждый следующий проверяем по sysctl или lscpu, потому что на одних машинах он есть, а на других его прячут предвыборка и системный кэш.
Виджет: две ручки и тепловая карта
Вся гора M4 Max целиком. Левый график это срез по размеру при выбранном шаге, правый срез по шагу при выбранном размере, снизу вся поверхность как тепловая карта, где клетка кликается и выбирает точку для обоих срезов. Три ползунка над левым графиком предлагают тебе поставить границы L1, L2 и L3 на глаз, а кнопка сравнивает догадку с данными.
Попробуй в таком порядке. Поставь шаг 8 и найди обрыв L1, потом переключи на шаг 1 и посмотри, как он почти исчезает. Выбери размер 128 КБ и пройди по шагам: линия почти ровная, потому что весь рабочий набор в L1 и шаг ничего не меняет. Выбери 256 КБ и пройди по шагам ещё раз: теперь каждая точка это разная доля промахов.
Срез по шагу: линия и предвыборка
Теперь зафиксируем размер и пройдём по шагам. Вот строка 256 КБ целиком, первый размер, который уже не помещается в L1:
| шаг | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| МБ/с | 79876 | 55905 | 45076 | 36083 | 29151 | 24520 | 21168 | 20841 | 20123 | 19748 | 21643 | 28225 | 19346 | 19901 | 28296 |
Полоса падает от шага 1 до шага 8, а дальше держится около 20 ГБ/с. Объяснение из урока про организацию кэша: промах приносит из L2 целую линию, и пока шаг меньше линии, одна линия обслуживает несколько чтений. При шаге 1 из восьми чтений промахивается одно, при шаге 4 каждое второе, при шаге 8 каждое. Дальше увеличивать шаг бессмысленно: хуже чем «каждое чтение это промах» не бывает, и склон переходит в плато.
По излому можно прочитать длину линии. Плато начинается с шага 8, то есть с 64 байт. sysctl hw.cachelinesize при этом говорит 128. Это не противоречие, а вопрос «линия чего»: у Apple разные уровни иерархии работают с разной гранулярностью, sysctl сообщает большую, а гора отвечает на вопрос, какая гранулярность важна для этого цикла. На Core i7 из книги линия 64 байта на всех уровнях, и её срез для 4 МБ тоже выходит на плато ровно с шага 8.
Ещё одно наблюдение против наивной арифметики. Если бы каждый промах стоил одинаково и всё определялось их долей, шаг 8 был бы в восемь раз медленнее шага 1. На деле 79876 к 20841, меньше четырёх раз. Промахи на регулярном шаге тоже перекрываются: предвыборка по шагу подтягивает следующие линии, а внеочередной процессор из урока про модель процессора держит несколько промахов в полёте одновременно. Гора измеряет пропускную способность, а не задержку, и по ней нельзя узнать, сколько наносекунд стоит один промах в память: это задача для замера с обходом случайной перестановки, где предвыборке угадывать нечего, и она есть в упражнениях.
Наконец, выбросы на шагах 12 и 15, 28225 и 28296 вместо ожидаемых двадцати тысяч. Они повторяются от прогона к прогону, значит, это не шум. Честный ответ: точной причины у нас нет, а гипотезы про то, как предвыборщик Apple группирует линии по 128 байт при шагах в 96 и 120 байт, проверить без документации нельзя. Книга в таких местах пишет «природа провалов не совсем понятна», и мы поступим так же. Гора это карта, а не объяснение.
Задача: такты на слово
Упражнение книги 6.21 просит по горе оценить, сколько тактов стоит чтение одного слова из L1. Переформулируем для обеих машин.
Ширина полосы в мегабайтах в секунду, частота в мегагерцах, слово восемь байт. Тогда тактов на слово это частота / полоса × 8.
Core i7 Haswell из книги: устойчивая полоса в области L1 около 12000 МБ/с, частота 2100 МГц. Получается 2100 / 12000 × 8 = 1.4 такта на слово. Номинальная задержка L1 у Haswell четыре такта, значит, в среднем в полёте одновременно почти три загрузки: это заслуга четырёх аккумуляторов и внеочередного исполнения.
Apple M4 Max: полоса в области L1 на длинных строках около 89500 МБ/с. Частоту Apple не публикует, и sysctl на Apple Silicon её не отдаёт; по сторонним замерам ядро производительности M4 Max работает до 4500 МГц. Берём её как верхнюю оценку: 4500 / 89500 × 8 = 0.40 такта на слово, то есть два с половиной слова за такт. Это уже не «одна загрузка перекрывает другую», а несколько портов загрузки, работающих каждый такт. Тот же расчёт на дне горы, 9304 МБ/с при 128 МБ и шаге 15, даёт 3.9 такта на слово, меньше наносекунды на линию. Задержка DRAM на порядок больше, и это ещё одно напоминание, что гора показывает пропускную способность с предвыборкой, а не задержку одного промаха.
x86-64 против Apple Silicon
Сведём книжную гору и нашу в одну таблицу. Числа Haswell из рисунков книги, числа M4 из прогона выше.
| Core i7 Haswell (книга) | Apple M4 Max | |
|---|---|---|
| частота | 2.1 ГГц | до 4.5 ГГц, не публикуется |
| L1d | 32 КБ | 128 КБ на ядре производительности, 64 КБ на ядре экономии |
| L2 | 256 КБ на ядро | 16 МБ на кластер из шести ядер |
| L3 | 8 МБ общий | нет, есть системный кэш вне sysctl |
линия по lscpu или sysctl | 64 байта | 128 байт |
| линия по излому горы | 64 байта | 64 байта |
| вершина, L1 при шаге 1 | около 14 ГБ/с | около 90 ГБ/с |
| хребет шага 1 через все уровни | около 12 ГБ/с | 76 до 82 ГБ/с |
| дно, 128 МБ при большом шаге | около 900 МБ/с | около 9.3 ГБ/с |
| вершина к дну | около 15 | около 10 |
| видно на срезе шага 8 | обрывы L1, L2, L3 | только обрыв L1 |
Общее у них важнее различий. Обе горы имеют плоскую вершину в области L1, где шаг почти не важен. У обеих хребет вдоль шага 1 держится на уровне около 85 процентов от вершины через все границы кэшей: предвыборка на последовательном обходе одинаково хороша и в 2013, и в 2024 году. У обеих склон по шагу выходит на плато ровно на 64 байтах.
Различия в масштабе и в том, что видно. Дно у M4 в десять раз выше книжного: LPDDR5X с широкой шиной и агрессивная предвыборка по шагу. Границ L2 и L3 на горе M4 нет, потому что нет обрыва между «в кэше» и «в памяти», есть пологий склон. На x86-64 с классической иерархией из трёх уровней и линией 64 байта на всех уровнях книжный рецепт «срез по шагу 8, три обрыва, три кэша» работает как написано. На Apple Silicon он даёт один обрыв и требует сверки с sysctl. Если снимешь гору на AMD Zen или на Intel последних поколений, ожидай третьего варианта: L2 на 1 до 2 МБ, большой L3 и, скорее всего, обрывы на обоих.
Гора как карта пройденного
Каждый из уроков про иерархию памяти живёт в какой-то точке этой поверхности.
Оси горы это два вида локальности: размер рабочего набора это временная, шаг это пространственная. Сама гора, а не плоскость, доказывает, что локальность измерима.
Обрывы по размеру это ёмкость уровней из урока про организацию кэша, а излом склона по шагу это длина линии. Параметры (S, E, B), которые ты разбирал на бумаге, здесь прочитаны с железа.
Три класса промахов из урока про симулятор тоже здесь. Холодные промахи выброшены разогревом. Промахи ёмкости и есть обрывы: рабочий набор больше уровня, каждый круг вытесняет то, что нужно на следующем. Симулятор считает, сколько их будет; гора показывает, сколько они стоят. Разница между ними, предвыборка и перекрытие промахов, это то, чего в симуляторе нет, и то, из-за чего шаг 8 медленнее шага 1 не в восемь раз, а в четыре.
Наконец, порядки циклов и блочное разбиение это маршруты по горе. Внутренний цикл с шагом n по столбцу матрицы идёт вдоль оси шага вниз по склону; блочное разбиение уменьшает рабочий набор так, чтобы вернуться левее обрыва L1. Когда в следующий раз ты будешь выбирать структуру данных, представь, куда на горе она тебя ставит.
Практика: своя гора
Упражнение 6.44 книги просит запустить программу горы на своей машине и оценить размеры кэшей. У тебя есть всё, чтобы сделать это честно.
- Собери
mountain.zigвReleaseFastи запусти на тихой машине с ключом--out mountain.json. Пока идёт минута замера, ничего не запускай. - Собери
cliffs.zigи прогони его по своему JSON для шагов 1, 8 и 15. - Прочитай, что говорит система:
sysctl hw.perflevel0на macOS,lscpuи/sys/devices/system/cpu/cpu0/cache/index*/sizeна Linux. - Сверь. Первый обрыв на шаге 8 с L1d, длину линии по излому среза по шагу с тем, что сообщает система. Для L2 и L3 честно запиши, виден обрыв или нет.
- Запиши три числа в заметки к уроку: вершина, дно и их отношение. Это паспорт твоей машины на ближайшие годы.
Если гора вышла ровной, проверь режим сборки. Если строка 128 КБ на шаге 1 ниже, чем 256 КБ, машина не была тихой. Если обрыв L1 встал на 64 КБ на Apple Silicon, поток уехал на ядро экономии.
Упражнения
Итоги
- Гора памяти это пропускная способность чтения как функция размера рабочего набора и шага обхода: первый отвечает за временную локальность, второй за пространственную. У каждой машины она своя.
- Ядро замера обязано читать по-настоящему: четыре аккумулятора снимают границу задержки сложения,
noinlineиdoNotOptimizeAwayне дают компилятору сложить повторы в один проход, а контрольная сумма доказывает, что чтения были. - Честный замер это
ReleaseFast, разогрев, повторы до миллионов чтений, минимум из попыток и монотонные часы. ВDebugгора превращается в равнину на 1 ГБ/с, на загруженной машине числа не воспроизводятся, на чужом ядре обрыв встаёт не там. - На срезе по размеру граница кэша выглядит как обрыв; на M4 Max между 128 КБ и 256 КБ полоса на шаге 8 падает в 3.5 раза, и это L1d ядра производительности, что подтверждает
hw.perflevel0.l1dcachesize. - На шаге 1 обрывов нет: предвыборка держит хребет около 80 ГБ/с через все уровни до 128 МБ. Границы кэшей ищут на шаге не меньше длины линии.
- Программа поиска обрывов это подсказка, не оракул: на шаге 15 она находит ложную L2 на 256 КБ, а настоящую L2 на 16 МБ не видит ни один шаг. Каждый обрыв сверяют с
sysctlилиlscpu. - На срезе по шагу склон выходит на плато на длине линии: с шага 8, 64 байта, и на Haswell, и на M4, хотя
sysctlу Apple сообщает 128. Падение между шагами 1 и 8 меньше восьмикратного, потому что промахи перекрываются. - Такты на слово читаются с горы как частота, делённая на полосу, умноженная на восемь: 1.4 такта в L1 у книжного Haswell, около 0.4 у M4 Max.
- Гора Haswell и гора M4 совпадают по форме (плоская вершина, хребет шага 1 на 85 процентах от вершины, излом на 64 байтах) и различаются масштабом: вершина 90 против 14 ГБ/с, дно 9.3 ГБ/с против 900 МБ/с, и у M4 нет обрывов L2 и L3.
- Гора собирает уроки про иерархию памяти в одну картину: оси это два вида локальности, обрывы это ёмкость уровней, излом это длина линии, промахи ёмкости из симулятора это её обрывы, а порядки циклов и блочное разбиение это маршруты по ней.
Дальше
С иерархией памяти мы закончили. У тебя есть симулятор кэша, который считает промахи по трассе, и гора, которая показывает, во что они обходятся на живом железе, и ты умеешь сверять одно с другим.
Дальше мы спускаемся на уровень ниже исходного кода и выше процессора: к тому, что лежит между zig build-exe и готовым исполняемым файлом. Компилятор выпускает объектные файлы, и в каждом из них есть секции с кодом и данными, таблица символов и список мест, которые ещё предстоит исправить. Компоновщик решает, что стоит за каждым именем, склеивает секции и заполняет пропуски адресами. Следующий урок открывает эту тему разбором объектного файла по байтам: формат ELF, секции .text, .rodata, .data и .bss, таблица символов и то, куда Zig кладёт export, extern, var и const. Инструменты будут те же, что у системщика на Linux, readelf и nm, а к концу уроков про компоновку ты напишешь их сам.
домашка