Производительность компилятора и LLVM

Я всегда хотел, чтобы компилятор Cone работал быстро. Более быстрая сборка позволяет программисту проще и быстрее выполнять итерации и экспериментировать. Компиляторы, созданные для скорости, такие как Turbo Pascal, D and Go, завоевывают похвалу и лояльность. Языки, которые больше борются с этим, такие как C ++ или Rust, регулярно получают жалобы и запросы, чтобы ускорить время сборки.

Скорость компилятора также важна для Джонатана Блоу. В своих видео он демонстрирует способность перестраивать большую Jai-программу за считанные секунды и утверждает, что Jai-компилятор может собрать 100kloc за секунду. Я бы хотел, чтобы Cone соответствовал этой скорости, при условии, что она не мешает другим приоритетам.

Для этого я разработал компилятор Cone для повышения производительности, следуя принципам, перечисленным в разделе "Преждевременная оптимизация" . В этом посте позвольте мне поделиться с вами сделанным мной выбором кодирования и некоторыми недавними измерениями производительности, которые оценивают, были ли эти выборы правильными. Эти цифры неизбежно приводят нас к некоторым интересным вопросам о слоне в комнате: характеристиках работы LLVM.

Архитектура для производительности

Давайте начнем с выбора дизайна компилятора Cone для повышения производительности:

• C . Выбор любого системного языка (C ++, Rust, D), вероятно, приведет к значительно более быстрым программам. С моей точки зрения, выбор C улучшает шансы, так как облегчает приближение к металлу. Для еще более жесткого управления производительностью компилятор использует только одну внешнюю библиотеку. Хотя некоторые могут утверждать, что C замедлил мою производительность, раздул базу кода и сделал ее восприимчивой к всевозможным ошибкам безопасности, что не было моим опытом. Единственное, о чем я сожалею, так это о том, что я хотел бы вместо этого принять это в Cone.

• Управление памятью. Компиляторы выделяют много крошечных фрагментов данных, в основном для узлов AST / IR и таблиц символов. Чтобы практически исключить нетривиальные затраты времени выполнения malloc (), free () и отслеживания живучести для каждого фрагмента данных, компилятор Cone использует очень простой распределитель арены с указателем на удар. Распределение занимает всего несколько инструкций, чтобы извлечь следующий укус из большой, плохо выверенной арены. Ссылки никогда не отслеживаются и не освобождаются, но при этом безопасны на 100%. Теоретическим недостатком этой стратегии является то, что потребление памяти растет безостановочно. Однако на практике я не боюсь, что компиляции когда-либо не хватит памяти. В среднем компилятор Cone потребляет около 35 байтов памяти на каждый байт исходного кода. Насколько большим должен быть ваш исходный код, прежде чем вы будете использовать всю память?

• Данные редко копируются. Почти все структуры данных, включая IR и таблицу глобальных имен, являются изменяемыми и могут использоваться повторно. Кроме того, конструкция IR означает, что большинство узлов IR выживают в значительной степени неповрежденными на всем пути от анализа до поколения. Даже временные рабочие стеки данных выделяются один раз и используются повторно. Кроме того, строковые копии токенов загруженного исходного файла происходят не более одного раза, при интернировании имен и при захвате строковых литералов. Компиляторы, которые переписывают свои узлы AST / IR или используют неизменяемые структуры данных, будут подвергаться измеримым затратам на распределение и копирование для этого.

• Имена интернированы. Лексер отвечает за включение всех имен в глобальную таблицу имен. В результате, остальная часть компилятора (включая синтаксический анализ и разрешение имен) никогда не замедляется никаким сравнением строк или поиском в хеш-таблице. Корреляция имени с IR-узлом почти так же проста, как разыменование указателя. Между лексингом и генерацией компилятор не обращает никакого внимания на строки, кроме как на генерацию сообщений об ошибках.

• Специальная, встроенная эвристика. Семантический анализ проходит полный IR только три раза. Никакие «решатели» не используются для вывода типа или проверки заимствований, поскольку достаточно каскадных цепочек условных выражений. Кроме того, ни один из семантического анализа не происходит на уровнях абстракции (например, с помощью шаблонов базовой библиотеки или шаблонов).

Я не претендую на какие-либо безупречные доказательства того, что эти стратегии действительно являются лучшими вариантами выбора, которые я мог сделать. Если существуют какие-либо проверенные исследования, которые подтверждают этот выбор, я не знаю об этом. Я могу указать на статью Уолтера Брайта «Повышение скорости компиляции более чем на 75%», в которой количественно определяется выигрыш в производительности при распределении памяти на основе арены. Я приветствую любые другие достоверные данные и / или рекомендации, касающиеся этих (или альтернативных) вариантов проектирования, основанных на характеристиках.

Компилятор Cone - производительность фронт-энда

Компилятор Cone выводит сообщение, в котором обобщается прошедшее время и использование памяти для каждой компиляции. Работающие на моем сервере, как часть Playground, небольшие программы обычно компилируются за 4-11 миллисекунд.

Хотя, довольствуясь этим, мне недавно стало любопытно, что происходит под одеялом. Я запустил профилировщик Visual Studio. Одним из неожиданных результатов было то, что большинство шагов компиляции (таких как синтаксический анализ и семантический анализ) даже не отображались в журнале.

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

Для небольшой программы размером 200 LOC (3800 байт) среднее время, прошедшее на моем ноутбуке для каждой стадии фронтального компилятора:

Микросекунды	Этап компиляции
300	Загрузка. Полностью загрузить исходную программу (ы) с SSD диска в память
100	Lex. Преобразуйте исходные символы UTF-8 в готовые к использованию интернированные токены
300	Синтаксический. Конвертировать токены в высокоуровневые ИК-узлы
100	Анализ. Все 3 семантических этапа: разрешение имени, проверка типа, поток данных

Не следует читать слишком много в эти цифры. Несколько этапов почти наверняка замедлятся, особенно когда в Cone добавлена ​​поддержка метапрограммирования. Кроме того, мы не знаем, как эти результаты будут масштабироваться для более крупных программ. Даже если логика предполагает, что масштабирование, скорее всего, будет линейным, необходимо выполнить тесты, подтверждающие это. Тесты проводились на моем ноутбуке, конкурируя с другими программами для процессора, и результаты варьировались от ± 50% от одного запуска к другому.

Все предостережения в стороне, эти результаты захватывают дух. Ненастроенный интерфейсный компилятор жует до 250Kloc в секунду, несмотря на то, что почти 40% времени тратится на дисковый ввод-вывод. Эти лучшие, чем ожидалось, результаты укрепляют мою уверенность в том, что первоначальные дизайнерские решения Cone были в основном правильными.

Я удивляюсь, почему разбор работает медленнее, чем анализ и анализ. На ум приходят две возможности: каждый токен, вероятно, будет многократно совпадать с парсером рекурсивного спуска по нескольким функциям (что менее верно в отношении обработки лексером символов исходного кода). Более интригующим является то, что это может быть связано с затратами на строительство IR-узлов Cone. По сравнению с лексизмом и анализом, синтаксический анализ, безусловно, делает большую часть мутаций памяти. Замедляет ли обширная мутация памяти такие вещи (например, из-за аннулирования кэша)?

Проницательный читатель заметит, что я не дал номер для этапа генерации кода. Здесь, к сожалению, новости о производительности гораздо менее звездные. Создание оптимизированного объектного файла из анализируемой ИК занимает около 115 500 мкСек. Это 99,3% от общего времени компиляции! Чтобы понять этот неутешительный результат, мы должны поговорить о LLVM.

Производительность LLVM бэк-энд

Как и многие недавние компиляторы, Cone использует LLVM для генерации оптимизированного нативного кода. По существу, этап генерации кода компилятора создает двоичный IR LLVM из IR Cone, просит LLVM проверить и оптимизировать его, а затем LLVM сгенерирует объектный файл для соответствующей целевой архитектуры ЦП.

В целом, мой опыт использования LLVM был чрезвычайно положительным. Я сомневаюсь, что решил бы создать компилятор для Cone без LLVM. Мои опасения по поводу производительности LLVM (и его большого объема времени выполнения / сборки) - единственные существенные проблемы, которые у меня возникают по поводу использования LLVM в Cone.

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

Микросекунды	Стадия LLVM
2500	Настроить.
11 000	Gen LLVM IR. Создайте LLVM IR, пройдя через узлы Cone IR
3000	Проверьте LLVMIR. Проверьте сборку LLVM IR
15000	Оптимизация. Оптимизировать LLVM IR
84000	Gen obj. Преобразуйте LLVM IR в объектный файл и сохраните его

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

• Настройка. Это позволяет LLVM поддерживать генерацию кода для указанной цели компиляции (из 15 поддерживаемых целевых архитектур). Он инициализирует информацию о целевом компьютере, макете данных и глобальном контексте. Действительно ли для выполнения этой работы требуется 2,5 мсек (в 3 раза больше, чем загрузка и анализ небольшой программы Cone)? Это чувствует себя потенциально чрезмерным. Однако, к счастью, это истекшее время, вероятно, является постоянным и не будет расти, так как исходные программы становятся больше и сложнее.

• Gen LLVM IR. Это единственный этап, который смешивает код Cone и LLVM. Логика на стороне конуса пересекает Cone IR аналогично проходам семантического анализа, генерируя множество отдельных вызовов API LLVM, которые создают соответствующие узлы LLVM IR, эффективно понижая Cone IR до LLVM IR. Поскольку логика на стороне конуса, вероятно, не займет больше времени, чем 100 мксек (стоимость трехпроходного семантического анализа), построение 1000 узлов LLVM IR SSA, очевидно, займет более чем в 100 раз больше. Алгоритмическая сложность здесь, вероятно, по большей части равна O (n), масштабируясь примерно линейно до количества ИК-узлов Cone. Процесс снижения типов Cone IR до типов LLVM может быть не O (n), так как LLVM нормализует информацию о типах для уникальности.

• Проверьте LLVMIR. Этот шаг является эффективно семантическим анализом для LLVM IR. Это гарантирует, что IR модуля правильно сформирован, включая проверку типа. Этот этап, вероятно, можно было бы пропустить в производственном компиляторе, который знает, что он генерирует только действительный IR LLVM. Несмотря на то, что он намного быстрее, чем другие стадии бэкэнда, он все равно занимает в 30 раз больше времени, чем все три семантических пасса Cone. Его алгоритмическая сложность, вероятно, O (n), линейно масштабируясь до количества узлов IR LLVM.

• Оптимизация LLVMIR. Выполняется 6 этапов оптимизации LLVM: преобразование переменных стека в регистры, встраивание функций, простое переворачивание глазков / битов, повторная ассоциация выражений, устранение общих подвыражений и упрощение графов потоков управления. Эти проходы сканируют и переваривают LLVM IR на каждом проходе и, вероятно, каждый раз перезаписывают LLVM IR. Некоторые из проходов оптимизации могут быть O (n), но другие почти наверняка экспоненциально более сложны.

• Gen Obj. Этот шаг понижает IR LLVM до машинного языка цели и сохраняет его на диске в виде объектного файла для конкретной цели. Этот последний этап LLVM занимает 73% времени работы LLVM. Мы ожидаем, что этот шаг понижения займет больше времени, чем предыдущий, отчасти потому, что данные input-> outut больше (800 LOC LLVM IR превращается в 1900 LOC ассемблера), а отчасти потому, что процесс опускания намного сложнее из-за распределение целевых регистров и другие алгоритмы оптимизации.

LLVM должен быть таким медленным?

Я хочу быть очень осторожным, когда говорю о LLVM и производительности. Хотя мое намерение состоит в том, чтобы предложить полезную обратную связь и сведения о том, чего ожидать от LLVM, приоритет показывает, что мои слова могут быть неверно истолкованы как грубые или несправедливые по отношению ко многим людям, которые вложили сотни человеческих лет в развитие этого удивительного инструмента. Было бы стыдно, если бы люди почувствовали острую необходимость энергично (и неоправданно) защищать LLVM вместо того, чтобы вступать в проницательный диалог, который исследует то, что мы можем изучить.

Однако, когда производительность LLVM играет доминирующую роль во время сборки компилятора (99,3%!), Стоит спросить, действительно ли бэкэнд должен потреблять почти в 200 раз больше ЦП, чем интерфейс. Если мы хотим быстрое время компиляции (как и я), нам нужно найти способы ускорить бэкэнд.

Не секрет, что LLVM большой (1,2 мкл кода C ++) и переживает много циклов ЦП. Каждый компилятор, который его использует (например, Clang, Rust, Swift), имеет репутацию более медленного, чем хотелось бы, времени компиляции. Напротив, компиляторы с репутацией для гораздо более быстрого времени компиляции (например, D, Go, tcc и Jai) этого не делают. Создание более гибкой внутренней библиотеки генерации кода стало ключевым драйвером для ряда альтернатив LLVM, таких как Cranelift на основе Rust, libFirm и QBE. Эта проблема также вынудила команду WebKit заменить LLVM на свой собственный бэкэнд FTL JIT.

Можем ли мы получить какие-либо дополнительные сведения о производительности LLVM (и как ее улучшить), основываясь на результатах прошедшего времени, приведенных выше? Конечно, нельзя сделать окончательных выводов, учитывая, что эти цифры основаны на составлении небольшой простой программы. Мы не можем делать точных прогнозов того, как эти результаты изменятся после увеличения размера или сложности программы. Увеличение размера программы могло бы сделать бэкэнд еще хуже по сравнению с внешним интерфейсом. Тем не менее, сложная программа, которая зависит от многих внешних пакетов или интенсивно использует метапрограммирование, вполне могла бы быть в большей степени ориентирована на обработку внешнего интерфейса (как наглядно демонстрируют эти диаграммы профилировщика с диаграммой пламени Clang).

Учитывая эти предостережения, давайте рассмотрим возможные объяснения того, почему LLVM часто доминирует в ЦП и что можно с этим сделать.

Влияние оптимизации

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

Здесь есть правда. Некоторые формы оптимизации являются вычислительно дорогими, экспоненциально реагируя на сложность. LLVM предлагает превосходную оптимизацию, заметно лучше, чем tcc, например, за счет гораздо более медленной компиляции (5-9x).

Должна ли цена быть такой крутой? Мы не можем сказать наверняка, но, безусловно, это означает, что gcc и clang очень похожи как во время компиляции, так и в качестве оптимизации. Возможно, крутой штраф во время компиляции - неудачная, но необходимая стоимость для оптимальной скорости выполнения. Тем не менее, один такой пример не является доказательством того, что работа по оптимизации полностью объясняет скорость LLVM.

Однако есть несколько хороших новостей о том, как оптимизировать поддержку LLVM. LLVM позволяет улучшить время компиляции, выполняя меньше проходов оптимизации. Для отладочных сборок это привлекательный вариант. Исходя из моих цифр, исключение всех проходов оптимизации приведет к восстановлению не более 15% использования ЦП LLVM. Это не впечатляет. 1

Использование LLVM более эффективно

Другое объяснение производительности LLVM заключается в том, что Cone может не настроить LLVM для успеха. Хотя существует опубликованное руководство под названием «Советы по повышению производительности для авторов из внешнего интерфейса», оно посвящено тому, как помочь оптимизатору. Он не предлагает никаких предложений о том, как заставить LLVM работать быстрее.

Помимо исключения проходов оптимизации и проверки IR, могут ли быть другие способы для компилятора Cone ускорить обработку LLVM?

• Предварительно оптимизированная генерация ИК. Чем меньше генерируемый IR, тем меньше работы LLVM тратит на обработку и оптимизацию.

• Нормализованные типы. Определенные типы конусов (например, ссылки) периодически понижаются до типов LLVM, которые затем нормализуются для уникальности. Если бы компилятор Cone предварительно нормализовал эти типы, это позволило бы избежать потенциально более дорогостоящих затрат для LLVM на выполнение этой работы.

• Быстрее LLVM IR здание. Я прочитал статью о переполнении стека, в которой предполагалось, что LLVM может принимать текстовый IR-файл LLVM намного быстрее, чем некоторые компиляторы могут создавать IR с помощью API. Это объяснило этот противоречивый результат в результате улучшения локальности памяти. Было бы интересно выяснить, есть ли у служебных программ LLVM способ быстрого создания инструкций, в отличие от одноразового построителя инструкций, предоставляемого API C ++ (или C).

У меня нет оснований ожидать, что эти или другие изменения на основе Cone приведут к огромному ускорению LLVM, но их, вероятно, стоит изучить.

Улучшения внутренней архитектуры

Возможно ли, что медлительность LLVM также может быть результатом его архитектурного выбора? Несовершенное сравнение между несколькими контрольными числами открывает такую ​​возможность:

• Этап верификации LLVM IR занял в 30 раз больше времени, чем 3 прохода семантического анализа для Cone. Характер работы, выполняемой на обоих этапах, неопределенно похож. Оба имеют линейную сложность O (n). Проверка LLVM обычно обрабатывает больше узлов IR, чем семантический анализ Cone, но в обоих случаях проверки типов одинаково просты. Не удивительно, что LLVM требует в 30 раз больше времени, чем Cone, чтобы выполнить проверку IR. Может ли потребоваться меньше времени, если LLVM были построены на разных архитектурных решениях?

• Поколения этап, который понижает Cone IR построить LLVM IR, занимает почти 40x больше , чем разбор конуса, который понижает лексему Cone IR. Они оба имеют в значительной степени линейную сложность O (n), и основная ответственность за оба этапа заключается в построении ИК-графика. Результирующий IR-график LLVM будет иметь больше узлов, чем IR-график Cone, но потребует ли это в 40 раз больше усилий, если будет сделан более эффективный выбор дизайна?

Разрыв в производительности в 30-40 раз достаточно велик, чтобы гарантировать, что в конструкции LLVM есть некий подакцизный жир, причем не только на этих этапах, но и, возможно, также на более поздних, более трудоемких этапах, которые также потребляют тот же IR LLVM. структуры данных. Если этот избыток жира не вызван оптимизацией LLVM и гибкостью целевой архитектуры, что еще может быть важным фактором?

Новый IR LuaJIT 2.0 предлагает вдохновение для одной многообещающей линии атаки. Этот низкоуровневый IR-дизайн ловко упаковывает каждый узел SSA в 64-битное значение. Перекрестные ссылки на узлы занимают только 16 бит. Все ИК узлы для функции плотно упакованы вместе. Такая схема не только дружественна кешу, но и удобна для регистрации, что принесло бы огромный выигрыш в производительности. Объединение узлов в узлы также уменьшает распределение памяти / свободное время выполнения.

Я не предлагаю, чтобы LLVM использовал схему IR LuaJIT, тем более что IR LuaJIT разработан для поддержки более простого языка с динамической типизацией. Узлы для более универсального LLVM-подобного IR почти наверняка потребуют более 64 бит. Скорее, мне интересно, какой выигрыш в производительности может возникнуть в результате изменения низкоуровневого IR бэкэнда (и управления памятью) по аналогичным высокопроизводительным линиям. 2 Даже если эти улучшения обеспечивают только более быстрые отладочные сборки, это гораздо лучше, чем вообще никаких улучшений.

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

Следующие шаги

Невозможно сделать какие-либо твердые выводы об архитектуре производительности Cone или LLVM, основываясь исключительно на данных и анализе, приведенных в этом посте. Единственный способ сделать более четкие выводы - это тщательные тесты, сравнивающие производительность различных подходов к проектированию, которые выполняют одну и ту же задачу.

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

• Проектирование для повышения производительности может работать очень хорошо, вопреки предупреждениям скептиков, вдохновленных Кнутом. Могут быть приняты правильные решения для повышения производительности, которые повышают производительность труда программиста и приводят к понятному коду. Я хочу продолжать улучшаться в этом. Я также хочу разработать язык Cone, чтобы облегчить его программистам.
• Мне действительно не нужно фокусироваться на настройке производительности внешнего интерфейса компилятора Cone. Я действительно очень доволен его текущей скоростью на данный момент. После добавления поддержки макросов и обобщений, вероятно, было бы полезно вернуться к этим цифрам.
• LLVM станет якорем для быстрой сборки Конуса. В ближайшей перспективе я мог бы изучить способы ускорения моего использования LLVM, как указано выше (предварительная оптимизация генерации IR LLVM и нормализация типа).
• В долгосрочной перспективе мне, вероятно, следует изучить альтернативы LLVM, особенно для выполнения отладочных сборок, где генерация оптимизированных сред выполнения не является приоритетом. Поскольку я не стремлюсь взяться за работу по созданию пользовательского бэкэнда, я, безусловно, более подробно рассмотрю способы использования других бэкэндов, что продемонстрировали компиляторы, которые могут похвастаться гораздо более быстрой генерацией кода (например, tcc или Jai) ,

Как всегда, мне интересно учиться на опыте и знаниях других людей относительно производительности компилятора и LLVM / бэкенда, будь то в ваших собственных проектах или на основе результатов, которые вы видели опубликованными другими командами, которые наверняка борются с подобными проблемами.

---

[1] Спасибо u / sanxlyn за указание на FastISel, быстрый режим для генерации кода LLVM, вариант, о котором я забыл. Когда я набрал оптимизацию codegen с «агрессивного» на «none», он сократил время генерации кода вдвое.

[2] Оказывается, к счастью, другие в этом понимании намного опережают меня: как объясняет pcwalton, «Cranelift» на основе Rust в некотором смысле является попыткой перестроить LLVM для более быстрой скорости компиляции, написанной некоторыми давними участниками LLVM. Например, Cranelift имеет только один IR, что позволяет избежать многократного перестраивания деревьев, а IR хранится плотно упакованным, а не разбросанным по всей памяти ». Кроме того, LLVM 9, очевидно, планирует заменить SelectionDag и FastISel в значительной степени переписанным модулем GlobalISel. , Производительность является ключевой целью, которая достигается частично за счет унификации и упрощения структур данных IR, используемых во время Codegen.