Устройство инкрементальной компиляции в Zig

mlugg, участник core-команды Zig, рассказывает о том, как компилятор определяет, какие объявления изменились со времени прошлой сборки, перекомпилирует только их и патчит полученные байты прямо в выходной бинарный файл. Демонстрационный проект - Fizzy, пиксельный редактор: 5 секунд на холодную сборку и затем 50-70 мс на каждую повторную. Ни один этап конвейера не имеет права требовать анализа всей программы целиком.

Пофайлово: кэширование IR, а не результата

Первый этап проходит по исходным файлам: чтение, парсинг в AST, понижение уровня до ZIR (нетипизированное промежуточное представление в форме SSA) через проход AstGen. AstGen заодно находит вызовы @import, благодаря чему вообще формируется набор файлов проекта.

Три свойства делают этот этап простым. Обработка файла - чистая функция от его содержимого, без разделяемого или внешнего состояния. Парсинг вместе с AstGen по всему каталогу src/ компилятора Zig занимает около 920 мс на ноутбуке автора без всякого параллелизма. А поскольку ZIR спроектирован с упором на data-oriented design, он пишется на диск и читается с него за один системный вызов writev/readv - никакого этапа сериализации, просто байты.

Чистота функций даёт предельный параллелизм (по задаче на файл в пуле потоков; единственное разделяемое состояние - защищённый мьютексом хэш-сет уже просмотренных путей) и тривиальную инкрементальность: ZIR каждого файла кэшируется и пересобирается, только если файл изменился. И то, и другое включено по умолчанию уже много лет. Эту часть умеют и другие компиляторы.

Семантический анализ: единицы анализа и граф зависимостей

Семантический анализ интерпретирует ZIR: проверяет типы и вычисляет comptime-выражения, выдавая ошибки компиляции, а для функций времени выполнения генерируя AIR для последующих этапов. Сделать инкрементальным именно этот этап труднее всего, и именно здесь дизайн языка начинает накладывать жесткие ограничения. Архитектуру Zig годами меняли (порой вызывая споры) именно ради того, чтобы эта задача оставалась разрешимой.

Базовым элементом работы выступает единица анализа (analysis unit). Их четыре вида: структура размещения памяти (layout) для struct или union, тип объявления на уровне контейнера, значение константы const на уровне контейнера и тело функции времени выполнения. Анализ единицы фиксирует, от каких других единиц она зависела. Для кода

var global_0: u32 = 123;
const global_1: u32 = 456;

pub fn foo(cond: bool) u32 {
    if (cond) return global_0 else return global_1;
}

тело foo в итоге зависит от типов обеих глобальных переменных и от значения global_1 - от последнего только потому, что это const, значение которого известно во время компиляции и считывается на этапе comptime. Из этого следуют две асимметрии. Ничто не может зависеть от тела функции, поэтому у единиц функций бывают только исходящие рёбра. А зависимости от значения объявления существуют исключительно потому, что Zig разрешает использовать такие значения в comptime; без этой возможности зависеть от значения было бы так же невозможно, как и от тела функции.

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

Распространение изменений останавливается как можно раньше. Если поменять const lucky_number = 42; на 43, компилятор заново генерирует ZIR, сопоставляет старые объявления с новыми по именам, находит ровно один изменившийся хэш исходника и заново анализирует значение lucky_number. Если бы правка затронула только пробелы, значение осталось бы прежним и каскад остановился бы на этом шаге. Но поскольку значение изменилось, два зависящих от него тела функций отправляются на повторный анализ - а так как от тела функции зависеть ничто не может, цикл завершается.

Кодогенерация: простой этап

Кодогенерация превращает AIR в MIR - представление, практически 1:1 соответствующее машинным инструкциям, со своей реализацией под каждую целевую архитектуру. Этап параллелится столь же легко, как и обработка файлов: между функциями нет разделяемого состояния. Есть лишь один нюанс: очередь ожидающих функций требует ограничения по размеру, иначе, если кодогенерация отстанет от семантического анализа, накопившийся AIR быстро забьёт память.

С точки зрения инкрементальности это самый простой этап. AIR и MIR уже разбиты по функциям, что идеально совпадает с гранулярностью инкрементальной компиляции, поэтому ни тот, ни другой никогда не кэшируются. AIR удаляется сразу по завершении кодогенерации, а MIR - как только его потребит линкер.

Линковка: отображаемый в память файл с деревом узлов

Инкрементальная линковка - главная причина, почему, по мнению mlugg, ни один крупный тулчейн до сих пор этого не делает. Универсальных инкрементальных линкеров почти нет: wild изначально задумывался как инкрементальный, но затем переключился на скорость холодной линковки без конкретных сроков по инкрементальности. Одна из проблем, выделенных Дэвидом Латтимором (David Lattimore) в wild, - необходимость сравнивать входные объектные файлы, чтобы понять, что изменилось. Контроль над всем конвейером компиляции снимает эту проблему целиком, пусть и ценой жесткой привязки линкера к компилятору.

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

Основная сложность - перемещение данных. Рост секции .text может потребовать сдвига соседних секций, что меняет их смещения в файле и виртуальные адреса, а это инвалидирует записи в таблице символов и все указывающие на них релокации. Абстракция link.MappedFile Джейкоба Янга (Jacob Young) решает эту задачу: выходной файл отображается в память через mmap и отслеживается как дерево узлов, где корень покрывает весь файл, а дочерние узлы - области родительского. Вызывающий код добавляет узел или увеличивает его размер; если родительский узел не вмещает изменение, MappedFile сдвигает другие узлы, освобождая место, и ставит dirty-флаг на всё, что было затронуто.

Генерация функции сводится к следующему: создать узел достаточного размера под код (или изменить размер существующего), скопировать туда код и обязательно пометить этот узел как dirty, чтобы к нему применились релокации. В этот момент бинарник обычно находится в некорректном состоянии, и это нормально: когда очередь потока линкера опустеет или когда компиляция подойдёт к концу, он обходит dirty-флаги и вносит исправления - новые виртуальные адреса, заголовки секций и программы, адреса таблицы символов и повторно применённые релокации.

Такая корректировка может стоить дорого, если в динамическом исполняемом файле сдвигается PLT, поскольку на неё указывает множество релокаций. Узлы растут с экспоненциальным шагом (тот же приём, что используется в ArrayList), благодаря чему накладные расходы амортизируются и возникают редко - ценой чуть большего размера бинарников при разработке. По словам mlugg, он ни разу не сталкивался с медленными обновлениями на практике, несмотря на почти ежедневное использование.

Сброс на диск и куда на самом деле уходит время

В конце обновления остаются две несвязанные детали. Ленивый анализ в Zig означает, что скомпилированный на прошлом обновлении фрагмент кода теперь может оказаться неиспользуемым. Соответственно, ошибки его компиляции нужно проигнорировать, а символы - не экспортировать, для чего требуется обход графа ссылок. Затем запускается собственный метод flush линкера, время работы которого намеренно приближено к O(1): для ELF он записывает секцию .dynamic, поле entry в заголовке - и на этом всё.

Трассировка в Tracy для 37-миллисекундного обновления Fizzy наглядно показывает неравномерность распределения времени. Первые ~6 мс уходят на всё то, что интуитивно должно было занимать большую часть: всплеск пофайловой работы по всему пулу потоков (проверяется каждый исходный файл, а не только изменённый), около 1 мс в computeAliveFiles на обход графа импортов для распределения файлов по модулям, около 1 мс в updateZirRefs на переназначение ссылок со старых индексов инструкций ZIR на новые, затем 1.2 мс на семантический анализ, 240 мкс на кодогенерацию, 170 мкс на линковку и 50 мкс на перегенерацию таблицы поиска @errorName. Конвейер, доминирующий при холодной сборке, здесь занимает всего около 1.6 мс.

Оставшиеся ~31 мс приходятся на resolveReferencesInner - обход графа ссылок, который пересчитывается целиком, даже если сам граф ссылок не изменился. mlugg оставил этот момент в статье, не пытаясь предварительно его исправить, поскольку он показывает потенциал для дальнейшей оптимизации: пропускать пересчёт, если граф не менялся, а при изменениях обновлять его инкрементально через динамический алгоритм поиска кратчайшего пути от одного источника (SSSP).

Как это использовать

$ zig build --watch -fincremental

Флаг --watch заставляет систему сборки следить за файловой системой; -fincremental выставляет флаг инкрементальности для каждого std.Build.Step.Compile. Существующие кэши несовместимы с новым форматом, поэтому первый запуск пересобирает всё с нуля даже при прогретом кэше; добавление опции -Dincremental в build.zig и установка exe.incremental = true позволяют ограничить это одной компиляцией.

Ограничения весьма ощутимы. Сейчас это работает только для x86_64-linux, так как бэкенды кодогенерации и линкера для остальных платформ ещё не готовы: core-команда сначала оптимизировала работу под свои рабочие машины, и расширение списка платформ теперь в приоритете. Состояние компилятора пока не сохраняется на диск, поэтому при обычном вызове zig build инкрементальность не работает автоматически. Комбинация --watch с шагом запуска подходит для короткоживущих программ, но долгоживущее графическое приложение заблокирует следующую пересборку до своего завершения. Кроме того, функциональность пока нестабильна: возможны как ложные ошибки компиляции, так и некорректная кодогенерация.

В Zig 0.16.0 инкрементальная компиляция уже есть, но в ней отсутствуют добавленные позже возможности линкера, поэтому для работы требуется ветка master или версия 0.17.0. Это согласуется с картиной из returning-to-zig, где в 0.17 ожидаются ломающие изменения в системе сборки для всех проектов. Быстрая пересборка - награда за готовность мириться с нестабильностью версий.