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

Пределы: регистры, ветвления и память

lead~170 мин

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

Пределы: регистры, ветвления и память

В прошлом уроке ты дошёл до границы пропускной способности: несколько аккумуляторов разрезали цепочку зависимостей, и combine6 стал упираться уже не в задержку операции, а в число исполнительных блоков. Казалось бы, дальше только больше аккумуляторов. Сегодня разберём, где эта дорога кончается и какие ещё три стены стоят вокруг горячего цикла: регистров конечное число, и лишние аккумуляторы вытесняются на стек; условный переход, который процессор не может угадать, стоит десяток тактов; а запись в память, за которой следует чтение того же адреса, протягивает цепочку зависимостей через буфер записи. Каждую стену увидим в ассемблере и в тактах, а в конце шагнём за книгу: @Vector обходит ограничение на число блоков через ширину данных.

Цели урока

Увидеть в ассемблере, что происходит при k, большем числа регистров: вытеснение аккумуляторов на стек и цена этого в CPE.
Разделить два вида ветвлений в горячем цикле: предсказуемое почти бесплатно, непредсказуемое стоит очистки конвейера, и понять, когда компилятор ставит cmov сам, а когда его надо вынудить.
Разобрать модель блоков загрузки и сохранения: буфер записи, сверка адресов, пересылка данных из буфера в загрузку.
Измерить зависимость запись/чтение на write_read и на копировании со сдвигом и предсказать CPE по графу потока данных.
Написать memset словами с головой, серединой и хвостом и посмотреть, что с ним делает компилятор.
Переписать свёртку через @Vector и понять, почему четыре векторных аккумулятора почти достают до границы пропускной способности.
Сравнить два диспетчера байткода zl под предсказателем и собрать развилку в JIT через cmov, выбирая шаблон по данным.

Идея: три стены вокруг горячего цикла

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

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

стена	что происходит	цена
регистры	аккумулятор не влез в регистр, живёт на стеке	загрузка плюс сохранение на каждой итерации, и цепочка удлиняется на задержку пересылки из буфера записи
ветвления	предсказатель ошибся	конвейер очищается, от 15 до 20 тактов на современном ядре
память	чтение по адресу, куда только что записали	значение идёт не из кэша, а из буфера записи, и цепочка через память тянется от 5 до 7 тактов на звено

Разберём каждую стену на коде. Все замеры сняты на Apple M4 Max (aarch64, macOS), Zig 0.16.0, ReleaseFast, 2026-09-13, частота откалибрована по цепочке сложений и вышла 4.48 ГГц. Ассемблер, где он показан, снят кросс-компиляцией под x86_64-linux, потому что это платформа курса, а на некоторых примерах дополнительно приведён aarch64, потому что разница между ними и есть часть урока.

Секундомер для всех замеров

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

//! Секундомер для циклов этого урока: наносекунды с монотонных часов,
//! такты через калибровку частоты цепочкой зависимых сложений.

const std = @import("std");

/// Пропускает значение через пустой asm: дальше компилятор считает его
/// неизвестным и не может ни свернуть цикл, ни доказать, что два
/// указателя различны.
pub inline fn blackBox(value: anytype) @TypeOf(value) {
    var v = value;
    asm volatile (""
        : [v] "+r" (v),
    );
    return v;
}

fn now(io: std.Io) std.Io.Timestamp {
    return std.Io.Timestamp.now(io, .awake);
}

fn elapsedNs(io: std.Io, started: std.Io.Timestamp) f64 {
    return @floatFromInt(started.durationTo(now(io)).nanoseconds);
}

const calibration_adds: usize = 100_000_000;

/// Цепочка зависимых сложений: ровно по такту на сложение на любом
/// современном ядре, поэтому частота это число сложений на время.
fn addChain(n: usize) u64 {
    var acc: u64 = 1;
    const step: u64 = blackBox(@as(u64, 7));
    var i: usize = 0;
    while (i < n) : (i += 1) acc = blackBox(acc +% step);
    return acc;
}

pub const Clock = struct {
    io: std.Io,
    /// Тактов в наносекунду.
    ghz: f64,

    pub fn init(io: std.Io) Clock {
        var best_ns: f64 = std.math.inf(f64);
        for (0..5) |_| {
            const started = now(io);
            const result = addChain(calibration_adds);
            const ns = elapsedNs(io, started);
            std.mem.doNotOptimizeAway(result);
            best_ns = @min(best_ns, ns);
        }
        return .{ .io = io, .ghz = @as(f64, @floatFromInt(calibration_adds)) / best_ns };
    }

    /// Такты одного вызова `ctx.run()`: два разогрева, потом минимум из семи.
    pub fn cycles(self: Clock, ctx: anytype) f64 {
        var best_ns: f64 = std.math.inf(f64);
        for (0..9) |run| {
            const started = now(self.io);
            ctx.run();
            const ns = elapsedNs(self.io, started);
            if (run >= 2) best_ns = @min(best_ns, ns);
        }
        return best_ns * self.ghz;
    }
};

test "blackBox возвращает значение как есть" {
    try std.testing.expectEqual(@as(u64, 42), blackBox(@as(u64, 42)));
}

Одно предупреждение, которое пригодится на каждом замере сегодня. blackBox нужен не для красоты. Стоит убрать его из цикла копирования, и LLVM узнает идиому, заменит цикл вызовом memmove и покажет тебе CPE библиотечной функции вместо твоей. Стоит убрать его с указателей в write_read, и компилятор увидит, что src и dest это разные локальные переменные, и заменит миллион итераций одной записью. Замер, из которого убрали blackBox, чаще всего меряет не то, что ты думаешь.

Стена первая: регистров шестнадцать

В прошлом уроке k аккумуляторов делили цепочку на k частей, и при k около десяти произведение целых ложилось на границу пропускной способности. Что будет при k = 20? Аккумуляторов двадцать, регистров общего назначения в x86-64 шестнадцать, из них %rsp занят стеком, ещё несколько нужны под указатель на данные, счётчик и длину. Остальные аккумуляторы компилятору некуда положить, кроме как на стек.

Это называется вытеснение регистров, и его прекрасно видно в ассемблере. Берём произведение, а не сумму, нарочно: для суммы целых LLVM умеет упаковать пары аккумуляторов в XMM-регистры и сложить их одной paddq, а для 64-битного умножения такой инструкции в базовом наборе x86-64 нет, и аккумуляторы остаются в регистрах общего назначения.

//! Развёртка k x k для произведения: аккумуляторов больше, чем регистров.

fn productKxK(comptime k: usize, data: []const i64) i64 {
    var acc: [k]i64 = @splat(1);
    var i: usize = 0;
    while (i + k <= data.len) : (i += k) {
        inline for (0..k) |j| acc[j] *%= data[i + j];
    }
    while (i < data.len) : (i += 1) acc[0] *%= data[i];
    var result = acc[0];
    inline for (1..k) |j| result *%= acc[j];
    return result;
}

export fn product10(ptr: [*]const i64, len: usize) i64 {
    return productKxK(10, ptr[0..len]);
}

export fn product20(ptr: [*]const i64, len: usize) i64 {
    return productKxK(20, ptr[0..len]);
}

Функции помечены export, иначе они встроятся в место вызова и отдельного тела в ассемблере не будет. Снимаем:

zig build-obj spill.zig -O ReleaseFast -fstrip -femit-asm=spill.s -fno-emit-bin -target x86_64-linux

Горячий цикл product10, синтаксис Intel, как печатает -femit-asm. Десять аккумуляторов лежат в десяти регистрах, каждая итерация это десять imul с операндом из памяти и ничего больше:

.LBB1_9:
	imul	rdx, qword ptr [rdi + 8*r13]
	imul	rax, qword ptr [rdi + 8*r13 + 8]
	imul	r10, qword ptr [rdi + 8*r13 + 16]
	imul	r11, qword ptr [rdi + 8*r13 + 24]
	imul	r8, qword ptr [rdi + 8*r13 + 32]
	imul	r15, qword ptr [rdi + 8*r13 + 40]
	imul	r9, qword ptr [rdi + 8*r13 + 48]
	imul	rbx, qword ptr [rdi + 8*r13 + 56]
	imul	r14, qword ptr [rdi + 8*r13 + 64]
	imul	rcx, qword ptr [rdi + 8*r13 + 72]
	...
	jbe	.LBB1_9

А вот product20. Первые девять аккумуляторов остались в регистрах, а дальше начинается то, чего в цикле быть не должно:

.LBB0_10:
	imul	rdx, qword ptr [rdi + 8*rcx]
	imul	r8, qword ptr [rdi + 8*rcx + 8]
	imul	rax, qword ptr [rdi + 8*rcx + 16]
	imul	r10, qword ptr [rdi + 8*rcx + 24]
	imul	r13, qword ptr [rdi + 8*rcx + 32]
	imul	r12, qword ptr [rdi + 8*rcx + 40]
	imul	r9, qword ptr [rdi + 8*rcx + 48]
	imul	rbx, qword ptr [rdi + 8*rcx + 56]
	imul	r11, qword ptr [rdi + 8*rcx + 64]
	mov	rsi, qword ptr [rbp - 56]
	imul	rsi, qword ptr [rdi + 8*rcx + 72]
	mov	qword ptr [rbp - 56], rsi
	mov	rsi, qword ptr [rbp - 48]
	imul	rsi, qword ptr [rdi + 8*rcx + 80]
	mov	qword ptr [rbp - 48], rsi
	imul	r15, qword ptr [rdi + 8*rcx + 88]
	mov	rsi, qword ptr [rbp - 96]
	imul	rsi, qword ptr [rdi + 8*rcx + 96]
	mov	qword ptr [rbp - 96], rsi
	...
	cmp	rcx, qword ptr [rbp - 120]
	mov	rcx, rsi
	jbe	.LBB0_10

Аккумулятор номер десять живёт по адресу [rbp - 56]. На каждой итерации его загружают в %rsi, умножают и кладут обратно. Так выглядят девять из двадцати аккумуляторов, и даже длина массива, [rbp - 120], не поместилась в регистр: её читают из памяти в самом cmp. Тройка mov, imul, mov вместо одного imul это не просто три инструкции вместо одной. Между mov qword ptr [rbp - 56], rsi на этой итерации и mov rsi, qword ptr [rbp - 56] на следующей стоит зависимость через память, и у неё своя задержка, о которой третья часть урока. Цепочка этого аккумулятора стала длиннее не на такт, а на пять или семь.

Сколько это стоит в тактах? Меряем на нашей машине k от 1 до 40:

//! Сколько стоит вытеснение: произведение с k аккумуляторами при k = 1, 4, 10, 20, 40.

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

fn productKxK(comptime k: usize, data: []const i64) i64 {
    var acc: [k]i64 = @splat(1);
    var i: usize = 0;
    while (i + k <= data.len) : (i += k) {
        inline for (0..k) |j| acc[j] *%= data[i + j];
    }
    while (i < data.len) : (i += 1) acc[0] *%= data[i];
    var result = acc[0];
    inline for (1..k) |j| result *%= acc[j];
    return result;
}

const n: usize = 8000;

fn Case(comptime k: usize) type {
    return struct {
        data: []const i64,
        pub fn run(self: @This()) void {
            for (0..100) |_| std.mem.doNotOptimizeAway(productKxK(k, clock.blackBox(self.data.ptr)[0..n]));
        }
    };
}

pub fn main(init: std.process.Init) !void {
    var out: [128]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &out);
    const timer = clock.Clock.init(init.io);
    try w.interface.print("частота по калибровке: {d:.2} ГГц\n", .{timer.ghz});

    var data: [n]i64 = undefined;
    for (&data, 0..) |*x, i| x.* = @intCast(i % 3 + 1);

    inline for ([_]usize{ 1, 4, 10, 20, 40 }) |k| {
        const cycles = timer.cycles(Case(k){ .data = &data });
        try w.interface.print("k = {d:>2}: CPE {d:.2}\n", .{ k, cycles / 100 / n });
    }
    try w.interface.flush();
}

частота по калибровке: 4.47 ГГц
k =  1: CPE 2.96
k =  4: CPE 0.76
k = 10: CPE 0.33
k = 20: CPE 0.34
k = 40: CPE 0.45

Первые три строки повторяют прошлый урок: один аккумулятор упирается в задержку умножения (2.99 такта на M4), четыре делят её на четыре, десять достают до границы пропускной способности 0.33. А дальше интересное. При k = 20 вытеснения на нашей машине ещё нет, потому что у aarch64 тридцать один регистр общего назначения, а не шестнадцать: ассемблер под aarch64-macos для product20 держит все двадцать аккумуляторов в x-регистрах, только в прологе сохраняет x19 до x28 на стек, как велит соглашение о вызовах. При k = 40 регистров не хватает уже и здесь, и CPE поднимается с 0.33 до 0.45. На x86-64 тот же подъём случился бы уже между k = 10 и k = 20, ты видел его причину в листинге выше.

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

Стена вторая: переход, который нельзя угадать

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

Возьмём сумму элементов, меньших 128. Две версии: с настоящим переходом и без него, где сравнение превращается в маску из всех единиц или всех нулей, и слагаемое либо проходит через and целиком, либо обнуляется.

//! Ветвление в горячем цикле: переход против условной пересылки,
//! случайные данные против отсортированных.

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

/// Сумма элементов меньше 128 через настоящий условный переход.
noinline fn sumBelowBranch(data: []const i64) i64 {
    var sum: i64 = 0;
    for (data) |item| {
        const x = clock.blackBox(item);
        if (x < 128) {
            // Сложение спрятано за asm, поэтому его нельзя выполнить
            // заранее и выбрать результат: остаётся настоящий переход.
            sum = clock.blackBox(sum +% x);
        }
    }
    return sum;
}

/// То же самое без ветки: сравнение превращается в маску, и слагаемое
/// либо проходит через `and` целиком, либо обнуляется.
noinline fn sumBelowMask(data: []const i64) i64 {
    var sum: i64 = 0;
    for (data) |item| {
        const x = clock.blackBox(item);
        // Маска из сравнения: все единицы, если x < 128, иначе нули.
        const keep: i64 = clock.blackBox(-@as(i64, @intFromBool(x < 128)));
        sum +%= x & keep;
    }
    return sum;
}

const n: usize = 16384;

const Case = struct {
    data: []const i64,
    select: bool,

    pub fn run(self: Case) void {
        for (0..50) |_| {
            const result = if (self.select) sumBelowMask(self.data) else sumBelowBranch(self.data);
            std.mem.doNotOptimizeAway(result);
        }
    }
};

pub fn main(init: std.process.Init) !void {
    var out: [128]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &out);
    const timer = clock.Clock.init(init.io);
    try w.interface.print("частота по калибровке: {d:.2} ГГц\n", .{timer.ghz});

    var random: [n]i64 = undefined;
    var prng = std.Random.DefaultPrng.init(42);
    for (&random) |*x| x.* = prng.random().intRangeAtMost(i64, 0, 255);
    var sorted = random;
    std.mem.sort(i64, &sorted, {}, std.sort.asc(i64));

    const rows = [_]struct { name: []const u8, data: []const i64, select: bool }{
        .{ .name = "переход, случайные", .data = &random, .select = false },
        .{ .name = "переход, сортированные", .data = &sorted, .select = false },
        .{ .name = "cmov, случайные", .data = &random, .select = true },
        .{ .name = "cmov, сортированные", .data = &sorted, .select = true },
    };
    for (rows) |row| {
        const cycles = timer.cycles(Case{ .data = row.data, .select = row.select });
        try w.interface.print("{s:<24} CPE {d:.2}\n", .{ row.name, cycles / 50 / n });
    }
    try w.interface.flush();
}

test "обе версии считают одно и то же" {
    const data = [_]i64{ 1, 200, 127, 128, 0, 255, 5 };
    try std.testing.expectEqual(@as(i64, 133), sumBelowBranch(&data));
    try std.testing.expectEqual(@as(i64, 133), sumBelowMask(&data));
}

Два blackBox внутри циклов стоят не зря. Без них LLVM делает то, что должен делать хороший компилятор: замечает, что обе функции считают одно и то же, склеивает их в одну и сам выбирает форму без перехода. Тогда сравнивать нечего. Мы связываем ему руки, чтобы увидеть обе формы в чистом виде. Ассемблер под x86_64-linux, только тела циклов:

.Lbranch.sumBelowBranch:
.LBB1_3:
	mov	rdx, qword ptr [rdi + 8*rcx]
	cmp	rdx, 128
	jge	.LBB1_4
	add	rdx, rax
	mov	rax, rdx
	jmp	.LBB1_4
.LBB1_4:
	add	rcx, 1
	cmp	rsi, rcx
	je	.LBB1_5

.Lbranch.sumBelowMask:
.LBB0_3:
	mov	rdx, qword ptr [rdi + 8*rcx]
	xor	r8d, r8d
	cmp	rdx, 128
	setl	r8b
	neg	r8
	and	r8, rdx
	add	rax, r8
	add	rcx, 1
	cmp	rsi, rcx
	jne	.LBB0_3

В первой версии jge зависит от данных, во второй переход только один, на конец цикла, и он всегда предсказуем. Под aarch64 картина та же: b.ge против csetm плюс and. Числа:

частота по калибровке: 4.49 ГГц
переход, случайные       CPE 7.87
переход, сортированные   CPE 1.03
cmov, случайные          CPE 1.27
cmov, сортированные      CPE 1.27

Разбираем построчно. Случайные данные и переход: половина переходов угадана неверно, промах стоит около 14 тактов, среднее 7.87 на элемент. Отсортированные данные и тот же код: предсказатель ошибается один раз на весь массив, там, где элементы переваливают через 128, и цикл идёт по такту на элемент. Маска не зависит от данных вовсе, но платит за лишние инструкции постоянные 1.27 в обоих случаях.

Отсюда правило, которое компилятор применить не может, потому что не знает твоих данных. Если условие предсказуемо (отсортированный массив, редкая ветка ошибки, проверка границ, которая почти всегда проходит), переход дешевле любой безусловной формы: он бесплатен, а cmov заставляет вычислять обе ветви. Если условие случайно относительно истории (сравнение с медианой, фильтр по хэшу, слияние двух отсортированных потоков), безусловная форма выигрывает в разы: у нас 7.87 против 1.27. Компилятор выбирает по эвристике, и когда он ошибается в горячем цикле, форму приходится диктовать руками, как мы сделали через маску.

Пример второго случая из книги: шаг слияния из сортировки слиянием, упражнение 5.9 в нашей формулировке. Два отсортированных среза, left и right, сливаются в dest: на каждом шаге берётся меньший из двух текущих элементов. Условие left[i] < right[j] для двух независимо перемешанных потоков это почти монета, и версия с if платит промах через шаг. Перепиши тело так, чтобы оба кандидата загружались всегда, а выбор и продвижение индексов делались арифметикой:

const std = @import("std");

/// Шаг слияния без перехода в теле цикла: оба кандидата прочитаны,
/// выбор и сдвиг индексов сделаны через 0 или 1 из сравнения.
pub fn mergeBranchless(dest: []i64, left: []const i64, right: []const i64) void {
    var i: usize = 0;
    var j: usize = 0;
    var k: usize = 0;
    while (i < left.len and j < right.len) : (k += 1) {
        const a = left[i];
        const b = right[j];
        const take_left: usize = @intFromBool(a < b);
        dest[k] = if (take_left == 1) a else b;
        i += take_left;
        j += 1 - take_left;
    }
    // Один из хвостов пуст, другой копируется как есть.
    @memcpy(dest[k .. k + left.len - i], left[i..]);
    k += left.len - i;
    @memcpy(dest[k .. k + right.len - j], right[j..]);
}

test "слияние двух отсортированных срезов" {
    const left = [_]i64{ 1, 4, 5, 9 };
    const right = [_]i64{ 2, 3, 8, 10, 11 };
    var dest: [9]i64 = undefined;
    mergeBranchless(&dest, &left, &right);
    try std.testing.expectEqualSlices(i64, &[_]i64{ 1, 2, 3, 4, 5, 8, 9, 10, 11 }, &dest);
}

test "пустой левый и пустой правый" {
    const some = [_]i64{ 3, 7 };
    var dest: [2]i64 = undefined;
    mergeBranchless(&dest, &[_]i64{}, &some);
    try std.testing.expectEqualSlices(i64, &some, &dest);
    mergeBranchless(&dest, &some, &[_]i64{});
    try std.testing.expectEqualSlices(i64, &some, &dest);
}

Выражение if (take_left == 1) a else b компилятор превращает в cmov, потому что обе стороны уже вычислены и побочных эффектов нет; i += take_left и j += 1 - take_left это два сложения без всякого условия. В домашнем задании ты снимешь ассемблер и проверишь, что в цикле не осталось jl, а потом сравнишь CPE двух версий на случайных данных.

Стена третья: загрузка и сохранение

До сих пор память в наших циклах была только источником: data[i] читается, аккумулятор живёт в регистре. Добавим записи, и появится новый класс зависимостей, которых в графе потока данных не видно, пока не посмотришь на адреса.

Начнём с модели. Блок загрузки и блок сохранения это такие же исполнительные блоки, как сумматоры, у каждого своя пропускная способность. На M4 загрузок за такт можно выдать три, сохранений два; на x86-64 Haswell из книги две загрузки и одно сохранение. Уже отсюда следует нижняя граница любого цикла с записью: если на элемент приходится по одному сохранению, цикл не может идти быстрее одного элемента за такт на Haswell и половины такта на M4, что бы ни делала арифметика.

Сохранение устроено сложнее загрузки. Инструкция mov qword ptr [rdi], rax не пишет в кэш сразу: она кладёт пару «адрес, данные» в буфер записи, и уходит в кэш только когда инструкция сохранения отработала до конца. Адрес известен рано, его считает блок вычисления адреса; данные могут прийти позже, когда доехала цепочка, которая их вычисляет. А каждая загрузка сверяет свой адрес со всеми адресами в буфере. Совпал: значение нельзя брать из кэша, оно устарело, надо ждать, пока у сохранения появятся данные, и переслать их из буфера в загрузку. Эта пересылка и есть звено цепочки через память, и на Haswell книга оценивает его так: сохранение данных в буфер 2 такта, загрузка 4 такта, вместе с арифметикой между ними около 7 тактов на итерацию.

Проверим на программе из книги. write_read делает n раз одно и то же: записать value по dest, прочитать src, прибавить единицу. Пока src и dest разные адреса, чтение не зависит от записи, и итерации накладываются друг на друга. Если это один адрес, чтение на каждой итерации ждёт запись с предыдущей:

//! Зависимость запись/чтение: сохранить в dest, прочитать из src.
//! Пока адреса разные, такты не зависят друг от друга. Как только src
//! и dest один адрес, каждое чтение ждёт предыдущую запись.

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

/// Пример из книги: `*dest = val; val = *src + 1`, n раз.
noinline fn writeRead(src: *i64, dest: *i64, n: usize) void {
    var count = n;
    var value: i64 = 0;
    while (count > 0) : (count -= 1) {
        dest.* = value;
        value = src.* +% 1;
    }
}

const Case = struct {
    src: *i64,
    dest: *i64,
    n: usize,

    pub fn run(self: Case) void {
        writeRead(self.src, self.dest, self.n);
        std.mem.doNotOptimizeAway(self.dest.*);
    }
};

pub fn main(init: std.process.Init) !void {
    var buf: [128]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const timer = clock.Clock.init(init.io);
    try w.interface.print("частота по калибровке: {d:.2} ГГц\n", .{timer.ghz});

    var a: i64 = 0;
    var b: i64 = 0;
    const n: usize = 1_000_000;
    // Указатели прячем от компилятора: иначе он видит, что a и b
    // разные переменные, и заменяет весь цикл одной записью.
    const pa = clock.blackBox(&a);
    const pb = clock.blackBox(&b);

    const apart = timer.cycles(Case{ .src = pa, .dest = pb, .n = n });
    const same = timer.cycles(Case{ .src = pa, .dest = pa, .n = n });
    try w.interface.print("разные адреса: {d:.2} такта на итерацию\n", .{apart / n});
    try w.interface.print("один адрес:    {d:.2} такта на итерацию\n", .{same / n});
    try w.interface.flush();
}

test "с разными адресами в dest остаётся src + 1" {
    var src: i64 = 10;
    var dest: i64 = 0;
    writeRead(&src, &dest, 5);
    try std.testing.expectEqual(@as(i64, 11), dest);
}

test "с одним адресом ячейка считает" {
    var cell: i64 = 0;
    writeRead(&cell, &cell, 5);
    try std.testing.expectEqual(@as(i64, 4), cell);
}

частота по калибровке: 4.48 ГГц
разные адреса: 0.99 такта на итерацию
один адрес:    6.96 такта на итерацию

Один и тот же машинный код, одна и та же функция, а разница в семь раз. Ни в исходнике, ни в ассемблере, ни в графе потока данных по регистрам этой цепочки нет: она возникает во время исполнения, когда блок загрузки находит свой адрес в буфере записи. Книжный Haswell даёт 1.3 против 7.3, наш M4 даёт 0.99 против 6.96, звено цепочки почти той же длины, хотя между чипами одиннадцать лет.

Проиграй эту цепочку по тактам. Виджет держит книжные задержки (загрузка 4, данные в буфер 2, уход в кэш 1), а ты выбираешь цикл и сдвиг между адресами. При нулевом сдвиге в write_read каждая загрузка после первой останавливается в фазе ожидания, пока у предыдущего сохранения не появятся данные, и установившийся CPE выходит ровно 7. При сдвиге в один и больше элементов буфер записи адрес не находит, и цикл идёт по такту.

Второй пресет виджета это копирование внутри одного буфера, и здесь стоит остановиться на упражнении 5.10 книги. Функция копирования copy_array(dest, src, n) делает dest[i] = src[i] для i от 0 до n. Три вызова на одном массиве a:

copy_array(a + 1, a, 999): приёмник впереди источника на один элемент. Итерация i записывает a[i + 1], итерация i + 1 читает его же. Цепочка через память на каждом шаге, и по модели книги CPE около 7.
copy_array(a, a + 1, 999): приёмник позади. Итерация i записывает a[i], а читает a[i + 1], куда никто ещё не писал. Зависимости нет, около 1.
copy_array(a, a, 999): приёмник и источник совпадают. Кажется, что это худший случай, но посмотри на адреса: итерация i читает a[i] и пишет в a[i], а следующая читает a[i + 1], куда эта итерация не писала. Сохранение зависит от загрузки, но ни одна загрузка не зависит от сохранения. CPE около 1.

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

//! Копирование внутри одного буфера со сдвигом: элемент, записанный на
//! шаге i, читается на шаге i + shift. Чем меньше сдвиг, тем длиннее
//! цепочка через память. Два варианта: чистая копия и копия с операцией.

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

/// `buf[i + shift] = buf[i]` для i от 0 до count.
noinline fn copyShifted(buf: []i64, shift: usize, count: usize) void {
    var i: usize = 0;
    while (i < count) : (i += 1) {
        // blackBox не даёт компилятору узнать в цикле идиому и заменить
        // его на memset или memmove: мы меряем именно этот цикл.
        buf[i + shift] = clock.blackBox(buf[i]);
    }
}

/// То же, но между загрузкой и сохранением стоит сложение.
noinline fn copyShiftedPlusOne(buf: []i64, shift: usize, count: usize) void {
    var i: usize = 0;
    while (i < count) : (i += 1) {
        buf[i + shift] = clock.blackBox(buf[i]) +% 1;
    }
}

const n: usize = 8192;
const shifts = [_]usize{ 1, 2, 3, 4, 8, 64, 1024 };

const Case = struct {
    buf: []i64,
    shift: usize,
    plus_one: bool,

    pub fn run(self: Case) void {
        // Один вызов слишком короток для часов, повторяем сто раз.
        for (0..100) |_| {
            const shift = clock.blackBox(self.shift);
            if (self.plus_one) copyShiftedPlusOne(self.buf, shift, n) else copyShifted(self.buf, shift, n);
        }
        std.mem.doNotOptimizeAway(self.buf[n]);
    }
};

pub fn main(init: std.process.Init) !void {
    var out: [128]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &out);
    const timer = clock.Clock.init(init.io);
    try w.interface.print("частота по калибровке: {d:.2} ГГц\n", .{timer.ghz});

    var storage: [n + 1024]i64 = undefined;
    for (&storage, 0..) |*x, i| x.* = @intCast(i);

    try w.interface.print("{s:>6} {s:>12} {s:>14}\n", .{ "сдвиг", "копия, CPE", "копия + 1, CPE" });
    for (shifts) |shift| {
        const plain = timer.cycles(Case{ .buf = &storage, .shift = shift, .plus_one = false });
        const plus = timer.cycles(Case{ .buf = &storage, .shift = shift, .plus_one = true });
        try w.interface.print("{d:>6} {d:>12.2} {d:>14.2}\n", .{ shift, plain / 100 / n, plus / 100 / n });
    }
    try w.interface.flush();
}

test "сдвиг 1 размножает первый элемент" {
    var buf = [_]i64{ 7, 1, 2, 3, 4, 5 };
    copyShifted(&buf, 1, 5);
    try std.testing.expectEqualSlices(i64, &[_]i64{ 7, 7, 7, 7, 7, 7 }, &buf);
}

test "положительный сдвиг это цикл std.mem.copyForwards" {
    var got = [_]i64{ 1, 2, 3, 4, 5, 6, 7, 8 };
    var expected = got;
    copyShifted(&got, 2, 6);
    std.mem.copyForwards(i64, expected[2..8], expected[0..6]);
    try std.testing.expectEqualSlices(i64, &expected, &got);
}

test "копия с единицей наращивает по цепочке" {
    var buf = [_]i64{ 0, 9, 9, 9 };
    copyShiftedPlusOne(&buf, 1, 3);
    try std.testing.expectEqualSlices(i64, &[_]i64{ 0, 1, 2, 3 }, &buf);
}

Два прогона подряд на нашей машине:

частота по калибровке: 4.02 ГГц
 сдвиг   копия, CPE копия + 1, CPE
     1         1.01           4.75
     2         1.01           1.01
     3         1.00           1.00
     4         1.00           1.00
     8         1.17           1.46
    64         1.02           1.00
  1024         1.02           1.00

частота по калибровке: 4.09 ГГц
 сдвиг   копия, CPE копия + 1, CPE
     1         1.01           1.00
     2         1.00           1.00
     ...

Здесь модель книги и наша машина расходятся, и это стоит разобрать честно, а не прятать. Чистая копия со сдвигом 1 на M4 идёт по такту на элемент, хотя каждая загрузка читает ровно то, что сохранила предыдущая итерация. Apple Silicon умеет переименовывать память: если загрузка точно совпадает по адресу и размеру с недавним сохранением, значение прокидывается из регистра в регистр, минуя буфер записи, и цепочка исчезает. Как только между загрузкой и сохранением встаёт сложение, цепочка возвращается, 4.75 такта на элемент, а на сдвиге 2 две цепочки вперемешку укладываются в такт. И даже это работает не всегда: второй прогон той же программы дал 1.00 на сдвиге 1, потому что предсказатель зависимостей по памяти в этот раз распознал шаблон и обошёл буфер. На Haswell из книги никакого переименования нет, и copy_array(a + 1, a, 999) стабильно стоит 7.3.

Два вывода. Первый: модель «сохранение, потом загрузка того же адреса это от 5 до 7 тактов» остаётся верной нижней оценкой, когда между ними есть вычисление; write_read показал это без всяких оговорок. Второй: когда замер противоречит модели, виновата не модель и не замер, а неучтённый механизм, и его надо найти по имени. Разница между двумя прогонами одной программы это не шум, это предсказатель, и такие вещи выясняют не усреднением, а чтением документации на микроархитектуру.

И последнее про копирование, уже не про такты, а про правильность. copyShifted со сдвигом 1 не сдвигает массив, а размножает первый элемент, потому что читает то, что сама только что записала. Ровно так ведёт себя std.mem.copyForwards, и ровно поэтому в стандартной библиотеке есть std.mem.copyBackwards: при пересекающихся срезах, где приёмник впереди источника, копировать нужно с конца. Тест в листинге проверяет, что наш цикл совпадает с copyForwards; с copyBackwards он совпал бы только там, где срезы не пересекаются.

memset словами: голова, середина, хвост

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

Отсюда три части. Голова: байты от начала среза до первого адреса, кратного восьми, пишутся побайтно; если срез уже выровнен, головы нет. Середина: целые слова, где значение размножено на все восемь байт умножением на 0x0101010101010101. Хвост: остаток меньше слова, снова побайтно.

//! Заполнение памяти: побайтно и словами.

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

/// Наивно: по байту за итерацию. Без blackBox компилятор узнаёт идиому
/// и заменяет весь цикл вызовом memset из libc, мерить было бы нечего.
pub fn memsetByte(dest: []u8, value: u8) void {
    for (dest) |*byte| byte.* = clock.blackBox(value);
}

/// Словами `usize`: голова до выравнивания, тело словами, хвост побайтно.
pub fn memsetWord(dest: []u8, value: u8) void {
    const word_size = @sizeOf(usize);
    const address = @intFromPtr(dest.ptr);
    // Сколько байт до ближайшей границы слова (0, если уже на ней).
    const head = @min(dest.len, (word_size - address % word_size) % word_size);

    var i: usize = 0;
    while (i < head) : (i += 1) dest[i] = value;

    // Слово из восьми копий байта: 0x0101...01 * value.
    const word: usize = @as(usize, value) * (std.math.maxInt(usize) / 0xff);
    const body_end = head + (dest.len - head) / word_size * word_size;
    while (i < body_end) : (i += word_size) {
        const target: *align(1) usize = @ptrCast(dest[i..][0..word_size]);
        target.* = word;
    }

    while (i < dest.len) : (i += 1) dest[i] = value;
}

const Kind = enum { byte, word, builtin };

const Case = struct {
    dest: []u8,
    kind: Kind,

    pub fn run(self: Case) void {
        const value = clock.blackBox(@as(u8, 0xab));
        for (0..64) |_| {
            // Указатель прячем на каждом повторе: иначе 63 заполнения из 64
            // выбрасываются как мёртвые записи, их всё равно перезапишут.
            const dest = clock.blackBox(self.dest.ptr)[0..self.dest.len];
            switch (self.kind) {
                .byte => memsetByte(dest, value),
                .word => memsetWord(dest, value),
                .builtin => @memset(dest, value),
            }
            std.mem.doNotOptimizeAway(dest[dest.len - 1]);
        }
    }
};

pub fn main(init: std.process.Init) !void {
    var out: [128]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &out);
    const timer = clock.Clock.init(init.io);
    try w.interface.print("частота по калибровке: {d:.2} ГГц\n", .{timer.ghz});

    var storage: [64 * 1024 + 16]u8 align(16) = undefined;
    const names = [_][]const u8{ "побайтно", "словами", "@memset" };
    const kinds = [_]Kind{ .byte, .word, .builtin };
    for (names, kinds) |name, kind| {
        const aligned = timer.cycles(Case{ .dest = storage[0 .. 64 * 1024], .kind = kind });
        const shifted = timer.cycles(Case{ .dest = storage[3 .. 64 * 1024 + 3], .kind = kind });
        try w.interface.print("{s:<10} выровнено {d:.3} такта на байт, со сдвигом 3 {d:.3}\n", .{
            name, aligned / 64 / (64 * 1024), shifted / 64 / (64 * 1024),
        });
    }
    try w.interface.flush();
}

test "словами то же, что побайтно, на всех длинах и сдвигах" {
    var expected: [80]u8 = undefined;
    var got: [80]u8 = undefined;
    for (0..8) |offset| {
        var length: usize = 0;
        while (offset + length <= expected.len) : (length += 1) {
            @memset(&expected, 0);
            @memset(&got, 0);
            memsetByte(expected[offset..][0..length], 0xab);
            memsetWord(got[offset..][0..length], 0xab);
            try std.testing.expectEqualSlices(u8, &expected, &got);
        }
    }
}

Формула головы (word_size - address % word_size) % word_size заслуживает минуты. Если адрес уже кратен восьми, address % 8 это 0, 8 - 0 это 8, а 8 % 8 снова 0: головы нет. Если адрес даёт остаток 3, до границы пять байт: (8 - 3) % 8 = 5. Внешний @min с длиной среза нужен для коротких срезов: у среза из трёх байт с остатком 3 голова съедает всё, и слов не остаётся. Тест перебирает все восемь сдвигов начала и все длины до 80, потому что ошибки в такой арифметике живут именно на границах.

Теперь ассемблер memsetWord под x86_64-linux. Он расскажет больше, чем я ожидал:

memsetWord:
	mov	r15d, r14d
	neg	r15d
	and	r15d, 7            ; голова: (-address) & 7
	cmp	rsi, r15
	cmovb	r15, rsi           ; @min(len, head)
	movzx	r12d, dl
	test	r15, r15
	je	.LBB0_2
	mov	rdi, r14
	mov	esi, r12d
	mov	rdx, r15
	call	memset@PLT         ; голова: цикл узнан и заменён вызовом
.LBB0_2:
	mov	rax, rbx
	sub	rax, r15
	and	rax, -8            ; длина середины, кратная 8
	je	.LBB0_5
	movabs	rcx, 72340172838076673   ; 0x0101010101010101
	imul	rcx, r12           ; слово из восьми копий байта
	or	rax, r15
.LBB0_4:
	mov	qword ptr [r14 + r15], rcx
	add	r15, 8
	cmp	r15, rax
	jb	.LBB0_4
.LBB0_5:
	sub	rbx, r15
	jbe	.LBB0_6
	...
	jmp	memset@PLT         ; хвост: то же самое, хвостовой вызов

Середина скомпилировалась в точности как задумано: movabs с магической константой, одно imul, и цикл из одного сохранения на восемь байт. А вот голову и хвост LLVM узнал как идиому и заменил вызовами библиотечного memset, с настоящим call на голове и хвостовым jmp на хвосте. Для семи байт это откровенно дорого: вызов, пролог, диспетчер по длине внутри libc. Так компилятор сам показывает, что побайтный цикл ему не нравится, и одновременно напоминает: то, что ты написал, и то, что исполняется, разные вещи, пока не посмотришь в ассемблер.

Числа, 64 КБ, всё внутри L1:

частота по калибровке: 4.49 ГГц
побайтно   выровнено 0.996 такта на байт, со сдвигом 3 1.022
словами    выровнено 0.125 такта на байт, со сдвигом 3 0.125
@memset    выровнено 0.032 такта на байт, со сдвигом 3 0.032

Побайтная версия идёт ровно по такту на байт, как и предсказывает граница одного сохранения за такт: наш blackBox не даёт ей ни векторизоваться, ни стать memset. Словами ровно в восемь раз быстрее, 0.125 такта на байт, то есть одно сохранение за такт, только теперь по восемь байт. Сдвиг начала на три байта ничего не меняет: голова из пяти байт на 64 КБ незаметна. А встроенный @memset ещё вчетверо быстрее словной версии, потому что пишет 32-байтными векторными сохранениями и по два за такт. Это следующий уровень той же лестницы, и о нём последняя часть урока.

Дальше книги: ширина вместо количества

Все границы в последних уроках считались в операциях за такт: столько-то сумматоров, столько-то умножителей, столько-то блоков сохранения. Но операция необязательно обрабатывает одно число. В уроке про плавающую точку и SIMD ты видел, что регистр YMM держит четыре f64 или восемь f32, и vaddpd складывает все дорожки одной инструкцией. Значит, тот же сумматор за тот же такт делает в четыре раза больше работы, и границу пропускной способности можно обойти не количеством блоков, а шириной данных.

В Zig для этого есть @Vector(N, T). Аккумулятор становится вектором: lanes независимых цепочек в одном регистре. А чтобы закрыть задержку, векторных аккумуляторов берём несколько, ровно по тем же соображениям, что и в прошлом уроке. Хвост, не кратный ширине блока, добивается скалярно, а в конце вектор сворачивается в число через @reduce.

//! Свёртка через `@Vector`: одна инструкция обрабатывает несколько
//! элементов, а несколько векторных аккумуляторов закрывают задержку.

const std = @import("std");

pub const Op = enum { add, mul };

pub fn ident(comptime T: type, comptime op: Op) T {
    return switch (op) {
        .add => 0,
        .mul => 1,
    };
}

/// Операция над скаляром или над вектором: у целых с заворачиванием.
pub inline fn apply(comptime T: type, comptime op: Op, a: T, b: T) T {
    const Elem = switch (@typeInfo(T)) {
        .vector => |v| v.child,
        else => T,
    };
    return switch (@typeInfo(Elem)) {
        .int => switch (op) {
            .add => a +% b,
            .mul => a *% b,
        },
        else => switch (op) {
            .add => a + b,
            .mul => a * b,
        },
    };
}

/// Скалярный ориентир: combine4 из прошлых уроков.
pub fn combine4(comptime T: type, comptime op: Op, data: []const T) T {
    var acc = ident(T, op);
    for (data) |x| acc = apply(T, op, acc, x);
    return acc;
}

/// Ширина вектора по умолчанию: 4 дробных или 8 целых на аккумулятор.
pub fn defaultLanes(comptime T: type) usize {
    return if (@typeInfo(T) == .float) 4 else 8;
}

/// Свёртка через `@Vector(lanes, T)` с `accs` векторными аккумуляторами.
pub fn combineSimd(
    comptime T: type,
    comptime op: Op,
    comptime lanes: usize,
    comptime accs: usize,
    data: []const T,
) T {
    const V = @Vector(lanes, T);
    const block = lanes * accs;

    var acc: [accs]V = @splat(@splat(ident(T, op)));
    var i: usize = 0;
    while (i + block <= data.len) : (i += block) {
        inline for (0..accs) |j| {
            const chunk: V = data[i + j * lanes ..][0..lanes].*;
            acc[j] = apply(V, op, acc[j], chunk);
        }
    }

    var folded = acc[0];
    inline for (1..accs) |j| folded = apply(V, op, folded, acc[j]);
    var result = @reduce(if (op == .add) .Add else .Mul, folded);
    while (i < data.len) : (i += 1) result = apply(T, op, result, data[i]);
    return result;
}

pub fn combineSimd1(comptime T: type, comptime op: Op, data: []const T) T {
    return combineSimd(T, op, defaultLanes(T), 1, data);
}

pub fn combineSimd4(comptime T: type, comptime op: Op, data: []const T) T {
    return combineSimd(T, op, defaultLanes(T), 4, data);
}

test "векторная свёртка совпадает со скалярной, хвост тоже" {
    var data: [37]i64 = undefined;
    for (&data, 0..) |*x, i| x.* = @as(i64, @intCast(i % 5)) + 1;
    const expected = combine4(i64, .mul, &data);
    try std.testing.expectEqual(expected, combineSimd1(i64, .mul, &data));
    try std.testing.expectEqual(expected, combineSimd4(i64, .mul, &data));
}

test "дробное сложение сходится с точностью до порядка округления" {
    var data: [1000]f64 = undefined;
    for (&data, 0..) |*x, i| x.* = 0.1 * @as(f64, @floatFromInt(i % 7));
    const scalar = combine4(f64, .add, &data);
    const vector = combineSimd4(f64, .add, &data);
    try std.testing.expectApproxEqRel(scalar, vector, 1e-12);
}

test "длины 0 и 1 не ломают хвост" {
    const empty: [0]f64 = .{};
    try std.testing.expectEqual(@as(f64, 0), combineSimd4(f64, .add, &empty));
    const one = [_]f64{2.5};
    try std.testing.expectEqual(@as(f64, 2.5), combineSimd4(f64, .mul, &one));
}

Строка const chunk: V = data[i + j * lanes ..][0..lanes].*; это загрузка вектора: срез известной длины lanes разыменовывается в массив, а массив приводится к вектору без копирования. apply устроен так, что работает и над скаляром, и над вектором: у вектора он спрашивает тип элемента, потому что заворачивающие +% и *% есть у целых и нет у дробных, а сам векторный тип об этом молчит.

Второй тест важнее, чем кажется. Для дробных чисел векторная сумма даёт другой результат, чем скалярная: порядок сложений изменился, а сложение f64 не ассоциативно. Именно поэтому компилятор никогда не сделает такую трансформацию сам, ты видел это в прошлом уроке на combine7 для f64. Мы делаем её руками и тем самым берём ответственность за последние биты. Для целых с заворачиванием ассоциативность точная, и expectEqual там законен.

Во что это компилируется под AVX2, -target x86_64-linux -mcpu=x86_64_v3, сумма f64 с четырьмя аккумуляторами:

.LBB0_2:
	vaddpd	ymm0, ymm0, ymmword ptr [rdi + 8*rax]
	vaddpd	ymm1, ymm1, ymmword ptr [rdi + 8*rax + 32]
	vaddpd	ymm2, ymm2, ymmword ptr [rdi + 8*rax + 64]
	vaddpd	ymm3, ymm3, ymmword ptr [rdi + 8*rax + 96]
	add	rax, 16
	add	rcx, 32
	cmp	rcx, rsi
	jbe	.LBB0_2
	vaddpd	ymm0, ymm1, ymm0
	vaddpd	ymm0, ymm2, ymm0
	vaddpd	ymm0, ymm3, ymm0
.LBB0_4:
	vshufpd	xmm1, xmm0, xmm0, 1
	vaddsd	xmm1, xmm0, xmm1
	vextractf128	xmm0, ymm0, 1
	vaddsd	xmm1, xmm1, xmm0
	vshufpd	xmm0, xmm0, xmm0, 1
	vaddsd	xmm0, xmm1, xmm0

Четыре vaddpd на итерацию, каждая складывает четыре f64 прямо из памяти, шестнадцать элементов за итерацию. После цикла четыре аккумулятора складываются между собой, а @reduce разворачивается в горизонтальную сумму: перестановка дорожек, извлечение верхней половины и три скалярных vaddsd. Это ровно то дерево, которое ты рисовал в уроке про горизонтальную сумму.

Числа сняты тем же бенчмарком свёрток, что и в прошлых уроках, на Apple M4 Max (aarch64, NEON, регистр 128 бит, то есть две дорожки f64 или два i64), Zig 0.16.0, ReleaseFast, 2026-09-09; рядом границы для скалярной операции:

версия	i64 плюс	i64 умножить	f64 плюс	f64 умножить	приём
combine4	1.06	2.99	2.46	3.40	скалярный аккумулятор в регистре
combine6	0.73	1.50	1.26	1.75	два скалярных аккумулятора
simd1	0.27	2.14	0.66	0.88	вектор, один аккумулятор
simd4	0.19	1.12	0.20	0.25	вектор, четыре аккумулятора
граница задержки	1.00	2.99	2.49	3.42
граница пропускной способности	0.16	0.33	0.25	0.25

Смотри на столбец f64 плюс. Скалярный combine4 сидит на задержке 2.49. Один векторный аккумулятор даёт 0.66: цепочка та же, задержка та же, но каждое звено обрабатывает несколько элементов, поэтому на элемент выходит задержка, делённая на число дорожек. Четыре векторных аккумулятора дают 0.20 при границе пропускной способности 0.25 для скалярного сложения. То есть векторная версия зашла ниже границы, посчитанной для скалярных операций, потому что граница была про инструкции, а не про элементы. Настоящая граница для вектора это скалярная, делённая на ширину, и simd4 почти её достаёт по всем четырём столбцам. Единственное исключение это умножение целых: у NEON нет умножения 64-битных дорожек, компилятор разворачивает его в несколько инструкций, и выигрыш скромнее.

Эта же лестница объясняет @memset из прошлой части: побайтно по такту на байт, словами по восемь, векторами по тридцать два, и на каждой ступени число сохранений за такт не меняется, меняется только ширина каждого. Домашняя задача про memsetVector доводит нашу версию до той же ступени.

Шаг проекта: zl под предсказателем переходов

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

Диспетчер: один переход или двенадцать

Два диспетчера из урока про переходы и таблицы различаются ровно одним: runLoop выбирает команду в одном месте, runLabeled в конце каждой ветки. Сколько непрямых переходов получилось на самом деле, считаем в том же ReleaseFast, в котором меряли, под aarch64:

$ zig build asm -Doptimize=ReleaseFast
$ for f in runLoop runLabeled; do
    objdump -d --no-show-raw-insn --disassemble-symbols=_bytecode.Machine.$f zig-out/bin/zl-llvm |
      grep -cE '\sbr\s'
  done
1
12

Один br на весь цикл против двенадцати. Под x86-64 картина другая: там LLVM сам размножил хвост цикла, и в ReleaseFast у runLoop двенадцать jmp по регистру, у runLabeled тринадцать (мы считали это в уроке 13). Поэтому честное сравнение одного перехода с размноженными есть только здесь, на M4.

Классическое объяснение выигрыша labeled switch такое. Единственный переход в конце цикла видит все команды подряд, и если предсказатель помнит для него только последнюю цель, он ошибается почти всегда. Двенадцать переходов делят эту историю: переход в конце arg помнит, что после arg обычно идёт constant, и угадывает чаще. Проверим на числах из урока про устранение неэффективности:

Нагрузка	loop	labeled	разница
`fib`, тактов на вызов	311.6	290.7	7 процентов
`last`, тактов на ячейку	149.5	149.1	нет

Посчитаем, сколько стоил бы классический сценарий. Внутренний вызов fib исполняет 23 команды, значит 23 выбора следующей команды. Промах на M4 стоит от 14 до 20 тактов (мы мерили это выше на branch.zig). Если бы единственный переход runLoop промахивался хотя бы на половине команд, это было бы 160 тактов на вызов, а разница между диспетчерами 21 такт. Значит предсказатель угадывает цель одного-единственного перехода почти всегда.

Так и должно быть на современном ядре. Предсказатель непрямых переходов давно смотрит не на адрес перехода, а на адрес вместе с историей предыдущих переходов, и последовательность команд байткода для него такой же узор, как для двенадцати отдельных переходов. У last девять команд на ячейку идут в одном и том же порядке каждый виток, и оба диспетчера предсказываются одинаково идеально. У fib порядок меняется с глубиной рекурсии, и двенадцать переходов дают предсказателю чуть больше контекста: отсюда 7 процентов. Исследователи проверили это на ядрах Intel вплоть до Haswell ещё в 2015 году и пришли к тому же выводу: выигрыш размноженного перехода, огромный на процессорах начала 2000-х, на новых ядрах почти исчез.

Подтвердить это счётчиком промахов, как советует книга, на этой машине нельзя, и честнее сказать почему. perf есть только на Linux. Счётчики ядер M4 в macOS показывает Instruments, а своей программе они доступны только с правами суперпользователя через закрытый интерфейс. А виртуальная машина, в которой крутится Docker, аппаратные счётчики гостю не отдаёт вовсе:

$ docker run --rm --privileged --platform linux/arm64 debian:bookworm-slim \
    ls /sys/bus/event_source/devices/
breakpoint
kprobe
software
tracepoint
uprobe

Устройства cpu в списке нет, значит perf stat -e branch-misses там считать нечем. На Linux на x86-64 это одна команда, и она в упражнениях.

Развилка в JIT: переход или cmov

Шаблон cond из урока про JIT это всегда cmp, je и jmp. На случайных данных он платит промахом через раз. Вариант без перехода мы знаем из этого урока: посчитать обе стороны и выбрать cmov. Посчитать обе стороны можно не всегда: если ветка зовёт примитив или читает car, исполнять её заранее нельзя, car от числа прочитал бы память по адресу, которого нет. Поэтому cmov получают только развилки, у которых обе ветки это готовые значения: число, слово или параметр.

Сначала энкодер. cmovne это двухбайтовый opcode 0x0F 0x45, приёмник в поле reg, источник в поле rm:

/// `cmovne src, dst`: пересылка, если предыдущее сравнение дало «не равно».
/// REX.W, двухбайтовый opcode `0x0F 0x45`, приёмник в поле reg, источник в rm.
/// Флаги не меняет и перехода не делает: предсказывать процессору нечего.
pub fn cmovne(buf: *Buf, dst: Reg, src: Reg) void {
    buf.emit(rex(true, dst.extended(), false, src.extended()));
    buf.emit(0x0F);
    buf.emit(0x45);
    buf.emit(modrm(0b11, dst.low3(), src.low3()));
}

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

/// Во что превращается `cond`, у которой обе ветки это готовые значения.
pub const Select = enum {
    /// Всегда `cmp`, `je` и `jmp`: процессор угадывает ветку.
    branch,
    /// Обе ветки считаются, `cmovne` выбирает: угадывать нечего.
    cmov,
};

/// Ветка, которую можно посчитать заранее: одна пересылка, без вызовов,
/// без чтения памяти по чужому адресу и без побочных эффектов. `car` сюда
/// не входит: в ветке, которая не должна была исполниться, он прочитал бы
/// память по адресу, которого нет.
fn isLeaf(expr: *const Expr) bool {
    return switch (expr.*) {
        .fixnum, .word, .param => true,
        else => false,
    };
}

Шаблон на cmov держится на двух свойствах x86-64. Пересылки mov и movabs флагов не трогают, поэтому результат cmp доживает до cmovne через обе ветки. И %rcx свободен: вызовов между ним и cmovne нет, а значит и затирать его некому.

            // Обе ветки готовые значения: считаем обе, пересылки флагов не
            // трогают, и `cmovne` оставляет первую, если проверка не nil.
            .cond => |cond| if (self.select == .cmov and isLeaf(cond.on_true) and isLeaf(cond.on_false)) {
                self.gen(cond.check, depth);
                x86.cmpImm8(buf, .rax, 0);
                self.gen(cond.on_true, depth);
                x86.movRegReg(buf, .rcx, .rax);
                self.gen(cond.on_false, depth);
                x86.cmovne(buf, .rax, .rcx);
            } else {

Остальной cond остаётся прежним, в ветке else. Вход compile не изменил поведения, рядом появился compileSelect:

pub fn compile(buf: *x86.Buf, expr: *const Expr) void {
    compileSelect(buf, expr, .branch);
}

/// То же с выбором, как компилировать `cond` на готовых значениях.
pub fn compileSelect(buf: *x86.Buf, expr: *const Expr, select: Select) void {
    const frame = x86.frameSize(scratchDepth(expr));
    var compiler: Compiler = .{ .buf = buf, .body = x86.prologue(buf, frame), .select = select };
    compiler.gen(expr, 0);
    x86.epilogue(buf);
}

Чтобы развилкам в настоящих программах было что выбирать, спуск учится сворачивать ветку с всегда истинным условием. Без этого (t 0) в конце cond оставалась бы вложенной развилкой на символе t, то есть не готовым значением, и cmov не срабатывал бы никогда:

        // Число, `t` и `quote` истинны всегда: развилка на них не нужна,
        // а ветки после такой недостижимы.
        if (isTrueConstant(check)) return on_true;

fn isTrueConstant(e: *const jit.Expr) bool {
    return switch (e.*) {
        .fixnum => true,
        .word => |w| w != jit.nil,
        else => false,
    };
}

Замер, который сначала ничего не показал

Нагрузка: сколько чисел списка меньше 50. Внутренняя cond выбирает между единицей и нулём, это ровно наш случай. Список из случайных чисел от 0 до 99 и тот же набор по возрастанию:

/// Нагрузка для развилки: сколько чисел списка меньше 50. Внутренняя `cond`
/// выбирает между двумя готовыми числами, и JIT может собрать её и переходом,
/// и через `cmov`. На случайных числах от 0 до 99 переход угадывается через раз.
pub const small_definition =
    \\(define small (lambda (xs) (cond (xs (+ (cond ((< (car xs) 50) 1) (t 0)) (small (cdr xs)))) (t 0))))
;

/// Список из n чисел от 0 до 99, случайных или по возрастанию. Числа одни и
/// те же при одном `seed`: отсортированный список это тот же набор.
pub fn digits(vm: *Vm, gpa: std.mem.Allocator, n: usize, seed: u64, sorted: bool) errors.Error!Value {
    const items = try gpa.alloc(i64, n);
    defer gpa.free(items);
    var prng: std.Random.DefaultPrng = .init(seed);
    for (items) |*item| item.* = prng.random().intRangeLessThan(i64, 0, 100);
    if (sorted) std.mem.sort(i64, items, {}, std.sort.asc(i64));
    var head: Value = .nil;
    var i = n;
    while (i > 0) {
        i -= 1;
        head = try vm.heap.cons(.fromFixnum(items[i]), head);
    }
    return head;
}

Бенч получает ключ cmov и мерит скомпилированный small напрямую, без машины байткода, обоими способами на обоих списках:

const Mode = enum { executors, cmov };

pub fn main(init: std.process.Init) !void {
    var out_buf: [4096]u8 = undefined;
    var stdout = std.Io.File.stdout().writerStreaming(init.io, &out_buf);
    const out = &stdout.interface;

    const args = try init.minimal.args.toSlice(init.arena.allocator());
    var mode: Mode = .executors;
    var chosen: [4]Executor = undefined;
    var count: usize = 0;
    for (args[1..]) |arg| {
        if (std.mem.eql(u8, arg, "cmov")) {
            mode = .cmov;
        } else {
            chosen[count] = std.meta.stringToEnum(Executor, arg) orelse {
                try out.print("исполнитель: tree, loop, labeled или jit, а не {s}\n", .{arg});
                try out.flush();
                return error.BadArgument;
            };
            count += 1;
        }
    }
    if (count == 0) {
        for (std.enums.values(Executor)) |e| {
            if (e == .jit and !zl.jit.canRun()) continue;
            chosen[count] = e;
            count += 1;
        }
    }
    if (mode == .cmov and !zl.jit.canRun()) {
        try out.writeAll("cmov меряет машинный код x86-64, а этот процессор другой\n");
        try out.flush();
        return error.BadArgument;
    }

    const thread = try std.Thread.spawn(.{ .stack_size = big_stack }, benchAll, .{ init.io, out, mode, chosen[0..count] });
    thread.join();
}

fn benchAll(io: std.Io, out: *std.Io.Writer, mode: Mode, chosen: []const Executor) void {
    if (builtin.os.tag == .macos) _ = pthread_set_qos_class_self_np(qos_class_user_interactive, 0);
    const done = switch (mode) {
        .executors => measureAll(io, out, chosen),
        .cmov => measureSelect(io, out),
    };
    done catch |err| std.debug.panic("бенч: {t}", .{err});
}

// --- Развилка в машинном коде: переход против cmov ---

/// Вызов скомпилированного `small` на списке нужной длины.
const Select = struct {
    vm: *Vm,
    body: zl.jit.Body,
    list: Value,

    pub fn run(self: *Select, n: usize) void {
        _ = n;
        std.mem.doNotOptimizeAway(self.body(self.vm, @bitCast(self.list)));
    }
};

fn measureSelect(io: std.Io, out: *std.Io.Writer) !void {
    const gpa = std.heap.smp_allocator;
    const clock: harness.Clock = .init(io);
    try out.print("частота ядра по калибровке: {d:.2} ГГц\n", .{clock.ghz});
    try out.writeAll("данные          переход, тактов на ячейку   cmov, тактов на ячейку\n");
    try out.flush();

    for ([_]bool{ false, true }) |sorted| {
        try out.print("{s:<14}", .{if (sorted) "по возрастанию" else "случайные"});
        for ([_]zl.jit.Select{ .branch, .cmov }) |select| {
            var points: [list_lengths.len]harness.Point = undefined;
            for (list_lengths, &points) |n, *p| p.* = try selectPoint(clock, gpa, n, sorted, select);
            try out.print("  {d:>10.2} (шум {d:.2})      ", .{ harness.fitPoints(&points).cpe, worstNoise(&points) });
        }
        try out.writeByte('\n');
        try out.flush();
    }
}

fn selectPoint(clock: harness.Clock, gpa: std.mem.Allocator, n: usize, sorted: bool, select: zl.jit.Select) !harness.Point {
    var vm: Vm = try .init(gpa);
    defer vm.deinit();
    _ = try zl.eval.evalSource(&vm, workload.small_definition);
    var arena: std.heap.ArenaAllocator = .init(gpa);
    defer arena.deinit();
    const callee = vm.lookupGlobal(try vm.intern("small")).?;
    const tree = (try zl.lower.translate(arena.allocator(), &vm, callee)).?;

    var buf: zl.x86.Buf = .{};
    zl.jit.compileSelect(&buf, tree, select);
    var code = try zl.jit.Code.map(buf.slice());
    defer code.deinit();

    var b: Select = .{ .vm = &vm, .body = code.body(), .list = try workload.digits(&vm, gpa, n, 2026, sorted) };
    return harness.measure(clock, &b, &.{n}, .{ .work = 4_000_000, .runs = 5 }).items()[0];
}

Первый прогон под эмуляцией amd64 выглядел так:

$ docker run --rm --platform linux/amd64 -v "$PWD":/work -w /work \
    ghcr.io/bondiano/runner-zig:dev-amd64 sh -c \
    'zig build --cache-dir /work/.zc --global-cache-dir /work/.zg --prefix /work/.zc/out &&
     /work/.zc/out/bin/bench cmov'
частота ядра по калибровке: 3.42 ГГц
данные          переход, тактов на ячейку   cmov, тактов на ячейку
случайные       39.94 (шум 0.03)             40.39 (шум 0.04)
по возрастанию       22.17 (шум 0.05)             23.14 (шум 0.03)

Случайные данные дороже отсортированных на 18 тактов на ячейку, как и положено непредсказуемому переходу. Но cmov платит те же 18 тактов, хотя перехода в развилке больше нет. Значит непредсказуемый переход живёт где-то ещё. Где, показывает ассемблер входа примитива < под x86-64:

$ zig build asm -Dtarget=x86_64-linux -Doptimize=ReleaseFast
$ objdump -d --no-show-raw-insn --disassemble-symbols=primitives.native__struct_28420.entry \
    zig-out/bin/zl-llvm | sed -n '/sarq/,/retq/p'
 10758d7:      	sarq	$0x3, %rdx
 10758db:      	sarq	$0x3, %rcx
 10758df:      	cmpq	%rcx, %rdx
 10758e2:      	jge	0x10758f4 <primitives.native__struct_28420.entry+0x74>
 10758e4:      	movl	0xb4(%rdi), %eax
 10758ea:      	shlq	$0x4, %rax
 10758ee:      	orq	$0x8, %rax
 10758f2:      	popq	%rbp
 10758f3:      	retq

Вот он, jge. Примитив сравнения был написан как if (less) vm.true_() else .nil, и компилятор поставил на это условный переход: истина читается из памяти (vm.sym.t), и LLVM решил не читать её зря. Переход живёт в примитиве, результат < приезжает в развилку JIT уже после промаха, и собирать саму развилку через cmov бесполезно. Та же мысль, что в разделе про cmov выше: компилятор выбирает между переходом и пересылкой эвристикой, не зная данных, и выбор иногда надо диктовать руками. Маска из условия:

/// `t` или nil без перехода: условие становится маской из всех единиц или
/// нулей. С `if` компилятор ставит сюда условный переход, и на случайных
/// данных сравнение платит промахом предсказателя через раз, как бы ни был
/// собран код, который его зовёт.
fn truth(vm: *const Vm, yes: bool) Value {
    const mask = -%@as(u64, @intFromBool(yes));
    return .{ .bits = vm.true_().bits & mask };
}

fn primLess(vm: *Vm, args: Value) Error!Value {
    const pair = try takeTwo(args);
    const less = (try asNumber(pair[0])) < (try asNumber(pair[1]));
    return truth(vm, less);
}

Тем же truth теперь отвечают atom, eq и =. Вход < после правки, той же командой:

 10758a7:      	sarq	$0x3, %rcx
 10758ab:      	sarq	$0x3, %rdx
 10758af:      	movl	0xb4(%rdi), %esi
 10758b5:      	shlq	$0x4, %rsi
 10758b9:      	orq	$0x8, %rsi
 10758bd:      	xorl	%eax, %eax
 10758bf:      	cmpq	%rdx, %rcx
 10758c2:      	cmovlq	%rsi, %rax
 10758c6:      	popq	%rbp
 10758c7:      	retq

Перехода нет, компилятор сам поставил cmovl. Замер ещё раз, два прогона подряд:

частота ядра по калибровке: 4.00 ГГц
данные          переход, тактов на ячейку   cmov, тактов на ячейку
случайные       43.39 (шум 0.09)             24.31 (шум 0.09)
по возрастанию       24.45 (шум 0.01)             21.42 (шум 0.07)
частота ядра по калибровке: 3.98 ГГц
данные          переход, тактов на ячейку   cmov, тактов на ячейку
случайные       41.64 (шум 0.03)             22.35 (шум 0.04)
по возрастанию       23.08 (шум 0.04)             22.54 (шум 0.10)

Это снова эмуляция amd64 на M4 Max (Rosetta 2), настоящего x86-64 под рукой нет. Абсолютные такты здесь это такты M4 на переведённом коде, но различие строк честное: переведённый переход остаётся переходом, а пересылка пересылкой. Теперь картина такая, как учит этот урок. Переход на отсортированных данных стоит 23 такта на ячейку, на случайных 42: восемнадцать с лишним тактов на ячейку это промах через раз. cmov стоит 22 такта всегда. На отсортированных данных он не проигрывает, потому что обе его ветки это одна пересылка.

Какой шаблон выбрать по умолчанию? Для развилки на двух готовых значениях cmov не проиграл ни на одних данных, и дешевле он потому, что посчитать обе стороны почти ничего не стоит. Но наш замер это одна функция, а тесты шага 19 проверяют байты шаблона с переходом. Поэтому машина байткода по-прежнему компилирует cond переходом, а cmov доступен через compileSelect: сделать его выбором по умолчанию это упражнение, и в нём придётся поправить тесты байтов.

Тесты шага

//! Шаг 35: развилка в JIT переходом и через `cmov`.
//!
//! `cond`, у которой обе ветки это готовые значения, JIT умеет собрать без
//! перехода: посчитать обе ветки и выбрать `cmovne`. Байты проверяются на
//! любой машине, исполнение только на x86-64. Спуск заодно сворачивает
//! ветки с всегда истинным условием, иначе `(t 0)` оставалась бы развилкой.

const std = @import("std");

const zl = @import("zl");

const jit = zl.jit;
const lower = zl.lower;
const workload = zl.workload;
const x86 = zl.x86;
const Expr = jit.Expr;
const Vm = zl.Vm;

const testing = std.testing;

test "cmovne кодируется REX.W, 0F 45 и ModRM" {
    var buf: x86.Buf = .{};
    x86.cmovne(&buf, .rax, .rcx);
    x86.cmovne(&buf, .r9, .rax);
    x86.cmovne(&buf, .rdx, .r15);
    try testing.expectEqualSlices(u8, &.{
        0x48, 0x0F, 0x45, 0xC1, // cmovne %rcx, %rax
        0x4C, 0x0F, 0x45, 0xC8, // cmovne %rax, %r9: приёмник расширенный, бит R
        0x49, 0x0F, 0x45, 0xD7, // cmovne %r15, %rdx: источник расширенный, бит B
    }, buf.slice());
}

fn contains(haystack: []const u8, needle: []const u8) bool {
    return std.mem.indexOf(u8, haystack, needle) != null;
}

const je_opcode = [_]u8{ 0x0F, 0x84 };
const cmovne_rcx_rax = [_]u8{ 0x48, 0x0F, 0x45, 0xC1 };

test "развилка на готовых значениях становится cmovne, остальные остаются переходом" {
    const one: Expr = .{ .fixnum = 1 };
    const zero: Expr = .{ .fixnum = 0 };
    const p: Expr = .param;
    const rest: Expr = .{ .cdr = &p };
    const leaf: Expr = .{ .cond = .{ .check = &p, .on_true = &one, .on_false = &zero } };
    const deep: Expr = .{ .cond = .{ .check = &p, .on_true = &rest, .on_false = &zero } };

    var branch: x86.Buf = .{};
    jit.compileSelect(&branch, &leaf, .branch);
    try testing.expect(contains(branch.slice(), &je_opcode));
    try testing.expect(!contains(branch.slice(), &cmovne_rcx_rax));

    var select: x86.Buf = .{};
    jit.compileSelect(&select, &leaf, .cmov);
    try testing.expect(!contains(select.slice(), &je_opcode));
    // После пролога: параметр, cmp, первая ветка, mov %rax, %rcx,
    // вторая ветка, cmovne. Ни одного перехода.
    try testing.expectEqualSlices(u8, &cmovne_rcx_rax, select.slice()[19 + 4 + 4 + 10 + 3 + 10 ..][0..4]);
    try testing.expect(select.len < branch.len);

    // `cdr` в ветке это чтение памяти: считать его заранее нельзя.
    var guarded: x86.Buf = .{};
    jit.compileSelect(&guarded, &deep, .cmov);
    try testing.expect(contains(guarded.slice(), &je_opcode));
}

test "спуск сворачивает ветку с всегда истинным условием" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    _ = try zl.eval.evalSource(&vm, workload.small_definition);
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();

    const callee = vm.lookupGlobal(try vm.intern("small")).?;
    const small = (try lower.translate(arena.allocator(), &vm, callee)).?;
    // (cond (xs ...) (t 0)): вторая ветка это просто ноль, без проверки t.
    try testing.expectEqual(@as(i64, 0), small.cond.on_false.fixnum);
    const inner = small.cond.on_true.call.a;
    try testing.expectEqual(@as(i64, 1), inner.cond.on_true.fixnum);
    try testing.expectEqual(@as(i64, 0), inner.cond.on_false.fixnum);
}

test "переход и cmov считают одно и то же" {
    if (!jit.canRun()) return error.SkipZigTest;

    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    _ = try zl.eval.evalSource(&vm, workload.small_definition);
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    const callee = vm.lookupGlobal(try vm.intern("small")).?;
    const small = (try lower.translate(arena.allocator(), &vm, callee)).?;

    for ([_]bool{ false, true }) |sorted| {
        const xs = try workload.digits(&vm, testing.allocator, 1000, 42, sorted);
        var expected: i64 = 0;
        var rest = xs;
        while (rest.isCons()) : (rest = rest.asCell().cdr) {
            if (rest.asCell().car.asFixnum() < 50) expected += 1;
        }

        for ([_]jit.Select{ .branch, .cmov }) |select| {
            var buf: x86.Buf = .{};
            jit.compileSelect(&buf, small, select);
            var code = try jit.Code.map(buf.slice());
            defer code.deinit();
            const result: zl.Value = @bitCast(code.body()(&vm, @bitCast(xs)));
            try testing.expectEqual(expected, result.asFixnum());
            try testing.expectEqual(@as(jit.Value, @bitCast(result)), jit.interpret(&vm, small, @bitCast(xs)));
        }
    }
}

Первые три теста проверяют байты и спуск и идут на любой машине, четвёртый исполняет оба варианта на списках и сверяет их с толкователем дерева и со счётом в Zig:

$ zig build test --summary all
Build Summary: 19/19 steps succeeded; 73/84 tests passed (11 skipped)

$ docker run --rm --platform linux/amd64 -v "$PWD":/work -w /work \
    ghcr.io/bondiano/runner-zig:dev-amd64 \
    zig build test --summary all --cache-dir /work/.zc --global-cache-dir /work/.zg
Build Summary: 19/19 steps succeeded; 84/84 tests passed

Практика

Задача про memset словами из этого урока, теперь в песочнице и с тестами на всех границах. Заготовка содержит три функции, реализовать нужно все три: wordFill размножает байт на все восемь позиций слова (для 0x41 это 0x4141414141414141); wordCount считает, сколько целых слов помещается в середине среза длины len, начало которого сдвинуто на misalign байт от границы слова; fastMemset заполняет срез в три части, голова и хвост побайтно, середина через указатель [*]align(word_size) usize. Приведение @alignCast в отладочной сборке проверяет, что адрес середины действительно кратен восьми, поэтому неверная формула головы падает не тихо, а с incorrect alignment, и делать это приведение нужно только когда слов больше нуля. Тесты сверяют fastMemset с @memset для длин от 0 до 80 и всех восьми сдвигов начала, проверяют, что байты за пределами среза остались нетронутыми, гоняют wordCount против эталонной формулы для всех пар длины и сдвига, и заполняют большой буфер с невыровненным началом.

Упражнения

CHK-1★★

Сними ассемблер product20 под x86_64-linux и посчитай, сколько аккумуляторов живёт в регистрах, а сколько на стеке. Потом собери тот же файл под aarch64-linux и повтори подсчёт. Объясни разницу числом регистров общего назначения в каждой архитектуре и предскажи, при каком k вытеснение начнётся на aarch64.

CHK-2★★

В branch.zig замени порог 128 на 250: теперь ветка берётся редко, но всё ещё случайно. Предскажи CPE версии с переходом на случайных данных через долю промахов и цену одного промаха, потом измерь. Затем сделай порог 5 и проверь, что предсказание работает в обе стороны.

CHK-3★★★

Три вызова из упражнения 5.10: copy_array(a + 1, a, 999), copy_array(a, a + 1, 999) и copy_array(a, a, 999). Для каждого нарисуй граф потока данных двух соседних итераций с блоками загрузки, сохранения и буфера записи и отметь, есть ли ребро от сохранения одной итерации к загрузке следующей. Реализуй все три в Zig с blackBox на загруженном значении и на указателях и сверь свои предсказания с замером. Если чистая копия со сдвигом 1 идёт по такту, добавь сложение между загрузкой и сохранением и объясни, что изменилось.

CHK-4★★

В виджете выбери копирование со сдвигом и пройди сдвиги от 1 до 4 по тактам. Для каждого сдвига выпиши, сколько независимых цепочек через память крутится одновременно и как это связано с установившимся CPE. Потом объясни, почему при сдвиге 8 буфер записи не находит адрес вовсе, хотя запись по нему была: сколько тактов запись живёт в буфере в модели виджета?

CHK-5★★

Убери clock.blackBox из memsetByte и сними ассемблер: найди, во что превратился цикл. Потом верни blackBox, но добавь в memsetWord подсказку @setRuntimeSafety(false) и проверь, изменилось ли что-то в горячем цикле середины в ReleaseFast. Сформулируй, когда blackBox в замере обязателен, а когда он мешает мерить настоящую программу.

CHK-6★★★

Собери combineSimd для f32 с шириной 8 и восемью аккумуляторами под -mcpu=x86_64_v3 и посчитай по ассемблеру, сколько регистров YMM занято. Потом возьми шестнадцать аккумуляторов и найди в листинге вытеснение векторных регистров на стек: первая и третья стены этого урока встретились. Предскажи по таблице блоков, при каком числе аккумуляторов CPE перестанет падать, и проверь замером.

CHK-7★★

На Linux на x86-64 (своя машина, виртуалка с проброшенными счётчиками или облачный сервер) собери шаг zl и сними perf stat -e branches,branch-misses для zig build bench -- loop и zig build bench -- labeled. Какая доля промахов у каждого диспетчера? Сходится ли разница в тактах с числом промахов, умноженным на цену одного промаха, и что говорит этот ответ о том, почему у LLVM под x86-64 оба диспетчера получились с размноженным переходом?

CHK-8★★★

Сделай cmov выбором по умолчанию в машине байткода: lower.compile собирает код через compileSelect(.cmov). Какие тесты шага 19 упадут и почему, как их переписать, чтобы они проверяли оба шаблона? Потом найди программу, на которой cmov проиграет переходу: подсказка, обе ветки должны стоить больше одной пересылки, а данные быть предсказуемыми, и подумай, почему isLeaf такую программу к cmov не пустит.

Итоги

Развёртка с k аккумуляторами имеет потолок, равный числу свободных регистров: на x86-64 их шестнадцать, на aarch64 тридцать один. Лишние аккумуляторы вытесняются на стек, каждая итерация получает пару обращений к памяти на аккумулятор и цепочку через буфер записи. Для произведения i64 на M4 это подъём CPE с 0.33 при k = 10 до 0.45 при k = 40.
LLVM умеет упаковать пары аккумуляторов суммы в XMM-регистры, поэтому вытеснение на сумме целых показать труднее, чем на произведении: для 64-битного умножения в базовом x86-64 нет векторной инструкции.
Переход в горячем цикле стоит либо ноль, либо промах от 14 до 20 тактов. Случайные данные и переход: 7.87 такта на элемент. Отсортированные данные и тот же код: 1.03. Форма без перехода через маску или cmov: 1.27 всегда, потому что вычисляет обе стороны.
Компилятор выбирает между переходом и cmov эвристикой и не знает твоих данных. Когда он ошибся, форму диктуют руками: маска через @intFromBool, if с уже вычисленными сторонами, blackBox там, где нужно запретить склейку.
Сохранение идёт через буфер записи: адрес известен сразу, данные позже, в кэш запись уходит после завершения инструкции. Загрузка сверяет адрес с буфером и при совпадении ждёт данных и пересылки. Так возникает цепочка через память, которой нет ни в исходнике, ни в графе по регистрам.
write_read с одним адресом стоит 6.96 такта на итерацию против 0.99 с разными, книжный Haswell даёт 7.3 против 1.3. Правило: цепочка есть, когда загрузка читает адрес, по которому недавно писало ещё не ушедшее в кэш сохранение; направление сдвига решает всё.
M4 умеет переименовывать память и прокидывать чистую копию мимо буфера записи, поэтому copyShifted со сдвигом 1 идёт по такту; со сложением между загрузкой и сохранением цепочка возвращается, 4.75, и её появление зависит от предсказателя зависимостей, а не от шума.
memset словами: голова до выравнивания побайтно, середина словами из 0x0101010101010101 * value, хвост побайтно. Побайтно 1.0 такта на байт, словами 0.125, @memset векторами 0.032: число сохранений за такт не меняется, меняется ширина.
LLVM узнаёт идиомы: побайтная голова и хвост memsetWord стали вызовами memset из libc, цикл копирования без blackBox стал бы memmove. То, что написано, и то, что исполняется, разные вещи, пока не посмотришь в ассемблер.
@Vector(N, T) обходит границу пропускной способности через ширину данных: simd4 для f64 даёт 0.20 при скалярной границе 0.25, потому что настоящая граница вектора это скалярная, делённая на число дорожек. Для дробных это меняет порядок сложений и последние биты, поэтому компилятор такое не делает сам.
Шаг zl: на M4 диспетчер с одним непрямым переходом отстаёт от двенадцати размноженных на 7 процентов на fib и не отстаёт на обходе списка: предсказатель с историей угадывает и единственный переход. Развилка в JIT собирается через cmov, если обе ветки готовые значения, но выиграла она только после того, как из примитива < ушёл условный переход: на случайных данных 42 такта на ячейку против 22, на отсортированных поровну.

Дальше

У тебя теперь есть полный набор ограничений горячего цикла: задержка и пропускная способность операций, число регистров, цена промаха предсказателя и цепочка через буфер записи. Осталось научиться быстро находить, в какое из них упёрлась настоящая программа, а не наш цикл на восемь строк. Следующий урок про инструменты: perf stat считает такты, инструкции и промахи предсказания, perf record с flame graph показывает, где программа проводит время, а callgrind считает инструкции детерминированно там, где счётчиков нет. Там же разберём ловушки микробенчмарков, в которые ты сегодня уже дважды чуть не попал, мёртвый код и склейку функций, и закон Амдала как правило, куда смотреть в первую очередь. А в домашних задачах вернёмся к многочлену и к сумме, у которой CPE ниже задержки сложения.

домашка

Домашка

Перепиши шаг слияния из сортировки слиянием без условного перехода в теле цикла (форма упражнения 5.9): оба кандидата загружаются всегда, выбор и сдвиг индексов делаются через @intFromBool. Сними ассемблер под x86_64-linux и убедись, что в цикле нет jl, только cmov или setl.L
Расширь memsetWord до memsetVector: середина пишется через @Vector(32, u8) по 32 байта, голова и хвост по-прежнему побайтно. Проверь равенство с @memset на всех сдвигах начала от 0 до 31 и длинах от 0 до 100, потом сравни такты на байт с версией словами и с @memset.L
Измерь копирование со сдвигом в обратную сторону, buf[i] = buf[i + shift], для сдвигов 1, 2, 4, 8, и объясни через граф зависимостей, почему у этого цикла нет цепочки через память ни при каком сдвиге, в отличие от прямого.S