▍ Введение

Компиляторы всегда были окружены аурой загадочности и магии. Из-за этого многие из нас верят, что они делают то, чего они не делают, или что они не делают того, что делают¹

Эта статья станет своего рода продолжением статьи о компиляторных оптимизациях. Я перечислю некоторые заблуждения, с которыми я сталкивался за долгие годы (многие из них были моими), и постараюсь развеять все мифы. Заранее скажу, что эта статья посвящена только крупным популярным компиляторам общего назначения наподобие LLVM, GCC и ICX. Некоторые из сделанных здесь утверждений не относятся, например, к специализированным компиляторам², а также к мелким и средним компиляторам³.

▍ Оптимизация создаёт оптимальные программы

Во-первых, нужно определиться: оптимальные по какой метрике? Например, метрикой может быть размер кода. Но обычно в качестве метрики компиляторы выбирают время выполнения (то есть задержки единичного прогона программы). Впрочем, как бы то ни было, «оптимизация» — это неверный термин. Компиляторы даже не пытаются найти оптимальную программу. Вместо этого они сначала опускают уровень абстракции программы очень простым способом, а затем просто пытаются улучшить программу. «Улучшение» — гораздо более слабый термин, чем «оптимизация», зато он точнее.

Но почему мы не получаем оптимальную программу? Это очень сложная и очень медленная задача. При оптимизации под размер кода у нас есть хоть какая-то надежда получить результат за разумное время, потому что размер кода как метрика обладает множеством удобных свойств. Например, мы можем измерять размер кода чрезвычайно точно и надёжно; по сути, это размер файла сгенерированной программы. Кроме того, разные измерения дают в точности одинаковое значение (например, если мы измерим размер сейчас и через минуту). Наконец, размер кода обладает оптимальной подструктурой. ДОПОЛНЕНИЕ: на самом деле, похоже, я здесь ошибся.
См. комментарий. Надеюсь, у меня будет время вернуться к этому вопросу.

Время выполнения не обладает ни одним из этих свойств. Во-первых, его нельзя измерить точно. Разные прогоны программы будут иметь слегка различающееся время выполнения. Хуже того, на время выполнения влияет множество мелких факторов (например, известная статья [1, 2] показала, что нечто, кажущееся невинным, например, структура программы, способно вызывать колебания результатов бенчмарков в пределах 40%). Более того, улучшение времени выполнения не обладает оптимальной подструктурой. Например, у вас есть оптимальная версия с двумя отдельными циклами, но глобальный минимум может потребовать слияния этих двух циклов. Наконец, «у нас совершенно нет надлежащих моделей машин, для которых мы выполняем компиляцию». В последнее время исследователи выяснили это на собственной шкуре. goSLP генерирует глобально оптимальный SLP-векторизованный код. Но оптимизированный согласно чему? Согласно моделям оборудования. А поскольку эти модели плохи⁴, авторы обнаружили, что сгенерированные программы не только неоптимальны, но и могут быть медленнее, чем LLVM!

▍ Веса ветвей и блок предсказания ветвления CPU

В большинстве современных компиляторов, в том числе в GCC, LLVM и ICX, условное ветвление может иметь веса. По сути, это вероятности того, будет ли выбрана ветвь. Такие веса добавляются или оптимизацией на основе профилей (PGO), или программистом при помощи встроенных функций наподобие __builtin_expect:

if (__builtin_expect(x == 0, 1)) { // Вероятность перехода по этой ветви велика
}

Заблуждение здесь заключается в том, что для архитектур x86 компилятор якобы генерирует branch hint (команды) для блока предсказания ветвления CPU. До недавнего времени это было неправдой. Хотя Intel внедрила branch hint ещё в Pentium 4, выяснилось, что на практике они не дают никакого выигрыша производительности и просто увеличивают размер кода⁵. Вы можете добавлять branch hint в ассемблерный код, но CPU просто их игнорирует.

Так для чего же используются эти hint/веса? Это подсказки для «блока предсказания ветвления» компилятора, который в основном применяется для эффективного размещения блоков кода. Например, если вероятность ветвления высока, компилятор помещает целевой блок непосредственно под текущим, чтобы выполнение «опустилось» к нему, повышая локальность кэша команд.

Но недавно Intel выпустила архитектуру Redwood Cove, в которой branch hint снова стали актуальными⁶. То есть теоретически компилятор может генерировать такие подсказки для этой архитектуры.

Однако это сложно встретить на практике. Я не смог найти ни одного примера, в котором можно было бы передать компилятору код на C и при какой-то комбинации флагов он выдал бы ассемблерный код x86 с branch hint; это не удалось сделать ни для одного из следующих компиляторов: GCC, LLVM, ICX. Я даже не знаю, как можно выбрать в качестве целевой платформы конкретно Redwood Cove. Однако мы можем заставить её генерировать hint. Если взять этот код промежуточного представления LLVM⁷:

; Source C code:
;
; void foo(int x, int y, int *p) {
;   if (__builtin_expect(x == 0, 1)) {
;     *p = y;
;   }
; }

define void @foo(i32 %x, ptr %p) {
entry:
  %cmp = icmp eq i32 %x, 0
  br i1 %cmp, label %if.then, label %if.end, !prof !0

if.then:                                          ; preds = %entry
  store i32 %x, ptr %p
  br label %if.end

if.end:                                           ; preds = %if.then, %entry
  ret void
}

!0 = !{!"branch_weights", i32 49, i32 51}

и передать его llc⁸ следующей командой:

llc < test.ll -mtriple=x86_64 -mattr=+branch-hint -enable-branch-hint

то мы получим (godbolt):

foo:                                    # @foo
        test    edi, edi
        ds  # <--- Это branch hint
        jne     .LBB0_2
        mov     dword ptr [rsi], edi
.LBB0_2:                                # %if.end
        ret

В строке 3 есть branch hint.

Для других архитектур ситуация может быть другой, но я в основном знаком только с x86.

▍ -O3 генерирует код, который гораздо быстрее кода с -O2

В 2019 году, то есть по меркам компиляторов совсем недавно, Эмери Бергер выступил с докладом на конференции Strange Loop Conference. В этом докладе он продемонстрировал доказательства следующего смелого заявления (основанного на статье Stabilizer): в Clang нет статистической разницы между -O2 и -O3⁹! Я тоже ощутил это на своём опыте, особенно с Clang. -O2 компилятора GCC менее агрессивен, чем у Clang, поэтому разница здесь есть, но не особо большая. Кроме того, -O3 почти полностью игнорирует размер кода, и это может вызывать проблемы с кэшем команд.

Мораль такова: это не чёткое правило, а один из тех случаев, когда требуется бенчмарк.

▍ Интерпретаторы Javascript являются JIT во время выполнения, потому что они заранее не знают, какие пути выполнения будут «горячими»

Знания о том, какие пути в байт-коде Javascript будут «горячими», недостаточно для генерации оптимизированного кода; нужно ещё знать и типы. А типы мы узнаём только во время выполнения. Это одна из причин того, что JIT-компиляторы компилируют код в среде выполнения.

▍ Если у вас есть компилятор, то вам не нужен интерпретатор

Это сильно зависит от ситуации. Да, вероятно, в конвейерах C/C++ интерпретатор будет не особо полезен, к тому же попробуйте-ка написать его. Но существуют и случаи, когда интерпретатор может быть полезен. Один из таких интересных случаев — WebAssembly.

Недавно Бен Титцер опубликовал статью A Fast In-Place Interpreter for WebAssembly. В этой статье Титцер рассказывает нам историю о реализациях WebAssembly.

Для ненативных языков обычно первым разрабатывается интерпретатор, а уже затем (JIT)-компилятор. Это вызвано тем, что интерпретатор обычно проще разрабатывать и использовать, а компилятор нужен для обеспечения производительности. Однако любопытно, что в экосистеме WebAssembly первыми были разработаны JIT-компиляторы. Насколько я понимаю, на это повлияло три аспекта, о которых мы поговорим ниже.

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

Убедительность. Хотя у WebAssembly изначально имелась «политическая» власть¹⁰, проектировавшие язык всё равно хотели убедить разработчиков и предоставить доказательство того, что WebAssembly и в самом деле реалистичный вариант для тех, кого волнует производительность. А такое доказательство не получить без компилятора.

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

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

▍ Промежуточный слой независим от целевой платформы

LLVM имеет самый популярный промежуточный слой, но для него это неверно. Я написал целую статью по этой теме.

▍ Компилятор выполняет оптимизацию для обеспечения локальности данных

Это почти всегда не так!¹¹ Да, компиляторы выполняют оптимизацию с целью обеспечения локальности кэша команд; мы говорили об этом выше. У компиляторных исследований по оптимизации кэша есть длинная история¹²; но ни одна из них не добралась до популярных компиляторов. Самый серьёзный пример (из известных мне) фреймворка оптимизации локальности данных — это Polly¹³, становящийся частью большого популярного компилятора. Тем не менее, он всё равно не включён в LLVM по умолчанию.

Доклад на CppCon Майка Эктона Data-Oriented Design and C++ набрал 690 тысяч просмотров не в последнюю очередь потому, что он донёс мысль о том, что компилятор C++ не оптимизирует локальность кэша. Этот доклад, по сути, положил начало¹⁴ движению data-oriented design, основная цель которого заключается в написании кода, качественного использующего кэш.

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

class DenseMap {
  struct BucketT { KeyT Key; ValueT Value; };
  unsigned NumBuckets;
  BucketT *Buckets;
...

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

Чтобы сохранить поведение кода таким же, нам придётся изменить каждое из мест, в котором используется исходный массив: распределения, места, где мы получаем ключ, где мы задаём значение и так далее. В C/C++ это очень сложно сделать надёжным образом. Но, что самое важное, компилятору просто не разрешается делать это. В общем случае компилятору C/C++ просто запрещено изменять порядок полей struct¹⁵.

И последнее: даже если компилятору разрешено делать это, у абстракций в программах на C/C++ есть слишком мало информации для того, чтобы компилятор смог опознать такие возможности¹⁶. Проще говоря, компилятор имеет слишком неточный обзор операций доступа к памяти программы, чтобы хорошо понимать, какие оптимизации пойдут на пользу.

▍ -O0 обеспечивает быструю компиляцию

Популярные компиляторы наподобие Clang и GCC очень медленные, поэтому точнее было бы сказать, что -O0 обеспечивает предсказуемый код, который можно отлаживать, а не то, что он выдаёт код быстро.

В общем случае да, -O0 быстрее, чем, допустим -O2, хоть я и не проводил крупномасштабных экспериментов, доказывающих это. Но, например, на компиляцию сборки Release zstd уходит примерно 34 секунды, а сборка Debug требует примерно 11 секунд. Нечто подобное истинно и для одного из моих проектов на пять тысяч строк, в котором используется unity-сборка. Однако даже утверждение о том, что -O0 всегда быстрее, чем -O2, не является истиной. Например, на моём десктопе для компиляции Debug-версии LLVM требуется примерно 25 минут, но примерно 23 минуты на компиляцию Release-версии¹⁷.

Суть в том, что если вам очень нужна быстрая компиляция, то нужно каким-то образом обойти стандартный конвейер компиляции, особенно если вы начинаете с C++. Один из вариантов: просто использовать компилятор поменьше, потому что они обычно быстрее (например, TinyCC). Второй вариант — пропускать хотя бы некоторые из этапов компиляции. Для этого можно, например, непосредственно сгенерировать промежуточное представление (IR) LLVM, что заметили и некоторые исследователи баз данных. В популярной статье за 2011 год¹⁸о компиляции запросов¹⁹ авторы говорят:

[Компиляции IR LLVM] обычно требуется несколько миллисекунд на компиляцию запросов, а компиляторам C или C++ для этого требуются секунды.

А компиляция запросов — это одна из ситуаций, в которых быстрая компиляция важна, поскольку она происходит онлайн.

Легко понять, почему эта цитата верна, когда мы используем в качестве компилятора Clang, потому что ему всё равно нужно пройти через IR LLVM. Кроме того, у C/C++ нет двоичного формата, который бы ускорил обработку, только текстовый. А у IR LLVM он есть.

▍ Шаблоны медленно компилируются

Это не совсем так… Шаблоны C++ медленно компилируются, поскольку модель компиляции C++ ужасна²⁰. Разумеется, шаблоны повышают сложность компиляции, но не настолько, чтобы это делало их использование непрактичным.

В данном случае можно привести пример стандартной библиотеки Dlang Phobos. На моём не особо быстром ноутбуке компиляция Phobos в оптимизированной сборке занимает примерно 12 секунд, хотя она состоит из более чем 250 тысяч строк кода с кучей шаблонов²¹. Стоит отметить, что DMD, основной компилятор D, не делает ничего особо сложного. Разумеется, главный разработчик D и DMD Уолтер Брайт — это один из лучших проектировщиков компиляторов в мире, и он точно знает, как заставить компилятор работать быстро. Но DMD не делает ничего безумного, он даже не многопоточный.

▍ Отдельная компиляция всегда себя оправдывает

Отдельная компиляция (separate compilation) — это принцип компиляции отдельного объектного файла для каждого файла исходников²². Довод о её пользе звучит так: если вы меняете один файл исходников, то вам придётся заново компилировать только один файл, и вы просто «скомпонуете» его с другими объектными файлами; заново компилировать весь проект не придётся.

Идея выглядит привлекательной, и в сфере обучения computer science она стала чем-то вроде священной догмы²³, а оттуда проникла в среды продакшена. Проблема в том, что на практике компоновка невероятно медленная. К сожалению, я не изучал компоновку достаточно глубоко, чтобы рассуждать, является ли эта проблема неотъемлемой²⁴. Но это и неважно, в реальности всё именно так.

То есть во многих проектах отдельная компиляция себя не оправдывает. Обычно гораздо более оптимальным вариантом оказывается unity-сборка, при которой мы просто включаем всё в один файл. Покажу несколько примеров. Во-первых, я убедился, что это оправдывает себя не во всех написанных мной проектах на C/C++. Допустим, до 20 тысяч строк в одном проекте. Например, minijava-cpp — это написанный на C++ компилятор MiniJava, в котором есть достаточно тяжёлый код. На моём ноутбуке он компилируется примерно за 0,7 с, а компоновка всех этих отдельных файлов занимает гораздо больше времени. Если вкратце, я в своих проектах никогда не сталкивался с кодом, для которого отдельная компиляция оказывалась лучше unity-сборки.

Если говорить не только о личном опыте, то Ubisoft тоже недавно сообщила о том, что использование unity-сборок улучшает время компиляции её игр²⁵. SQLite тоже компилирует всё в единую программу .c.

Наряду со временем компиляции, у unity-сборок есть другие преимущества. Например, мы получаем оптимизацию для программы целиком без необходимости применения оптимизации времени компоновки (см. ниже). Кроме того, всё компилируются только один раз, что сильно положительно влияет и на ускорение компиляции, и на удобство логов ошибок. Если при модели компиляции C++ (см. выше раздел про шаблоны) включить один и тот же файл в разные единицы трансляции, то он будет компилироваться по одному разу для каждой единицы. Если поверх этого добавить ещё и то, что шаблоны генерируют множество версий одного и того же, то мы получим, что один код заново компилируются снова и снова.

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

▍ Почему оптимизация времени компоновки (link-time optimization, LTO) происходит во время компоновки?

Расскажу историю. Два года назад я проводил аудит курса Викрама Адве²⁶ «Advanced Compiler Construction». Однажды Викрам задал вопрос на миллион долларов: почему оптимизация времени компоновки происходит во время компоновки? Это может показаться оксимороном, но на самом деле вопрос таков: почему оптимизация программы целиком происходит на этапе компоновки?

Это очень разумный вопрос, потому что на самом деле никого не волнует оптимизация времени компоновки; людям важна оптимизация всей программы. А в общем случае компоновщики не являются оптимизаторами, это не их работа. На самом деле, теоретически гораздо логичнее выполнять оптимизацию всей программы на промежуточном этапе (middle-end). Во-первых, задача middle-end и заключается в оптимизации. Во-вторых, middle-end работает с IR, предназначенным для оптимизации, в отличие от ассемблерного кода, обычно содержащегося в объектных файлах. Кроме того, ничего не мешает компилятору иметь глобальную картину всей программы. Он может транслировать все входные файлы C/C++ в IR LLVM, а затем получить обзор всей программы. Тогда почему же, чёрт возьми, это происходит во время компоновки? Я должен был бы сказать, что никто не знает ответа.

Викрам объяснил (изложу своими словами), что ответ кроется в печальной реальности систем сборки C/C++. Удачи вам искать файлы исходников на C/C++ в огромных проектах и разбираться, кто кого вызывает. Инструментарий C++ просто для этого не предназначен. С другой стороны, компоновщик обязан найти все объектные файлы. То есть инструментарий устроен так, что компоновщик может находить весь код для проекта. Разумеется, обычно объектные файлы содержат ассемблированный код, с которым никто не хочет возиться. Поэтому компилятор, например, просто вставляет в объектный файл IR LLVM, чтобы компилятор получал к нему доступ.

▍ Встраивание в первую очередь полезно тем, что избавляет от команды вызова

Устранение команды вызова (последовательности) идёт на пользу, но оно частично полезно из-за локальности кэша команд, а не потому, что эта команда такая уж медленная. Однако важнее всего то, что самое большое преимущество (с большим отрывом от других) встраивания (inlining) заключается в том, что оно позволяет обеспечивать трансформацию, то есть позволяет использовать другие оптимизации. Более подробное объяснение представлено здесь, но позвольте мне подчеркнуть один часто не замечаемый эффект встраивания.

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

int sat_div(int num, int denom) {
  if (denom == 0) {
    return (num > 0) ? INT_MAX : INT_MIN;
  }
  return num / denom;
}

int foo(int a) {
  int b = sat_div(a, 3);
  return b;
}

После оптимизации код foo выглядит так (godbolt):

// ... sat_div не меняется

int foo(int a) {
  // Сгенерированный код сбивает с толку, потому что
  // компилятор превратил деление в умножение.
  return a / 3;
}

То есть компилятор выполнил подстановку констант, подставив константу 3 в denom, устранил мёртвый if, потому что в этом случае условие равно false, и превратил деление в умножение. Но как он это сделал? Не с помощью межпроцедурных версий подстановки констант²⁷, устранения мёртвого кода или комбинирования команд. Нет, этот эффект возник благодаря тому, что компилятор сначала встроил вызов sat_div (godbolt), который затем обеспечил возможность интрапроцедурных²⁸ версий этих трансформаций. Иными словами, встраивание объединило всё в одну функцию, что позволило выполнить обычные трансформации. Именно поэтому встраивание считается многими (например, Чендлером Карретом) самой важной оптимизацией оптимизирующих компиляторов²⁹.

Значит ли это, что встраивание — единственный способ межпроцедурной оптимизации? С одной стороны, есть куча литературы о межпроцедурных оптимизациях, и некоторые из них добрались до продакшен-компиляторов³⁰. С другой стороны, в большинстве популярных компиляторов почти вся межпроцедурная работа выполняется встраиванием. Именно поэтому практически все последние исследования моделей затрат компиляторов связаны с встраиванием межпроцедурных оптимизаций целевых платформ³¹.

▍ Роль ключевого слова inline

Я имею в виду следующее (cppreference):

#ifndef EXAMPLE_H
#define EXAMPLE_H
 
// function included in multiple source files must be inline
inline int sum(int a, int b) {
  return a + b;
}

#endif

Основная часть документации по этому ключевому слову посвящена его роли в компоновке. И действительно, семантически оно важно именно в ней. Но ответить я хочу на следующий вопрос: связано ли это как-то с оптимизацией встраиванием?

Этот вопрос должен бы быть простым. В конце концов, Чендлер Каррет рассказал нам, что «ключевое слово inline в C++, вероятно, никак не связано с оптимизацией»³². Но на самом деле история не так проста. С одной стороны, cppreference говорит нам, что:

Изначально ключевое слово inline задумывалось как индикатор для оптимизатора того, что встраиваемая подстановка функции предпочтительнее, чем вызов функции.

а если посмотреть последний драфт стандарта C++³³, то в нём говорится следующее³⁴:

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

С другой стороны, в cppreference также говорится:

[...] ключевое слово inline для функций стало скорее значить «допустимы множественные определения», чем «предпочтительно встраивание» с C++98, это значение было расширено до переменных.

Учитывая все эти противоречивые утверждения из доверенных источников³⁵, вполне можно запутаться. Так в чём же истина? Как и во многих случаях с языком C++, «истина» — это то, что выбрала реализация. Так как я больше всего знаком с LLVM, давайте разберём его.

Итак, LLVM обращает внимание на ключевое слово inline, и делает это как минимум с 2010 года. IR LLVM имеет атрибут inlinehint³⁶, который Clang добавит к вашему определению функции, если вы добавите ключевое слово inline³⁷. Например, в этом примере Clang добавляет атрибут inlinehint к int_run. Согласно справке IR LLVM по inlinehint:

Этот атрибут указывает, что исходный код содержит подсказку, что желательно встраивание этой функции (аналогично ключевому слову «inline» в C/C++). Это просто подсказка; она ни к чему не обязует инструмент встраивания.

И в самом деле, оптимизатор повышает порог встраивания для функций, имеющих атрибут inlinehint³⁸. Однако изменение относительно мало. Так что да, ключевое слово inline как-то связано с оптимизацией, и да, оптимизатор учитывает его добавление; но не особо сильно (простите!). Думаю, если вы сильно хотите, чтобы функция была встроенной, то нужно добавить указатель always_inline, с которым ситуация совершенно иная: компилятор всегда будет встраивать такие функции, если это возможно.

▍ Больше всего для обучения среди продакшен-компиляторов подходит LLVM

Поверьте, я люблю LLVM!³⁹. Во многих смыслах, из него можно многому научиться. Но он огромен! LLVM применим к куче сценариев использования. LLVM используется и во встроенных системах, и в дата-центрах Google, и в JIT-компиляторах, и в сценариях агрессивной высокой производительности, от Zig и Rust до <название нового крутого языка>. Поэтому при изучении LLVM вы столкнётесь с множеством пограничных и особых случаев, которые он пытается обработать и которые не имеют ценности для образования. Также вы встретите множество сложных алгоритмов. Например, стандартный алгоритм Ленгауера-Тарджана уже достаточно сложно понять. А в LLVM используется ещё более сложный алгоритм, который реализован только недавно.

Так что хоть я и рекомендую когда-нибудь серьёзно изучить внутреннее устройство LLVM, но начинать с этого не стоит. Уточню: это в случае, если вам интересно обучение разработке компиляторов. Если вы пользователь, то LLVM, вероятно — лучший выбор. Если вы изучаете компиляторы, то, как и в моём комментарии на Reddit, посоветую взглянуть на компилятор Go. Это продакшен-компилятор, который разрабатывают очень серьёзные люди, но он не настолько чудовищен, как LLVM. Также я многому научился у разработчиков LDC и DMD.

▍ Неопределённое поведение только открывает возможности для оптимизаций

Нет, неопределённое поведение может и закрывать возможности оптимизации. Я написал об этом статью.

▍ Компилятор может «просто» определить неопределённое поведение

В общем случае компилятору всегда разрешается определять неопределённое поведение⁴⁰. Например, компилятору разрешено определять разыменование из указателя int*, указывающего на NULL, как 0. Однако это влияет на производительность, например, потребует, чтобы компилятор вставлял if в каждом разыменовании указателя.

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

▍ Показатель корректности в 99% — это нормально

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

Очень долгое время модели затрат писались и поддерживались вручную. Однако настраиваемые вручную модели часто очень скучно создавать и сложно масштабировать (особенно с увеличением количества архитектур); к тому же разработчики оборудования так мало говорят нам о своих архитектурах, что настраиваемые вручную модели затрат оказываются (как и основанные на машинном обучении) «чёрной магией»; их невозможно интерпретировать и понять интуитивно. Иными словами, это подходящий случай для использования машинного обучения и нейросетей, потому что они способны автоматизировать процесс. За последнее десятилетие появилось множество исследований моделей затрат на основе машинного обучения, и некоторые из таких моделей даже добрались до продакшена. Например, недавно Google начала использовать нейросетевую модель затрат для своего компилятора XLA.

Но тут есть тонкий момент. Модели затрат стали подходящей областью применения нейросетей, потому что нам не нужны строгие гарантии. В частности, моделям затрат передаётся для выбора множество корректных программ. Поэтому неважно, какой выбор сделает модель затрат — сгенерированный код всё равно будет корректным⁴¹! Так что, несмотря на то, что у нейросетей сейчас есть «небольшая» проблема, заключающаяся в том, что мы понятия не имеем, как они работают, и они не дают гарантий, в случае моделей затрат это нас устраивает. Однако нас это не устроит в случае генерации кода⁴²! Когда-то это было очевидным, но похоже, что сегодня это уже не так. Например, недавно мы получили комментарий от одного из ревьюеров Dias, в котором, по сути, говорилось «разве нельзя просто использовать LLM?» Нет! Сейчас я объясню, почему использовать LLM для генерации кода совершенно неприемлемо (по крайней мере, на текущий момент).

Всё это сводится к следующему вопросу: устроит ли нас, если сгенерированный компилятором код корректен, допустим, в 99% случаев? Здесь требуется уточнение. Значит ли то, что из 100 сгенерированных программ 99 полностью корректны и одна оказывается почти полным мусором? Очевидно, что нет, это нереалистично. Более реалистичным было бы такое предположение: из 100 строк кода компилятор генерирует корректный код для 99 из них. Я знаю, что это всё равно слишком упрощённая картина, но она вполне подходит для рассуждений. Итак, устроит ли нас это?

Надеюсь, что вы ответили «нет». С точки зрения разработчика компиляторов, это полный отстой. По сути, таким компилятором невозможно пользоваться. В лучшем случае это некий исследовательский артефакт, позволяющий изучить концепцию. Но о продакшене забудьте.
Это не подходит даже для отладки. Чтобы понять, почему, рассмотрим небольшой проект, например, из 5000 строк кода. При показателе корректности в 99% при каждой компиляции 50 строк кода будут некорректными. Пятьдесят! А хуже всего то, что вы не знаете, какие, и они будут разными при каждом изменении в коде. Вероятно, вам доводилось выискивать баг даже в одной строке кода, это может быть утомительным и долгим процессом. Представьте теперь, каково будет отлаживать 50 меняющихся строк кода! А теперь представьте всё это в крупномасштабном проекте, в котором может быть несколько миллионов строк кода⁴³. Нет уж, спасибо.

И последнее: даже если бы LLM генерировали корректный код, пока они крайне медленные по сравнению с компиляторами. Да, я говорил выше, что компиляторы не особо быстрые. Но по сравнению с LLM популярные компиляторы невероятно быстры. Так что, несмотря на многообещающее будущее и светлое настоящее LLM, есть задачи, которые они пока не могут решить. Одна из них — (онлайн-)генерация кода.

▍ Примечания

1. И именно поэтому многие из нас так ими восхищены! ↩
2. Например, Halide выполняет оптимизацию для локальности кэша. ↩
3. Например, Tiny C Compiler достаточно быстр с -O0. ↩
4. На самом деле, поскольку goSLP использует целочисленное линейное программирование, она ограничена линейными моделями, что ещё больше усугубляет ситуацию. ↩
5. Источник: исходный код GCC. ↩
6. См. комментарии в исходном коде GCC, а также раздел 2.1.1.1 руководства Intel по оптимизации. ↩
7. Он взят непосредственно из тестового случая LLVM. ↩
8. Который можно воспринимать как бэкенд LLVM. ↩
9. См. этот фрагмент видео (на 23:58). ↩
10. Достаточно взглянуть на исходную статью. Авторы разработают в компаниях-разработчиках всех популярных браузеров. ↩
11. Я говорю «почти» лишь потому, что у меня нет доказательств, требуемых для столь обобщающего заявления. Но я попросту не могу вспомнить, найти или придумать ни единого примера, когда популярный компилятор наподобие GCC или LLVM выполнял оптимизацию для локальности данных (по умолчанию, в рамках традиционных конвейеров, например, -O1, -O2 и так далее). ↩
12. Вот одна из важнейших статей: A data locality optimizing algorithm. ↩
13. Среди всего прочего… ↩
14. Или, по крайней мере, существенно увеличил количество его сторонников. ↩
15. Даже если компилятор может доказать, что изменение сохранит семантику в одной единице трансляции, то стандарты вызова не допустят этого в случае, когда код вызывается из другой единицы трансляции. ↩
16. С другой стороны, нишевые языки наподобие Halide или TACO могут выполнять существенные оптимизации именно благодаря предоставляемым ими богатым абстракциям. ↩
17. Хотя это, вероятно, вызвано обращением к диску, а не более медленным компилятором. ↩
18. Стоит отметить, что тогда Clang был быстрее, чем сегодня. ↩
19. Efficiently Compiling Efficient Query Plans for Modern Hardware. ↩
20. См. Walter Bright: C++ Compilation Speed. ↩
21. Для сравнения: компиляция DMD (референсного компилятора Dlang) занимает примерно 4 секунды. Он содержит примерно 530 тысяч строк кода на D (а также примерно 15 тысяч строк на C++), но год гораздо менее сложный. ↩
22. Обычно это только файлы .c или .cpp, но не файлы заголовков. ↩
23. Если бы в моём студенчестве вы не сделали этого, а вместо этого создали unity-сборку, то могли провалиться на экзамене. ↩
24. Моя гипотеза заключается в том, что для большинства современного ПО не является. ↩
25. Кстати, об играх: в написанной с нуля Handmade Hero Кейси тоже выяснил, что лучше использовать unity-сборки. ↩
26. Который был помощником Криса Лэттнера, и вместе они создали LLVM. ↩
27. В LLVM есть проход межпроцедурной (разреженно условной) подстановки констант, но в этом случае он ничего не делал. ↩
28. «Интра», по сути, означает «внутри». ↩
29. Лично я не согласен с этим утверждением в случае высокопроизводительного программирования. По моему опыту, важнее всего написание высокопроизводительного кода, выбор команд и распределение регистров, в основном потому, что я не могу заниматься этим сам. ↩
30. Хорошими примерами этого являются фреймворк Attributor в LLVM (хоть на момент написания статьи он не был включён по умолчанию даже в -O3), а также все межпроцедурные оптимизации GCC, описанные здесь. ↩
31. Например: MLGO: a Machine Learning Guided Compiler Optimizations Framework. ↩
32. Если честно, это написано в 2015 году. Но то, что я говорю ниже, по сути, релевантно с 2010 года (когда сообщения LLVM всё ещё были крутыми и когда атрибут inlinehint был реализован по-настоящему)! ↩
33. То есть это определённо НЕ предложение! ↩
34. Раздел 9.2.8 — «The inline specifier», пункт 2. ↩
35. Понятия не имею, что считается доверенным источником в мире C++. Стандарт C++ и все эти «авторитетные источники» всё больше становятся похожими на трансляции генераторов случайных строк. ↩
36. Как я сказал в предыдущем примечании, с 2010 года. ↩
37. Исходник. ↩
38. Исходник. ↩
39. Я ведь даже написал половину терминологии циклов LLVM. ↩
40. Под «разрешается» я подразумеваю, что он будет продолжать соответствовать стандарту C/C++ и что генеририруемый код будет соответствовать тому, что гласит стандарт. ↩
41. Хотя она и может сделать плохой выбор с точки зрения производительности. ↩
42. Я имею в виду случай, когда вы пытаетесь напрямую использовать вывод нейросети. Разумеется, можно связать, например, большие языковые модели (LLM) с другими методиками, чтобы, допустим, сделать так, чтобы принимать только тот код, корректность которого доказана или хотя бы протестирована. ↩
43. К счастью для Dias, нам не нужно выполнять такие крупномасштабные эксперименты. В реальности всё ещё более печально. Мы просто показали простые промты и некорректность их вывода. ↩

Telegram-канал со скидками, розыгрышами призов и новостями IT ?