Рейтинг@Mail.ru
[Войти] [Зарегистрироваться]

Наши друзья и партнеры

UnixForum
купить дешевый 
компьютер родом из Dhgate.com




Lines Club

Ищем достойных соперников.

Библиотека сайта rus-linux.net

Ninja

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

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

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

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

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

Разбор файлов

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

Оригинальная функция для анализа отдельного символа достаточно быстро появилась в выводе профайлера:
static bool IsIdentifierCharacter(char c) {
  return
    ('a' <= c && c <= 'z') ||
    ('A' <= c && c <= 'Z') ||
    // и так далее...
}
Простое исправление, которое позволило сохранить 200 мс, заключалось в замене функции на таблицу соответствия из 256 элементов, которая могла использоваться для поиска входного символа по его индексу. Такую таблицу достаточно просто сформировать с помощью подобного кода на языке Python:
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),
Этот прием позволил на некоторое время повысить производительность системы Ninja. В конце концов мы внесли более принципиальное изменение: перешли к использованию генератора лексических анализаторов re2c, применяемого в интерпретаторе PHP. Он позволяет генерировать более сложные таблицы соответствия и код со сложными синтаксическими структурами. Например:
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 формирует журнал сборки, полностью записывая команды, используемые для генерации каждого из выходных файлов.9 При каждой последующей сборке Ninja загружает журнал предыдущей сборки и сравнивает команды текущей сборки с командами из журнала сборки для установления наличия изменений. Фрагмент кода, ответственный за эту операцию, как и фрагменты кода, ответственные за загрузку файлов журнала и канонизацию путей, также часто появлялся в данных профилирования.

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


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


Эта статья еще не оценивалась
Вы сможете оценить статью и оставить комментарий, если войдете или зарегистрируетесь.
Только зарегистрированные пользователи могут оценивать и комментировать статьи.

Комментарии отсутствуют