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

Код, дружественный к кэшу

lead~160 мин

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

Код, дружественный к кэшу

В прошлом уроке ты собрал симулятор кэша и генератор трасс: любая Zig-программа теперь может рассказать, куда она ходила в память, а симулятор посчитает, сколько из этих походов кончились промахом. До сих пор мы смотрели на кэш со стороны железа: наборы, теги, LRU. Сегодня разворачиваемся и смотрим со стороны программы. Одна и та же арифметика, те же три вложенных цикла, а число промахов отличается в четыре раза, и время на настоящей машине в семнадцать. Разберём, откуда берётся эта разница, научимся её предсказывать на бумаге, проверять симулятором и убирать четырьмя приёмами: порядком циклов, блочным разбиением, раскладкой данных и разведением горячих полей по разным линиям.

Цели урока

Сформулировать три правила кода, дружественного к кэшу, и понимать, какое из них нарушает каждый медленный цикл.
Разложить шесть порядков циклов умножения матриц на три класса по внутреннему циклу и посчитать промахи на итерацию по книжной оценке.
Снять те же промахи симулятором из прошлого урока и объяснить, где и почему симулятор расходится с оценкой: конечная матрица, степень двойки, конфликтные промахи.
Увидеть разницу между порядками во времени на настоящей машине и понять, почему худший порядок медленнее лучшего не в четыре раза, а в семнадцать.
Написать блочное умножение и объяснить одной фразой, почему блок возвращает временную локальность.
Разобрать три версии транспонирования на кэше cachelab и понять, почему на 64 на 64 блок 8 на 8 не помогает вовсе.
Сравнить массив структур со структурой массивов на задачах книги про водоросли и знать, где в Zig эта раскладка лежит готовой.
Показать ложное разделение двумя потоками и вылечить его одним словом align(64).
Измерить обход списка zl при четырёх раскладках ячеек и объяснить, почему куча, которая выдаёт ячейки подряд, важнее для быстрого исполнителя, чем для медленного.

Идея: три правила и одна метрика

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

Второе правило это пространственная локальность, третье это временная локальность. Ты видел оба слова в уроке про локальность, теперь они станут инструментом.

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

Шесть порядков циклов умножения матриц

Умножение матриц это тело c[i][j] += a[i][k] * b[k][j] внутри трёх вложенных циклов по i, j и k. Тело одно, порядков вложенности шесть, и все шесть считают одно и то же, потому что сложение ассоциативно (для чисел с плавающей точкой почти ассоциативно, и на матрицах без экстремальных значений разница не видна). Вот все шесть в одном файле, матрицы лежат в срезах построчно, элемент (i, j) это m[i * n + j].

//! Шесть порядков циклов умножения матриц. Тело одно: c[i][j] += a[i][k] * b[k][j].
//! Матрицы n на n лежат построчно в срезах, элемент (i, j) это m[i * n + j].

const std = @import("std");

pub const Order = enum {
    ijk,
    jik,
    jki,
    kji,
    kij,
    ikj,

    pub const all = [_]Order{ .ijk, .jik, .jki, .kji, .kij, .ikj };
};

/// C += A * B в заданном порядке циклов.
pub fn multiply(order: Order, n: usize, a: []const f64, b: []const f64, c: []f64) void {
    switch (order) {
        .ijk => for (0..n) |i| {
            for (0..n) |j| {
                var sum: f64 = 0;
                for (0..n) |k| sum += a[i * n + k] * b[k * n + j];
                c[i * n + j] += sum;
            }
        },
        .jik => for (0..n) |j| {
            for (0..n) |i| {
                var sum: f64 = 0;
                for (0..n) |k| sum += a[i * n + k] * b[k * n + j];
                c[i * n + j] += sum;
            }
        },
        .jki => for (0..n) |j| {
            for (0..n) |k| {
                const r = b[k * n + j];
                for (0..n) |i| c[i * n + j] += a[i * n + k] * r;
            }
        },
        .kji => for (0..n) |k| {
            for (0..n) |j| {
                const r = b[k * n + j];
                for (0..n) |i| c[i * n + j] += a[i * n + k] * r;
            }
        },
        .kij => for (0..n) |k| {
            for (0..n) |i| {
                const r = a[i * n + k];
                for (0..n) |j| c[i * n + j] += r * b[k * n + j];
            }
        },
        .ikj => for (0..n) |i| {
            for (0..n) |k| {
                const r = a[i * n + k];
                for (0..n) |j| c[i * n + j] += r * b[k * n + j];
            }
        },
    }
}

test "все шесть порядков дают одно произведение" {
    const gpa = std.testing.allocator;
    for ([_]usize{ 1, 4, 5 }) |n| {
        const a = try gpa.alloc(f64, n * n);
        defer gpa.free(a);
        const b = try gpa.alloc(f64, n * n);
        defer gpa.free(b);
        for (a, 0..) |*x, idx| x.* = @floatFromInt(idx % 7);
        for (b, 0..) |*x, idx| x.* = @floatFromInt(idx % 5);

        const reference = try gpa.alloc(f64, n * n);
        defer gpa.free(reference);
        @memset(reference, 0);
        multiply(.ijk, n, a, b, reference);

        for (Order.all[1..]) |order| {
            const c = try gpa.alloc(f64, n * n);
            defer gpa.free(c);
            @memset(c, 0);
            multiply(order, n, a, b, c);
            try std.testing.expectEqualSlices(f64, reference, c);
        }
    }
}

test "c[0][0] это скалярное произведение строки A и столбца B" {
    const a = [_]f64{ 1, 2, 3, 4 };
    const b = [_]f64{ 5, 6, 7, 8 };
    var c = [_]f64{0} ** 4;
    multiply(.kij, 2, &a, &b, &c);
    try std.testing.expectEqual(@as(f64, 1 * 5 + 2 * 7), c[0]);
    try std.testing.expectEqual(@as(f64, 3 * 6 + 4 * 8), c[3]);
}

Обрати внимание на мелкие правки внутри тела. В ijk и jik сумма копится в локальной переменной, и c[i][j] трогается один раз после внутреннего цикла. В остальных четырёх одно из значений внутреннего цикла не зависит от его переменной, поэтому вынесено в r. Компилятор в ReleaseFast сделал бы это сам, но нам важно, чтобы обращения к памяти в трассе были ровно те, которые мы считаем на бумаге.

Три класса по внутреннему циклу

Шесть порядков различаются только тем, какая переменная стоит во внутреннем цикле, и это делит их на три класса. Класс называют по двум матрицам, которые внутренний цикл трогает.

Внутренний цикл по k (порядки ijk, jik), класс AB. Читаем a[i][k] вдоль строки, шаг 1. Читаем b[k][j] вдоль столбца, шаг n. C не трогаем вовсе, сумма сидит в регистре. Два чтения, ноль записей на итерацию.

Внутренний цикл по i (порядки jki, kji), класс AC. b[k][j] в регистре. Читаем a[i][k] вдоль столбца и меняем c[i][j] вдоль столбца, оба с шагом n. Два чтения и одна запись.

Внутренний цикл по j (порядки kij, ikj), класс BC. a[i][k] в регистре. Читаем b[k][j] вдоль строки и меняем c[i][j] вдоль строки, оба с шагом 1. Два чтения и одна запись.

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

Класс	Порядки	Чтений	Записей	Промахов A	Промахов B	Промахов C	Всего
AB	`ijk`, `jik`	2	0	0.25	1.00	0.00	1.25
AC	`jki`, `kji`	2	1	1.00	0.00	1.00	2.00
BC	`kij`, `ikj`	2	1	0.00	0.25	0.25	0.50

Заметь парадокс: класс BC делает на одно обращение к памяти больше, чем AB, и при этом промахивается в два с половиной раза реже. Число обращений и число промахов это разные вещи, и кэш платит только за вторую.

Промахи по симулятору

Оценка сделана для бесконечно большой матрицы. Симулятор из прошлого урока покажет, что происходит на конечной. Программа ниже собирается рядом с cache.zig, gen.zig, trace.zig и matmul.zig эталона. Эталонный matmul.zig устроен как листинг выше, только матрицы обёрнуты в Matrix(f64) из генератора трасс, а measure подключает к трассировщику кэш как сток: обращения не копятся в памяти, а сразу проигрываются на кэше, потому что трасса умножения 100 на 100 это три миллиона строк.

//! Промахи шести порядков циклов на симуляторе из прошлого урока.
//! Собирается рядом с cache.zig, gen.zig, trace.zig и matmul.zig.

const std = @import("std");
const cache = @import("cache.zig");
const matmul = @import("matmul.zig");

fn table(out: *std.Io.Writer, gpa: std.mem.Allocator, params: cache.Params, n: usize) !void {
    try out.print("кэш (s, E, b) = ({d}, {d}, {d}), {d} байт, n = {d}\n", .{
        params.s, params.e, params.b, params.capacityBytes(), n,
    });
    try out.writeAll("цикл   обращений  промахов  на итерацию\n");
    for (matmul.Order.all) |order| {
        const report = try matmul.measure(gpa, order, n, params);
        try out.print("{s:<5} {d:>10} {d:>9} {d:>12.3}\n", .{
            @tagName(order),
            report.stats.accesses(),
            report.stats.misses,
            report.missesPerIteration(),
        });
    }
    try out.print("\n", .{});
}

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

    // Кэш книги: блок 32 байта, четыре f64 в линии. 32 набора по одной
    // строке, всего 1 КБ. Строка матрицы n = 100 это 800 байт, три строки в
    // кэш уже не помещаются, как и требует оценка из главы.
    try table(out, init.gpa, .{ .s = 5, .e = 1, .b = 5 }, 100);
    // Тот же кэш, но n степень двойки: строки матриц ложатся на одни наборы.
    try table(out, init.gpa, .{ .s = 5, .e = 1, .b = 5 }, 64);
    // Та же ёмкость, но две строки в наборе: конфликт двух строк снят.
    try table(out, init.gpa, .{ .s = 4, .e = 2, .b = 5 }, 64);
    try out.flush();
}

$ zig run -O ReleaseFast matmul_report.zig
кэш (s, E, b) = (5, 1, 5), 1024 байт, n = 100
цикл   обращений  промахов  на итерацию
ijk      2020000   1282229        1.282
jik      2020000   1282237        1.282
jki      3010000   2009943        2.010
kji      3010000   2009940        2.010
kij      3010000    504231        0.504
ikj      3010000    504491        0.504

кэш (s, E, b) = (5, 1, 5), 1024 байт, n = 64
цикл   обращений  промахов  на итерацию
ijk       532480    278400        1.062
jik       532480    337920        1.289
jki       790528    528384        2.016
kji       790528    528384        2.016
kij       790528    301536        1.150
ikj       790528    301536        1.150

кэш (s, E, b) = (4, 2, 5), 1024 байт, n = 64
цикл   обращений  промахов  на итерацию
ijk       532480    272256        1.039
jik       532480    331776        1.266
jki       790528    528384        2.016
kji       790528    528384        2.016
kij       790528     74688        0.285
ikj       790528     74688        0.285

Первая таблица это оценка книги, воспроизведённая до второго знака: 1.28 против 1.25, 2.01 против 2.00, 0.50 против 0.50. Лишние сотые в классе AB это край матрицы: строка из ста f64 это 800 байт, то есть 25 линий, и первая линия каждой строки промахивается независимо от того, сколько элементов в ней использовали.

Вторая таблица важнее. Тот же кэш, но n = 64, и класс BC внезапно промахивается в два раза чаще класса AB, хотя по оценке должен в два с половиной раза реже. Это конфликтные промахи. Строка матрицы 64 на 64 это 512 байт, ровно половина кэша, поэтому строка i матрицы C и строка k матрицы B ложатся на одни и те же наборы всякий раз, когда i и k одной чётности. Внутренний цикл класса BC читает b[k][j] и тут же меняет c[i][j] с тем же j: два обращения в один набор, кэш прямого отображения держит одну строку, и они выбивают друг друга на каждой итерации. Половина пар (i, k) конфликтует, отсюда 1.15 вместо 0.28.

Третья таблица лечит это без единой правки в коде: два ряда в наборе вместо одного при той же ёмкости, и BC возвращается к своим 0.285. Запомни этот эффект, он вернётся в транспонировании: размеры, кратные степени двойки, красивы для человека и опасны для кэша прямого отображения.

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

Секундомер

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

//! Время шести порядков циклов и блочной версии на настоящей машине.
//! Собирать в ReleaseFast: zig build-exe matmul_bench.zig -O ReleaseFast

const std = @import("std");

const Order = enum { ijk, jik, jki, kji, kij, ikj, blocked };

fn multiply(order: Order, n: usize, a: []const f64, b: []const f64, c: []f64) void {
    switch (order) {
        .ijk => for (0..n) |i| {
            for (0..n) |j| {
                var sum: f64 = 0;
                for (0..n) |k| sum += a[i * n + k] * b[k * n + j];
                c[i * n + j] += sum;
            }
        },
        .jik => for (0..n) |j| {
            for (0..n) |i| {
                var sum: f64 = 0;
                for (0..n) |k| sum += a[i * n + k] * b[k * n + j];
                c[i * n + j] += sum;
            }
        },
        .jki => for (0..n) |j| {
            for (0..n) |k| {
                const r = b[k * n + j];
                for (0..n) |i| c[i * n + j] += a[i * n + k] * r;
            }
        },
        .kji => for (0..n) |k| {
            for (0..n) |j| {
                const r = b[k * n + j];
                for (0..n) |i| c[i * n + j] += a[i * n + k] * r;
            }
        },
        .kij => for (0..n) |k| {
            for (0..n) |i| {
                const r = a[i * n + k];
                for (0..n) |j| c[i * n + j] += r * b[k * n + j];
            }
        },
        .ikj => for (0..n) |i| {
            for (0..n) |k| {
                const r = a[i * n + k];
                for (0..n) |j| c[i * n + j] += r * b[k * n + j];
            }
        },
        .blocked => multiplyBlocked(32, n, a, b, c),
    }
}

fn multiplyBlocked(comptime bsize: usize, n: usize, a: []const f64, b: []const f64, c: []f64) void {
    var kk: usize = 0;
    while (kk < n) : (kk += bsize) {
        var jj: usize = 0;
        while (jj < n) : (jj += bsize) {
            const k_end = @min(kk + bsize, n);
            const j_end = @min(jj + bsize, n);
            for (0..n) |i| {
                for (kk..k_end) |k| {
                    const r = a[i * n + k];
                    for (jj..j_end) |j| c[i * n + j] += r * b[k * n + j];
                }
            }
        }
    }
}

pub fn main(init: std.process.Init) !void {
    const gpa = init.gpa;
    const io = init.io;
    var buf: [512]u8 = undefined;
    var w = std.Io.File.stdout().writer(io, &buf);
    const out = &w.interface;

    const n: usize = 512;
    const a = try gpa.alloc(f64, n * n);
    defer gpa.free(a);
    const b = try gpa.alloc(f64, n * n);
    defer gpa.free(b);
    const c = try gpa.alloc(f64, n * n);
    defer gpa.free(c);
    for (a, 0..) |*x, idx| x.* = @floatFromInt(idx % 7);
    for (b, 0..) |*x, idx| x.* = @floatFromInt(idx % 5);

    const iterations: f64 = @floatFromInt(n * n * n);
    try out.print("n = {d}, лучшее из 3 прогонов\n", .{n});
    try out.writeAll("порядок       мс  нс/итерацию\n");
    for (std.enums.values(Order)) |order| {
        var best_ns: f64 = std.math.inf(f64);
        for (0..3) |_| {
            @memset(c, 0);
            const started = std.Io.Clock.awake.now(io);
            multiply(order, n, a, b, c);
            const elapsed = started.durationTo(std.Io.Clock.awake.now(io));
            best_ns = @min(best_ns, @as(f64, @floatFromInt(elapsed.toNanoseconds())));
        }
        std.mem.doNotOptimizeAway(c[0]);
        try out.print("{s:<8} {d:>8.1} {d:>12.2}\n", .{ @tagName(order), best_ns / 1e6, best_ns / iterations });
    }
    try out.flush();
}

Снято на Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-13. Машина в этот момент была занята другими сборками, так что абсолютные числа на твоём ноутбуке будут другими, а вот отношения между строками устойчивы.

$ zig build-exe matmul_bench.zig -O ReleaseFast && ./matmul_bench
n = 512, лучшее из 3 прогонов
порядок       мс  нс/итерацию
ijk         299.0         2.23
jik         335.9         2.50
jki        1346.7        10.03
kji        1461.7        10.89
kij          91.4         0.68
ikj          82.4         0.61
blocked      29.6         0.22

Три класса видны невооружённым глазом: два порядка около 2.3 нс, два около 10 нс, два меньше 0.7 нс. Но отношения между классами не те, что в таблице промахов. По промахам худший класс хуже лучшего в четыре раза, по времени в семнадцать. Причина в том, что промах промаху рознь. У класса BC внутренний цикл идёт по строке с шагом 1, и предвыборка подтягивает следующие линии заранее: промах числится в счётчике, но процессор его почти не ждёт. Вдобавок цикл по строке компилятор векторизует: четыре f64 за одну инструкцию. У класса AC оба обхода идут с шагом в 4 КБ, предвыборка бессильна, векторизовать нечего, и каждый промах это полноценное ожидание памяти. Так что метрика промахов на итерацию правильно упорядочивает варианты, но не предсказывает время в разы; за временем всегда иди к секундомеру.

Последняя строка, blocked, в три раза быстрее лучшего из шести порядков. Про неё следующий раздел.

Блочное разбиение

Даже лучший порядок ikj тратит на каждую итерацию четверть промаха на B и четверть на C, а всего матрица B перечитывается из памяти n раз, по разу на каждую строку A. Пока n маленькое и B помещается в кэш целиком, это ничего не стоит. При n = 512 матрица занимает 2 МБ и в L1 не помещается никак: к тому времени, как внешний цикл перейдёт к следующему i, от B в кэше не останется ничего, и всё едет заново.

Блочное разбиение возвращает временную локальность. Идея: не ходить по всей B, а работать с квадратом bsize на bsize. Пока квадрат из B и полоска из A шириной bsize сидят в кэше, мы делаем с ними всё, что можно, и только потом переходим к соседнему квадрату. Каждый элемент B теперь приезжает из памяти не n раз, а n / bsize раз.

//! Блочное умножение матриц: тот же ikj, но поверх квадратов bsize на bsize.
//! Матрицы n на n лежат построчно, элемент (i, j) это m[i * n + j].

const std = @import("std");

/// C += A * B без блоков, порядок ikj: лучший из шести.
pub fn multiply(n: usize, a: []const f64, b: []const f64, c: []f64) void {
    for (0..n) |i| {
        for (0..n) |k| {
            const r = a[i * n + k];
            for (0..n) |j| c[i * n + j] += r * b[k * n + j];
        }
    }
}

/// C += A * B блоками: внешние циклы идут по блокам, внутренние по элементам
/// одного блока. Пока блок считается, в работе bsize строк A, квадрат bsize на
/// bsize из B и квадрат из C, и всё это помещается в кэш.
pub fn multiplyBlocked(comptime bsize: usize, n: usize, a: []const f64, b: []const f64, c: []f64) void {
    var kk: usize = 0;
    while (kk < n) : (kk += bsize) {
        var jj: usize = 0;
        while (jj < n) : (jj += bsize) {
            // Края: последний блок бывает неполным, когда n не делится на bsize.
            const k_end = @min(kk + bsize, n);
            const j_end = @min(jj + bsize, n);
            for (0..n) |i| {
                for (kk..k_end) |k| {
                    const r = a[i * n + k];
                    for (jj..j_end) |j| c[i * n + j] += r * b[k * n + j];
                }
            }
        }
    }
}

test "блочное произведение совпадает с обычным, включая неполные блоки" {
    const gpa = std.testing.allocator;
    for ([_]usize{ 1, 7, 16, 37 }) |n| {
        const a = try gpa.alloc(f64, n * n);
        defer gpa.free(a);
        const b = try gpa.alloc(f64, n * n);
        defer gpa.free(b);
        for (a, 0..) |*x, idx| x.* = @floatFromInt(idx % 11);
        for (b, 0..) |*x, idx| x.* = @floatFromInt(idx % 13);

        const plain = try gpa.alloc(f64, n * n);
        defer gpa.free(plain);
        @memset(plain, 0);
        multiply(n, a, b, plain);

        const blocked = try gpa.alloc(f64, n * n);
        defer gpa.free(blocked);
        @memset(blocked, 0);
        multiplyBlocked(8, n, a, b, blocked);

        try std.testing.expectEqualSlices(f64, plain, blocked);
    }
}

Разбери структуру. Два внешних цикла по kk и jj выбирают квадрат в B. Затем цикл по всем i проходит по строкам A, но из каждой строки берёт только bsize элементов с kk по k_end, и обновляет в строке C только bsize элементов с jj по j_end. Рабочее множество на одну итерацию по i: квадрат B (bsize в квадрате чисел), кусочек строки A и кусочек строки C. При bsize = 32 квадрат это 8 КБ, что в L1 помещается с запасом, и он остаётся там на все n итераций по i.

Две детали, о которых легко забыть. Размер блока это comptime-параметр: компилятор знает длину внутренних циклов и разворачивает их. И границы @min(kk + bsize, n): тест на n = 7 и n = 37 при блоке 8 ловит именно ту версию, где края потеряны. Оптимальный bsize зависит от машины, и единственный честный способ его найти это таблица времени по размерам блока; она в упражнениях.

Блочное разбиение не лечит всё. У класса BC внутренний цикл и так шёл с шагом 1, поэтому его хватило на трёхкратный выигрыш; попробуй заблокировать jki, и получишь гораздо меньше, потому что обход по столбцу внутри блока остаётся обходом по столбцу.

Транспонирование с минимумом промахов

Вторая половина cachelab это транспонирование: B[j][i] = A[i][j] для матриц из i32 на кэше (s, E, b) = (5, 1, 5), 32 набора по одной линии в 32 байта, 1 КБ прямого отображения. Считаются только обращения к A и B, локальные переменные это регистры. Порог лаборатории: меньше 300 промахов на 32 на 32, меньше 1300 на 64 на 64, меньше 2000 на 61 на 67.

Ниже эталонный transpose.zig целиком. Как и matmul.zig, он живёт рядом с cache.zig и gen.zig, а Mat это Matrix(i32) из генератора трасс.

//! Транспонирование матрицы в трёх версиях и промахи каждой на кэше
//! cachelab: 32 набора по одной строке в 32 байта, всего 1 КБ прямого
//! отображения.

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

pub const Mat = gen.Matrix(i32);

/// Кэш cachelab: (s, E, b) = (5, 1, 5).
pub const params: cache.Params = .{ .s = 5, .e = 1, .b = 5 };

/// A и B лежат на расстоянии, кратном размеру кэша, поэтому элемент A и
/// элемент B с одинаковым смещением попадают в один набор.
pub const base_a: u64 = 0x100000;
pub const base_b: u64 = 0x140000;

pub const Version = union(enum) {
    naive,
    /// Блочная с квадратным блоком заданной стороны.
    blocked: usize,
    /// Блочная с обходом диагонали: для 32 на 32 и 64 на 64 отдельные
    /// приёмы, для остальных размеров блок 16.
    diagonal,
};

pub fn run(version: Version, a: Mat, b: Mat) void {
    switch (version) {
        .naive => naive(a, b),
        .blocked => |size| blocked(a, b, size),
        .diagonal => diagonal(a, b),
    }
}

/// B = A^T в лоб: A читается по строкам, B пишется по столбцам.
pub fn naive(a: Mat, b: Mat) void {
    var i: usize = 0;
    while (i < a.rows) : (i += 1) {
        var j: usize = 0;
        while (j < a.cols) : (j += 1) b.set(j, i, a.get(i, j));
    }
}

/// Блочная версия: пока блок A читается, блок B целиком сидит в кэше.
pub fn blocked(a: Mat, b: Mat, size: usize) void {
    var ii: usize = 0;
    while (ii < a.rows) : (ii += size) {
        var jj: usize = 0;
        while (jj < a.cols) : (jj += size) {
            var i: usize = ii;
            while (i < @min(ii + size, a.rows)) : (i += 1) {
                var j: usize = jj;
                while (j < @min(jj + size, a.cols)) : (j += 1) b.set(j, i, a.get(i, j));
            }
        }
    }
}

pub fn diagonal(a: Mat, b: Mat) void {
    if (a.rows == 32 and a.cols == 32) return diagonal32(a, b);
    if (a.rows == 64 and a.cols == 64) return diagonal64(a, b);
    blocked(a, b, 16);
}

/// 32 на 32: блок 8 на 8, строка A читается в восемь локальных переменных
/// целиком и только потом пишется в столбец B. На диагонали строка A и
/// столбец B делят один набор, и без этого приёма они бы выбивали друг
/// друга по очереди.
fn diagonal32(a: Mat, b: Mat) void {
    var ii: usize = 0;
    while (ii < 32) : (ii += 8) {
        var jj: usize = 0;
        while (jj < 32) : (jj += 8) {
            var i: usize = ii;
            while (i < ii + 8) : (i += 1) {
                var row: [8]i32 = undefined;
                for (&row, 0..) |*x, t| x.* = a.get(i, jj + t);
                for (row, 0..) |x, t| b.set(jj + t, i, x);
            }
        }
    }
}

/// 64 на 64: строка занимает 256 байт, так что четыре строки заполняют
/// весь кэш, и блок 8 на 8 в B не помещается. Блок делится на четыре
/// четверти по 4 на 4, а правая верхняя четверть B служит временным
/// хранилищем для правой верхней четверти A.
fn diagonal64(a: Mat, b: Mat) void {
    var ii: usize = 0;
    while (ii < 64) : (ii += 8) {
        var jj: usize = 0;
        while (jj < 64) : (jj += 8) block64(a, b, ii, jj);
    }
}

fn block64(a: Mat, b: Mat, ii: usize, jj: usize) void {
    // 1. Верхняя половина A по строкам: левая четверть встаёт в B на место,
    //    правая пока ложится в правую верхнюю четверть B.
    var i: usize = ii;
    while (i < ii + 4) : (i += 1) {
        var row: [8]i32 = undefined;
        for (&row, 0..) |*x, t| x.* = a.get(i, jj + t);
        for (row[0..4], 0..) |x, t| b.set(jj + t, i, x);
        for (row[4..8], 0..) |x, t| b.set(jj + t, i + 4, x);
    }
    // 2. По столбцам j: временные значения из B переезжают в левую нижнюю
    //    четверть, а их место занимает столбец из левой нижней четверти A.
    var j: usize = jj;
    while (j < jj + 4) : (j += 1) {
        var saved: [4]i32 = undefined;
        for (&saved, 0..) |*x, t| x.* = b.get(j, ii + 4 + t);
        var column: [4]i32 = undefined;
        for (&column, 0..) |*x, t| x.* = a.get(ii + 4 + t, j);
        for (column, 0..) |x, t| b.set(j, ii + 4 + t, x);
        for (saved, 0..) |x, t| b.set(j + 4, ii + t, x);
    }
    // 3. Правая нижняя четверть как обычно.
    i = ii + 4;
    while (i < ii + 8) : (i += 1) {
        var row: [4]i32 = undefined;
        for (&row, 0..) |*x, t| x.* = a.get(i, jj + 4 + t);
        for (row, 0..) |x, t| b.set(jj + 4 + t, i, x);
    }
}

/// Проверка результата без трассы: B[j][i] == A[i][j] всюду.
pub fn isTransposed(a: Mat, b: Mat) bool {
    var i: usize = 0;
    while (i < a.rows) : (i += 1) {
        var j: usize = 0;
        while (j < a.cols) : (j += 1) {
            if (b.at(j, i).* != a.at(i, j).*) return false;
        }
    }
    return true;
}

pub const Report = struct {
    stats: cache.Stats,
    correct: bool,
};

/// Снимает трассу транспонирования rows на cols и проигрывает её на кэше
/// cachelab. Только обращения к A и B попадают в трассу: локальные
/// переменные, как и в cachelab, считаются регистрами.
pub fn measure(gpa: std.mem.Allocator, version: Version, rows: usize, cols: usize) !Report {
    const a_items = try gpa.alloc(i32, rows * cols);
    defer gpa.free(a_items);
    const b_items = try gpa.alloc(i32, rows * cols);
    defer gpa.free(b_items);
    for (a_items, 0..) |*x, idx| x.* = @intCast(idx);
    @memset(b_items, -1);

    var tracer: gen.Tracer = .init(gpa);
    defer tracer.deinit();
    const a: Mat = .init(&tracer, base_a, a_items, rows, cols);
    const b: Mat = .init(&tracer, base_b, b_items, cols, rows);
    run(version, a, b);

    return .{
        .stats = try cache.simulate(gpa, params, .write_back, try tracer.slice()),
        .correct = isTransposed(a, b),
    };
}

test "все версии транспонируют правильно" {
    const cases = [_]struct { Version, usize, usize }{
        .{ .naive, 32, 32 },
        .{ .{ .blocked = 8 }, 32, 32 },
        .{ .diagonal, 32, 32 },
        .{ .diagonal, 64, 64 },
        .{ .{ .blocked = 16 }, 61, 67 },
        .{ .diagonal, 61, 67 },
        .{ .{ .blocked = 5 }, 7, 13 },
    };
    for (cases) |case| {
        const version, const rows, const cols = case;
        const report = try measure(std.testing.allocator, version, rows, cols);
        try std.testing.expect(report.correct);
    }
}

И маленькая программа, которая снимает промахи всех версий на трёх размерах лаборатории.

//! Промахи трёх версий транспонирования на кэше cachelab (s, E, b) = (5, 1, 5).
//! Собирается рядом с cache.zig, gen.zig, trace.zig и transpose.zig.

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

/// Имя версии в столбце на 14 знаков: ширина считается в символах, не в байтах.
fn column(out: *std.Io.Writer, name: []const u8) !void {
    try out.writeAll(name);
    const width = try std.unicode.utf8CountCodepoints(name);
    try out.splatByteAll(' ', 14 - width);
}

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

    const sizes = [_][2]usize{ .{ 32, 32 }, .{ 64, 64 }, .{ 61, 67 } };
    const versions = [_]struct { []const u8, transpose.Version }{
        .{ "наивное", .naive },
        .{ "блок 8", .{ .blocked = 8 } },
        .{ "блок 16", .{ .blocked = 16 } },
        .{ "по диагонали", .diagonal },
    };
    try column(out, "версия");
    for (sizes) |size| try out.print(" {d:>3}x{d:<3}", .{ size[0], size[1] });
    try out.print("\n", .{});
    for (versions) |version| {
        const name, const which = version;
        try column(out, name);
        for (sizes) |size| {
            const report = try transpose.measure(init.gpa, which, size[0], size[1]);
            std.debug.assert(report.correct);
            try out.print(" {d:>7}", .{report.stats.misses});
        }
        try out.print("\n", .{});
    }
    try out.flush();
}

$ zig run -O ReleaseFast transpose_report.zig
версия          32x32   64x64   61x67
наивное           1180    4720    4706
блок 8             340    4720    2222
блок 16           1180    4720    2005
по диагонали       284    1224    2005

Разберём таблицу по столбцам, потому что в каждом своя история.

32 на 32, наивное: 1180. Строка из 32 i32 это 128 байт, четыре линии; вся матрица 4 КБ, четыре размера кэша. Чтение A по строкам стоит промах на линию, 256 промахов на всю матрицу. Запись B по столбцам это классический обход с шагом в строку: каждая запись в свою линию, а к моменту возврата в ту же линию за соседним элементом столбца её уже выбили. Почти тысяча промахов из 1180 это B.

32 на 32, блок 8: 340. Блок 8 на 8 в B это восемь строк по 32 байта, восемь линий, которые все помещаются в кэш и не мешают друг другу. Чтение блока A восемь линий, запись блока B восемь линий, шестнадцать промахов на блок, шестнадцать блоков, 256 промахов плюс конфликты. Блок 16 при этом даёт ровно наивные 1180: шестнадцать строк это 2 КБ, в кэш на 1 КБ не помещаются, и блочная структура ничего не меняет. Размер блока согласуют с кэшем, а не берут «побольше».

32 на 32, по диагонали: 284. Откуда 84 лишних промаха у блока 8? A и B лежат на расстоянии, кратном размеру кэша, поэтому A[i][j] и B[i][j] попадают в один набор. В блоках на диагонали A[i][i..i+8] читается из той же линии, в которую тут же пишется B[i][i], и они выбивают друг друга по очереди, по два промаха вместо одного. Лечение в diagonal32: строку блока A читаем в восемь локальных переменных (в cachelab это регистры), а потом восемь раз пишем в B. Линия A нужна один раз, и никто её не выбивает посередине. 284 меньше 300, зачёт.

64 на 64: блок 8 не помогает вовсе, 4720 у всех. Строка из 64 i32 это 256 байт, восемь линий. Четыре строки заполняют весь кэш: строки i и i + 4 ложатся на одни наборы. Блок 8 на 8 в B это восемь строк, а помещаются четыре, и верхняя половина блока выбивает нижнюю. Это те же конфликтные промахи, что и в умножении при n = 64, только теперь они съедают весь выигрыш. Решение block64 хитрое: блок делится на четверти 4 на 4, и правая верхняя четверть B временно хранит данные, которые потом переедут в левую нижнюю. Так в работе всегда не больше четырёх строк каждой матрицы, и 1224 промаха проходят под порог 1300.

61 на 67: 2005 у блока 16. Размеры не делятся ни на что, конфликтов почти нет, и обычный блок 16 даёт почти минимум. Порог лаборатории 2000; последние пять промахов эталон не выжимает, это одно из упражнений.

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

Массив структур против структуры массивов

До сих пор мы меняли порядок обхода. Второй рычаг это раскладка самих данных. Возьмём задачу книги: в игре есть сетка 16 на 16 водорослей, у каждой два поля x и y по 4 байта, и цикл считает среднее положение. Кэш 1 КБ прямого отображения с блоком 16 байт, массив начинается с адреса 0, в кэш ходят только обращения к сетке, счётчики в регистрах. Сетка это 2 КБ, два размера кэша, в линию помещаются две структуры.

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

//! Массив структур против структуры массивов на игрушечном кэше: 1 КБ
//! прямого отображения, блок 16 байт, как в задачах книги про водоросли.
//! Симулятор здесь трёхстрочный: хранить надо только тег каждого набора.

const std = @import("std");

const Cache = struct {
    const sets = 64; // 1024 / 16
    const block = 16;

    tags: [sets]?u64 = .{null} ** sets,
    reads: u64 = 0,
    misses: u64 = 0,

    fn read(c: *Cache, addr: u64) void {
        c.reads += 1;
        const set = (addr / block) % sets;
        const tag = addr / block / sets;
        if (c.tags[set] != tag) {
            c.misses += 1;
            c.tags[set] = tag;
        }
    }

    fn missRate(c: Cache) f64 {
        return @as(f64, @floatFromInt(c.misses)) / @as(f64, @floatFromInt(c.reads));
    }
};

/// Массив структур: x и y каждой водоросли лежат рядом, 8 байт на структуру,
/// grid[i][j] по адресу (i * 16 + j) * 8 от начала массива.
const Aos = struct {
    fn x(i: u64, j: u64) u64 {
        return (i * 16 + j) * 8;
    }
    fn y(i: u64, j: u64) u64 {
        return (i * 16 + j) * 8 + 4;
    }
};

/// Два прохода: сначала все x построчно, потом все y построчно.
fn twoPasses(c: *Cache) void {
    for (0..16) |i| {
        for (0..16) |j| c.read(Aos.x(i, j));
    }
    for (0..16) |i| {
        for (0..16) |j| c.read(Aos.y(i, j));
    }
}

/// Один проход по столбцам: grid[j][i], x и y вместе.
fn columnWise(c: *Cache) void {
    for (0..16) |i| {
        for (0..16) |j| {
            c.read(Aos.x(j, i));
            c.read(Aos.y(j, i));
        }
    }
}

/// Один проход по строкам: grid[i][j], x и y вместе.
fn rowWise(c: *Cache) void {
    for (0..16) |i| {
        for (0..16) |j| {
            c.read(Aos.x(i, j));
            c.read(Aos.y(i, j));
        }
    }
}

/// Структура массивов: сначала 256 значений x подряд, потом 256 значений y.
const Soa = struct {
    fn x(i: u64, j: u64) u64 {
        return (i * 16 + j) * 4;
    }
    fn y(i: u64, j: u64) u64 {
        return 1024 + (i * 16 + j) * 4;
    }
};

/// Те же два прохода, что в twoPasses, но по структуре массивов.
fn twoPassesSoa(c: *Cache) void {
    for (0..16) |i| {
        for (0..16) |j| c.read(Soa.x(i, j));
    }
    for (0..16) |i| {
        for (0..16) |j| c.read(Soa.y(i, j));
    }
}

test "два прохода по массиву структур: каждая вторая загрузка промах" {
    var c: Cache = .{};
    twoPasses(&c);
    try std.testing.expectEqual(@as(u64, 512), c.reads);
    try std.testing.expectEqual(@as(u64, 256), c.misses);
    try std.testing.expectEqual(@as(f64, 0.5), c.missRate());
}

test "обход по столбцам: половина массива вытесняет другую" {
    var c: Cache = .{};
    columnWise(&c);
    try std.testing.expectEqual(@as(u64, 512), c.reads);
    try std.testing.expectEqual(@as(u64, 256), c.misses);
}

test "обход по строкам: только холодные промахи" {
    var c: Cache = .{};
    rowWise(&c);
    try std.testing.expectEqual(@as(u64, 512), c.reads);
    try std.testing.expectEqual(@as(u64, 128), c.misses);
    try std.testing.expectEqual(@as(f64, 0.25), c.missRate());
}

test "структура массивов: два прохода стоят как один" {
    var c: Cache = .{};
    twoPassesSoa(&c);
    try std.testing.expectEqual(@as(u64, 512), c.reads);
    try std.testing.expectEqual(@as(u64, 128), c.misses);
}

Теперь разбор, почему тесты зелёные. Задача про два прохода (по книге это задача 6.18): первый цикл читает только x, вторая структура в линии приезжает вместе с первой, поэтому промах, попадание, промах, попадание: 128 промахов на 256 чтений. Второй цикл читает y, но сетка вдвое больше кэша, и к началу второго прохода первая половина уже выбита второй: снова 128 промахов. Итого 512 чтений, 256 промахов, половина. Заметь, что половина y каждый раз ехала в кэш зря: мы её привезли в первом проходе и не использовали, а во втором привезли снова.

Задача про обход по столбцам (6.19): читаем grid[j][i], то есть идём вниз по столбцу, каждый шаг это 128 байт, новая линия. Первый столбец: 16 промахов на 32 чтения, потому что x и y одной структуры в одной линии. Но столбец из 16 строк это 16 линий по разным наборам, а строки j и j + 8 попадают в один набор (8 строк это 1 КБ, размер кэша). Пока мы дошли до низа столбца, верх уже выбит. На втором столбце соседняя структура, которая лежала в той же линии, снова не в кэше. Опять 256 из 512. И тут отличие от первой задачи: если удвоить кэш, вся сетка поместится, и промахи станут только холодными, 128, четверть. Первой задаче удвоение кэша тоже помогло бы, а вот третьей уже нет.

Задача про обход по строкам (6.20): grid[i][j], шаг 1, x и y вместе. Первая структура в линии промахивается, всё остальное попадания: 128 холодных промахов на 512 чтений, четверть. Это нижняя граница для такой раскладки, никакой кэш её не улучшит: каждую линию всё равно надо привезти хотя бы раз.

И четвёртый вариант: структура массивов. Те же два прохода, что в первой задаче, но x лежат подряд отдельно от y. Первый проход читает 256 чисел по 4 байта, в линию помещаются четыре, 64 промаха. Второй такой же, ещё 64. Итого 128, как у лучшего варианта с одним проходом, хотя циклов по-прежнему два. Раскладка данных заменила перестановку циклов.

В Zig структуру массивов не надо собирать руками: std.MultiArrayList(T) хранит каждое поле T отдельным массивом и отдаёт срез поля через list.items(.x). Ты видел раскладку структур в памяти в уроке про массивы и выравнивание, теперь ясно, зачем стандартной библиотеке второй контейнер для того же списка: когда горячий цикл трогает одно поле из десяти, обычный массив везёт из памяти в десять раз больше, чем использует.

Линия кэша и ложное разделение

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

//! Ложное разделение: два потока пишут в разные счётчики, но счётчики
//! лежат в одной линии кэша. Собирать в ReleaseFast.

const std = @import("std");

const rounds: u64 = 50_000_000;

/// Соседи: два счётчика в одной линии по 64 байта.
const Packed = struct { a: u64 = 0, b: u64 = 0 };

/// Разведены: каждый счётчик в начале своей линии.
const Padded = struct { a: u64 align(64) = 0, b: u64 align(64) = 0 };

fn bump(counter: *u64) void {
    for (0..rounds) |_| _ = @atomicRmw(u64, counter, .Add, 1, .monotonic);
}

fn race(a: *u64, b: *u64, io: std.Io) !f64 {
    const started = std.Io.Clock.awake.now(io);
    const t1 = try std.Thread.spawn(.{}, bump, .{a});
    const t2 = try std.Thread.spawn(.{}, bump, .{b});
    t1.join();
    t2.join();
    const elapsed = started.durationTo(std.Io.Clock.awake.now(io));
    return @as(f64, @floatFromInt(elapsed.toNanoseconds())) / 1e6;
}

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

    var packed_counters: Packed = .{};
    var padded_counters: Padded = .{};
    try out.print("{d} инкрементов на поток, лучшее из 3\n", .{rounds});

    var best_packed: f64 = std.math.inf(f64);
    var best_padded: f64 = std.math.inf(f64);
    for (0..3) |_| {
        best_packed = @min(best_packed, try race(&packed_counters.a, &packed_counters.b, init.io));
        best_padded = @min(best_padded, try race(&padded_counters.a, &padded_counters.b, init.io));
    }
    try out.print("в одной линии:   {d:>8.1} мс (a и b на расстоянии {d} байт)\n", .{
        best_packed, @offsetOf(Packed, "b") - @offsetOf(Packed, "a"),
    });
    try out.print("в разных линиях: {d:>8.1} мс (a и b на расстоянии {d} байт)\n", .{
        best_padded, @offsetOf(Padded, "b") - @offsetOf(Padded, "a"),
    });
    try out.flush();
}

Снято на Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-13.

$ zig build-exe false_sharing.zig -O ReleaseFast && ./false_sharing
50000000 инкрементов на поток, лучшее из 3
в одной линии:      618.1 мс (a и b на расстоянии 8 байт)
в разных линиях:    134.7 мс (a и b на расстоянии 64 байт)

В четыре с половиной раза, а разница в коде это слово align(64) у двух полей. Оно заставляет каждое поле начинаться на границе линии, поэтому b уезжает в следующую линию, и ядра больше не мешают друг другу. На x86-64 разрыв обычно ещё больше, чем на Apple Silicon: там межъядерный обмен дороже. Полный разбор того, что именно происходит с линией, протокол MESI и то, как это лечат в Rust через #[repr(align(64))] и CachePadded, есть в уроке про аппаратную модель памяти раздела про Rust. Здесь достаточно правила: горячие поля, в которые пишут разные потоки, разводи по разным линиям, и не верь глазам, а меряй, потому что на глаз безобидное соседство полей от ложного разделения не отличить.

Шаг проекта: cons-ячейки zl и кэш

Всё, что урок говорил про массивы структур, про cons-ячейки верно вдвойне. Ячейка zl это 16 байт: car и cdr. В линию кэша M4 на 128 байт ложится восемь ячеек, в линию x86-64 на 64 байта четыре. А обход списка хуже любого обхода массива тем, что адрес следующей ячейки известен, только когда прочитана текущая: это цепочка зависимых загрузок, и процессор не может забежать вперёд так, как забегает по массиву с известным шагом. Цена обхода почти целиком решается тем, где лежит следующая ячейка.

Куча zl пока арена, и она выдаёт ячейки подряд, в порядке выделения: список, построенный за один проход, лежит в памяти так же подряд, как массив. Пул ячеек из урока про аллокатор сохранит это свойство. Сравним такой список с тремя другими раскладками того же списка:

подряд: соседи по списку соседи в памяти, восемь ячеек на линию;
через линию: каждая следующая ячейка лежит в следующей линии, та же память, но на каждую ячейку новая линия;
вперемешку: те же ячейки в случайном порядке;
общий аллокатор: каждая ячейка отдельным create у std.heap.smp_allocator, а между ними он выдаёт чужие объекты от 16 до 256 байт, как в программе, где список строится посреди другой работы.

locality.zig

Раскладку делает перешивка: ячейки берутся из кучи подряд, а потом cdr каждой указывает на ту, что идёт следующей в нужном порядке. Значения car расставлены так, что список в любой раскладке читается как (1 2 ... n). walk это сам измеряемый обход, lineChanges считает, сколько раз обход переходит в новую линию.

//! Cons-ячейки и кэш: один и тот же список, разложенный в памяти по-разному.
//!
//! Обход списка это цепочка загрузок, где адрес следующей ячейки известен
//! только после чтения текущей. Процессор не может забежать вперёд, и цена
//! обхода почти целиком зависит от того, где лежит следующая ячейка: в той же
//! линии кэша, в соседней или неизвестно где.
//!
//! Раскладки, которые сравнивает шаг:
//!   * `sequential`: соседи по списку соседи в куче, 8 ячеек на линию 128 байт;
//!   * `stride`: соседи по списку лежат через линию, каждая ячейка в новой;
//!   * `shuffled`: те же ячейки в случайном порядке;
//!   * `scattered` (отдельная функция): каждая ячейка от общего аллокатора,
//!     вперемешку с чужими объектами разного размера.

const std = @import("std");

const value = @import("value.zig");
const Vm = @import("vm.zig").Vm;

const Cell = value.Cell;
const Value = value.Value;

pub const Layout = enum { sequential, stride, shuffled };

/// Ячеек в линии кэша на 128 байт, как у Apple M4. На x86-64 линия 64 байта.
pub const cells_per_line = 128 / @sizeOf(Cell);

/// Список `(1 2 ... n)` в куче с заданной раскладкой. Ячейки берутся из кучи
/// подряд, а потом `cdr` перешиваются в нужном порядке.
pub fn build(vm: *Vm, gpa: std.mem.Allocator, n: usize, layout: Layout, seed: u64) !Value {
    if (n == 0) return .nil;

    const cells = try gpa.alloc(*Cell, n);
    defer gpa.free(cells);
    for (cells) |*cell| cell.* = (try vm.heap.cons(.nil, .nil)).asCell();

    // order[k] это номер ячейки, которую обход посетит k-й.
    const order = try gpa.alloc(usize, n);
    defer gpa.free(order);
    for (order, 0..) |*slot, k| slot.* = k;
    switch (layout) {
        .sequential => {},
        // Сначала каждая восьмая ячейка, начиная с нулевой, потом с первой и
        // так далее: соседи по списку всегда в разных линиях.
        .stride => {
            var k: usize = 0;
            for (0..cells_per_line) |offset| {
                var i = offset;
                while (i < n) : (i += cells_per_line) {
                    order[k] = i;
                    k += 1;
                }
            }
        },
        .shuffled => {
            var prng: std.Random.DefaultPrng = .init(seed);
            prng.random().shuffle(usize, order);
        },
    }

    for (order, 0..) |index, k| {
        cells[index].* = .{
            .car = .fromFixnum(@intCast(k + 1)),
            .cdr = if (k + 1 < n) .fromCell(cells[order[k + 1]]) else .nil,
        };
    }
    return .fromCell(cells[order[0]]);
}

/// Тот же список, но каждая ячейка от общего аллокатора, и между ними
/// аллокатор выдаёт чужие объекты от 16 до 256 байт, как в программе, где
/// списки строятся посреди другой работы. Сборщик об этих ячейках не знает.
pub const Scattered = struct {
    gpa: std.mem.Allocator,
    cells: []*Cell,
    noise: [][]u8,
    list: Value,

    pub fn init(gpa: std.mem.Allocator, n: usize, seed: u64) !Scattered {
        const cells = try gpa.alloc(*Cell, n);
        errdefer gpa.free(cells);
        const noise = try gpa.alloc([]u8, n);
        errdefer gpa.free(noise);
        var prng: std.Random.DefaultPrng = .init(seed);
        var made: usize = 0;
        errdefer for (cells[0..made], noise[0..made]) |cell, bytes| {
            gpa.destroy(cell);
            gpa.free(bytes);
        };
        while (made < n) : (made += 1) {
            cells[made] = try gpa.create(Cell);
            noise[made] = try gpa.alloc(u8, prng.random().intRangeAtMost(usize, 16, 256));
        }
        for (cells, 0..) |cell, k| {
            cell.* = .{
                .car = .fromFixnum(@intCast(k + 1)),
                .cdr = if (k + 1 < n) .fromCell(cells[k + 1]) else .nil,
            };
        }
        return .{ .gpa = gpa, .cells = cells, .noise = noise, .list = if (n > 0) .fromCell(cells[0]) else .nil };
    }

    pub fn deinit(self: *Scattered) void {
        for (self.cells, self.noise) |cell, bytes| {
            self.gpa.destroy(cell);
            self.gpa.free(bytes);
        }
        self.gpa.free(self.cells);
        self.gpa.free(self.noise);
        self.* = undefined;
    }
};

/// Обход до конца: число ячеек. Это и есть измеряемая цепочка загрузок.
pub noinline fn walk(list: Value) usize {
    var count: usize = 0;
    var rest = list;
    while (rest.isCons()) : (rest = rest.asCell().cdr) count += 1;
    return count;
}

/// Сколько раз обход переходит в другую линию кэша. Это промахи кэша, в
/// котором помещается одна линия: нижняя граница для любого настоящего,
/// когда список больше кэша целиком.
pub fn lineChanges(list: Value, line_bytes: usize) usize {
    var changes: usize = 0;
    var line: usize = std.math.maxInt(usize);
    var rest = list;
    while (rest.isCons()) : (rest = rest.asCell().cdr) {
        const here = @intFromPtr(rest.asCell()) / line_bytes;
        if (here != line) changes += 1;
        line = here;
    }
    return changes;
}

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

Бенч: ключ cache

Бенч получает третий режим:

const Mode = enum { executors, cmov, cache };

        } else if (std.mem.eql(u8, arg, "cache")) {
            mode = .cache;

    const done = switch (mode) {
        .executors => measureAll(io, out, chosen),
        .cmov => measureSelect(io, out),
        .cache => measureCache(io, out),
    };

Сам режим: четыре длины списка, от 64 КБ, которые помещаются в L1d ядра M4, до 64 МБ, которые не помещаются никуда. На каждую раскладку своя машина, чтобы списки не смешивались в одной куче. В конце тот же обход, но исполнителем zl: (last xs) байткодом по списку подряд и вперемешку.

// --- Обход списка при разных раскладках ячеек ---

/// Длины списка: 64 КБ (помещается в L1d ядра M4), 1 МБ, 16 МБ и 64 МБ.
const cache_lengths = [_]usize{ 1 << 12, 1 << 16, 1 << 20, 1 << 22 };

const Walk = struct {
    list: Value,

    pub fn run(self: *Walk, n: usize) void {
        _ = n;
        std.mem.doNotOptimizeAway(zl.locality.walk(self.list));
    }
};

/// Тактов на ячейку одного обхода списка длины n.
fn perCell(clock: harness.Clock, list: Value, n: usize) f64 {
    var w: Walk = .{ .list = list };
    const series = harness.measure(clock, &w, &.{n}, .{ .work = @max(n, 1 << 22), .runs = 5 });
    return series.items()[0].cycles / @as(f64, @floatFromInt(n));
}

/// Новых линий на ячейку при линии 128 и 64 байта.
fn newLines(list: Value, n: usize) [2]f64 {
    var out: [2]f64 = undefined;
    for ([_]usize{ 128, 64 }, &out) |bytes, *per_cell| {
        const changes: f64 = @floatFromInt(zl.locality.lineChanges(list, bytes));
        per_cell.* = changes / @as(f64, @floatFromInt(n));
    }
    return out;
}

fn measureCache(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("ячеек       подряд  через линию  вперемешку  общий аллокатор   (тактов на ячейку)\n");
    try out.flush();

    // Новые линии на ячейку считаются по адресам самого большого списка.
    var lines: [4][2]f64 = undefined;
    for (cache_lengths) |n| {
        try out.print("{d:>8}", .{n});
        for (std.enums.values(zl.locality.Layout), 0..) |layout, column| {
            var vm: Vm = try .init(gpa);
            defer vm.deinit();
            const list = try zl.locality.build(&vm, gpa, n, layout, 2026);
            try out.print(" {d:>11.1}", .{perCell(clock, list, n)});
            lines[column] = newLines(list, n);
        }
        var scattered: zl.locality.Scattered = try .init(gpa, n, 2026);
        defer scattered.deinit();
        try out.print(" {d:>11.1}\n", .{perCell(clock, scattered.list, n)});
        lines[3] = newLines(scattered.list, n);
        try out.flush();
    }
    for ([_]usize{ 128, 64 }, 0..) |bytes, row| {
        try out.print("линия {d:>3} Б", .{bytes});
        for (lines) |column| try out.print(" {d:>11.3}", .{column[row]});
        try out.writeAll("   (новых линий на ячейку)\n");
    }

    // Тот же обход, но исполнителем zl: байткод под labeled switch.
    const n = 1 << 20;
    try out.writeAll("\nzl, (last xs) байткодом, миллион ячеек (тактов на ячейку)\n");
    for ([_]zl.locality.Layout{ .sequential, .shuffled }) |layout| {
        var vm: Vm = try .init(gpa);
        defer vm.deinit();
        var machine: zl.bytecode.Machine = .init(&vm);
        defer machine.deinit();
        _ = try zl.eval.evalSource(&vm, workload.definitions);
        try vm.defineNamed("xs", try zl.locality.build(&vm, gpa, n, layout, 2026));
        var b: Bench = .{ .machine = &machine, .executor = .labeled, .form = try workload.form(&vm, "(last xs)") };
        const series = harness.measure(clock, &b, &.{n}, .{ .work = n, .runs = 5 });
        try out.print("{t:<12} {d:>8.1}\n", .{ layout, series.items()[0].cycles / @as(f64, @floatFromInt(n)) });
        try out.flush();
    }
}

Что показал замер

$ zig build bench -- cache
частота ядра по калибровке: 4.10 ГГц
ячеек       подряд  через линию  вперемешку  общий аллокатор   (тактов на ячейку)
    4096         3.3         3.8         3.1         3.1
   65536         3.2         7.4        23.8         3.5
 1048576         2.4         8.3        49.2         3.4
 4194304         2.6        30.5       258.3         3.8
линия 128 Б       0.125       1.000       1.000       0.822   (новых линий на ячейку)
линия  64 Б       0.250       1.000       1.000       0.847   (новых линий на ячейку)

zl, (last xs) байткодом, миллион ячеек (тактов на ячейку)
sequential      149.1
shuffled        168.1

Снято на Apple M4 Max, Zig 0.16.0, ReleaseFast; второй прогон дал те же числа с разбросом в пределах 10 процентов, кроме строки миллиона ячеек подряд (1.6 против 2.4).

Читаем по строкам. На 64 КБ весь список в L1d, и все раскладки стоят около трёх тактов на ячейку: это задержка загрузки из L1, цепочка ждёт каждое звено. На 1 МБ список в L2, и вперемешку уже 24 такта, задержка L2. На 16 МБ 49 тактов, на 64 МБ 258: это около 63 наносекунд, почти целое обращение к памяти на каждую ячейку. Случайный порядок это худший случай, ради которого и нужны пул и порядок выделения.

Подряд на больших списках стоит от 1.6 до 2.6 такта на ячейку, меньше, чем на маленьком, и меньше задержки загрузки из L1. Значит ядро не ждёт каждое звено цепочки. Почему маленький список этой скидки не получил, наш замер не говорит. Предвыборка тут ни при чём: она привозит линию заранее, но адрес следующей загрузки всё равно известен только после предыдущей. Самое правдоподобное объяснение: ядро угадывает адрес следующей загрузки по шагу предыдущих и не ждёт, пока прочитается cdr. Ядра Apple так умеют, и в 2025 году исследователи описали этот механизм, предсказание адреса загрузки, как канал утечки данных. Счётчиками мы это подтвердить не можем, но меньше задержки L1 цепочка иначе не бывает. Для нас важнее другое: на M4 обход списка подряд перестаёт быть цепочкой зависимостей, а на x86-64 им остаётся.

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

Общий аллокатор оказался неожиданно хорош: 3.5 такта, хотя новая линия почти на каждой ячейке. Посмотреть, куда он кладёт соседние ячейки, можно распределением разностей адресов: в нашем прогоне на миллионе ячеек соседи отстоят чаще всего на плюс-минус 64 КБ. Ячейки одного размера smp_allocator раздаёт из своих участков, и список ходит между несколькими такими участками, каждый из которых заполнен подряд. Для предсказателя и предвыборки это несколько регулярных потоков, и они с ним справляются. Вывод осторожный: этот аллокатор, этот шум и этот процессор. Аллокатор без классов размеров или долгоживущая куча с дырами после сборок дадут ближе к столбцу «вперемешку», и это одно из упражнений.

И последняя строка, самая отрезвляющая. Байткод zl на миллионе ячеек платит за случайную раскладку всего 19 тактов на ячейку сверху, 168 против 149, хотя голый обход теряет на ней 47. Интерпретатор тратит на ячейку полторы сотни тактов своей работы, и внеочередное ядро успевает спрятать большую часть промаха за этой работой. Раскладка начнёт решать, когда исполнитель станет быстрым: у JIT на ячейку под эмуляцией уходит около семи тактов, и для него лишние 47 тактов на промах это обход в разы медленнее.

cdr-coding

Если cdr почти всегда указывает на соседнюю ячейку, его можно не хранить. Это и есть cdr-coding Лисп-машин семидесятых: в ячейке два бита кода вместо cdr, «следующий элемент сразу за мной», «список кончился» или «дальше обычный указатель». Список, выделенный подряд, становится массивом car с пометками, занимает вдвое меньше памяти и укладывается по шестнадцать элементов в линию вместо восьми. Это тот же переход от массива структур к структуре массивов, что выше, только для списка, и цена та же: set-cdr! на середине такого списка требует переезда хвоста. В zl мы его не делаем, но заметь, что место под код уже есть: бит 1 тега из урока про выравнивание свободен у значения любого вида.

Тесты шага

//! Шаг 40: cons-ячейки и кэш.
//!
//! Один и тот же список `(1 2 ... n)` раскладывается в памяти по-разному.
//! Время обхода меряет бенч (`zig build bench -- cache`), а тесты проверяют,
//! что раскладки честные: список тот же, а переходов между линиями кэша
//! ровно столько, сколько обещает раскладка.

const std = @import("std");

const zl = @import("zl");

const locality = zl.locality;
const Value = zl.Value;
const Vm = zl.Vm;

const testing = std.testing;

const n = 4096;

fn expectOneToN(list: Value) !void {
    var expected: i64 = 1;
    var rest = list;
    while (rest.isCons()) : (rest = rest.asCell().cdr) {
        try testing.expectEqual(expected, rest.asCell().car.asFixnum());
        expected += 1;
    }
    try testing.expectEqual(@as(i64, n + 1), expected);
}

test "все раскладки дают один и тот же список" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    for (std.enums.values(locality.Layout)) |layout| {
        const list = try locality.build(&vm, testing.allocator, n, layout, 7);
        try testing.expectEqual(@as(usize, n), locality.walk(list));
        try expectOneToN(list);
    }

    var scattered: locality.Scattered = try .init(testing.allocator, n, 7);
    defer scattered.deinit();
    try expectOneToN(scattered.list);
}

test "подряд это одна новая линия на восемь ячеек, через линию каждая" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();

    const sequential = try locality.build(&vm, testing.allocator, n, .sequential, 0);
    const lines = locality.lineChanges(sequential, 128);
    // Ячейки выровнены на 16, а не на 128, и куча может быть нарезана на
    // куски (арена растит свои буферы), поэтому лишние переходы на стыках
    // допустимы, но их немного.
    try testing.expect(lines >= n / 8 and lines < n / 8 + n / 16);
    // На x86-64 линия 64 байта: четыре ячейки.
    try testing.expect(locality.lineChanges(sequential, 64) < n / 4 + n / 16);

    const stride = try locality.build(&vm, testing.allocator, n, .stride, 0);
    try testing.expectEqual(@as(usize, n), locality.lineChanges(stride, 128));

    // Вперемешку почти каждый шаг в новую линию: совпадения редки.
    const shuffled = try locality.build(&vm, testing.allocator, n, .shuffled, 7);
    try testing.expect(locality.lineChanges(shuffled, 128) > n * 9 / 10);
}

$ zig build test --summary all
Build Summary: 21/21 steps succeeded; 75/86 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: 21/21 steps succeeded; 86/86 tests passed

Практика

Задача переносит блочное транспонирование на обычные срезы без трассировщика. Тебе дан transposeNaive (два вложенных цикла, dst[j * n + i] = src[i * n + j]) и две заглушки. transposeBlocked(comptime block, n, src, dst) должна идти по матрице квадратами block на block: два внешних цикла по блокам, два внутренних по элементам блока, с обрезкой границ по n, потому что крайние блоки бывают неполными. blockedOrder(comptime block, n, allocator) возвращает список пар (i, j) в том порядке, в каком их посещает transposeBlocked: те же четыре цикла, но вместо копирования шаг записывается в срез из n * n пар, который освобождает вызывающий.

Тесты проверяют корректность на n, кратных блоку и нет (1, 3, 10, 13, 37), на блоке больше матрицы, на блоке из одного элемента и на пустой матрице. Локальность проверяется через порядок обхода: это должна быть перестановка всех n * n пар без повторов, и каждое окно из block * block подряд идущих шагов должно трогать не больше block разных строк src и не больше block разных строк dst. Построчный обход это условие проваливает: на n = 32 и блоке 8 первые же 64 шага задевают все 32 столбца. Память под порядок выделяется через std.testing.allocator, и утечка проваливает тест, так что ставь errdefer allocator.free(order) сразу после выделения.

Упражнения

CHK-1★★

Найди лучший размер блока для multiplyBlocked на своей машине: прогони n = 512 с bsize 8, 16, 32, 64 и 128, запиши время и объясни, где кривая ломается. Посчитай для каждого размера рабочее множество одной итерации по i (квадрат B, кусок строки A, кусок строки C) и сравни с размером L1d, который ты узнаешь в следующем уроке или уже знаешь из sysctl и lscpu.

CHK-2★★★

Домашняя задача книги про транспонирование, в развёрнутом виде: напиши на Zig функцию, которая транспонирует матрицу N на N из i32 как можно быстрее, и покажи на N = 4096 выигрыш не меньше чем вдвое против наивной версии. Начни с блоков, потом попробуй читать строку блока в локальный массив, как diagonal32, и проверь, помогает ли это без трассировщика, на настоящем кэше с восемью строками в наборе.

CHK-3★★★

Домашняя задача книги про граф, в развёрнутом виде: матрица смежности G из нулей и единиц, и цикл G[j][i] = G[j][i] или G[i][j] превращает ориентированный граф в неориентированный. Наивный цикл читает G[i][j] по строке, а пишет G[j][i] по столбцу. Заметь, что результат симметричен, и пары (i, j) и (j, i) можно обрабатывать вместе, обходя только половину над диагональю блоками, как в транспонировании. Напиши эту версию, докажи тестом, что результат тот же, и замерь на N = 4096.

CHK-4★★

Снизь промахи транспонирования 61 на 67 ниже 2000: эталонный блок 16 даёт 2005. Прогони transpose_report.zig с блоками 4, 8, 12, 16, 20, 24, добавь вариант с неквадратным блоком (например, 16 строк на 4 столбца) и найди, что именно мешает последним пяти промахам: посчитай, в какие наборы попадают строки A и B при ширине строки 268 байт.

CHK-5★★

Переведи задачи про водоросли на трассировщик прошлого урока: положи сетку 16 на 16 в Traced(struct { x: i32, y: i32 }), читай поля через getField, а трассу проигрывай на Cache с параметрами (6, 1, 4). Три числа обязаны совпасть с тестами из algae.zig. Потом переложи ту же сетку в std.MultiArrayList и сними трассу обхода по одному полю: сколько промахов даёт items(.x) против массива структур?

CHK-6★★★

Расширь false_sharing.zig до четырёх и восьми потоков, у каждого свой счётчик в одной структуре, и построй таблицу «потоков против времени» для двух раскладок. Затем прогони то же в песочнице x86-64 или в контейнере под --platform linux/amd64 и сравни отношение времён с Apple Silicon. Объясни по уроку про MESI, почему на восьми потоках в одной линии всё становится ещё хуже, чем на двух.

CHK-7★★

Сделай шаг zl у себя и запиши трассу адресов обхода каждой раскладки в формате симулятора из прошлого урока (одно чтение L на car и одно на cdr). Прогони трассы через кэш с параметрами L1d M4 (128 КБ, 8 рядов, линия 128 байт) и сверь промахи со строкой «новых линий на ячейку» из урока. Где модель одной линии совпала с настоящим кэшем, а где нет, и почему?

CHK-8★★★

Сломай общему аллокатору регулярность: построй список из Scattered, освободи каждый второй объект шума и построй второй список в освободившихся дырах. Сними обход второго списка на 64 МБ и найди, между какими столбцами таблицы урока он встал. Потом реализуй cdr-coding для списков, построенных за один проход: массив car и два бита кода на элемент, и измерь обход такого списка против списка подряд в куче.

Итоги

Три правила дружественного к кэшу кода: смотри на внутренние циклы, ходи с шагом 1, используй привезённое слово столько раз, сколько можешь. Метрика для сравнения версий это промахи на итерацию внутреннего цикла.
Шесть порядков циклов умножения матриц делятся на три класса по внутреннему циклу. Книжная оценка для большой матрицы и линии на четыре f64: класс BC (kij, ikj) 0.5 промаха на итерацию, AB (ijk, jik) 1.25, AC (jki, kji) 2.0. Число обращений к памяти и число промахов это разные вещи: BC делает обращений больше, а промахивается реже.
Симулятор воспроизводит оценку до второго знака на n = 100 и расходится с ней на n = 64: строки матриц ложатся на одни наборы, и класс BC получает конфликтные промахи. Две строки в наборе при той же ёмкости убирают их без правки кода.
По времени разница между классами больше, чем по промахам: обход с шагом 1 предвыбирается и векторизуется, обход по столбцу нет. На M4 Max худший порядок медленнее лучшего в семнадцать раз при четырёхкратной разнице в промахах.
Блочное разбиение возвращает временную локальность: каждый элемент B приезжает из памяти n / bsize раз вместо n. Блок обязан помещаться в кэш вместе с полосками A и C, размер это comptime-параметр, границы обрезаются по n.
Транспонирование на кэше cachelab: наивная версия платит промах за каждую запись в B; блок 8 на 32 на 32 даёт 340; на диагонали строка A и столбец B делят набор, и чтение строки в регистры доводит до 284. На 64 на 64 четыре строки заполняют кэш, блок 8 не помогает вовсе, и нужен обход четвертями 4 на 4 с временным хранилищем в B.
Раскладка данных это второй рычаг после порядка обхода. На задачах про водоросли обход по строкам даёт 128 холодных промахов из 512 чтений, обход по столбцам и два прохода по массиву структур по 256, а структура массивов возвращает 128 даже при двух проходах. В Zig это std.MultiArrayList.
Ложное разделение: два потока, два независимых счётчика в одной линии, и линия мечется между ядрами. align(64) у горячих полей разводит их по разным линиям, на M4 Max это в четыре с половиной раза.
Шаг zl: обход списка это цепочка зависимых загрузок, и цена ячейки решается её соседями. На M4 Max на 64 МБ список подряд стоит 2.6 такта на ячейку, через линию 30, вперемешку 258; куча, которая выдаёт ячейки в порядке выделения, держит соседей по списку соседями в памяти. Интерпретатор прячет промах за своей работой, JIT уже нет. cdr-coding превращает список подряд в массив с пометками.

Дальше

Весь урок мы считали, что знаем про кэш две вещи: его размер и длину линии. На симуляторе мы их задавали сами, а на настоящем M4 Max просто верили sysctl. В следующем уроке ты напишешь программу, которая ничего не спрашивает у системы, а снимает пропускную способность чтения по размеру рабочего множества и по шагу, и по обрывам на получившейся горе прочитаешь размеры L1, L2 и L3 своей машины, увидишь предвыборку своими глазами и сравнишь профиль x86-64 с Apple Silicon.

домашка

Домашка

Напиши транспонирование матрицы N на N, которое на твоей машине быстрее наивного не меньше чем вдвое при N = 4096, и покажи таблицу времени по размерам блока.L
Перепиши преобразование ориентированного графа в неориентированный (матрица смежности, G[i][j] = G[i][j] или G[j][i]) так, чтобы оба элемента пары читались из одной линии кэша, и сравни время с наивным циклом.L
Возьми любую свою структуру с пятью и больше полями, положи тысячу штук в обычный массив и в std.MultiArrayList, и замерь обход по одному полю там и там.S