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

Инварианты цикла, вызовы и обращения к памяти

senior~120 мин

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

Инварианты цикла, вызовы и обращения к памяти

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

Цели урока

Увидеть на живой программе, во что обходится инвариант цикла, пересчитанный на каждой итерации: квадратичное время там, где ожидалось линейное.
Объяснить, почему компилятор не выносит вызов из условия цикла сам: вызов с невидимым телом это чёрный ящик с возможным побочным эффектом.
Пройти путь от combine2 к combine3, заменив процедуру доступа с проверкой границ на прямой индекс, и понять, что даёт этот шаг на нашем железе.
Прочитать ассемблер combine3 и combine4 и найти в нём единственную инструкцию, которая различает версии.
Показать программой, что combine3 и combine4 дают разные ответы, когда указатель результата смотрит внутрь вектора, и увидеть в этом причину, по которой компилятор обязан оставить запись в памяти.
Проверить, что noalias из прошлого урока снимает запрет, и компилятор сам превращает combine3 в combine4.
Сравнить многочлен в лоб и по Горнеру: меньше операций, но длиннее цепочка зависимостей, и на измерениях видно, что побеждает цепочка.
Снять CPE четырёх исполнителей zl на fib и обходе списка и найти в интерпретаторе те же три неэффективности, что в combine1.

Инвариант цикла, который считают заново

Начнём не со свёртки, а с более грубой ошибки, которую видно невооружённым глазом. Функция переводит строку в нижний регистр и на каждой итерации спрашивает у строки длину. Длина за время цикла не меняется, это инвариант цикла, но программа честно пересчитывает его каждый раз. В книге эта функция называется lower1, а длину она узнаёт через strlen, которая идёт по строке до нулевого байта. В Zig срез знает свою длину, поэтому, чтобы воспроизвести ситуацию, придётся работать со строкой с нулём на конце и написать length руками.

const std = @import("std");

/// Длина строки с нулём на конце. `noinline`, как библиотечная функция
/// в другой единице трансляции: компилятор не видит, что она чистая.
noinline fn length(s: [*:0]const u8) usize {
    var n: usize = 0;
    while (s[n] != 0) : (n += 1) {}
    return n;
}

/// Версия 1: длина спрашивается в условии на каждой итерации.
fn lower1(s: [*:0]u8) void {
    var i: usize = 0;
    while (i < length(s)) : (i += 1) {
        if (s[i] >= 'A' and s[i] <= 'Z') s[i] += 'a' - 'A';
    }
}

/// Версия 2: длина взята один раз до цикла.
fn lower2(s: [*:0]u8) void {
    const n = length(s);
    var i: usize = 0;
    while (i < n) : (i += 1) {
        if (s[i] >= 'A' and s[i] <= 'Z') s[i] += 'a' - 'A';
    }
}

fn millis(io: std.Io, s: [*:0]u8, comptime lower: fn ([*:0]u8) void) f64 {
    const started = std.Io.Timestamp.now(io, .awake);
    lower(s);
    const ns = started.durationTo(std.Io.Timestamp.now(io, .awake)).nanoseconds;
    return @as(f64, @floatFromInt(ns)) / 1e6;
}

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

    try out.print("{s:>8} {s:>12} {s:>12}\n", .{ "n", "lower1, мс", "lower2, мс" });
    var n: usize = 8192;
    while (n <= 131072) : (n *= 2) {
        const s = try allocator.allocSentinel(u8, n, 0);
        @memset(s, 'Q');
        const t1 = millis(init.io, s.ptr, lower1);
        @memset(s, 'Q');
        const t2 = millis(init.io, s.ptr, lower2);
        try out.print("{d:>8} {d:>12.2} {d:>12.3}\n", .{ n, t1, t2 });
    }
    try out.flush();
}

Собери с оптимизацией и запусти. Числа сняты на Apple M4 Max, Zig 0.16.0, ReleaseFast.

$ zig build-exe lower.zig -O ReleaseFast && ./lower
       n lower1, мс lower2, мс
    8192         7.14        0.004
   16384        28.98        0.007
   32768        89.24        0.017
   65536       264.54        0.033
  131072       988.81        0.066

Читай таблицу по столбцам. У lower2 время удваивается вместе с n: это линейный рост, как и должно быть у прохода по строке. У lower1 время растёт примерно вчетверо на каждое удвоение, то есть квадратично: на каждой из n итераций length проходит по всем n байтам. На 128 тысячах символов разница уже в пятнадцать тысяч раз, и на мегабайте lower1 будет работать минуту. Книга приводит эту функцию как случай из практики: программа тратила часы на файл, с которым должна была справляться за секунды, и виновата была ровно одна строка в условии цикла.

Теперь главный вопрос урока: почему компилятор не вынес length(s) из условия сам? Он умеет выносить инварианты, это одна из базовых оптимизаций. Но для этого ему нужно доказать, что выражение действительно инвариант. Вызов length он видит только как вызов: тело помечено noinline, а в книге лежит в другой единице трансляции, и с точки зрения оптимизатора это чёрный ящик, который мог изменить строку, глобальную переменную, что угодно. Ещё хуже, компилятор видит, что цикл сам пишет в s[i], и по одному этому обязан допустить, что длина строки после записи изменилась. Логически мы понимаем, что замена заглавной буквы на строчную нулевой байт не породит. Компилятор такого рассуждения не ведёт: он проверяет, есть ли в цикле запись в память, которую читает length, и находит её. Приём номер один, вынести инвариант в переменную до цикла, остаётся за программистом.

От процедуры доступа к прямому индексу

Возвращаемся к свёртке. Напомню все версии одним файлом, чтобы дальше по уроку не листать назад. Здесь тот же Vec, что и в прошлом уроке, с noinline на len и get: без этой пометки LLVM встроил бы обе процедуры и сам сделал бы из combine1 что-то вроде combine3, и мерить было бы нечего.

//! Свёртка вектора: четыре версии, от абстрактной процедуры до
//! аккумулятора в регистре. Все обобщены по типу элемента `T`
//! (`i64` или `f64`) и по операции `op`.

const std = @import("std");

pub const Op = enum { add, mul };

/// Нейтральный элемент операции: 0 для сложения, 1 для умножения.
pub fn ident(comptime T: type, comptime op: Op) T {
    return switch (op) {
        .add => 0,
        .mul => 1,
    };
}

/// Сама операция. Для целых с заворачиванием, как в книге, где
/// переполнение `long` просто отбрасывает старшие биты.
pub inline fn apply(comptime T: type, comptime op: Op, a: T, b: T) T {
    return switch (@typeInfo(T)) {
        .int => switch (op) {
            .add => a +% b,
            .mul => a *% b,
        },
        else => switch (op) {
            .add => a + b,
            .mul => a * b,
        },
    };
}

/// Вектор из книги: данные плюс абстрактный интерфейс к ним.
/// `len` и `get` помечены `noinline`: в книге они лежат в другой единице
/// трансляции, и компилятор не видит их тел. В Zig всё собирается
/// вместе, поэтому границу приходится проводить явно.
pub fn Vec(comptime T: type) type {
    return struct {
        const Self = @This();

        data: []T,

        pub fn init(data: []T) Self {
            return .{ .data = data };
        }

        pub noinline fn len(self: *const Self) usize {
            return self.data.len;
        }

        /// Элемент с проверкой границ: `false`, если индекс вне вектора.
        pub noinline fn get(self: *const Self, index: usize, dest: *T) bool {
            if (index >= self.data.len) return false;
            dest.* = self.data[index];
            return true;
        }
    };
}

/// Версия 1: длина на каждом шаге, элемент через `get`, результат в `dest.*`.
pub fn combine1(comptime T: type, comptime op: Op, v: *const Vec(T), dest: *T) void {
    dest.* = ident(T, op);
    var i: usize = 0;
    while (i < v.len()) : (i += 1) {
        var value: T = undefined;
        _ = v.get(i, &value);
        dest.* = apply(T, op, dest.*, value);
    }
}

/// Версия 2: длина вынесена из условия цикла.
pub fn combine2(comptime T: type, comptime op: Op, v: *const Vec(T), dest: *T) void {
    const length = v.len();
    dest.* = ident(T, op);
    var i: usize = 0;
    while (i < length) : (i += 1) {
        var value: T = undefined;
        _ = v.get(i, &value);
        dest.* = apply(T, op, dest.*, value);
    }
}

/// Версия 3: прямой доступ к данным вместо `get`.
pub fn combine3(comptime T: type, comptime op: Op, v: *const Vec(T), dest: *T) void {
    const length = v.len();
    const data = v.data;
    dest.* = ident(T, op);
    var i: usize = 0;
    while (i < length) : (i += 1) {
        dest.* = apply(T, op, dest.*, data[i]);
    }
}

/// Версия 4: аккумулятор в локальной переменной, то есть в регистре.
/// Компилятор сам так не сделает: `dest` может указывать внутрь `data`,
/// и тогда каждая запись в `dest.*` меняла бы будущие элементы.
pub fn combine4(comptime T: type, comptime op: Op, v: *const Vec(T), dest: *T) void {
    const length = v.len();
    const data = v.data;
    var acc = ident(T, op);
    var i: usize = 0;
    while (i < length) : (i += 1) {
        acc = apply(T, op, acc, data[i]);
    }
    dest.* = acc;
}

test "combine4 считает то же, что combine3, на целых и дробных" {
    var ints = [_]i64{ 3, 5, 7, 11, 13 };
    const vi = Vec(i64).init(&ints);
    var a: i64 = undefined;
    var b: i64 = undefined;
    combine3(i64, .mul, &vi, &a);
    combine4(i64, .mul, &vi, &b);
    try std.testing.expectEqual(@as(i64, 15015), a);
    try std.testing.expectEqual(a, b);

    var floats = [_]f64{ 0.5, 1.5, 2.5 };
    const vf = Vec(f64).init(&floats);
    var c: f64 = undefined;
    var d: f64 = undefined;
    combine3(f64, .add, &vf, &c);
    combine4(f64, .add, &vf, &d);
    try std.testing.expectEqual(@as(f64, 4.5), c);
    try std.testing.expectEqual(c, d);
}

test "пустой вектор даёт нейтральный элемент" {
    var empty = [_]i64{};
    const v = Vec(i64).init(&empty);
    var sum: i64 = undefined;
    var product: i64 = undefined;
    combine4(i64, .add, &v, &sum);
    combine4(i64, .mul, &v, &product);
    try std.testing.expectEqual(@as(i64, 0), sum);
    try std.testing.expectEqual(@as(i64, 1), product);
}

test "при наложении dest на вектор версии расходятся" {
    var data3 = [_]i64{ 2, 3, 5 };
    var data4 = [_]i64{ 2, 3, 5 };
    const v3 = Vec(i64).init(&data3);
    const v4 = Vec(i64).init(&data4);
    combine3(i64, .add, &v3, &data3[1]);
    combine4(i64, .add, &v4, &data4[1]);
    try std.testing.expectEqual(@as(i64, 9), data3[1]);
    try std.testing.expectEqual(@as(i64, 10), data4[1]);
}

$ zig test combine.zig
1/3 combine.test.combine4 считает то же, что combine3, на целых и дробных...OK
2/3 combine.test.пустой вектор даёт нейтральный элемент...OK
3/3 combine.test.при наложении dest на вектор версии расходятся...OK
All 3 tests passed.

Третий тест выглядит странно: две версии одной функции дают разные числа, и тест это одобряет. К нему мы вернёмся, он и есть сердце урока. Пока смотрим на шаг от combine2 к combine3.

combine2 уже вынесла длину из условия, но каждый элемент по-прежнему достаётся вызовом get. Что делает get: сравнивает индекс с длиной, читает элемент, пишет его по указателю, возвращает флаг. Это вызов процедуры, а значит: аргументы в регистры, call, пролог, сравнение, чтение, запись, ret, и всё это ради одного ldr. Проверка границ здесь бессмысленна: цикл сам идёт от нуля до length, индекс за границу не выйдет никогда, но get этого не знает и проверяет каждый раз. combine3 заменяет вызов на data[i]: берёт срез один раз до цикла и читает элементы напрямую. С точки зрения книги это нарушение абстракции: клиент вектора лезет в его внутренности. С точки зрения производительности это единственный способ убрать вызов, тело которого компилятор не видит.

В Zig у этого шага есть своя оговорка. Индексация среза data[i] в Debug и ReleaseSafe тоже проверяет границы. Но эта проверка сделана компилятором, а не библиотекой, и в цикле с известной границей он видит, что i < data.len выполнено по условию цикла, и убирает её. В ReleaseFast проверок нет вовсе. То есть прямой индекс не обязан быть небезопасным: он позволяет компилятору доказать безопасность там, где get заставлял проверять вслепую.

Смотрим, что дал этот шаг на нашей машине. Числа из прошлого урока, Apple M4 Max, Zig 0.16.0, ReleaseFast:

версия	i64 плюс	i64 умножить	f64 плюс	f64 умножить	приём
combine1	4.09	4.04	4.20	3.99	абстрактная процедура
combine2	4.05	4.04	4.16	4.20	длина вынесена из условия
combine3	1.04	3.01	2.50	3.41	прямой доступ к данным
combine4	1.06	2.99	2.46	3.40	аккумулятор в регистре
граница задержки	1.00	2.99	2.49	3.42

Два наблюдения. Первое: combine1 и combine2 почти не различаются, около четырёх тактов на элемент в любой колонке. Их время уходит на вызовы len и get, а не на арифметику, поэтому CPE не зависит от того, складываем мы или умножаем. Вынос len из условия сэкономил один вызов на итерацию из двух, а CPE почти не сдвинулся: вызовы независимы друг от друга и от аккумулятора, процессор исполняет их параллельно с арифметикой, и пока в цикле остаётся хоть один call, именно он задаёт темп. Второе: combine3 сразу падает на границу задержки во всех четырёх колонках. Целое сложение идёт по одному такту, умножение по три, дробные по своим задержкам. Убрали последний вызов, и цикл стал стоить ровно столько, сколько стоит цепочка операций.

Здесь наша таблица расходится с книгой, и это расхождение стоит разобрать честно. У авторов книги, на Core i7 Haswell и с компилятором GCC 2015 года, combine3 почти не отличалась от combine2: 7.17 против 7.02 тактов на целое сложение, и только combine4 опускалась до 1.27. У нас combine3 уже на границе, а combine4 ничего не добавляет. Чтобы понять, почему, нужен ассемблер.

Аккумулятор в регистре: что видно в ассемблере

combine3 копит результат в dest.*: на каждой итерации читает значение из памяти, применяет операцию и пишет обратно. combine4 копит в локальной переменной acc и пишет в память один раз после цикла. Книга объясняет разницу так: у combine3 каждая итерация делает чтение и запись по одному адресу, и следующее чтение обязано дождаться предыдущей записи. На процессоре книги это обходилось в несколько тактов: продвижение из буфера записи добавляло в цепочку аккумулятора четыре с лишним такта на каждый элемент.

Проверим, что делает наш компилятор. Возьмём умножение дробных, как в книге, и соберём обе версии в ассемблер для x86-64. Функции объявлены export, иначе LLVM встроит их и на выходе не окажется ничего. Указатели здесь простые, без Vec, чтобы листинг был короче: data это начало массива, len его длина.

export fn combine3_mul(data: [*]const f64, len: usize, dest: *f64) void {
    dest.* = 1;
    var i: usize = 0;
    while (i < len) : (i += 1) {
        dest.* = dest.* * data[i];
    }
}

export fn combine4_mul(data: [*]const f64, len: usize, dest: *f64) void {
    var acc: f64 = 1;
    var i: usize = 0;
    while (i < len) : (i += 1) {
        acc = acc * data[i];
    }
    dest.* = acc;
}

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

LLVM развернул оба цикла (в combine3_mul по четыре элемента за итерацию, в combine4_mul по восемь) и добавил хвостовой цикл по одному элементу для остатка. Развёртка это тема урока про параллелизм, поэтому смотрим на хвостовые циклы: они делают то же, что и основные, но по одному элементу, и различие между версиями в них видно лучше всего. Синтаксис Intel, как его печатает Zig: приёмник слева.

; combine3_mul, хвостовой цикл. data в rcx, счётчик в rsi, dest в rdx.
.LBB3_7:
        mulsd   xmm0, qword ptr [rcx + 8*rsi]   ; acc = acc * data[i]
        movsd   qword ptr [rdx], xmm0           ; dest.* = acc, каждую итерацию
        add     rsi, 1
        cmp     rax, rsi
        jne     .LBB3_7

; combine4_mul, хвостовой цикл. Те же регистры.
.LBB2_8:
        mulsd   xmm0, qword ptr [rcx + 8*rsi]   ; acc = acc * data[i]
        add     rsi, 1
        cmp     rax, rsi
        jne     .LBB2_8
        movsd   qword ptr [rdx], xmm0           ; dest.* = acc, один раз после цикла

Вот и ответ на расхождение с книгой. В обеих версиях аккумулятор живёт в xmm0. В combine3 нет чтения dest.* из памяти: компилятор помнит, что последним по этому адресу записал xmm0, а между записью и следующим чтением никто в память не писал, значит читать обратно незачем. Это законно, и LLVM это делает. GCC 2015 года этого не делал, и в его цикле стояли три инструкции: прочитать dest.*, умножить, записать. Оттуда и семь тактов в книге.

А вот запись movsd [rdx], xmm0 в combine3 осталась, на каждой итерации. Её компилятор убрать не смог. Разница между версиями свелась к одной инструкции, и на нашей таблице она не видна: запись не входит в цепочку зависимостей аккумулятора, буфер записи принимает её и не задерживает следующее умножение. Цикл combine3 тратит порт записи, но при одном аккумуляторе темп задаёт задержка операции, а не порт. Эта лишняя запись начнёт стоить позже, когда в уроке про параллелизм мы опустим CPE ниже единицы: порт записи на многих ядрах один, и цикл, который пишет на каждом элементе, ниже одного такта на элемент не опустится никогда.

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

; combine3_add, aarch64. data в x0, счётчик в x1, dest в x2, аккумулятор в x8.
LBB1_2:
        ldr     x9, [x0], #8        ; x9 = data[i], указатель сдвинуть на 8
        add     x8, x9, x8          ; acc += x9
        str     x8, [x2]            ; dest.* = acc, каждую итерацию
        subs    x1, x1, #1
        b.ne    LBB1_2

; combine4_add, aarch64.
LBB0_2:
        ldr     x9, [x0], #8
        add     x8, x9, x8
        subs    x1, x1, #1
        b.ne    LBB0_2
        str     x8, [x2]            ; один раз после цикла

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

Почему компилятор не сделает этого сам

Потому что запись меняет память, а компилятор не знает, чью. Указатель dest пришёл в функцию снаружи, и ничто не запрещает ему указывать на один из элементов data. Это наложение указателей, aliasing, тема прошлого урока. Если dest указывает на data[1], то запись dest.* = acc на нулевой итерации меняет data[1], и на первой итерации цикл прочитает уже не исходное значение, а результат записи. Программа, в которой запись делается на каждой итерации, и программа, в которой она делается один раз в конце, дают в этой ситуации разные ответы. Компилятор обязан сохранить поведение исходного кода при любых аргументах, включая такие, и потому обязан оставить запись там, где она написана.

Посмотрим на это глазами, а не рассуждением. Программа делает свёртку двумя способами, сначала с dest отдельно от вектора, потом с dest, который указывает на a[1].

const std = @import("std");

/// Свёртка через память: результат копится в `dest.*` на каждой итерации.
fn sumViaMemory(data: []i64, dest: *i64) void {
    dest.* = 0;
    for (0..data.len) |i| dest.* +%= data[i];
}

/// Свёртка через регистр: одна запись в `dest.*` в самом конце.
fn sumViaRegister(data: []i64, dest: *i64) void {
    var acc: i64 = 0;
    for (0..data.len) |i| acc +%= data[i];
    dest.* = acc;
}

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 a = [_]i64{ 2, 3, 5 };
    var separate: i64 = undefined;
    sumViaMemory(&a, &separate);
    try out.print("dest отдельно:          память {d}\n", .{separate});

    // dest указывает внутрь самого вектора, на a[1].
    a = .{ 2, 3, 5 };
    sumViaMemory(&a, &a[1]);
    try out.print("dest = &a[1]:           память {d}, вектор стал {any}\n", .{ a[1], a });

    a = .{ 2, 3, 5 };
    sumViaRegister(&a, &a[1]);
    try out.print("dest = &a[1]:           регистр {d}, вектор стал {any}\n", .{ a[1], a });
    try out.flush();
}

$ zig run alias.zig
dest отдельно:          память 10
dest = &a[1]:           память 9, вектор стал { 2, 9, 5 }
dest = &a[1]:           регистр 10, вектор стал { 2, 10, 5 }

Проследи за версией через память при dest = &a[1] по шагам.

Первое же действие dest.* = 0 затирает a[1]: вектор стал { 2, 0, 5 }.
Нулевая итерация прибавляет a[0]: a[1] становится двойкой.
Первая итерация прибавляет a[1], то есть саму себя: четыре.
Вторая прибавляет a[2]: девять.

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

Прошлый урок закончился словом noalias: обещанием компилятору, что указатель не пересекается ни с чем, к чему функция обращается через другие указатели. Проверим, снимает ли обещание запрет. Одно слово в сигнатуре, всё остальное как в combine3_mul:

export fn combine3_noalias(data: [*]const f64, len: usize, noalias dest: *f64) void {
    dest.* = 1;
    var i: usize = 0;
    while (i < len) : (i += 1) {
        dest.* = dest.* * data[i];
    }
}

; combine3_noalias, хвостовой цикл: записи в теле нет
.LBB0_7:
        mulsd   xmm0, qword ptr [rcx + 8*rsi]
        add     rsi, 1
        cmp     rax, rsi
        jne     .LBB0_7
        movsd   qword ptr [rdx], xmm0           ; единственная запись, после цикла

С noalias LLVM сам сделал из combine3 ровно combine4: запись уехала за цикл, тело стало тем же, что у версии с локальной переменной. Компилятор умел это с самого начала, ему не хватало только права. Обещание при этом ничем не проверяется: передай &a[1] в функцию с noalias dest, и получишь десять вместо девяти, то есть не то, что написано в исходнике. Ответственность за истинность обещания целиком на тебе, и это та же сделка, что с restrict в C. Разница между noalias dest и локальной acc в том, что локальную переменную нельзя нарушить снаружи: она не имеет адреса, пока ты его не взял, и никто чужой в неё не запишет. Поэтому книга и рекомендует локальный аккумулятор, а не обещания в сигнатуре.

Четыре версии на одной шкале

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

Пройди по колонкам. В колонке целого сложения combine3 и combine4 лежат на единице: сложение занимает один такт, и цикл с одним аккумулятором быстрее не будет. В колонке дробного умножения они лежат на 3.4: столько занимает fmul на этом ядре. В combine1 и combine2 разницы между колонками нет, четыре такта с небольшим везде: их темп задают вызовы, а не арифметика. Заметь, как далеко от полосок стоит вторая граница, пропускной способности: 0.16 такта на целое сложение, то есть шесть сложений за такт. Ядро могло бы складывать в шесть раз быстрее, если бы сложения не выстраивались в цепочку, где каждое ждёт предыдущего. До этой границы мы будем идти два следующих урока, а пока запомни картину: три приёма урока сняли всё, что не было арифметикой, и цикл упёрся в задержку.

Многочлен: меньше операций не значит быстрее

Последняя тема урока про ту же цепочку зависимостей, но с неожиданной стороны. Считаем многочлен с коэффициентами a[0], a[1] и далее в точке x. Первый способ в лоб: держим текущую степень xpwr, на каждом шаге прибавляем a[i] * xpwr к результату и домножаем степень на x. Второй способ это схема Горнера: идём от старшего коэффициента и на каждом шаге считаем a[i] + x * result.

//! Многочлен a[0] + a[1] x + a[2] x² + ... двумя способами.

const std = @import("std");

/// В лоб: `result += a[i] * xpwr`, `xpwr *= x`. Два умножения и одно
/// сложение на коэффициент, но в двух независимых цепочках.
pub fn poly(a: []const f64, x: f64) f64 {
    var result: f64 = 0;
    var xpwr: f64 = 1;
    for (a) |coefficient| {
        result += coefficient * xpwr;
        xpwr *= x;
    }
    return result;
}

/// По Горнеру: `result = a[i] + x * result` от старшего коэффициента.
/// Одно умножение и одно сложение на коэффициент, но в одной цепочке.
pub fn polyHorner(a: []const f64, x: f64) f64 {
    var result: f64 = 0;
    var i: usize = a.len;
    while (i > 0) {
        i -= 1;
        result = a[i] + x * result;
    }
    return result;
}

test "оба способа считают один многочлен" {
    const a = [_]f64{ 1, -2, 0.5, 3, -1 };
    const x: f64 = 1.25;
    try std.testing.expectApproxEqRel(poly(&a, x), polyHorner(&a, x), 1e-12);
    // 1 + 2 * 2 + 3 * 4 = 17
    try std.testing.expectEqual(@as(f64, 17), poly(&[_]f64{ 1, 2, 3 }, 2));
    try std.testing.expectEqual(@as(f64, 17), polyHorner(&[_]f64{ 1, 2, 3 }, 2));
}

test "пустой набор и один коэффициент" {
    try std.testing.expectEqual(@as(f64, 0), poly(&[_]f64{}, 7));
    try std.testing.expectEqual(@as(f64, 0), polyHorner(&[_]f64{}, 7));
    try std.testing.expectEqual(@as(f64, 4.5), poly(&[_]f64{4.5}, 7));
    try std.testing.expectEqual(@as(f64, 4.5), polyHorner(&[_]f64{4.5}, 7));
}

$ zig test poly.zig
1/2 poly.test.оба способа считают один многочлен...OK
2/2 poly.test.пустой набор и один коэффициент...OK
All 2 tests passed.

Посчитаем операции на один коэффициент. В лоб: умножение coefficient * xpwr, сложение с result, умножение xpwr * x, итого два умножения и одно сложение. По Горнеру: умножение x * result и сложение с a[i], одно и одно. Горнер делает на треть меньше работы, и учебники по численным методам советуют его как правильный способ. Теперь измерим оба тем же измерителем, что и combine, на векторе коэффициентов из L1: CPE по прямой методом наименьших квадратов, x чуть больше единицы, чтобы степени не улетели в бесконечность.

$ zig build-exe poly_bench.zig -O ReleaseFast && ./poly_bench
poly       CPE 3.40 шум 0.05
polyHorner CPE 5.16 шум 0.02

Снято на том же Apple M4 Max тем же способом, что и таблица combine. Версия с меньшим числом операций медленнее в полтора раза. Разберём, почему, на двух задачках из книги. У авторов на Haswell результат тот же по смыслу: 5.0 такта на коэффициент в лоб против 8.0 по Горнеру.

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

Разбор. Одно сложение и два умножения, мы это уже посчитали. Но в цепочку зависимостей, то есть в последовательность операций, где каждая ждёт результата предыдущей, попадают не все три. Проследи, от чего зависит каждая. xpwr *= x на этой итерации зависит от xpwr с прошлой: это цепочка из умножений, по одному на коэффициент. result += coefficient * xpwr зависит от result с прошлой итерации через сложение: вторая цепочка, по одному сложению на коэффициент. А умножение coefficient * xpwr ни от какого результата этой цепочки не зависит: оно берёт xpwr из цепочки степеней и коэффициент из памяти, и его можно считать заранее, не дожидаясь result. Две цепочки идут параллельно, и цикл ограничен более медленной из них: цепочкой умножений xpwr. Пять тактов у авторов книги, 3.4 такта у нас, ровно граница задержки умножения из нашей таблицы. Второе умножение и сложение исполняются в тени первого.

Задачка, форма упражнения 5.6. Для схемы Горнера посчитай операции на коэффициент и объясни, почему на машине книги CPE равен восьми, при тех же задержках пять и три.

Разбор. Одно умножение и одно сложение, меньше, чем в лоб. Но посмотри на зависимость: result = a[i] + x * result. Умножение x * result ждёт result с прошлой итерации, сложение ждёт это умножение, а result следующей итерации это результат сложения. Обе операции сидят в одной цепочке, и на коэффициент цепочка удлиняется на задержку умножения плюс задержку сложения: пять плюс три, восемь тактов у авторов книги. У нас 3.42 плюс 2.49 дают около 5.9 по таблице границ, измерено 5.2: ядро M4 умеет запускать зависимое сложение чуть раньше, чем завершится умножение целиком, но форма ответа та же, цепочка из двух операций на коэффициент против одной. Горнер делает меньше операций, а критический путь у него длиннее, и решает путь.

Убедимся в ассемблере, что ни один компилятор нам не помог. Циклы на aarch64, где считалось:

; polyHorner: одна цепочка, fmul и fadd друг за другом в d1
LBB0_2:
        ldr     d2, [x8, x1, lsl #3]    ; d2 = a[i]
        fmul    d1, d0, d1              ; d1 = x * result
        fadd    d1, d1, d2              ; d1 = d1 + a[i], следующий result
        subs    x1, x1, #1
        b.ne    LBB0_2

; poly: две цепочки, result в d1, xpwr в d2
LBB1_2:
        ldr     d3, [x0], #8            ; d3 = coefficient
        fmul    d3, d2, d3              ; d3 = coefficient * xpwr, вне обеих цепочек
        fadd    d1, d1, d3              ; result += d3, цепочка сложений
        fmul    d2, d0, d2              ; xpwr *= x, цепочка умножений
        subs    x1, x1, #1
        b.ne    LBB1_2

В polyHorner регистр d1 проходит через fmul и fadd подряд, и следующий fmul ждёт этот fadd. В poly регистры d1 и d2 живут своей жизнью, каждый зависит только от себя, а d3 вычисляется между ними и не задерживает ни одну. LLVM развернул poly по четыре элемента на x86-64 и переупорядочил умножения между итерациями, но цепочки от этого не стали короче: их длина задана алгоритмом, а не компилятором. Про то, как читать такие цепочки систематически, через граф потока данных и критический путь, следующий урок. В домашних заданиях к уроку про профилирование ты сделаешь многочлен быстрее Горнера, разбив цепочку на две.

Шаг проекта: zl меряет своих исполнителей

У zl уже четыре способа исполнить одну программу: обход дерева из урока про eval, байткод под циклом со switch и под labeled switch из урока про переходы и таблицы и машинный код из урока про JIT. До сих пор мы знали только, что ответ у них один. Теперь снимем их цену тем же измерителем, что combine: CPE, такты на элемент, наклон прямой по наименьшим квадратам.

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

(fib k): вызовы и арифметика. Элемент это один вызов fib. Их число считается без запуска: calls(k) = 1 + calls(k - 1) + calls(k - 2), для k = 24 это 150 049 вызовов, для k = 25 уже 242 785.
(last xs): обход списка по указателям до последней ячейки. Элемент это одна cons-ячейка, длины от 125 тысяч до миллиона.

workload.zig: нагрузки и один вход для всех исполнителей

Исполнитель выбирается одним switch: обход дерева зовёт eval.eval, три остальных Machine.runForm с нужным диспетчером, а JIT включается на время одного вызова. Список строится прямо в куче, от хвоста к голове, поэтому соседи по списку лежат в памяти соседями: это пригодится в уроке про кэш-дружелюбный код.

//! Нагрузки для замеров исполнителей: одна и та же форма под обходом
//! дерева, под байткодом с каждым из диспетчеров и под JIT.
//!
//! Нагрузки две. `(fib k)` это вызовы и арифметика: элемент здесь один
//! вызов `fib`, их `2 * F(k + 1) - 1`. `(last xs)` это обход списка по
//! указателям: элемент одна cons-ячейка, функция доходит до последней.
//! Обе функции от одного аргумента, поэтому JIT берёт обе целиком.

const std = @import("std");

const bytecode = @import("bytecode.zig");
const errors = @import("errors.zig");
const eval = @import("eval.zig");
const reader = @import("reader.zig");
const value = @import("value.zig");
const Vm = @import("vm.zig").Vm;

const Value = value.Value;

pub const Executor = enum { tree, loop, labeled, jit };

pub const definitions =
    \\(define fib (lambda (n) (cond ((< n 2) n) (t (+ (fib (- n 1)) (fib (- n 2)))))))
    \\(define last (lambda (xs) (cond ((cdr xs) (last (cdr xs))) (t (car xs)))))
;

/// Сколько раз вызывается `fib`, пока считается `(fib k)`.
pub fn fibCalls(k: u32) u64 {
    // calls(k) = 1 + calls(k - 1) + calls(k - 2), calls(0) = calls(1) = 1.
    var a: u64 = 1;
    var b: u64 = 1;
    var i: u32 = 1;
    while (i < k) : (i += 1) {
        const next = 1 + a + b;
        a = b;
        b = next;
    }
    return b;
}

/// Список `(1 2 ... n)` в куче. Ячейки выделяются подряд, от хвоста к голове.
/// Недостроенный список лежит в локальной переменной, где его найдёт
/// консервативный скан стека, если посреди постройки случится сборка.
pub fn list(vm: *Vm, n: usize) errors.Error!Value {
    var head: Value = .nil;
    var i = n;
    while (i > 0) : (i -= 1) {
        head = try vm.heap.cons(.fromFixnum(@intCast(i)), head);
    }
    return head;
}

/// Прочитать одну форму, например `(fib 20)`.
pub fn form(vm: *Vm, source: []const u8) (errors.Error || reader.Error)!Value {
    return reader.readOne(vm, source);
}

/// Исполнить готовую форму выбранным исполнителем.
pub fn run(machine: *bytecode.Machine, f: Value, executor: Executor) errors.Error!Value {
    return switch (executor) {
        .tree => eval.eval(machine.vm, f, .nil),
        .loop => machine.runForm(f, .loop),
        .labeled => machine.runForm(f, .labeled),
        .jit => {
            machine.use_jit = true;
            defer machine.use_jit = false;
            return machine.runForm(f, .labeled);
        },
    };
}

bench/main.zig: замер

Измеритель берём из прошлого урока без единой правки: файл harness.zig ложится в bench/ рядом с бенчем. Нового в бенче три вещи, и все три появились не от хорошей жизни.

Свежая машина на каждую точку. Куча zl пока арена, и ничего не освобождает: обход дерева на (fib 24) выделяет по восемь ячеек на вызов, и серия из десятков прогонов съела бы гигабайты. Поэтому каждая точка прямой живёт на своей Vm и уходит вместе с ней. Цена точки от этого не меняется, а память возвращается.

Поток со стеком на два гигабайта. Обход дерева рекурсивен на стеке Zig: eval зовёт apply, та снова eval, и хвостовой вызов last для него такой же вызов, как любой другой. На миллионе ячеек это миллион вложенных кадров, стек потока по умолчанию кончается гораздо раньше, и процесс падает по SIGSEGV. Байткоду и JIT такой стек не нужен (у байткода кадры в своём массиве, у JIT хвостовой вызов это jmp), но проще отдать большой стек всему бенчу: память под него ядро выдаёт по мере касания.

Класс обслуживания. У M4 Max два вида ядер, и планировщик macOS вправе переселить поток на энергоэффективное посреди серии. Частота калибруется один раз, в начале, поэтому переезд испортил бы перевод в такты. pthread_set_qos_class_self_np с самым высоким классом просит держать поток на производительных ядрах. Это просьба, а не приказ, и шум в выводе показывает, насколько её выполнили.

//! Бенч исполнителей zl: CPE обхода дерева, байткода под двумя диспетчерами
//! и JIT на двух нагрузках.
//!
//!   zig build bench                    все исполнители, которые идут на этой машине
//!   zig build bench -- tree loop       только перечисленные
//!
//! Элемент нагрузки `fib` это один вызов `fib`, нагрузки `last` одна
//! cons-ячейка. CPE снимается измерителем из урока про CPE: минимум из серии
//! на каждом размере и прямая по наименьшим квадратам, наклон прямой это
//! такты на элемент. Частота ядра калибруется цепочкой сложений.

const std = @import("std");
const builtin = @import("builtin");

const zl = @import("zl");
const harness = @import("harness.zig");

const workload = zl.workload;
const Executor = workload.Executor;
const Value = zl.Value;
const Vm = zl.Vm;

/// Размеры `fib`: от 1 973 вызовов до 150 049.
const fib_ks = [_]u32{ 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
/// Длины обхода, до миллиона ячеек.
const list_lengths = [_]usize{ 125_000, 250_000, 500_000, 750_000, 1_000_000 };

/// Обход дерева рекурсивен на стеке Zig даже там, где вызов хвостовой: на
/// миллионе ячеек ему нужны сотни мегабайт стека. Поэтому весь бенч идёт
/// в потоке с большим стеком, память которого берётся по мере касания.
const big_stack = 2 << 30;

/// Класс обслуживания потока на macOS. Самый высокий просит планировщик
/// держать поток на производительных ядрах: иначе серия может переехать на
/// энергоэффективное ядро посреди замера, а частота калибруется один раз.
const qos_class_user_interactive = 0x21;
extern "c" fn pthread_set_qos_class_self_np(qos: c_uint, priority: c_int) c_int;

/// Одна форма под одним исполнителем.
const Bench = struct {
    machine: *zl.bytecode.Machine,
    executor: Executor,
    form: Value,

    pub fn run(self: *Bench, n: usize) void {
        _ = n;
        const result = workload.run(self.machine, self.form, self.executor) catch |err|
            std.debug.panic("{t}: {t}", .{ self.executor, err });
        std.mem.doNotOptimizeAway(result);
    }
};

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 chosen: [4]Executor = undefined;
    var count: usize = 0;
    for (args[1..]) |arg| {
        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;
        }
    }

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

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

fn measureAll(io: std.Io, out: *std.Io.Writer, chosen: []const Executor) !void {
    const clock: harness.Clock = .init(io);
    try out.print("частота ядра по калибровке: {d:.2} ГГц\n", .{clock.ghz});
    try out.writeAll("исполнитель  fib, тактов на вызов  last, тактов на ячейку\n");
    try out.flush();

    for (chosen) |executor| {
        var fib_points: [fib_ks.len]harness.Point = undefined;
        for (fib_ks, &fib_points) |k, *p| p.* = try fibPoint(clock, executor, k);
        var list_points: [list_lengths.len]harness.Point = undefined;
        for (list_lengths, &list_points) |n, *p| p.* = try lastPoint(clock, executor, n);
        try out.print("{t:<12} {d:>9.1} (шум {d:.2})  {d:>9.1} (шум {d:.2})\n", .{
            executor,
            harness.fitPoints(&fib_points).cpe,
            worstNoise(&fib_points),
            harness.fitPoints(&list_points).cpe,
            worstNoise(&list_points),
        });
        try out.flush();
    }
}

fn worstNoise(points: []const harness.Point) f64 {
    var worst: f64 = 0;
    for (points) |p| worst = @max(worst, p.noise);
    return worst;
}

// Каждая точка на свежей машине: все ячейки, выделенные за замер, уходят
// вместе с ней, и следующая точка начинает с пустой кучи.

fn fibPoint(clock: harness.Clock, executor: Executor, k: u32) !harness.Point {
    const gpa = std.heap.smp_allocator;
    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);

    var text_buf: [32]u8 = undefined;
    var b: Bench = .{
        .machine = &machine,
        .executor = executor,
        .form = try workload.form(&vm, try std.fmt.bufPrint(&text_buf, "(fib {d})", .{k})),
    };
    const n: usize = @intCast(workload.fibCalls(k));
    return harness.measure(clock, &b, &.{n}, .{ .work = 300_000, .runs = 5 }).items()[0];
}

fn lastPoint(clock: harness.Clock, executor: Executor, n: usize) !harness.Point {
    const gpa = std.heap.smp_allocator;
    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 workload.list(&vm, n));

    var b: Bench = .{ .machine = &machine, .executor = executor, .form = try workload.form(&vm, "(last xs)") };
    return harness.measure(clock, &b, &.{n}, .{ .work = n, .runs = 5 }).items()[0];
}

Bench.run это контекст для harness.measure: одна форма под одним исполнителем, ошибка превращается в панику, потому что в замере её быть не должно. fibPoint и lastPoint снимают по одной точке, а measureAll проводит прямые через десять точек fib и пять точек last и печатает наклоны.

build.zig и тесты

Бенч собирается всегда в ReleaseFast, какой бы ни была оптимизация остальной сборки, поэтому модуль zl для него собран отдельно. Вшитые программы подключаются к обоим модулям одной функцией:

    // Бенч исполнителей всегда собирается с оптимизацией, каким бы ни был
    // -Doptimize: мерить Debug значит мерить проверки безопасности.
    const zl_fast = b.createModule(.{
        .root_source_file = b.path("src/root.zig"),
        .target = target,
        .optimize = .ReleaseFast,
    });
    addPrograms(b, zl_fast);
    const bench = b.addExecutable(.{
        .name = "bench",
        .root_module = b.createModule(.{
            .root_source_file = b.path("bench/main.zig"),
            .target = target,
            .optimize = .ReleaseFast,
            .imports = &.{.{ .name = "zl", .module = zl_fast }},
        }),
    });
    b.installArtifact(bench);
    const bench_cmd = b.addRunArtifact(bench);
    // Бенч зовут ради свежих чисел, кэшировать его нельзя.
    bench_cmd.has_side_effects = true;
    if (b.args) |args| bench_cmd.addArgs(args);
    const bench_step = b.step("bench", "Снять CPE исполнителей: zig build bench -- tree loop");
    bench_step.dependOn(&bench_cmd.step);

/// Файл программы попадает в модуль под своим именем, и `@embedFile("fib.zl")`
/// находит его, хотя каталог `programs/` лежит за границей модуля.
fn addPrograms(b: *std.Build, zl: *std.Build.Module) void {
    for (zl_programs) |name| {
        zl.addAnonymousImport(name, .{ .root_source_file = b.path(b.fmt("programs/{s}", .{name})) });
    }
}

В src/root.zig добавляется строка pub const workload = @import("workload.zig");, в steps шаг "32". Замер тестом не бывает, его числа зависят от машины, а вот то, на чём он стоит, проверить можно: счёт вызовов fib, одинаковый ответ у всех исполнителей на обеих нагрузках и то, что список действительно лежит в памяти подряд.

//! Шаг 32: нагрузки для замера исполнителей.
//!
//! Сам замер живёт в `bench/` и тестом не бывает: его числа зависят от
//! машины. Тесты проверяют то, на чём замер стоит: счёт элементов верен,
//! и каждая нагрузка даёт один ответ у всех исполнителей.

const std = @import("std");

const zl = @import("zl");

const bytecode = zl.bytecode;
const workload = zl.workload;
const Vm = zl.Vm;

const testing = std.testing;

/// Вызовы `fib`, посчитанные прямой рекурсией.
fn countCalls(k: u32) u64 {
    return if (k < 2) 1 else 1 + countCalls(k - 1) + countCalls(k - 2);
}

test "число вызовов fib считается без рекурсии" {
    for (0..25) |k| try testing.expectEqual(countCalls(@intCast(k)), workload.fibCalls(@intCast(k)));
    // (fib 25) это четверть миллиона вызовов.
    try testing.expectEqual(@as(u64, 242_785), workload.fibCalls(25));
}

fn executors() []const workload.Executor {
    return if (zl.jit.canRun()) &.{ .tree, .loop, .labeled, .jit } else &.{ .tree, .loop, .labeled };
}

test "(fib 15) у каждого исполнителя один" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    var m: bytecode.Machine = .init(&vm);
    defer m.deinit();
    _ = try zl.eval.evalSource(&vm, workload.definitions);

    for (executors()) |executor| {
        const form = try workload.form(&vm, "(fib 15)");
        const result = try workload.run(&m, form, executor);
        try testing.expectEqual(@as(i64, 610), result.asFixnum());
    }
}

test "last проходит список до конца у каждого исполнителя" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    var m: bytecode.Machine = .init(&vm);
    defer m.deinit();
    _ = try zl.eval.evalSource(&vm, workload.definitions);
    try vm.defineNamed("xs", try workload.list(&vm, 5000));

    for (executors()) |executor| {
        const form = try workload.form(&vm, "(last xs)");
        const result = try workload.run(&m, form, executor);
        try testing.expectEqual(@as(i64, 5000), result.asFixnum());
    }
}

test "соседи по списку соседи и в памяти" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    const xs = try workload.list(&vm, 50_000);

    // Ячейки выделялись одна за другой, от хвоста к голове, поэтому
    // следующая по списку ячейка лежит на 16 байт раньше текущей.
    const first = @intFromPtr(xs.asCell());
    const second = @intFromPtr(xs.asCell().cdr.asCell());
    try testing.expectEqual(@as(usize, 16), first - second);
    try testing.expectEqual(@as(?usize, 50_000), zl.value.listLen(xs));
}

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

$ zig build bench
частота ядра по калибровке: 4.02 ГГц
исполнитель  fib, тактов на вызов  last, тактов на ячейку
tree             348.0 (шум 0.04)      267.1 (шум 0.01)
loop             311.6 (шум 0.02)      149.5 (шум 0.02)
labeled          290.7 (шум 0.03)      149.1 (шум 0.03)

Снято на Apple M4 Max. Машина в это время не простаивала, и соседний прогон дал числа на 7 до 10 процентов выше; порядок строк в обоих прогонах один. JIT на этом процессоре не исполняется, и его строки здесь нет.

Первое, что бросается в глаза: байткод почти не обогнал обход дерева на fib, 291 такт против 348. Компиляция в байткод убрала разбор вида узла, но вызов fib стоит сотни тактов не из-за разбора. Разложим один внутренний вызов по листингу байткода, как раскладывали combine1:

Вызов на каждый элемент. 23 команды, из них четыре вызова примитивов (<, два - и +), и каждый идёт через адрес из таблицы natives, вход с соглашением C, разбор списка аргументов и takeFailure на обратном пути.
Проверка вида на каждом доступе. Примитив не знает, что ему пришли числа: takeTwo проверяет, что аргументов ровно два, asNumber проверяет тег каждого. Это та же проверка границ, что у get в combine1, только на типах.
Аккумулятор в памяти. Аргументы примитиву собираются в список из новых ячеек кучи: две ячейки на вызов, восемь на внутренний вызов fib, пять в среднем по всем вызовам (листовых вызовов почти половина, и у них один примитив). Промежуточные значения живут на стеке значений, то есть в std.ArrayList, и каждая команда push это проверка ёмкости и запись в память. А семь команд name на вызов ищут <, +, -, fib и t в хеш-таблице глобальных имён.

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

На last байткод уже вдвое быстрее, 149 тактов на ячейку против 267: на ячейку девять команд, три поиска имени и два вызова cdr по одной ячейке аргументов, а обход дерева на том же шаге строит окружение, список аргументов и спускается на несколько уровней рекурсии Zig.

Два диспетчера различаются на 7 процентов на fib и никак на last. Выбор следующей команды это малая доля цены команды, когда сама команда стоит десятки тактов. Почему labeled switch всё же не хуже и когда он выигрывает, разбираем в уроке про ветвления.

JIT видно только под эмуляцией amd64 (OrbStack, Rosetta 2 на том же M4 Max). Такты там это такты ядра M4, исполняющего переведённый код, поэтому сравнивать можно только строки этой таблицы между собой, а не с таблицей выше:

$ 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'
частота ядра по калибровке: 4.17 ГГц
исполнитель  fib, тактов на вызов  last, тактов на ячейку
tree             640.8 (шум 0.09)      530.0 (шум 0.02)
loop             569.8 (шум 0.02)      263.5 (шум 0.01)
labeled          468.0 (шум 0.01)      240.8 (шум 0.13)
jit               19.8 (шум 0.02)        6.7 (шум 0.02)

Интерпретаторы под эмуляцией медленнее своих же нативных строк в 1.6 до 2 раз, это цена перевода. А JIT обгоняет байткод в 24 раза на fib и в 36 раз на last, и причина видна по списку выше: он убрал все три неэффективности разом. Имена связаны при компиляции, поиска нет. Список аргументов собирается в кадре входа, а не в куче. car и cdr это чтение по смещению без вызова и без проверки вида. Промежуточные значения живут в %rax и слотах кадра, диспетчера нет вовсе. Цикл last в машинном коде это пять инструкций, те самые из урока про JIT, и 6.7 такта на ячейку это две зависимые загрузки cdr на виток под переводом Rosetta.

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

Прогон тестов

$ zig build test --summary all
Build Summary: 17/17 steps succeeded; 70/80 tests passed (10 skipped)

Под amd64 шаг добавляет те же четыре теста, и все 80 проходят.

Практика

Задача повторяет путь урока на вектор из целых. Тебе дан Vec за абстрактной процедурой доступа: len() возвращает длину, get(i) возвращает элемент или null за границей, и обе процедуры считают свои вызовы в полях len_calls и get_calls. Данные лежат в поле items, к ним можно обращаться напрямую. Рядом лежит готовая combine1(op, v, dest) со всеми тремя неэффективностями: len() в условии цикла, get(i) на каждый элемент, накопление через dest.*. Напиши combine4(comptime op: Op, v: *Vec, dest: *i64) void без них: длина один раз до цикла, элементы через v.items, аккумулятор в локальной переменной, одна запись в dest.* после цикла. Арифметика с заворачиванием, как в apply из заготовки.

Тесты проверяют три вещи. Результат совпадает с combine1 на случайных векторах для сложения и умножения, включая пустой вектор, вектор из одного элемента и переполнение. При наложении, когда dest указывает на элемент самого вектора, твоя combine4 даёт свёртку исходных данных, а combine1 даёт другое число: для [2, 3, 5] и dest = &data[1] это десять против девяти, ровно как в программе alias.zig выше. И после вызова get_calls равен нулю, а len_calls не больше единицы: то есть тесты смотрят не только на ответ, но и на то, что ты действительно убрал вызовы, а не спрятал их.

Упражнения

CHK-1★

В lower.zig замени noinline fn length на обычную fn length, собери в ReleaseFast и сними таблицу заново. Объясни по ассемблеру (-femit-asm), что сделал компилятор с вызовом в условии цикла и почему теперь он смог, а с noinline нет. Потом верни noinline, но сделай так, чтобы цикл не писал в строку (например, только считал заглавные буквы), и проверь, вынесет ли компилятор length из условия в этом случае.

CHK-2★★

В combine.zig добавь версию combine3b, которая хранит аккумулятор в dest.*, но объявляет параметр как noalias dest: *T. Сними CPE всех версий измерителем прошлого урока для четырёх колонок и сверь ассемблер combine3b с combine4. Затем передай в combine3b указатель внутрь вектора, как в alias.zig, собери в Debug и в ReleaseFast и объясни, почему результаты различаются между режимами сборки и что это говорит о природе noalias.

CHK-3★★

Запись в dest.* на каждой итерации в combine3 на нашей таблице бесплатна. Придумай и измерь цикл, где она перестанет быть бесплатной: возьми два аккумулятора в памяти, dest0.* и dest1.*, по одному на чётные и нечётные элементы, и сравни с той же развёрткой на двух локальных переменных. Объясни результат через число портов записи и через границу пропускной способности из таблицы.

CHK-4★★

Многочлен третьей степени можно считать без цикла: a0 + x * (a1 + x * (a2 + x * a3)) по Горнеру или a0 + a1 * x + a2 * x2 + a3 * x3 с заранее посчитанными степенями. Нарисуй для обоих выражений цепочки зависимостей с задержками M4 (умножение 3.42, сложение 2.49) и предскажи, какое быстрее и на сколько. Проверь измерением: оберни каждое выражение в цикл по массиву точек x и сними CPE. Объясни, почему для одного многочлена, а не для массива коэффициентов, картина может отличаться от урока.

CHK-5★★★

Напиши функцию, которая переводит строку в нижний регистр через std.ascii.toLower в цикле по срезу, и убедись, что она линейна. Потом найди в любом своём прошлом проекте (или в стандартной библиотеке Zig) цикл, в условии или теле которого стоит вызов с инвариантным результатом: indexOf, count, длина через сентинел, размер контейнера через метод. Измерь его на входе в сто тысяч элементов до и после выноса инварианта и опиши, почему компилятор не вынес его сам: какой именно записи в память или какого вызова он испугался.

CHK-6★★

Сделай шаг zl у себя и убери из байткода аккумулятор в памяти: пусть Machine.call собирает список аргументов примитива не в куче, а в массиве ячеек на стеке Zig, как вход lower.entry из урока про JIT. Какой примитив так звать нельзя и почему? Сними CPE заново и посчитай, сколько тактов на вызов fib стоили пять ячеек кучи.

CHK-7★★★

Убери поиск имени: команда name при первом исполнении запоминает найденное глобальное значение рядом с собой, а дальше берёт его без хеш-таблицы. Что должно сбрасывать такую запомненную ссылку, чтобы define поверх старого имени продолжал работать? Сними CPE обеих нагрузок и сравни, сколько дал этот приём и сколько дало упражнение выше.

CHK-8★★

Узнай, сколько стека на самом деле съедает обход дерева на (last xs): запусти замер в потоке со стеком поменьше и найди наименьший, на котором миллион ячеек ещё проходит. Раздели на миллион и сверь с суммой размеров кадров eval, apply и evalCond из ассемблера ReleaseFast.

Итоги

Три приёма урока убирают из цикла всё, что не арифметика: инвариант выносится в переменную до цикла, процедура доступа заменяется прямым индексом, аккумулятор переезжает из памяти в локальную переменную. Каждый приём компилятор мог бы применить сам, будь у него доказательство безопасности, и ни для одного доказательства нет.
Инвариант в условии цикла превращает линейный алгоритм в квадратичный: lower1 на 128 тысячах символов работает секунду против 0.07 миллисекунды у lower2. Компилятор не выносит вызов, тело которого не видит, а цикл, который пишет в память, лишает его права считать вызов чистым.
На M4 с LLVM переход от combine2 к combine3 сразу кладёт цикл на границу задержки: около одного такта на целое сложение, три на умножение. Вызов get был последним, что задавало темп.
В ассемблере combine3 и combine4 различаются одной инструкцией: записью dest.* в теле цикла. Чтение компилятор убрал, потому что помнит, что сам записал; запись оставил, потому что dest может указывать внутрь data. Книга на GCC 2015 года видела и чтение, и семь тактов на элемент.
При наложении dest на элемент вектора версии дают разные ответы (девять против десяти на [2, 3, 5]), и обе правильны по правилам языка. Поэтому превратить одну в другую компилятор не имеет права, а ты имеешь.
noalias dest возвращает компилятору право, и он сам делает из combine3 combine4. Обещание не проверяется: локальный аккумулятор надёжнее, потому что его нельзя нарушить снаружи.
Многочлен по Горнеру делает на треть меньше операций, чем в лоб, и работает в полтора раза медленнее: 5.2 такта на коэффициент против 3.4 на M4, 8 против 5 в книге. Решает не число операций, а длина цепочки зависимостей: у Горнера умножение и сложение сидят в одной цепочке, в лоб они разведены по двум.
Граница пропускной способности осталась далеко: 0.16 такта на целое сложение против одного такта у лучшей версии. Чтобы к ней подойти, придётся ломать цепочку, и об этом следующие два урока.
Шаг zl: бенч исполнителей на измерителе CPE. На M4 Max обход дерева стоит 348 тактов на вызов fib и 267 на ячейку списка, байткод 291 и 149: компиляция убрала только разбор узла, а вызов примитива, проверки вида и аргументы в куче остались. JIT под эмуляцией в 24 и 36 раз быстрее байткода под той же эмуляцией.

Дальше

Мы дважды за урок сказали «цепочка зависимостей» и «критический путь» и оба раза посчитали их на пальцах. В следующем уроке появится инструмент, который считает их честно: модель суперскалярного процессора с несколькими функциональными блоками, внеочередным исполнением и переименованием регистров. Ассемблер цикла превратится в граф потока данных, из графа выделится критический путь, и его длина объяснит каждое число в нашей таблице, включая те 5.2 такта Горнера, которые не сошлись с суммой задержек. А ещё станет понятно, почему граница пропускной способности в шесть раз ниже границы задержки и как к ней подобраться.

домашка

Домашка

Сними на своей машине таблицу lower1 против lower2 для n от 8 тысяч до миллиона, построй по ней степень роста (во сколько раз растёт время при удвоении n) и найди n, при котором lower1 перестаёт умещаться в секунду.S
Собери combine3 в двух вариантах, с обычным dest и с noalias dest, сними CPE обоих измерителем прошлого урока и сверь ассемблер: покажи строку, которая исчезла, и объясни, почему компилятор имел право её убрать.S
Перенеси poly и polyHorner на i64 с заворачиванием, сними CPE обоих и объясни результат через границы задержки целого сложения и умножения с M4.MS