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

Границы оптимизирующего компилятора и метрика CPE

senior~130 мин

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

Границы оптимизирующего компилятора и метрика CPE

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

Цели урока

Понять, какие преобразования компилятор проводит сам: свёртку констант, вынос инвариантов, замену цикла формулой, и увидеть их в ассемблере.
Разобрать два запрета оптимизатора: наложение указателей и побочные эффекты вызовов, и показать на Zig, во что они обходятся.
Уметь снять запрет там, где он лишний (noalias), и поставить барьер там, где оптимизация мешает измерению (export, noinline, @call, volatile, пустой asm).
Знать метрику CPE как наклон прямой «такты от размера входа» и уметь сравнивать версии по двум числам: накладные расходы и CPE.
Собрать измеритель: калибровка частоты цепочкой сложений, разогрев, минимум из серии, оценка шума, прямая методом наименьших квадратов.
Написать первые три версии свёртки вектора и получить их CPE на реальном железе.
Переформулировать четыре задачи книги про наложение, прямые времени, число вызовов и сохранение через указатель, и решить их своими руками.

Идея: компилятор оптимизирует только то, что может доказать

Оптимизирующий компилятор это осторожный переписчик. Он имеет право заменить твою программу на любую другую, которая при любых входных данных ведёт себя точно так же. Ключевое слово здесь «при любых». Если хоть на одном входе новая программа даст другой результат, преобразование запрещено, даже если этот вход в твоей практике никогда не встречается. Компилятор не знает твоей практики, он знает только текст.

Из этого правила следуют обе половины урока: что он умеет и чего не имеет права.

Умеет он много. Посмотри на два цикла, которые считают сумму от единицы до n:

/// Сумма от 1 до n циклом. Оптимизатор видит арифметическую прогрессию.
export fn sumTo(n: u64) u64 {
    var acc: u64 = 0;
    var i: u64 = 1;
    while (i <= n) : (i += 1) acc +%= i;
    return acc;
}

/// Тот же цикл, но каждое частичное значение проходит через пустой asm.
export fn sumToOpaque(n: u64) u64 {
    var acc: u64 = 0;
    var i: u64 = 1;
    while (i <= n) : (i += 1) {
        acc +%= i;
        asm volatile (""
            : [acc] "+r" (acc),
        );
    }
    return acc;
}

Первый цикл LLVM узнаёт как арифметическую прогрессию и заменяет замкнутой формулой. Никакого цикла в машинном коде не остаётся, только умножение и несколько сложений:

$ zig build-obj fold.zig -O ReleaseFast -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=fold.o
$ objdump -d fold.o --no-show-raw-insn

0000000000000030 <sumTo>:
      30:   testq   %rdi, %rdi
      33:   je      0x4e <sumTo+0x1e>
      35:   leaq    -0x1(%rdi), %rax
      39:   leaq    -0x2(%rdi), %rcx
      3d:   mulq    %rcx
      40:   shldq   $0x3f, %rax, %rdx
      45:   leaq    (%rdx,%rdi,2), %rax
      49:   addq    $-0x1, %rax
      4d:   retq
      4e:   xorl    %eax, %eax
      50:   retq

Второй цикл отличается одной строкой: пустой asm volatile, через который на каждой итерации проходит частичная сумма. Компилятор обязан считать, что этот ассемблер мог сделать с acc что угодно, и формула становится невозможной. Цикл остаётся циклом:

0000000000000000 <sumToOpaque>:
       0:   testq   %rdi, %rdi
       3:   je      0x26 <sumToOpaque+0x26>
       5:   negq    %rdi
       8:   movl    $0x1, %ecx
       d:   xorl    %eax, %eax
      10:   addq    %rcx, %rax
      13:   leaq    (%rdi,%rcx), %rdx
      17:   addq    $0x1, %rdx
      1b:   addq    $0x1, %rcx
      1f:   cmpq    $0x1, %rdx
      23:   jne     0x10 <sumToOpaque+0x10>
      25:   retq
      26:   xorl    %eax, %eax
      28:   retq

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

Теперь про то, чего он не сделает.

Наложение указателей

это первый и самый важный запрет. Две функции ниже кажутся одинаковыми, но первая читает yp.* два раза, а вторая один:

const std = @import("std");

/// Два сложения через память: xp и yp читаются каждый раз заново.
fn twiddle1(xp: *i64, yp: *i64) void {
    xp.* += yp.*;
    xp.* += yp.*;
}

/// «То же самое», но yp прочитан один раз. Это не то же самое.
fn twiddle2(xp: *i64, yp: *i64) void {
    xp.* += 2 * yp.*;
}

/// Обмен через xor без временной переменной.
fn swapXor(xp: *i64, yp: *i64) void {
    xp.* = xp.* ^ yp.*;
    yp.* = xp.* ^ yp.*;
    xp.* = xp.* ^ yp.*;
}

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 = 10;
    var b: i64 = 10;
    twiddle1(&a, &a);
    twiddle2(&b, &b);
    try out.print("twiddle1(&x, &x): {d}\n", .{a});
    try out.print("twiddle2(&x, &x): {d}\n", .{b});

    var p: i64 = 3;
    var q: i64 = 5;
    swapXor(&p, &q);
    try out.print("swapXor(&p, &q): p = {d}, q = {d}\n", .{ p, q });
    swapXor(&p, &p);
    try out.print("swapXor(&p, &p): p = {d}\n", .{p});
    try out.flush();
}

$ zig run alias.zig
twiddle1(&x, &x): 40
twiddle2(&x, &x): 30
swapXor(&p, &q): p = 5, q = 3
swapXor(&p, &p): p = 0

Пока xp и yp смотрят в разные места, обе функции дают одно и то же: x увеличивается на 2 * y. Но стоит передать один и тот же адрес дважды, и первая функция удваивает x дважды, а вторая утраивает. Компилятор видит только текст, где xp и yp это два параметра, и обязан рассматривать случай, когда они равны. Поэтому он не имеет права превратить twiddle1 в twiddle2, хотя вторая читает память на один раз меньше и на одну запись короче.

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

export fn twiddle1(xp: *i64, yp: *i64) void {
    xp.* += yp.*;
    xp.* += yp.*;
}

export fn twiddle3(xp: *i64, noalias yp: *i64) void {
    xp.* += yp.*;
    xp.* += yp.*;
}

$ zig build-obj alias_asm.zig -O ReleaseFast -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=alias_asm.o
$ objdump -d alias_asm.o --no-show-raw-insn

0000000000000000 <twiddle3>:
       0:   movq    (%rsi), %rax
       3:   addq    %rax, %rax
       6:   addq    %rax, (%rdi)
       9:   retq

0000000000000010 <twiddle1>:
      10:   movq    (%rsi), %rax
      13:   addq    (%rdi), %rax
      16:   movq    %rax, (%rdi)
      19:   addq    (%rsi), %rax
      1c:   movq    %rax, (%rdi)
      1f:   retq

В twiddle1 компилятор честно записывает xp.* после первого сложения и заново читает yp.* перед вторым: вдруг запись в (%rdi) изменила то, что лежит по (%rsi). Шесть инструкций, две записи в память, три чтения. В twiddle3 слово noalias разрешает считать, что yp не пересекается ни с чем другим, что функция трогает, и получается ровно twiddle2: одно чтение, одно удвоение, одно сложение прямо в памяти.

noalias в Zig это обещание, а не проверка. Если ты пообещал и соврал, вызвав twiddle3(&x, &x), компилятор сгенерирует код для случая без наложения, и результат будет тридцать вместо сорока. Это то же самое, что restrict в C: инструмент для того, кто точно знает, откуда приходят указатели.

Задача про обмен через xor. Функция swapXor меняет местами два значения без временной переменной, тремя исключающими ИЛИ. На паре p = 3, q = 5 она работает. Такой приём иногда предлагают для перестановки элементов массива: swapXor(&a[i], &a[j]). Объясни, почему вывод выше показывает ноль при swapXor(&p, &p), и что сломается в сортировке, где i и j изредка совпадают.

Разбор. После первого шага xp.* = xp.* ^ yp.* при общем адресе оба «значения» стали нулём: число, исключающее ИЛИ с самим собой, всегда ноль. Дальше ноль уже не восстановить, второй и третий шаги тоже дают ноль. Обмен с временной переменной этой болезни не имеет: t = a[i]; a[i] = a[j]; a[j] = t при i == j ничего не меняет. В сортировке ошибка проявится не на каждом прогоне, а только когда алгоритм решит переставить элемент с самим собой, и ты получишь массив, в котором тихо появился лишний ноль. Это и есть наложение указателей в чистом виде: код правилен для разных адресов и молча неверен для одинаковых.

Побочные эффекты вызовов

Второй запрет проще, но обходится не дешевле. Выражение f() + f() + f() + f() так и просится в 4 * f(). Компилятор этого не сделает, потому что не знает, что делает f между вызовами:

const std = @import("std");

var counter: i64 = 0;

/// Функция с побочным эффектом: каждый вызов меняет глобальное состояние.
fn f() i64 {
    counter += 1;
    return counter;
}

/// Четыре вызова. Соблазн заменить на 4 * f() велик.
fn func1() i64 {
    return f() + f() + f() + f();
}

/// «Оптимизированная» версия: один вызов вместо четырёх.
fn func2() i64 {
    return 4 * f();
}

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

    counter = 0;
    try out.print("func1() = {d}\n", .{func1()});
    counter = 0;
    try out.print("func2() = {d}\n", .{func2()});
    try out.flush();
}

$ zig run side_effects.zig
func1() = 10
func2() = 4

Функция f увеличивает счётчик, поэтому четыре вызова возвращают один, два, три и четыре, в сумме десять, а один вызов, умноженный на четыре, даёт четыре.

Побочный эффект

делает вызов невоспроизводимым, и компилятор обязан оставить все четыре.

Здесь есть оговорка, которая для Zig важнее, чем для C. Когда тело f видно в той же единице компиляции, LLVM встроит её, увидит счётчик и, возможно, сложит четыре инкремента в один counter += 4. Результат при этом останется десять: встраивание это не нарушение запрета, компилятор просто получил доказательство, которого у него не было. Запрет действует, пока тело скрыто: вызов через указатель на функцию, функция из другого объектного файла, extern из C. В Zig всё обычно собирается вместе, поэтому дальше мы будем прятать тела руками.

Барьеры: как запретить оптимизацию нарочно

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

export. Экспортированная функция видна снаружи объектного файла, поэтому её тело обязано существовать в машинном коде с полной сигнатурой. Так мы снимаем ассемблер: без export функция встроилась бы в вызывающую или пропала целиком, как mult2 в уроке про машинный код. Параметры должны иметь представление в C: указатели, целые, [*] вместо среза.

noinline и @call. Модификатор noinline на объявлении запрещает встраивать функцию куда бы то ни было. Тот же эффект в одном месте вызова даёт @call(.never_inline, f, .{args}), а обратный, принудительное встраивание, @call(.always_inline, ...). Именно noinline стоит на len и get нашего вектора ниже: в книге они лежат в другом файле и компилятор их тел не видит, а у нас всё в одном модуле, и границу приходится проводить явно.

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

std.mem.doNotOptimizeAway. Функция стандартной библиотеки, которая делает вид, что использует значение. Компилятор обязан вычислить его и не может выкинуть цикл как «результат никому не нужен». Ставится в конце: посчитал, отдал в doNotOptimizeAway, и вычисление обязано состояться.

Пустой asm volatile. Самый точный барьер, и ты уже видел его в sumToOpaque. Конструкция asm volatile ("" : [v] "+r" (v)) говорит: вот значение в регистре, ассемблерный текст пустой, но считай, что регистр мог измениться. Ни одна инструкция не добавляется, а компилятор теряет право что-либо знать о значении. В отличие от doNotOptimizeAway, такой барьер можно поставить внутрь цепочки, между двумя операциями, и цепочка останется цепочкой. В измерителе это функция blackBox, и для дробных чисел ей нужен другой класс регистра: w на aarch64, x на x86-64.

Правило выбора такое. Ассемблер читать: export. Скрыть тело функции: noinline. Не дать выбросить результат: doNotOptimizeAway. Не дать свернуть цепочку операций: blackBox. volatile оставить железу.

Метрика CPE

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

CPE

определяется через прямую. Если функция обрабатывает n элементов, её время в тактах это T(n) = a + b * n, где a накладные расходы на вызов, подготовку и завершение, а b цена одного элемента. Именно b и называется CPE. Два числа вместо одного важны потому, что версия с маленькими накладными расходами и большим CPE выигрывает на коротких векторах и проигрывает на длинных, и без прямой этого не увидеть.

Задача про три прямые. Пусть три версии одной функции описываются прямыми A(n) = 50 + 8n, B(n) = 200 + 3n и C(n) = 500 + 1.2n тактов. Какая из них быстрее при каком n?

Разбор. Прямые сравниваются попарно в точках пересечения. A и B равны, когда 50 + 8n = 200 + 3n, то есть при n = 30; ниже этого A быстрее, выше B. B и C равны, когда 200 + 3n = 500 + 1.2n, при n около 167. Итог: до тридцати элементов бери A, от тридцати до ста шестидесяти семи B, дальше C. Заметь, что C с самым низким CPE проигрывает на всём диапазоне до 167 элементов, а на векторе из десяти элементов она в четыре раза медленнее A. Оптимизация под длинный вектор это не бесплатное улучшение, а сделка: накладные расходы растут вместе со сложностью цикла.

Как мерить честно

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

Ловушка первая: у программы нет счётчика тактов. Настоящий счётчик тактов процессора доступен только операционной системе. Пользовательская программа может прочитать rdtsc на x86-64 или cntvct_el0 на aarch64, но это счётчик времени, а не тактов: на Apple Silicon он идёт ровно на одном гигагерце независимо от того, разогнано ядро до четырёх с половиной или спит на одном. Поэтому время мы берём с монотонных часов std.Io.Clock, а в такты переводим через частоту ядра, которую не угадываем, а калибруем. Способ калибровки такой: цепочка зависимых целочисленных сложений выполняется ровно по одному такту на сложение на любом современном ядре, потому что следующее сложение не может начаться, пока не готово предыдущее, а сложение занимает один такт. Значит, двести миллионов сложений в цепочке занимают двести миллионов тактов, и частота равна их числу, делённому на измеренное время. Цепочку от свёртки в формулу защищает blackBox, тот самый пустой asm.

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

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

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

Вот измеритель целиком. Он взят в урок без сокращений, потому что каждая его часть отвечает на одну из ловушек:

//! Измеритель CPE (cycles per element, тактов на элемент).
//!
//! Модель из книги: время вызова над n элементами это прямая
//! `cycles = a + CPE * n`. Мы снимаем время для нескольких n, для каждого n
//! берём минимум из серии прогонов (минимум ближе всего к «чистой» работе
//! ядра, всё остальное это шум планировщика и прерываний), а потом проводим
//! прямую методом наименьших квадратов. Наклон прямой и есть CPE.
//!
//! Такты. У процессора нет счётчика, который программа могла бы прочитать
//! без прав, поэтому время берётся с монотонных часов `std.Io.Clock`, а
//! в такты переводится через частоту ядра. Частоту мы не угадываем, а
//! калибруем: цепочка зависимых целочисленных сложений выполняется ровно
//! по одному такту на сложение на любом современном ядре, значит
//! `частота = число сложений / время`. Счётчик `rdtsc` (x86-64) или
//! `cntvct_el0` (aarch64) читается как второй источник времени: на Apple
//! Silicon он идёт с постоянной частотой (здесь 1 ГГц, на старых чипах
//! 24 МГц), а не с частотой ядра, поэтому напрямую тактами не является.

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

/// Показания аппаратного счётчика времени.
pub fn ticks() u64 {
    return switch (builtin.cpu.arch) {
        .aarch64 => asm volatile ("mrs %[r], cntvct_el0"
            : [r] "=r" (-> u64),
        ),
        .x86_64 => blk: {
            var lo: u32 = undefined;
            var hi: u32 = undefined;
            asm volatile ("rdtsc"
                : [lo] "={eax}" (lo),
                  [hi] "={edx}" (hi),
            );
            break :blk (@as(u64, hi) << 32) | lo;
        },
        else => @compileError("на этой архитектуре счётчик тактов не подключён"),
    };
}

/// Пропускает значение через пустой asm: после этого компилятор обязан
/// считать его неизвестным. Так цепочка `a = blackBox(a + b)` остаётся
/// цепочкой, а не сворачивается в одно `a + n * b`.
pub inline fn blackBox(value: anytype) @TypeOf(value) {
    var v = value;
    switch (@typeInfo(@TypeOf(value))) {
        .float => switch (builtin.cpu.arch) {
            .aarch64 => asm volatile (""
                : [v] "+w" (v),
            ),
            .x86_64 => asm volatile (""
                : [v] "+x" (v),
            ),
            else => asm volatile (""
                : [v] "+r" (v),
            ),
        },
        else => asm volatile (""
            : [v] "+r" (v),
        ),
    }
    return v;
}

/// Часы бенчмарка: откуда брать наносекунды и как переводить их в такты.
pub const Clock = struct {
    io: std.Io,
    /// Частота ядра в гигагерцах: такты на наносекунду.
    ghz: f64,
    /// Частота счётчика `ticks()` в герцах, измерена относительно часов.
    tick_hz: f64,

    /// Калибрует частоту по цепочке зависимых сложений.
    pub fn init(io: std.Io) Clock {
        var best_ns: f64 = std.math.inf(f64);
        var tick_hz: f64 = 0;
        var attempt: usize = 0;
        while (attempt < 5) : (attempt += 1) {
            const t0 = ticks();
            const started = now(io);
            const result = addChain(calibration_adds);
            const ns = elapsedNs(io, started);
            const dt = @as(f64, @floatFromInt(ticks() - t0));
            std.mem.doNotOptimizeAway(result);
            if (ns < best_ns) {
                best_ns = ns;
                tick_hz = dt / ns * 1e9;
            }
        }
        return .{
            .io = io,
            .ghz = @as(f64, @floatFromInt(calibration_adds)) / best_ns,
            .tick_hz = tick_hz,
        };
    }

    /// Часы с частотой, заданной снаружи, без калибровки.
    pub fn withGhz(io: std.Io, ghz: f64) Clock {
        return .{ .io = io, .ghz = ghz, .tick_hz = 0 };
    }
};

const calibration_adds: usize = 200_000_000;

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

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

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

/// Одна точка серии: один размер входа.
pub const Point = struct {
    n: usize,
    /// Минимальное время одного вызова в наносекундах.
    ns: f64,
    /// То же в показаниях `ticks()`.
    ticks: f64,
    /// Оценка в тактах ядра: ns * ghz.
    cycles: f64,
    /// Шум серии: (медиана минус минимум) / минимум.
    noise: f64,
};

pub const max_points = 16;
pub const max_runs = 32;

/// Серия замеров одного ядра по нескольким n.
pub const Series = struct {
    points: [max_points]Point = undefined,
    count: usize = 0,
    ghz: f64,

    pub fn items(self: *const Series) []const Point {
        return self.points[0..self.count];
    }

    /// Худший шум по всем точкам серии.
    pub fn noise(self: *const Series) f64 {
        var worst: f64 = 0;
        for (self.items()) |p| worst = @max(worst, p.noise);
        return worst;
    }
};

pub const Options = struct {
    /// Прогонов на разогрев: их время не учитывается.
    warmup: usize = 2,
    /// Прогонов в серии, из них берётся минимум и медиана.
    runs: usize = 7,
    /// Сколько элементов уложить в один замер. Часы macOS идут с шагом
    /// в десятки наносекунд, поэтому один вызов на сотне элементов
    /// измерять нельзя: вызов повторяется `work / n` раз подряд.
    work: usize = 1_000_000,
};

/// Снимает серию. `ctx.run(n)` обязан выполнить работу ровно над n
/// элементами и сам защитить результат через `std.mem.doNotOptimizeAway`.
pub fn measure(clock: Clock, ctx: anytype, sizes: []const usize, options: Options) Series {
    var series = Series{ .ghz = clock.ghz };
    const runs = @min(options.runs, max_runs);
    for (sizes) |n| {
        if (series.count == max_points) break;
        const reps = @max(1, options.work / n);
        var warm: usize = 0;
        while (warm < options.warmup) : (warm += 1) repeat(ctx, n, reps);

        var samples: [max_runs]f64 = undefined;
        var tick_samples: [max_runs]f64 = undefined;
        var run: usize = 0;
        while (run < runs) : (run += 1) {
            const t0 = ticks();
            const started = now(clock.io);
            repeat(ctx, n, reps);
            samples[run] = elapsedNs(clock.io, started) / @as(f64, @floatFromInt(reps));
            tick_samples[run] = @as(f64, @floatFromInt(ticks() - t0)) / @as(f64, @floatFromInt(reps));
        }
        std.mem.sort(f64, samples[0..runs], {}, std.sort.asc(f64));
        std.mem.sort(f64, tick_samples[0..runs], {}, std.sort.asc(f64));
        const min_ns = samples[0];
        const median_ns = samples[runs / 2];
        series.points[series.count] = .{
            .n = n,
            .ns = min_ns,
            .ticks = tick_samples[0],
            .cycles = min_ns * clock.ghz,
            .noise = (median_ns - min_ns) / min_ns,
        };
        series.count += 1;
    }
    return series;
}

fn repeat(ctx: anytype, n: usize, reps: usize) void {
    var rep: usize = 0;
    while (rep < reps) : (rep += 1) ctx.run(n);
}

/// Прямая `cycles = intercept + cpe * n`, проведённая по точкам серии.
pub const Fit = struct {
    intercept: f64,
    cpe: f64,
    /// Наибольшее относительное отклонение точки от прямой.
    max_residual: f64,
};

pub fn fit(series: Series) Fit {
    return fitPoints(series.items());
}

/// Метод наименьших квадратов по парам (n, cycles).
pub fn fitPoints(points: []const Point) Fit {
    const count: f64 = @floatFromInt(points.len);
    var sum_x: f64 = 0;
    var sum_y: f64 = 0;
    var sum_xx: f64 = 0;
    var sum_xy: f64 = 0;
    for (points) |p| {
        const x: f64 = @floatFromInt(p.n);
        sum_x += x;
        sum_y += p.cycles;
        sum_xx += x * x;
        sum_xy += x * p.cycles;
    }
    const denominator = count * sum_xx - sum_x * sum_x;
    const slope = if (denominator == 0) 0 else (count * sum_xy - sum_x * sum_y) / denominator;
    const intercept = (sum_y - slope * sum_x) / count;

    var worst: f64 = 0;
    for (points) |p| {
        const predicted = intercept + slope * @as(f64, @floatFromInt(p.n));
        if (predicted != 0) worst = @max(worst, @abs(p.cycles - predicted) / predicted);
    }
    return .{ .intercept = intercept, .cpe = slope, .max_residual = worst };
}

/// Тактов на элемент: наклон прямой.
pub fn cpe(series: Series) f64 {
    return fit(series).cpe;
}

test "прямая восстанавливается по точкам без шума" {
    var points: [4]Point = undefined;
    for (&points, [_]usize{ 100, 200, 400, 800 }) |*p, n| {
        p.* = .{ .n = n, .ns = 0, .ticks = 0, .cycles = 50 + 1.5 * @as(f64, @floatFromInt(n)), .noise = 0 };
    }
    const line = fitPoints(&points);
    try std.testing.expectApproxEqAbs(1.5, line.cpe, 1e-9);
    try std.testing.expectApproxEqAbs(50, line.intercept, 1e-9);
    try std.testing.expectApproxEqAbs(0, line.max_residual, 1e-9);
}

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

Пройдись по нему сверху вниз. ticks читает аппаратный счётчик через встроенный ассемблер: на aarch64 это одна инструкция mrs, на x86-64 rdtsc возвращает результат двумя половинами в edx:eax. blackBox это барьер из прошлого раздела, обобщённый по типу: для дробных значений класс регистра другой. Clock.init пять раз гоняет цепочку из двухсот миллионов сложений и берёт лучшее время; заодно он меряет, с какой частотой идёт ticks, чтобы ты видел, что это не такты. measure для каждого размера делает разогрев, потом семь прогонов, сортирует времена и записывает минимум, медиану как шум и перевод в такты. Обрати внимание на work: часы macOS идут с шагом в десятки наносекунд, и один вызов на ста элементах в них не поместится, поэтому вызов повторяется work / n раз подряд, а время делится обратно. fitPoints это формулы наименьших квадратов: четыре суммы, знаменатель, наклон, свободный член. Два теста внизу проверяют, что прямая восстанавливается по идеальным точкам и что blackBox не портит значение.

$ zig test harness.zig
All 2 tests passed.

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

Сквозной пример: свёртка вектора

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

//! Сквозной пример книги: свёртка вектора одной операцией.
//!
//! Первые три версии одной и той же функции: абстрактная процедура с
//! вызовами на каждом шаге, вынос длины из условия, прямой доступ к
//! данным. Все они обобщены по типу элемента `T` (`i64` или `f64`) и по
//! операции `op` (сложение или умножение), и у всех одна сигнатура:
//!
//!     fn combineN(comptime T: type, comptime op: Op, v: *const Vec(T), dest: *T) void
//!
//! Для целых используются операции с заворачиванием (`+%`, `*%`), как
//! в книге, где переполнение `long` просто отбрасывает старшие биты.

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,
    };
}

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

/// Вектор из книги: данные плюс абстрактный интерфейс к ним.
///
/// `len` и `get` помечены `noinline`. В книге они лежат в другой единице
/// трансляции, и компилятор не видит их тел; в Zig всё собирается вместе,
/// поэтому границу приходится проводить явно. Без неё LLVM сам сделал бы
/// из combine1 что-то вроде combine3, и мерить было бы нечего.
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]);
    }
}

test "три версии дают одно и то же" {
    var data = [_]i64{ 3, 5, 7, 11, 13 };
    const v = Vec(i64).init(&data);
    var a: i64 = undefined;
    var b: i64 = undefined;
    var c: i64 = undefined;
    combine1(i64, .mul, &v, &a);
    combine2(i64, .mul, &v, &b);
    combine3(i64, .mul, &v, &c);
    try std.testing.expectEqual(@as(i64, 15015), a);
    try std.testing.expectEqual(a, b);
    try std.testing.expectEqual(a, c);
}

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

Вектор в книге спрятан за интерфейсом: длину спрашивают через len, элемент достают через get с проверкой границ. Это честная абстракция, такую написал бы любой из нас, и цена у неё есть. combine1 спрашивает длину в условии цикла на каждой итерации и копит результат прямо в dest.*. combine2 спрашивает длину один раз. combine3 перестаёт звать get и читает данные напрямую, но результат по-прежнему копит через указатель.

Про noinline на len и get ты уже знаешь: без него LLVM сам сделает из combine1 что-то вроде combine3, и сравнивать будет нечего. Оператор +% на целых это сложение с заворачиванием, как переполнение long в C, где старшие биты отбрасываются; без него в Debug каждый переполнившийся элемент останавливал бы программу.

$ zig test combine.zig
All 2 tests passed.

Задача про число вызовов. Ниже три цикла над тем же вектором, где len и get считают свои вызовы. Прежде чем запускать, посчитай на бумаге, сколько раз для вектора из десяти элементов вызовется каждая функция в loopA, loopB и loopC.

const std = @import("std");

var len_calls: usize = 0;
var get_calls: usize = 0;

const Vec = struct {
    data: []const i64,

    noinline fn len(self: *const Vec) usize {
        len_calls += 1;
        return self.data.len;
    }

    noinline fn get(self: *const Vec, index: usize) i64 {
        get_calls += 1;
        return self.data[index];
    }
};

/// Длина спрашивается в условии: на каждой итерации и ещё раз на выходе.
fn loopA(v: *const Vec) i64 {
    var sum: i64 = 0;
    var i: usize = 0;
    while (i < v.len()) : (i += 1) sum += v.get(i);
    return sum;
}

/// Длина вынесена из условия.
fn loopB(v: *const Vec) i64 {
    var sum: i64 = 0;
    const n = v.len();
    var i: usize = 0;
    while (i < n) : (i += 1) sum += v.get(i);
    return sum;
}

/// Элемент берётся дважды на итерацию, хотя он один и тот же.
fn loopC(v: *const Vec) i64 {
    var sum: i64 = 0;
    const n = v.len();
    var i: usize = 0;
    while (i < n) : (i += 1) sum += v.get(i) * v.get(i);
    return sum;
}

fn report(out: *std.Io.Writer, name: []const u8, value: i64) !void {
    try out.print("{s}: результат {d}, вызовов len {d}, вызовов get {d}\n", .{ name, value, len_calls, get_calls });
    len_calls = 0;
    get_calls = 0;
}

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;

    const data = [_]i64{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    const v = Vec{ .data = &data };
    try report(out, "loopA", loopA(&v));
    try report(out, "loopB", loopB(&v));
    try report(out, "loopC", loopC(&v));
    try out.flush();
}

$ zig run calls.zig
loopA: результат 55, вызовов len 11, вызовов get 10
loopB: результат 55, вызовов len 1, вызовов get 10
loopC: результат 385, вызовов len 1, вызовов get 20

Разбор. В loopA условие проверяется на каждой итерации и ещё один раз, когда оно наконец ложно: одиннадцать вызовов len на десять элементов. В loopB длина вынесена, один вызов. В loopC элемент достаётся дважды, потому что записан дважды, и компилятор не имеет права склеить два вызова get в один: у get может быть побочный эффект, и здесь он как раз есть, счётчик. Разница между loopA и loopB это ровно то, что отличает combine1 от combine2, и это первое, что компилятор не сделает за тебя: вынести вызов из условия он может, только доказав, что len без побочных эффектов и что тело цикла не меняет длину. Через noinline он ничего доказать не может.

Две границы: задержка и пропускная способность

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

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

//! Границы CPE: задержка и пропускная способность одной операции.
//!
//! Задержка меряется одной цепочкой зависимых операций: следующая ждёт
//! результата предыдущей, и время на операцию равно её задержке.
//! Пропускная способность меряется несколькими независимыми цепочками
//! сразу: их столько, что задержка закрыта, и упираемся уже в число
//! функциональных блоков и ширину выдачи.
//!
//! Операция записана обычным Zig, а `blackBox` после каждой не даёт
//! компилятору свернуть цепочку в одно действие.

const std = @import("std");
const combine = @import("combine.zig");
const harness = @import("harness.zig");

const Op = combine.Op;
const apply = combine.apply;
const blackBox = harness.blackBox;

/// Сколько независимых цепочек гонять для пропускной способности.
/// Больше, чем задержка умножить на число блоков у любого ядра.
pub const chains = 16;

/// Одна цепочка из n операций. Возвращает результат, чтобы вызывающий
/// мог защитить его от выбрасывания.
pub fn latency(comptime T: type, comptime op: Op, n: usize) T {
    var acc: T = blackBox(@as(T, 1));
    const step: T = blackBox(seed(T, op));
    var i: usize = 0;
    while (i < n) : (i += 1) {
        acc = blackBox(apply(T, op, acc, step));
    }
    return acc;
}

/// `chains` независимых цепочек, всего n операций.
pub fn throughput(comptime T: type, comptime op: Op, n: usize) T {
    var acc: [chains]T = undefined;
    inline for (0..chains) |j| acc[j] = blackBox(@as(T, 1));
    const step: T = blackBox(seed(T, op));
    var i: usize = 0;
    while (i + chains <= n) : (i += chains) {
        inline for (0..chains) |j| acc[j] = blackBox(apply(T, op, acc[j], step));
    }
    var total = acc[0];
    inline for (1..chains) |j| total = apply(T, op, total, acc[j]);
    return total;
}

/// Второй операнд: для дробного умножения близкий к единице, чтобы
/// значение не убежало в бесконечность или в денормализованные числа,
/// на которых процессор заметно замедляется.
fn seed(comptime T: type, comptime op: Op) T {
    return switch (@typeInfo(T)) {
        .float => if (op == .mul) 1.0000001 else 1.5,
        else => if (op == .mul) 3 else 7,
    };
}

test "цепочки считают то же, что и обычный цикл" {
    try std.testing.expectEqual(@as(i64, 1 + 7 * 100), latency(i64, .add, 100));
    try std.testing.expectEqual(@as(i64, chains + 7 * 160), throughput(i64, .add, 160));
}

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

Бенчмарк: три версии против двух границ

Сложим всё вместе. Бенчмарк калибрует часы, снимает четыре пары границ, потом три версии свёртки по четырём колонкам: целые и дробные, сложение и умножение. Размеры вектора от 128 до 4096 элементов помещаются в кэш первого уровня, поэтому мы меряем работу ядра, а не памяти. Что происходит, когда вектор в кэш не помещается, начнём разбирать в уроке про хранилища и локальность.

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

const std = @import("std");
const harness = @import("harness.zig");
const bounds = @import("bounds.zig");
const combine = @import("combine.zig");

const Op = combine.Op;
const Vec = combine.Vec;

/// Колонка таблицы: тип элемента и операция.
const Column = struct { key: []const u8, T: type, op: Op };

const columns = [_]Column{
    .{ .key = "i64+", .T = i64, .op = .add },
    .{ .key = "i64*", .T = i64, .op = .mul },
    .{ .key = "f64+", .T = f64, .op = .add },
    .{ .key = "f64*", .T = f64, .op = .mul },
};

const versions = [_][]const u8{ "combine1", "combine2", "combine3" };

/// Размеры вектора, по которым проводится прямая. Все помещаются в L1,
/// чтобы мерить работу ядра, а не память.
const sizes = [_]usize{ 128, 256, 512, 1024, 2048, 4096 };

/// Контекст для `measure`: гоняет одну версию свёртки над своим буфером.
fn Runner(comptime T: type, comptime op: Op, comptime which: []const u8) type {
    return struct {
        vec: Vec(T),

        pub fn run(self: *@This(), n: usize) void {
            var slice = Vec(T).init(self.vec.data[0..n]);
            var result: T = undefined;
            if (comptime std.mem.eql(u8, which, "combine1")) combine.combine1(T, op, &slice, &result);
            if (comptime std.mem.eql(u8, which, "combine2")) combine.combine2(T, op, &slice, &result);
            if (comptime std.mem.eql(u8, which, "combine3")) combine.combine3(T, op, &slice, &result);
            std.mem.doNotOptimizeAway(result);
        }
    };
}

fn LatencyRunner(comptime T: type, comptime op: Op) type {
    return struct {
        pub fn run(_: @This(), n: usize) void {
            std.mem.doNotOptimizeAway(bounds.latency(T, op, n));
        }
    };
}

fn ThroughputRunner(comptime T: type, comptime op: Op) type {
    return struct {
        pub fn run(_: @This(), n: usize) void {
            std.mem.doNotOptimizeAway(bounds.throughput(T, op, n));
        }
    };
}

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

    const clock = harness.Clock.init(init.io);
    try out.print("частота ядра по калибровке: {d:.2} ГГц\n", .{clock.ghz});
    try out.print("счётчик ticks(): {d:.2} МГц\n\n", .{clock.tick_hz / 1e6});
    try out.flush();

    try out.writeAll("границы, тактов на операцию\n");
    try out.writeAll("операция  задержка  пропускная\n");
    inline for (columns) |column| {
        const chain_sizes = [_]usize{ 4096, 8192, 16384, 32768 };
        const lat = harness.measure(clock, LatencyRunner(column.T, column.op){}, &chain_sizes, .{});
        const thr = harness.measure(clock, ThroughputRunner(column.T, column.op){}, &chain_sizes, .{});
        try out.print("{s:<8}  {d:>8.2}  {d:>10.2}\n", .{ column.key, harness.cpe(lat), harness.cpe(thr) });
    }
    try out.writeAll("\n");

    try out.writeAll("CPE по версиям\n");
    try out.writeAll("версия      i64+     i64*     f64+     f64*   шум\n");
    var worst_noise: f64 = 0;
    inline for (versions) |version| {
        try out.print("{s:<8}", .{version});
        inline for (columns) |column| {
            const data = try gpa.alloc(column.T, sizes[sizes.len - 1]);
            defer gpa.free(data);
            for (data, 0..) |*cell, i| {
                cell.* = switch (@typeInfo(column.T)) {
                    .float => 1.0 + @as(f64, @floatFromInt(i % 3)) / 1024.0,
                    else => @intCast(1 + i % 3),
                };
            }
            var runner = Runner(column.T, column.op, version){ .vec = Vec(column.T).init(data) };
            const series = harness.measure(clock, &runner, &sizes, .{});
            worst_noise = @max(worst_noise, series.noise());
            try out.print("  {d:>6.2}", .{harness.cpe(series)});
        }
        try out.writeAll("\n");
    }
    try out.print("\nхудший шум серии: {d:.1} процентов\n", .{worst_noise * 100});
    try out.flush();
}

Собирается только в ReleaseFast. В Debug ты измерил бы проверки безопасности, а не свёртку, и калибровка дала бы частоту в десятки раз ниже настоящей, потому что цепочка сложений перестаёт быть одним тактом на сложение.

$ zig build-exe main.zig -O ReleaseFast -femit-bin=bench
$ ./bench
частота ядра по калибровке: 4.50 ГГц
счётчик ticks(): 1000.00 МГц

границы, тактов на операцию
операция  задержка  пропускная
i64+          1.00        0.16
i64*          2.99        0.33
f64+          2.49        0.25
f64*          3.42        0.25

CPE по версиям
версия      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

худший шум серии: 14.3 процентов

Снято на Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-09, на тихой машине. Калибровка дала 4.50 ГГц, что совпадает с паспортной частотой ядра производительности, а ticks идёт ровно на одном гигагерце, как и было обещано. Худший шум четырнадцать процентов, поэтому третий знак после запятой в этой таблице ничего не значит, и сравнивать стоит только числа, которые отличаются заметно.

Что здесь видно.

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

combine1 и combine2 стоят по четыре такта на элемент во всех четырёх колонках. Операция не имеет значения: время уходит на два вызова за итерацию, len и get, с их проверкой границ и записью через указатель. Вынос длины из условия почти ничего не дал, потому что вызов get остался, а он дороже. В книге этот шаг заметен; на нашем ядре с его дешёвыми вызовами разницу съедает шум.

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

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

частота ядра по калибровке: 1.37 ГГц
счётчик ticks(): 1000.00 МГц

границы, тактов на операцию
операция  задержка  пропускная
i64+          0.53        0.15
i64*          1.60        0.25
f64+          1.18        0.19
f64*          2.05        0.18

CPE по версиям
версия      i64+     i64*     f64+     f64*   шум
combine1    2.52    2.60    2.72    2.60
combine2    2.65    2.56    2.56    3.47
combine3    0.75    1.58    1.21    2.46

худший шум серии: 907.3 процентов

Этот вывод неверен весь, и измеритель сам об этом сообщает: шум девятьсот процентов означает, что медиана в десять раз больше минимума, то есть большинство прогонов были прерваны. Но обрати внимание, как именно он неверен. Калибровку тоже прерывали, лучшая из пяти попыток оказалась втрое медленнее настоящей, и «частота» вышла 1.37 ГГц. Дальше все времена делились на эту заниженную частоту, и все CPE съехали вниз в те же три раза: задержка сложения целых стала полтакта, что физически невозможно. Отношения между строками при этом почти сохранились. Отсюда два правила. Перед тем как читать таблицу, посмотри на шум и на частоту: если частота не похожа на паспортную, а шум больше двадцати процентов, не читай дальше, перезапусти на тихой машине. И никогда не сравнивай числа из двух прогонов, между которыми могла измениться калибровка.

Что компилятор сделал с combine3

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

/// combine3 для i64 и сложения, развёрнутая в обычные указатели,
/// чтобы функцию можно было экспортировать и прочитать в objdump.
export fn combine3Add(data: [*]const i64, n: usize, dest: *i64) void {
    dest.* = 0;
    var i: usize = 0;
    while (i < n) : (i += 1) {
        dest.* +%= data[i];
    }
}

$ zig build-obj combine3_asm.zig -O ReleaseFast -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=combine3_asm.o
$ objdump -d combine3_asm.o --no-show-raw-insn

Основной цикл, развёрнутый компилятором по четыре элемента, выглядит так:

      30:   addq    (%rdi,%r8,8), %rcx
      34:   movq    %rcx, (%rdx)
      37:   addq    0x8(%rdi,%r8,8), %rcx
      3c:   movq    %rcx, (%rdx)
      3f:   addq    0x10(%rdi,%r8,8), %rcx
      44:   movq    %rcx, (%rdx)
      47:   addq    0x18(%rdi,%r8,8), %rcx
      4c:   movq    %rcx, (%rdx)
      4f:   addq    $0x4, %r8
      53:   cmpq    %r8, %rsi
      56:   jne     0x30 <combine3Add+0x30>

Задача про сохранение через указатель. В исходнике на каждой итерации написано dest.* +%= data[i]: прочитать dest.*, прибавить, записать. В машинном коде аккумулятор живёт в %rcx, из памяти (%rdx) он не читается ни разу, но записывается туда после каждого сложения. Ответь на три вопроса. Почему компилятор имел право не читать dest.* из памяти? Почему он не имел права убрать запись из цикла и записать один раз в конце? И правилен ли этот код, если dest указывает внутрь data?

Разбор. Читать dest.* не нужно, потому что последнее значение, записанное по (%rdx), компилятор помнит: оно в %rcx, и никто, кроме этого цикла, между записью и следующим чтением память не трогал; сам цикл в неё пишет только по (%rdx). Убрать запись нельзя из-за наложения: если dest совпадает с data[i + 1], то запись меняет следующий читаемый элемент, и загрузка addq 0x8(%rdi,%r8,8), %rcx обязана увидеть свежее значение. Именно поэтому запись стоит перед каждой следующей загрузкой. И да, при наложении код правилен: загрузки всегда читают память после записи, ровно так, как написано в исходнике. Компилятор выжал всё, что мог, не зная адресов: убрал чтение, но оставил запись. Убрать и запись, перенеся аккумулятор в регистр целиком, сможет только человек, который знает, что dest и data не пересекаются. Это combine4, и это тема следующего урока.

Упражнения

CHK-1★

Собери alias_asm.zig под aarch64-linux вместо x86_64-linux и прочитай обе функции. Найди в twiddle1 лишние обращения к памяти и покажи, что noalias убрал их и здесь. Сравни число инструкций с версией для x86-64 и объясни разницу через то, что arm не умеет складывать прямо в память.

CHK-2★★

Напиши функцию scale(dst: []f64, src: []const f64, k: f64), которая пишет в dst[i] значение src[i] * k, в двух вариантах: с noalias на обоих срезах и без. Экспортируй обёртки над сырыми указателями и сравни ассемблер под x86-64 в ReleaseFast. Объясни, почему в варианте без noalias компилятор вставил проверку пересечения диапазонов перед векторным циклом, и что происходит, когда проверка не проходит.

CHK-3★★

Замени в Clock.init цепочку сложений на цепочку умножений и сними частоту. Объясни по таблице границ, почему получилось втрое меньше, и почему калибровать нужно именно сложением. Затем убери blackBox из addChain и посмотри, что калибровка покажет теперь и какой ассемблер получился у цикла.

CHK-4★★

В measure вместо минимума возьми среднее из семи прогонов и пересними CPE combine3 для целых десять раз подряд. Запиши разброс наклона в обоих вариантах. Потом повтори эксперимент в виджете с уровнем шума 30 процентов и убедись, что картина та же: объясни, почему минимум устойчивее среднего, но при этом сам может быть занижен, если серия слишком короткая для часов.

CHK-5★★★

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

CHK-6★★★

Напиши combine3 на C с long *dest и собери через zig cc -O2 -target x86_64-linux. Сравни цикл с Zig-версией из урока. Потом добавь restrict к dest и покажи, что запись ушла из цикла. Объясни, почему в Zig того же эффекта достигает noalias, и почему оба слова это обещание программиста, которое компилятор не проверяет.

Итоги

Оптимизирующий компилятор имеет право на любое преобразование, которое сохраняет поведение при всех входах. Что зависит только от текста, он доведёт до конца сам: свернёт константы, вынесет инварианты, заменит цикл формулой.
Два запрета, которые он не может обойти: наложение указателей и побочные эффекты вызовов. При двух указателях он обязан считать, что они могут совпасть, и после каждой записи заново читать память. При вызове с невидимым телом он обязан оставить все вызовы на своих местах.
noalias в Zig, как restrict в C, снимает первый запрет обещанием программиста. Соврал в обещании, получил тихо неверный результат, как обмен через xor на одном адресе.
Барьеры для измерений: export чтобы читать ассемблер, noinline и @call(.never_inline) чтобы скрыть тело, std.mem.doNotOptimizeAway чтобы результат не выкинули, пустой asm volatile чтобы цепочка операций осталась цепочкой. volatile для регистров устройств, не для бенчмарков.
CPE это наклон прямой «такты от размера входа», а свободный член это накладные расходы. Две версии сравниваются по двум числам, и версия с меньшим CPE может проигрывать на коротких векторах.
Счётчика тактов у программы нет. Частота калибруется цепочкой зависимых целочисленных сложений, по одному такту на каждое; rdtsc и cntvct_el0 это часы с постоянной частотой, а не такты.
Честный замер: разогрев, минимум из серии, шум как расстояние медианы от минимума, прямая по нескольким размерам методом наименьших квадратов. Среднее тянет вверх каждая помеха, минимум помеха не трогает.
Границы операции: задержка на одной цепочке, пропускная способность на шестнадцати. На M4 Max сложение целых стоит один такт задержки и шестую долю такта пропускной способности; умножение целых три такта, дробные операции два с половиной и три с половиной.
combine1 и combine2 стоят четыре такта на элемент независимо от операции: время уходит на вызовы. combine3 ложится ровно на границу задержки: как только вызовы ушли, упор пришёлся в цепочку через аккумулятор.
Бенчмарк под нагрузкой врёт целиком, включая калибровку, и сам об этом сообщает через шум. Сначала смотри на шум и частоту, потом на таблицу.
В combine3 компилятор держит аккумулятор в регистре, но пишет его в память после каждого сложения, потому что dest может указывать внутрь данных. Снять эту запись может только программист.

Дальше

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

домашка

Домашка

Найди в своём коде на любом языке три функции, которые принимают два указателя или два среза, и для каждой опиши, что произойдёт, если обе ссылки укажут на одну память. Одну из них перепиши так, чтобы наложение было безопасным или невозможным по типу.S
Прогони бенчмарк урока на x86-64 Linux (виртуалка или песочница) и сравни калибровку частоты с паспортной. Объясни, откуда взялась разница, если она есть, и как ведёт себя rdtsc на этой машине относительно частоты ядра.S
Сними серию combine3 десять раз подряд: пять на тихой машине и пять во время сборки чего-нибудь большого. Запиши минимум, медиану и шум каждой серии и покажи, какой из показателей пережил нагрузку лучше.M