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

Профилирование и бенчмарки

senior~110 мин

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

Профилирование и бенчмарки

В прошлом уроке ты дошёл до края: аккумуляторов стало столько, что они перестали помещаться в регистры, предсказатель переходов начал ошибаться, а буфер записи выстроил store и load в цепочку. Все эти пять уроков мы смотрели на один цикл под микроскопом и знали заранее, что именно он горячий. В настоящей программе так не бывает. Там десятки функций, и вопрос номер один звучит не «как ускорить этот цикл», а «какой из циклов вообще стоит ускорять». Сегодня мы отвечаем на него инструментами: счётчиками процессора, сэмплирующим профилировщиком, детерминированным подсчётом инструкций и flame graph. Потом разбираем ловушки, из-за которых микробенчмарк врёт, и выводим правило, куда смотреть в первую очередь: закон Амдала. Под конец решаем две домашние задачи книги, которые в прошлых уроках остались открытыми: многочлен быстрее Горнера и префиксная сумма ниже задержки сложения.

Цели урока

Понять разницу между тремя способами узнать, где программа проводит время: счётчики на всю программу (perf stat), сэмплирование стека (perf record) и инструментирование (callgrind), и знать, когда какой брать.
Прочитать perf report и callgrind_annotate на живой программе и увидеть, что доля инструкций и доля времени у одной функции могут отличаться вчетверо.
Построить flame graph из свёрнутых стеков и читать его: ширина плашки это время, верх это где сейчас процессор.
Пройти цикл «профиль, исправление, профиль» на программе с двумя узкими местами и увидеть, как после первого исправления наверх выходит второе.
Сформулировать закон Амдала, посчитать по нему предел ускорения и понять, почему он запрещает оптимизировать наугад.
Перечислить ловушки микробенчмарка: мёртвый код, разогрев, частота ядра, выравнивание, шум и режим сборки, и знать приём против каждой.
Написать многочлен с несколькими независимыми цепочками, у которого CPE ниже задержки умножения, и префиксную сумму ниже задержки сложения, и проверить оба на своём железе.

Идея: сначала профиль, потом оптимизация

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

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

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

Подопытный: частотный словарь

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

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

//! words.zig: частотный словарь. Текст синтетический, чтобы программа
//! была самодостаточной: словарь из случайных слов, поток слов с перекосом
//! в сторону частых, подсчёт в хеш-таблице со списками, сортировка по
//! убыванию частоты. Два переключателя внизу включают исправления из урока.

const std = @import("std");

/// Переключатели урока: сначала оба false, потом по одному.
const better_hash = false;
const better_sort = false;

const word_total = 3_000_000;
const vocabulary_size = 20_000;
const table_size: usize = if (better_hash) 65_536 else 1_021;

const Entry = struct {
    word: []const u8,
    count: u32,
    next: ?*Entry,
};

/// Плохой хеш: сумма байтов. Слова из 4 до 9 строчных букв дают суммы
/// от 388 до 1098, то есть меньше тысячи разных корзин, и все посередине.
noinline fn hashWord(word: []const u8) usize {
    if (better_hash) return std.hash.Fnv1a_32.hash(word) % table_size;
    var h: u32 = 0;
    for (word) |c| h +%= c;
    return h % table_size;
}

const Table = struct {
    buckets: []?*Entry,
    entries: std.ArrayList(Entry) = .empty,

    /// Найти слово или завести новую запись, вернуть счётчик.
    noinline fn bump(self: *Table, gpa: std.mem.Allocator, word: []const u8) !void {
        const slot = hashWord(word);
        var cursor = self.buckets[slot];
        while (cursor) |entry| : (cursor = entry.next) {
            if (std.mem.eql(u8, entry.word, word)) {
                entry.count += 1;
                return;
            }
        }
        const entry = try self.entries.addOne(gpa);
        entry.* = .{ .word = word, .count = 1, .next = self.buckets[slot] };
        self.buckets[slot] = entry;
    }
};

fn byCountDesc(_: void, a: Entry, b: Entry) bool {
    return a.count > b.count;
}

/// Сортировка вставками: квадрат от числа разных слов.
noinline fn sortEntries(entries: []Entry) void {
    if (better_sort) return std.mem.sort(Entry, entries, {}, byCountDesc);
    var i: usize = 1;
    while (i < entries.len) : (i += 1) {
        const key = entries[i];
        var j = i;
        while (j > 0 and entries[j - 1].count < key.count) : (j -= 1) {
            entries[j] = entries[j - 1];
        }
        entries[j] = key;
    }
}

/// Словарь: случайные слова из 4 до 9 букв, и поток слов с перекосом.
noinline fn generate(gpa: std.mem.Allocator, vocab: [][]const u8, stream: []u32) !void {
    var prng = std.Random.DefaultPrng.init(36);
    const rnd = prng.random();
    for (vocab) |*word| {
        const len = rnd.intRangeAtMost(usize, 4, 9);
        const letters = try gpa.alloc(u8, len);
        for (letters) |*c| c.* = rnd.intRangeAtMost(u8, 'a', 'z');
        word.* = letters;
    }
    for (stream) |*index| {
        // Квадрат равномерной величины: малые индексы встречаются чаще.
        const u = rnd.float(f64);
        index.* = @intFromFloat(u * u * @as(f64, @floatFromInt(vocab.len)));
    }
}

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

    const started = std.Io.Timestamp.now(init.io, .awake);

    const vocab = try gpa.alloc([]const u8, vocabulary_size);
    const stream = try gpa.alloc(u32, word_total);
    try generate(gpa, vocab, stream);

    var table = Table{ .buckets = try gpa.alloc(?*Entry, table_size) };
    @memset(table.buckets, null);
    try table.entries.ensureTotalCapacity(gpa, vocabulary_size);
    for (stream) |index| try table.bump(gpa, vocab[index]);

    // Ссылки next после сортировки протухнут, но таблица больше не нужна.
    sortEntries(table.entries.items);

    const ms = @divFloor(started.durationTo(std.Io.Timestamp.now(init.io, .awake)).nanoseconds, std.time.ns_per_ms);
    try out.print("слов {d}, разных {d}, {d} мс\n", .{ word_total, table.entries.items.len, ms });
    for (table.entries.items[0..5]) |entry| try out.print("{s:<10} {d}\n", .{ entry.word, entry.count });
    try out.flush();
}

Функции помечены noinline. Без этого оптимизатор встроит hashWord в bump, а bump в main, и профиль покажет одну плашку main на всю ширину. Для настоящей программы так делать не надо: профилировщик умеет разворачивать встроенные функции по отладочной информации, но нам сегодня нужна картинка без сюрпризов.

Собираем и запускаем. Все прогоны в этом разделе сняты в Linux arm64 в контейнере на том же Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-13. Про то, почему в контейнере, а не в macOS напрямую, отдельная врезка ближе к концу.

zig build-exe words.zig -O ReleaseFast
./words

слов 3000000, разных 19986, 2833 мс
iyvqhvtpl  21028
rmneypcit  8856
sqalcoyd   6801
oabrz      5734
lpve       4991

Почти три секунды на три миллиона слов, по микросекунде на слово. Для программы, которая складывает байты и сравнивает строки, это слишком много. Где эти три секунды?

perf stat: счётчики на всю программу

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

perf stat -e task-clock,context-switches,page-faults,cycles,instructions,branches,branch-misses,cache-misses ./words

 Performance counter stats for './words':

           2795.04 msec task-clock                       #    0.999 CPUs utilized
                 4      context-switches                 #    1.431 /sec
               868      page-faults                      #  310.551 /sec
   <not supported>      cycles
   <not supported>      instructions
   <not supported>      branches
   <not supported>      branch-misses
   <not supported>      cache-misses

       2.797446092 seconds time elapsed

       2.787116000 seconds user
       0.009333000 seconds sys

Честный вывод из виртуальной машины: аппаратных счётчиков в ней нет, гипервизор их не пробрасывает, и perf пишет not supported. Программные события на месте: task-clock говорит, что процессор был занят программой почти сто процентов времени, четыре переключения контекста и восемьсот страниц памяти за три секунды это ничто. Уже полезно: узкое место не в ожидании ввода-вывода и не в планировщике, а в самом коде.

На настоящем Linux x86-64 те же пять строк заполнены числами, и читать их надо парами. Главная пара это cycles и instructions: их отношение, инструкций на такт, perf печатает в комментарии справа как insn per cycle. Это IPC, обратная величина к CPI из урока про конвейер и CPI. Наш bump ходит по спискам указателей, и на голом железе он показал бы IPC заметно ниже единицы: каждая следующая запись списка ждёт загрузку предыдущей. Две другие пары:

branches и branch-misses. Доля промахов выше двух или трёх процентов на программе, где ветвления в каждой итерации, означает, что предсказатель проигрывает, и вспоминается cmov из прошлого урока.
cache-misses вместе с cache-references. Сколько обращений ушло мимо кэша последнего уровня. Это тема следующих уроков про память, но счётчик уже сейчас подскажет, что программа упирается в память, а не в АЛУ.

Чего perf stat не скажет никогда: где именно. Это одно число на всю программу. Чтобы найти место, нужен следующий инструмент.

perf record и perf report: где процессор прямо сейчас

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

perf record -F 999 -g -o perf.data ./words
perf report -i perf.data --stdio --no-children

Флаг -F 999 задаёт частоту выборок, 999 в секунду, не круглое число, чтобы не попасть в резонанс с каким-нибудь таймером самой программы. Флаг -g просит записывать стек вызовов целиком, без него ты узнаешь, что время в std.mem.eql, но не узнаешь, кто её звал.

# Samples: 2K of event 'cpu-clock:pppH'
# Event count (approx.): 2183183181
#
# Overhead  Command  Shared Object      Symbol
# ........  .......  .................  ...............................
#
    79.78%  words    words              [.] words.Table.bump
            |
            ---words.Table.bump
               |
                --79.60%--words.Table.bump
                          main
                          __libc_start_call_main
                          __libc_start_main@@GLIBC_2.34
                          _start

    13.20%  words    words              [.] words.hashWord
            |
            ---words.hashWord
               words.Table.bump
               |
                --13.16%--words.Table.bump
                          main
                          __libc_start_call_main
                          __libc_start_main@@GLIBC_2.34
                          _start

     5.87%  words    words              [.] words.sortEntries
            |
            ---words.sortEntries
               main
               main
               __libc_start_call_main
               __libc_start_main@@GLIBC_2.34
               _start

     0.55%  words    words              [.] main
     0.41%  words    words              [.] words.generate

Событие называется cpu-clock, а не cycles: в виртуальной машине выборки идут по программному таймеру, а на голом железе perf взял бы аппаратный счётчик тактов. На распределение это не влияет.

Читаем. Восемьдесят процентов времени в bump, ещё тринадцать в hashWord, которую bump зовёт. Сортировка, на которую я тебя настраивал в начале урока, забирает шесть процентов. Флаг --no-children важен: с ним процент считается по тому, где процессор был в момент выборки (self), а не по всему поддереву вызовов. С флагом --children main показал бы сто процентов, и это тоже правда, но бесполезная.

Куда именно в bump уходит время, perf annotate покажет по инструкциям, но мы и так знаем ответ по коду: обход списка со сравнением строк. Со списком длиной в десятки записей на каждое из трёх миллионов слов это сотня миллионов вызовов std.mem.eql, и каждый сравнивает строки, которые лежат в разных местах кучи.

callgrind: инструкции, посчитанные точно

У сэмплирования есть слабость: две тысячи выборок это статистика, и функция на полпроцента в ней или есть, или нет. Есть другой способ, полная противоположность: инструментирование. valgrind --tool=callgrind не запускает программу на процессоре, а исполняет её на своей виртуальной машине и считает каждую инструкцию. Замедление в тридцать, а то и в пятьдесят раз, зато результат детерминированный до последней инструкции и не зависит от шума, частоты и соседей.

valgrind --tool=callgrind --callgrind-out-file=callgrind.out ./words
callgrind_annotate callgrind.out

==3961== Collected : 2890340277
==3961== I   refs:      2,890,340,277

--------------------------------------------------------------------------------
Ir                      file:function
--------------------------------------------------------------------------------
1,429,859,543 (49.47%)  /opt/zig/lib/std/mem.zig:words.Table.bump'2
  684,737,733 (23.69%)  words.zig:words.sortEntries'2 [/w/words]
  578,435,669 (20.01%)  words.zig:words.Table.bump'2 [/w/words]
  122,823,048 ( 4.25%)  words.zig:words.hashWord [/w/words]
   24,589,998 ( 0.85%)  words.zig:words.generate'2
   22,129,051 ( 0.77%)  /opt/zig/lib/std/Random/Xoshiro256.zig:words.generate'2 [/w/words]

Почти три миллиарда инструкций. Ir это instruction reads, число выполненных инструкций, и callgrind_annotate раскладывает его по парам файл и функция: половина всех инструкций это std.mem.eql, встроенная в bump (первая строка ссылается на mem.zig), ещё пятая часть сам bump, обход списка.

А теперь положи два отчёта рядом. У sortEntries 23.7 процента инструкций и 5.9 процента времени. У bump вместе с eql 69.5 процента инструкций и 79.8 процента времени. Одна инструкция сортировки вставками стоит вчетверо дешевле одной инструкции обхода списка. Причина в том, что сортировка двигает соседние элементы массива, они лежат подряд, предсказатель переходов угадывает почти всё, и ядро проглатывает по три-четыре инструкции за такт. Обход списка каждый шаг ждёт загрузку указателя из случайного места кучи. Это и есть разница между «сколько инструкций» и «сколько тактов», и это причина, по которой callgrind один, без perf, вводит в заблуждение на программах, ограниченных памятью.

Зато callgrind умеет то, чего не умеет perf: аннотировать исходник построчно с точным числом инструкций. Кусок из того же отчёта:

-- Auto-annotated source: words.zig
Ir
          .           noinline fn hashWord(word: []const u8) usize {
          .               if (better_hash) return std.hash.Fnv1a_32.hash(word) % table_size;
          .               var h: u32 = 0;
 89,823,048 ( 3.11%)      for (word) |c| h +%= c;
 33,000,000 ( 1.14%)      return h % table_size;
          .           }

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

Flame graph: тот же профиль, но видно сразу

perf report со стеками вызовов читается тяжело уже на десяти функциях. Брендан Грегг придумал для профилей картинку, которая с тех пор стала стандартом: flame graph. Строится он в два шага. Первый: свёрнутые стеки, folded stacks. Второй: скрипт flamegraph.pl, который превращает их в SVG.

git clone https://github.com/brendangregg/FlameGraph
perf script -i perf.data | FlameGraph/stackcollapse-perf.pl > folded.txt
FlameGraph/flamegraph.pl folded.txt > words.svg

Свёрнутые стеки нашей программы, отсортированные по числу выборок:

_start;__libc_start_main@@GLIBC_2.34;__libc_start_call_main;main;words.Table.bump;words.Table.bump 1736
_start;__libc_start_main@@GLIBC_2.34;__libc_start_call_main;main;words.Table.bump;words.Table.bump;words.hashWord 287
_start;__libc_start_main@@GLIBC_2.34;__libc_start_call_main;main;main;words.sortEntries 128
_start;__libc_start_main@@GLIBC_2.34;__libc_start_call_main;main;main 12
_start;__libc_start_main@@GLIBC_2.34;__libc_start_call_main;main;words.generate;words.generate 9

Кадр bump встречается дважды подряд, и main тоже: так perf разворачивает встроенные вызовы по отладочной информации, внешний кадр это место вызова, внутренний это тело. Числа справа в сумме дают 2181: все выборки прогона.

В SVG каждая строка становится столбиком плашек снизу вверх: _start в самом низу на всю ширину, над ним main, над ним bump шириной в 93 процента и sortEntries шириной в 6, над bump узкая плашка hashWord. Правила чтения три. Ширина плашки это доля времени в ней и во всём, что над ней. Верхняя плашка любого столбика это то, где процессор был в момент выборки. Порядок по горизонтали ничего не значит, плашки отсортированы по алфавиту, чтобы одинаковые стеки слились. Цвет тоже ничего не значит, это тёплые оттенки, отсюда и название.

Смотреть на flame graph надо не сверху и не снизу, а на самое широкое плато: широкая плашка, над которой ничего нет, это функция, которая жжёт время сама, а не через вызовы. У нас это bump. Широкая плашка, над которой много узких, это функция-диспетчер, которая сама дешёвая, но зовёт дорогое, там оптимизировать надо не её.

Чиним по профилю, а не по интуиции

Профиль сказал: bump и hashWord, вместе девяносто три процента. Сортировку не трогаем. В bump ничего не сломано, он честно идёт по списку; сломан хеш, который складывает двадцать тысяч слов в семьсот корзин. Включаем первый переключатель: Fnv1a_32 из стандартной библиотеки и таблица на 65 536 корзин.

const better_hash = true;
const better_sort = false;

слов 3000000, разных 19986, 108 мс
iyvqhvtpl  21028
rmneypcit  8856
sqalcoyd   6801
oabrz      5734
lpve       4991

Двадцать шесть раз. Тот же ответ, те же слова, а из 2833 миллисекунд осталось 108. Снимаем профиль заново, потому что старый уже ничего не значит:

    51.33%  words_v2  words_v2       [.] words_v2.sortEntries
    24.78%  words_v2  words_v2       [.] words_v2.hashWord
    18.58%  words_v2  words_v2       [.] words_v2.Table.bump
     2.65%  words_v2  words_v2       [.] words_v2.generate

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

const better_hash = true;
const better_sort = true;

слов 3000000, разных 19986, 61 мс

версия	что изменили	время	инструкций	верх профиля
1	как есть	2795 мс	2.89 млрд	`bump` 80 %, `hashWord` 13 %, `sortEntries` 6 %
2	FNV и 65 536 корзин	108 мс	1.05 млрд	`sortEntries` 51 %, `hashWord` 25 %, `bump` 19 %
3	плюс `std.mem.sort`	61 мс	0.37 млрд	`hashWord` 59 %, `bump` 31 %

Времена это task-clock из perf stat, инструкции это Ir из callgrind. Итого сорок шесть раз, и ни одного цикла мы не развернули. Третий профиль говорит, что теперь программа на две трети состоит из хеширования и поиска; если хочется ещё быстрее, дальше идти в hashWord, и тут уже пригодится всё, что было в пяти прошлых уроках. Но заметь, с какой стороны мы к этому пришли: снаружи, от профиля, а не изнутри, от цикла.

Закон Амдала: куда смотреть в первую очередь

Теперь формула, которая объясняет и три с половиной минуты из начала урока, и наши сорок шесть раз. Пусть одна часть программы занимает долю α времени, и её мы ускорили в k раз. Остальная программа, доля 1 − α, работает как работала. Новое время в долях старого это (1 − α) + α / k, а ускорение всей программы это обратная величина:

S = 1 / ((1 − α) + α / k)

Пример из книги: часть занимает 60 процентов времени, её ускорили втрое. S = 1 / (0.4 + 0.2) = 1.67. Не втрое, а на две трети. А теперь устреми k в бесконечность: слагаемое α / k исчезает, и остаётся S = 1 / (1 − α), для тех же 60 процентов это 2.5. Сколько ни ускоряй часть, программа быстрее, чем в 2.5 раза, не станет. Это и есть закон Амдала, и его вторая половина важнее первой: предел ускорения задаёт не то, насколько хороша оптимизация, а то, какую долю времени занимала часть до неё.

Отсюда и правило, куда смотреть. Функция на пять процентов профиля даёт предел 1.05, что бы ты с ней ни сделал. Функция на девяносто три процента даёт предел четырнадцать. Значит первым делом смотрим на самую широкую плашку, и только когда она сжалась, на следующую. Именно это мы только что проделали руками: у bump с hashWord было 93 процента, у сортировки 6, и трогать сортировку первой было бы ошибкой, хотя её код тоже плохой.

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

Закон Амдала работает и в обратную сторону, как проверка честности. Если профиль показал 93 процента в bump, а ты после исправления получил ускорение в двадцать шесть раз, значит bump ускорился не в двадцать шесть раз, а куда сильнее: 2795 мс на 108 это S = 25.9, из формулы 1 / (0.07 + 0.93 / k) = 25.9 следует k около трёхсот. Это правдоподобно: списки стали в шестьдесят раз короче, а сравнений строк в них ещё меньше, потому что Fnv1a разводит похожие слова по разным корзинам. Если бы формула дала k = 2, можно было бы искать ошибку в измерении.

Микробенчмарки и их ловушки

Профиль сказал, где. Теперь нужно мерить один кусок кода изолированно, чтобы сравнивать варианты, и здесь начинаются ловушки. Каждая из них хотя бы раз давала кому-то результат «ускорил в сто раз», который на деле означал «ничего не измерил».

Мёртвый код

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

//! Мёртвый код: оптимизатор выкидывает работу, результат которой никто не
//! читает, а цикл с замкнутой формулой заменяет формулой. Три замера.

const std = @import("std");

/// Линейный конгруэнтный генератор: замкнутой формулы у него нет.
fn churn(n: u64) u64 {
    var acc: u64 = 1;
    var i: u64 = 0;
    while (i < n) : (i += 1) acc = acc *% 6364136223846793005 +% i;
    return acc;
}

/// Сумма квадратов: у неё замкнутая формула есть, и LLVM её знает.
fn squares(n: u64) u64 {
    var acc: u64 = 0;
    var i: u64 = 0;
    while (i < n) : (i += 1) acc +%= i * i;
    return acc;
}

fn elapsedMs(io: std.Io, started: std.Io.Timestamp) f64 {
    const ns: f64 = @floatFromInt(started.durationTo(std.Io.Timestamp.now(io, .awake)).nanoseconds);
    return ns / 1e6;
}

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

    // 1. Результат не используется: цикла в бинарнике нет.
    var t = std.Io.Timestamp.now(init.io, .awake);
    _ = churn(n);
    try out.print("churn, результат выброшен:     {d:8.2} мс\n", .{elapsedMs(init.io, t)});

    // 2. Результат защищён: сто миллионов итераций выполняются честно.
    t = std.Io.Timestamp.now(init.io, .awake);
    std.mem.doNotOptimizeAway(churn(n));
    try out.print("churn, doNotOptimizeAway:      {d:8.2} мс\n", .{elapsedMs(init.io, t)});

    // 3. Результат защищён, но цикла всё равно нет: его заменила формула.
    t = std.Io.Timestamp.now(init.io, .awake);
    std.mem.doNotOptimizeAway(squares(n));
    try out.print("squares, doNotOptimizeAway:    {d:8.2} мс\n", .{elapsedMs(init.io, t)});
    try out.flush();
}

churn, результат выброшен:         0.00 мс
churn, doNotOptimizeAway:        223.47 мс
squares, doNotOptimizeAway:        0.00 мс

Снято на Apple M4 Max, ReleaseFast. Первая строка: сто миллионов итераций за ноль, потому что итераций нет. std.mem.doNotOptimizeAway это пустой asm volatile, который «читает» значение: компилятор обязан его вычислить, и вторая строка показывает настоящую цену. Третья строка коварнее: результат защищён, а цикла всё равно нет. LLVM узнал сумму квадратов и заменил её замкнутой формулой. Вот squares целиком в ассемблере x86-64, без единого перехода назад:

squares:
        test    rdi, rdi
        je      .LBB0_1
        lea     rax, [rdi - 1]
        lea     rcx, [rdi - 2]
        mul     rcx
        lea     rcx, [rdi - 3]
        imul    rcx, rax
        shr     rcx
        movabs  rsi, 6148914691236517206
        imul    rsi, rcx
        add     rsi, rdi
        shld    rdx, rax, 63
        lea     rax, [rdx + 2*rdx]
        add     rax, rsi
        add     rax, -1
        ret
.LBB0_1:
        xor     eax, eax
        ret

Умножение на 6148914691236517206 это деление на три через обратную величину, а всё вместе это n(n − 1)(2n − 1) / 6 по модулю 2⁶⁴. Отсюда два правила. Защищай не только выход, но и вход: если n или данные известны компилятору как константы, он вправе досчитать ответ при сборке. В harness из первого урока для этого есть blackBox, пустой asm с операндом «прочитай и запиши», после которого значение считается неизвестным. И всегда смотри в ассемблер, когда число получилось слишком хорошим: ноль миллисекунд это не рекорд, это диагноз.

Разогрев, минимум и шум

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

Дальше вопрос, какое число из серии считать ответом. Среднее плохо: шум только добавляет время, никогда не убавляет (прерывание, переезд на другое ядро, сосед, который вытеснил твои данные из кэша), и распределение получается с тяжёлым правым хвостом, который среднее тянет вверх. Минимум из серии ближе всего к «чистой» работе ядра, а расстояние между медианой и минимумом это оценка шума. В первом уроке про CPE ты видел это на графике: минимум из семи прогонов возвращает наклон прямой на место даже при десяти процентах фона. Дальше в уроке ты увидишь, что даже так серия от серии расходится на десять процентов, если рядом что-то собирается. Это не ошибка измерителя, это оценка того, чему верить.

Частота ядра

Такт это не единица времени. Ядро под нагрузкой разгоняется, под нагревом сбрасывает частоту, ноутбук от батареи живёт на другой ступени, а на Apple Silicon ещё и два вида ядер с разной частотой. Секундомер даёт наносекунды, а CPE нужен в тактах, и пересчёт зависит от того, какая частота была именно в эти наносекунды. Счётчик rdtsc не спасает: на современных процессорах он идёт с постоянной частотой, а не в такт ядру.

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

Выравнивание

Есть работа Mytkowicz и соавторов с названием «Producing Wrong Data Without Doing Anything Obviously Wrong». Они показали, что размер переменных окружения или порядок объектных файлов при линковке меняют время программ из набора SPEC на десятки процентов, потому что сдвигают адреса стека и горячих циклов, а от адреса зависит, попал ли цикл в одну строку кэша инструкций и как легли переходы для предсказателя. Вывод не в том, что мерить бесполезно, а в том, что разница в пять процентов между двумя вариантами ничего не значит, пока ты не проверил, что она переживает перестановку функций местами и запуск в другом каталоге. Разница вдвое переживает.

ReleaseFast против Debug

Это самая частая ошибка, и она встречается и у людей с опытом. В Debug Zig проверяет каждое переполнение, каждый индекс и каждое разыменование, не встраивает функции и держит переменные в памяти. Тот же микробенчмарк, что ниже даст 3.5 такта на элемент, в Debug печатает вот что:

режим Debug, частота по калибровке 0.23 ГГц
версия    CPE
poly           0.99
horner         0.78
fast           0.63

Число 0.23 ГГц это первый звонок: калибровочная цепочка в Debug идёт не по такту на сложение, а по двадцать, и все дальнейшие «такты» посчитаны в неправильных единицах. В Debug можно проверять правильность, мерить нельзя, поэтому build.zig эталона собирает бенч в ReleaseFast независимо от -Doptimize, и поэтому в листинге ниже режим печатается первой строкой.

Домашняя 5.18: многочлен ниже задержки умножения

Теперь две задачи книги, для которых у нас наконец есть и модель, и измеритель. Многочлен a₀ + a₁x + … + aₙxⁿ мы считали в уроке про вынос из цикла двумя способами. В лоб: result += a[i] * xpwr; xpwr *= x, два умножения на элемент. По Горнеру: result = a[i] + x * result от старшего коэффициента, одно умножение и одно сложение. Горнер делает меньше работы и оказывается медленнее, и после урока про критический путь ты знаешь почему: у Горнера умножение и сложение сидят в одной цепочке, критический путь на элемент это L_mul + L_add, на нашем железе 3.42 + 2.49. В лоб две цепочки, result и xpwr, и в каждой по одной операции на элемент; длинная из них это xpwr *= x, L_mul = 3.42.

Задача книги: написать версию, у которой критический путь короче обоих. Идея: разбить многочлен по чётности степеней. Любой многочлен это E(x²) + x · O(x²), где E собран из чётных коэффициентов, O из нечётных, и оба вдвое короче. Две схемы Горнера по x², независимые друг от друга, и одно объединение в конце:

/// Две схемы Горнера по x², одна на чётных коэффициентах, другая на
/// нечётных, и одно объединение в конце. Цепочек две, значит критический
/// путь на элемент вдвое короче Горнера.
pub fn polyFast(a: []const f64, x: f64) f64 {
    const xx = x * x;
    var even: f64 = 0;
    var odd: f64 = 0;
    var i: usize = a.len;
    // Хвост из одного коэффициента, чтобы дальше шагать парами.
    if (i % 2 == 1) {
        i -= 1;
        even = a[i];
    }
    while (i > 0) {
        i -= 2;
        even = a[i] + xx * even;
        odd = a[i + 1] + xx * odd;
    }
    return even + x * odd;
}

test "polyFast: пустой набор, один и нечётное число коэффициентов" {
    const empty = [_]f64{};
    try std.testing.expectEqual(@as(f64, 0), polyFast(&empty, 2));
    const one = [_]f64{7};
    try std.testing.expectEqual(@as(f64, 7), polyFast(&one, 2));
    // 1 + 2x + 3x² в точке 2: 1 + 4 + 12
    const three = [_]f64{ 1, 2, 3 };
    try std.testing.expectEqual(@as(f64, 17), polyFast(&three, 2));
}

const std = @import("std");

На бумаге: за итерацию два элемента, в каждой цепочке умножение и сложение, критический путь (3.42 + 2.49) / 2 = 2.96 такта на элемент. Ниже Горнера (5.91) и ниже версии в лоб (3.42). Теперь измеряем. Вот harness целиком, тот самый минимум, который нужен честному микробенчмарку: калибровка частоты, разогрев, минимум из серии, повторы для коротких вызовов, doNotOptimizeAway на выходе и CPE как наклон между n и 2n, чтобы накладные расходы вызова сократились. Кроме polyFast в нём уже лежит версия с четырьмя цепочками, о которой чуть ниже, и обе префиксные суммы для следующей задачи.

//! Микробенчмарк многочлена и префиксной суммы: CPE через разность двух
//! размеров. Всё, что нужно честному замеру, здесь на виду: калибровка
//! частоты, разогрев, минимум из серии, blackBox против мёртвого кода.

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

// ---- подопытные -----------------------------------------------------------

/// В лоб: две независимые цепочки, result и xpwr.
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;
}

/// По Горнеру: одна цепочка, умножение и сложение друг за другом.
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;
}

/// Две схемы Горнера по x², чётные и нечётные коэффициенты отдельно.
fn polyFast(a: []const f64, x: f64) f64 {
    const xx = x * x;
    var even: f64 = 0;
    var odd: f64 = 0;
    var i: usize = a.len;
    if (i % 2 == 1) {
        i -= 1;
        even = a[i];
    }
    while (i > 0) {
        i -= 2;
        even = a[i] + xx * even;
        odd = a[i + 1] + xx * odd;
    }
    return even + x * odd;
}

/// Четыре цепочки: две схемы Горнера по x⁴ на каждой чётности, склейка в конце.
fn polyFast4(a: []const f64, x: f64) f64 {
    const xx = x * x;
    const x4 = xx * xx;
    var c0: f64 = 0;
    var c1: f64 = 0;
    var c2: f64 = 0;
    var c3: f64 = 0;
    var i: usize = a.len;
    while (i % 4 != 0) {
        i -= 1;
        c0 = a[i] + x4 * c0;
        // Сдвинуть роли: c0 всегда принимает самый старший из оставшихся.
        const t = c3;
        c3 = c2;
        c2 = c1;
        c1 = c0;
        c0 = t;
    }
    while (i > 0) {
        i -= 4;
        c0 = a[i] + x4 * c0;
        c1 = a[i + 1] + x4 * c1;
        c2 = a[i + 2] + x4 * c2;
        c3 = a[i + 3] + x4 * c3;
    }
    return (c0 + xx * c2) + x * (c1 + xx * c3);
}

/// Префиксная сумма с аккумулятором в регистре: одно сложение на элемент в цепочке.
fn psum(a: []const f64, p: []f64) void {
    if (a.len == 0) return;
    var last = a[0];
    p[0] = last;
    var i: usize = 1;
    while (i < a.len) : (i += 1) {
        last += a[i];
        p[i] = last;
    }
}

/// Префиксная сумма ниже задержки сложения: в цепочку попадает одно
/// сложение на два элемента.
fn sumFast(a: []const f64, p: []f64) void {
    if (a.len == 0) return;
    var last = a[0];
    p[0] = last;
    var i: usize = 1;
    while (i + 1 < a.len) : (i += 2) {
        const pair = a[i] + a[i + 1];
        p[i] = last + a[i];
        last = last + pair;
        p[i + 1] = last;
    }
    while (i < a.len) : (i += 1) {
        last += a[i];
        p[i] = last;
    }
}

// ---- измеритель -----------------------------------------------------------

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

const calibration_adds: usize = 200_000_000;

/// Частота ядра: n зависимых целочисленных сложений это ровно n тактов.
fn calibrateGhz(io: std.Io) f64 {
    var best_ns: f64 = std.math.inf(f64);
    var attempt: usize = 0;
    while (attempt < 5) : (attempt += 1) {
        var acc: u64 = 1;
        const step: u64 = blackBox(@as(u64, 7));
        const started = std.Io.Timestamp.now(io, .awake);
        var i: usize = 0;
        while (i < calibration_adds) : (i += 1) acc = blackBox(acc +% step);
        const ns: f64 = @floatFromInt(started.durationTo(std.Io.Timestamp.now(io, .awake)).nanoseconds);
        std.mem.doNotOptimizeAway(acc);
        best_ns = @min(best_ns, ns);
    }
    return @as(f64, @floatFromInt(calibration_adds)) / best_ns;
}

const warmup = 2;
const runs = 15;
const work = 1_000_000;

/// Минимальное время одного вызова ctx.run(n) в наносекундах.
fn minNs(io: std.Io, ctx: anytype, n: usize) f64 {
    const reps = @max(1, work / n);
    var best: f64 = std.math.inf(f64);
    var run: usize = 0;
    while (run < warmup + runs) : (run += 1) {
        const started = std.Io.Timestamp.now(io, .awake);
        var rep: usize = 0;
        while (rep < reps) : (rep += 1) ctx.run(n);
        const ns: f64 = @floatFromInt(started.durationTo(std.Io.Timestamp.now(io, .awake)).nanoseconds);
        if (run >= warmup) best = @min(best, ns / @as(f64, @floatFromInt(reps)));
    }
    return best;
}

/// CPE как наклон между n и 2n: накладные расходы вызова сокращаются.
fn cpe(io: std.Io, ghz: f64, ctx: anytype, n: usize) f64 {
    const small = minNs(io, ctx, n);
    const large = minNs(io, ctx, 2 * n);
    return (large - small) * ghz / @as(f64, @floatFromInt(n));
}

const Kind = enum { poly, horner, fast, fast4, psum, sum_fast };

fn Runner(comptime kind: Kind) type {
    return struct {
        a: []const f64,
        p: []f64,
        x: f64,

        pub fn run(self: @This(), n: usize) void {
            const a = self.a[0..n];
            switch (kind) {
                .poly => std.mem.doNotOptimizeAway(poly(a, self.x)),
                .horner => std.mem.doNotOptimizeAway(polyHorner(a, self.x)),
                .fast => std.mem.doNotOptimizeAway(polyFast(a, self.x)),
                .fast4 => std.mem.doNotOptimizeAway(polyFast4(a, self.x)),
                .psum => psum(a, self.p[0..n]),
                .sum_fast => sumFast(a, self.p[0..n]),
            }
            std.mem.doNotOptimizeAway(self.p[0]);
        }
    };
}

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

    const n: usize = 1024;
    const a = try gpa.alloc(f64, 2 * n);
    const p = try gpa.alloc(f64, 2 * n);
    for (a, 0..) |*c, i| c.* = 1.0 + @as(f64, @floatFromInt(i % 3)) / 1024.0;

    const ghz = calibrateGhz(init.io);
    try out.print("режим {s}, частота по калибровке {d:.2} ГГц\n", .{ @tagName(builtin.mode), ghz });
    try out.print("{s:<12} {s:>6}\n", .{ "версия", "CPE" });
    inline for ([_]Kind{ .poly, .horner, .fast, .fast4, .psum, .sum_fast }) |kind| {
        const runner = Runner(kind){ .a = a, .p = p, .x = 1.0009765625 };
        try out.print("{s:<12} {d:>6.2}\n", .{ @tagName(kind), cpe(init.io, ghz, runner, n) });
    }
    try out.flush();
}

zig build-exe bench_poly.zig -O ReleaseFast
./bench_poly

режим ReleaseFast, частота по калибровке 4.48 ГГц
версия    CPE
poly           3.52
horner         5.95
fast           5.08
fast4          2.47
psum           1.96
sum_fast       1.54

Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-13; коэффициенты около единицы, x тоже, чтобы не уйти в бесконечность на тысяче степеней. Три повторных запуска той же программы дали horner от 5.1 до 5.9, fast от 4.1 до 5.1, fast4 от 2.0 до 2.5: рядом собирались другие проекты, и это та самая оценка шума из раздела про ловушки. Но картина устойчива, и в ней сюрприз. poly и horner легли туда, куда должны: 3.5 против границы 3.42, и 5 с лишним против 5.91. А polyFast дал не 2.96, а больше четырёх, хуже версии в лоб.

Когда число не сходится с моделью, смотрим в ассемблер. Цикл polyFast для aarch64:

LBB2_4:
        fmul.2d v1, v1, v2[0]
        ldr     q3, [x8], #-16
        fadd.2d v1, v1, v3
        subs    x1, x1, #2
        b.ne    LBB2_4

И для x86-64, если собрать с -target x86_64-linux:

.LBB2_3:
        mulpd   xmm1, xmm2
        movupd  xmm3, xmmword ptr [rdi + 8*rsi - 16]
        addpd   xmm1, xmm3
        add     rsi, -2
        jne     .LBB2_3

Компилятор увидел две одинаковые цепочки на соседних элементах и упаковал их в один векторный регистр: fmul.2d и mulpd умножают две дорожки сразу. Инструкций стало вдвое меньше, и с точки зрения счётчика инструкций это победа. Но обе цепочки теперь идут через один регистр, и задержка векторного умножения плюс векторного сложения на этой машине выходит около восьми тактов на пару элементов, больше, чем скалярных 5.91. Это ровно тот случай из урока про развёртывание, когда оптимизатор помогает пропускной способности и вредит задержке, и без измерения ты бы его не заметил.

Лекарство то же, что и всегда: больше независимых цепочек, чем помещается в один вектор. polyFast4 раскладывает многочлен по остатку степени от деления на четыре, ведёт четыре схемы Горнера по x⁴ и склеивает их двумя умножениями в конце. Векторизатор снова упакует их по две, но теперь векторных цепочек две и они независимы, критический путь на элемент это восемь тактов на четыре элемента. Измерение: 2.47, ниже границы задержки умножения 3.42. Задача книги решена, но не той версией, которую подсказывал бумажный расчёт, а следующей за ней, и разницу между ними показал только бенчмарк.

Домашняя 5.19: сумма ниже задержки сложения

Префиксная сумма p[i] = p[i − 1] + a[i] из урока про модель процессора упиралась в чтение из памяти, и версия с аккумулятором в регистре опустила её до одного сложения на элемент в цепочке, то есть до границы задержки сложения. Задача книги: опуститься ниже. Казалось бы, некуда: каждая сумма зависит от предыдущей по определению.

Приём тот же, что и у многочлена: найти работу, которая не зависит от аккумулятора, и вынести её из цепочки. За итерацию берём два элемента. Сумма пары a[i] + a[i + 1] от аккумулятора не зависит и считается сбоку. Тогда p[i] = last + a[i] тоже уходит сбоку, а в цепочку попадает одно сложение на два элемента: last = last + pair.

/// Префиксная сумма ниже задержки сложения. За итерацию два элемента:
/// `p[i] = last + a[i]` и `p[i+1] = last + (a[i] + a[i+1])`. Сумма пары
/// не зависит от `last`, поэтому в цепочку аккумулятора за два элемента
/// попадает одно сложение, и CPE опускается до половины задержки.
pub fn sumFast(a: []const f64, p: []f64) void {
    if (a.len == 0) return;
    var last = a[0];
    p[0] = last;
    var i: usize = 1;
    while (i + 1 < a.len) : (i += 2) {
        const pair = a[i] + a[i + 1];
        p[i] = last + a[i];
        last = last + pair;
        p[i + 1] = last;
    }
    while (i < a.len) : (i += 1) {
        last += a[i];
        p[i] = last;
    }
}

test "sumFast совпадает с наивной суммой на чётной и нечётной длине" {
    const a = [_]f64{ 1, 2, 3, 4, 5 };
    var p: [5]f64 = undefined;
    sumFast(&a, &p);
    try std.testing.expectEqualSlices(f64, &[_]f64{ 1, 3, 6, 10, 15 }, &p);
    var q: [4]f64 = undefined;
    sumFast(a[0..4], &q);
    try std.testing.expectEqualSlices(f64, &[_]f64{ 1, 3, 6, 10 }, &q);
}

const std = @import("std");

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

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

Обрати внимание на само число 1.96 у psum: оно ниже границы задержки сложения 2.49, которую harness снял на цепочке acc = acc + x. Один такой замер ничего не доказывает, но повод для вопроса даёт, и правильный следующий шаг тот же, что был с polyFast: посмотреть в ассемблер цикла и понять, что там сделал компилятор. Оставляю это тебе в упражнениях.

На macOS

Всё, что выше, снято в Linux, и это не случайность. На macOS нет ни perf, ни valgrind (для Apple Silicon он так и не портирован). Аналоги есть, и они неплохие, но другие:

sample <pid> <секунд> это встроенный сэмплирующий профилировщик из командной строки: снимает стеки раз в миллисекунду и печатает дерево вызовов текстом. Достаточно для первого взгляда. В этом уроке он не показан, потому что в песочнице, где готовился урок, ему не дали читать память процесса; на обычной машине он работает без прав.
xctrace record --template 'Time Profiler' --launch ./words пишет трассу для Instruments, графического профилировщика из Xcode. Открой .trace, и там будет тот же flame graph, только с зумом. Инструмент «Counters» в Instruments умеет и аппаратные счётчики, но только на своём железе Apple.
Linux-инструменты через контейнер. Именно так сняты числа урока: docker run --platform linux/arm64 -v "$PWD:/w" -w /w debian:bookworm, внутри apt-get install valgrind linux-perf и тарбол Zig для aarch64-linux. Контейнер на Apple Silicon это виртуальная машина, поэтому perf stat увидит только программные события, а perf record возьмёт cpu-clock вместо cycles; распределение по функциям при этом настоящее. callgrind от виртуализации не зависит вообще: он сам себе процессор. Для perf record контейнеру нужен флаг --privileged, иначе ядро откажет в perf_event_open.

Прогонять код на x86-64 в контейнере тоже можно, через --platform linux/amd64, но это уже эмуляция, и любые числа времени из неё относятся к эмулятору, а не к процессору. Для callgrind это неважно, он считает инструкции гостя. Для perf важно.

Куда смотреть: порядок действий

Соберём урок в список, который можно повесить над столом.

Сначала perf stat на всю программу. Он бесплатный и сразу скажет, процессор это или ожидание, и упирается ли ядро в память (IPC меньше единицы) или в промахи предсказателя.
Потом perf record -g и flame graph. Ищи самое широкое плато, а не самую верхнюю и не самую нижнюю плашку.
Посчитай по Амдалу предел для этого плато. Если предел меньше, чем нужно, ускорять это место не имеет смысла, ищи структурную замену (другой алгоритм, другая структура данных, меньше работы).
Исправь одно место. Одно.
Профиль заново. Старый профиль после исправления не значит ничего: наверх выходит то, что было спрятано.
Только когда плато это один цикл, доставай микробенчмарк, модель процессора и приёмы прошлых уроков: аккумуляторы, развёртка, переупорядочение. И callgrind, если нужно точное число инструкций до и после.
Каждое число из микробенчмарка проверяй на ловушки: режим сборки, калибровка частоты, минимум из серии, doNotOptimizeAway на выходе, blackBox на входе, взгляд в ассемблер, если получилось слишком хорошо или слишком плохо.

Практика

Задача про многочлен и сумму, но без секундомера: в песочнице время не измеряется, и вместо него тесты подсовывают в твои функции трассирующий тип, у которого каждая операция запоминает глубину своей цепочки зависимостей. Умножение стоит три, сложение один, коэффициенты и x лежат на глубине ноль. Даны polyHorner(T, a, x) и sumSeq(T, v), обобщённые по comptime T с интерфейсом T.zero, T.mul, T.add. Нужно написать polyFast(T, a, x), тот же многочлен, но с критическим путём короче Горнера и короче цепочки степеней, и sumFast(T, v), ту же сумму на двух или больше аккумуляторах.

Тесты проверяют значения на случайных многочленах степеней от 0 до 20 с арифметикой, где переполнение заворачивается по кругу (wrapping), включая пустой набор коэффициентов и константу,, сумму на векторах длин от 0 до 50, а потом глубину: у polyFast на степенях 8 и 16 она обязана быть строго меньше, чем у Горнера, и строго меньше 3 · степень, у sumFast не больше примерно половины длины. Чётно-нечётное разбиение из урока проходит, схема Эстрина деревом проходит тоже. Обработай пустой набор и один коэффициент до разбиения: на одном коэффициенте нечётная ветка пуста, и умножение нуля на x добавит глубину, которой тест не простит.

Упражнения

CHK-1★

Собери words.zig и сними профиль тем инструментом, который есть на твоей машине: perf record -g на Linux, sample или xctrace на macOS, callgrind в контейнере где угодно. Сравни распределение по функциям с приведённым в уроке. Потом убери все noinline, сними профиль ещё раз и объясни, что изменилось в отчёте и почему числа в сумме остались теми же.

CHK-2★★

В третьей версии words.zig (оба переключателя включены) хеширование и поиск занимают две трети времени. Посчитай по закону Амдала, какое ускорение всей программы даст hashWord, ускоренный вдвое, и какое даст полная замена таблицы на std.StringHashMap, если считать, что она сделает подсчёт в четыре раза быстрее. Реализуй второе, измерь и сравни с расчётом. Если разошлось больше чем на двадцать процентов, найди в профиле, где расчёт был неверен.

CHK-3★★

Возьми deadcode.zig и добавь четвёртый замер: churn с маленьким n, скажем 1000, в цикле из ста тысяч вызовов, один раз с константным n и один раз с n, пропущенным через blackBox. Сними ассемблер обоих вариантов через -femit-asm и найди, при каком n компилятор ещё досчитывает результат при сборке, а при каком уже нет. Объясни по ассемблеру, что он делает с циклом в каждом случае.

CHK-4★★★

Число 1.96 у psum в прогоне урока ниже границы задержки сложения 2.49. Сними ассемблер цикла psum для aarch64 или x86-64, найди, что сделал с ним компилятор, и объясни результат. Потом перепиши psum так, чтобы в цикле осталась ровно одна цепочка из одного fadd на элемент (подсказка: blackBox с правильным ограничением для регистра с плавающей точкой, "+w" на aarch64 и "+x" на x86-64), и покажи, что CPE вернулся к границе.

CHK-5★★★

Собери flame graph для bench_poly.zig целиком, включая калибровку, и посмотри, какую долю времени занимает сама калибровка и серии разогрева. Потом сделай harness хуже нарочно: убери разогрев, замени минимум на среднее, поставь runs = 1. Для каждой порчи запусти программу пять раз и запиши разброс fast4. Какая из трёх порч даёт самый большой разброс на твоей машине и почему?

Итоги

Три инструмента, три вопроса. perf stat считает такты, инструкции и промахи на всю программу и говорит, во что она упирается. perf record с -g раз в миллисекунду записывает стек и говорит, где. callgrind считает каждую инструкцию детерминированно и аннотирует строки, но не знает, сколько тактов стоит каждая инструкция.
Доля инструкций и доля времени у функции могут расходиться в разы: сортировка вставками на нашей программе это 24 процента инструкций и 6 процентов времени, обход списка с указателями наоборот. Один callgrind без perf обманет на коде, который ждёт память.
Flame graph это свёрнутые стеки, нарисованные плашками: ширина это время, верх это где процессор, порядок и цвет ничего не значат. Искать надо самое широкое плато.
Профиль после исправления не значит ничего: наверх выходит то, что было спрятано. Сортировка с шестью процентами стала половиной после того, как хеш-таблица ускорилась в сотни раз.
Закон Амдала: S = 1 / ((1 − α) + α / k), предел 1 / (1 − α). Предел задаёт доля части до оптимизации, а не качество оптимизации. Отсюда правило: сначала самая широкая плашка, и только потом следующая.
Ловушки микробенчмарка: мёртвый код и замкнутые формулы (doNotOptimizeAway на выходе, blackBox на входе, взгляд в ассемблер), разогрев (два холостых прогона), шум (минимум из серии, медиана минус минимум как оценка), частота ядра (калибровка цепочкой сложений), выравнивание (разница в пять процентов ничего не значит), режим сборки (в Debug мерить нельзя).
Многочлен быстрее Горнера: разбиение по чётности степеней даёт две независимые цепочки, но компилятор упаковывает их в один векторный регистр и критический путь не сокращается. Четыре цепочки по x⁴ дают 2.47 такта на элемент против границы умножения 3.42 на Apple M4 Max.
Сумма ниже задержки сложения: сумма пары не зависит от аккумулятора, в цепочку попадает одно сложение на два элемента. Измерено 1.54 против 1.96 у версии с одним сложением на элемент.
Порядок всегда один: профиль, Амдал, одно исправление, профиль заново, и только на последнем шаге микробенчмарк с моделью процессора.

Дальше

Уроки про производительность на этом закончены. За шесть уроков ты прошёл путь от «что имеет право сделать компилятор» через модель суперскалярного процессора, критический путь, развёртку и аккумуляторы до сегодняшнего взгляда снаружи: профиль, Амдал, одно исправление за раз. Два числа из этого урока тянут за собой следующие уроки. Первое: у bump в первом профиле IPC был бы ниже единицы, потому что каждая запись списка лежит в случайном месте кучи и ядро ждёт память. Второе: callgrind считает инструкции, но не такты, и разница между ними это в основном промахи кэша.

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

домашка

Домашка

Возьми любую свою программу, которая работает дольше секунды, сними perf record с колл-стеками (или sample на macOS), построй flame graph и назови три самые широкие плашки. Исправь только верхнюю и покажи новый профиль рядом со старым.S
По профилю words.zig до исправлений посчитай по закону Амдала, какой предел ускорения даёт идеальная сортировка (нулевое время) и какой идеальный поиск в таблице. Сравни с тем, что получилось на самом деле, и объясни разницу.S
Напиши префиксную сумму с четырьмя элементами за итерацию так, чтобы в цепочку аккумулятора попадало одно сложение на четыре элемента, прогони через harness урока и сверь CPE с полученным для sumFast. Объясни, почему выигрыш меньше двукратного.L