Ninja

Глава 3 из книги "Производительность приложений с открытым исходным кодом".

Оригинал: Ninja
Автор: Evan Martin
Перевод: А.Панин

Оптимизация системы Ninja

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

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

Изначально система Ninja использовала специально разработанный лексический анализатор и систему разбора с рекурсивным спуском. Я считал, что синтаксис был достаточно простым для использования подобных инструментов. Выяснилось, что для проектов достаточно большого размера, таких, как Chrome⁸, простой разбор файлов сборки (с расширением .ninja) может занять неожиданно большой промежуток времени.

static bool IsIdentifierCharacter(char c) {
  return
    ('a' <= c && c <= 'z') ||
    ('A' <= c && c <= 'Z') ||
    // и так далее...
}

cs = set()
for c in string.ascii_letters + string.digits + r'+,-./\_$':
    cs.add(ord(c))
for i in range(256):
    print '%d,' % (i in cs),

if (yych <= 'b') {
    if (yych == '`') goto yy24;
    if (yych <= 'a') goto yy21;
    // и так далее...

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

Система Ninja не использует строк для идентификации путей. Вместо этого Ninja сопоставляет каждый встреченный путь с уникальным объектом Node и этот объект Node используется впоследствии в коде. Повторное использование объекта позволяет быть уверенным в том, что заданный путь только однократно проверяется на диске и результат его проверки (т.е., данные времени модификации) может быть повторно использован в остальном коде.

Указатель на объект Node служит уникальным идентификатором для заданного пути. Для проверки того, указывают ли два объекта Node на один и тот же путь, достаточно сравнить указатели, а не выполнять более ресурсоемкую операцию сравнения строк. Например, по мере обхода системой Ninja графа входных данных для сборки, она формирует стек зависимых объектов Node для проверки наличия циклических зависимостей: в том случае, если путь A зависит от B, который зависит от C, который в свою очередь зависит от A, сборка не может выполняться. Этот стек, представляющий файлы, может быть реализован в виде простого массива указателей и равенство указателей может использоваться для проверки наличия дубликатов.

Для того, чтобы всегда использовать один и тот же объект для каждого из файлов, системе Ninja необходимо произвести надежное сопоставление каждого возможного имени файла с одним и тем же объектом Node. Для этого необходимо выполнить канонизацию всех путей, описанных в файлах сборки, в ходе которой такие пути, как foo/../bar.h будут преобразованы в bar.h. Изначально система Ninja просто предъявляла требование, согласно которому все пути должны были передаваться в канонизированной форме, но в конце концов по некоторым причинам данное решение оказалось неработоспособным. Первая причина состоит в том, что заданные пользователем пути (т.е., введенные в командной строке команды наподобие ninja ./bar.h) по понятным причинам должны быть работоспособны. Другая причина состоит в том, что переменные могут комбинироваться для формирования неканонизированных путей. Наконец, информация о зависимостях, выводимая gcc может содержать данные о путях в неканонизированной форме.

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

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

Одна из частей системы сборки ядра Linux предназначена для отслеживания команд, используемых для генерации выходных файлов. Рассмотрим пример, обосновывающий данный подход: вы компилируете файл исходного кода foo.c и получаете выходной объектный файл foo.o, после чего изменяете файл сборки таким образом, что проект должен быть пересобран с отличными флагами компиляции. Для того, чтобы система сборки имела представление о том, что ей требуется произвести повторную сборку результирующих файлов, она должна либо сделать запись о том, что объектный файл foo.o зависит от самих файлов сборки (причем это, в зависимости от организации проекта, может подразумевать, что изменение в файлах сборки потребует пересборки всего проекта), либо записывать команды, используемые для генерации каждого выходного файла и сравнивать их при каждой сборке.

В ядре (и, следовательно, в файлах Makefile Chrome и Ninja) используется последний описанный подход. В процессе сборки Ninja формирует журнал сборки, полностью записывая команды, используемые для генерации каждого из выходных файлов.⁹ При каждой последующей сборке Ninja загружает журнал предыдущей сборки и сравнивает команды текущей сборки с командами из журнала сборки для установления наличия изменений. Фрагмент кода, ответственный за эту операцию, как и фрагменты кода, ответственные за загрузку файлов журнала и канонизацию путей, также часто появлялся в данных профилирования.

После выполнения нескольких небольших оптимизаций Nico Weber, являющийся активным участником процесса разработки Ninja, реализовал новый формат журнала сборки. Вместо записи команд, которые обычно были очень длинными и требовали много времени для разбора, система Ninja производила запись хэш-суммы для каждой команды. При последующих сборках система Ninja производила сравнение хэш-суммы команды, которая должна была быть выполнена и записанной в журнал хэш-суммы. В том случае, если две хэш-суммы отличаются, выходные данные считаются устаревшими. Данный подход был очень удачным. Использование хэш-сумм позволило значительно уменьшить размер журнала сборки - с 200 МБ до менее чем 2 МБ на платформе Mac OS X - а также увеличить скорость его загрузки более чем в 20 раз.

Продолжение статьи: Файлы зависимостей.