Усаживайтесь поудобнее, ребята! Сегодня мы с вами разберём следующий увлекательный вопрос: что будет, если заинлайнить вообще всё?

Если вы пока не знакомы с техникой встраивания (inlining) то примите к сведению, что в сообществе специалистов по разработке компиляторов многие, в том числе очень авторитетные фигуры (например, Чендлер Каррут) считают этот приём наиважнейшим при оптимизации компиляторов. Подробнее о том, как устроено встраивание, рассказано здесь — мы беззастенчиво хвалимся той презентацией, с которой выступили перед участниками конференции LLVM Developers' Meeting по межпроцедурной оптимизации. Я рассказывал о встраивании и очень рекомендую вам посмотреть хотя бы первые 6 минут. В этом видео я рассказываю, почему встраивание — очень простое преобразование, а вот тут вашему вниманию предлагается реализация встраивания, предложенная великим Крисом Латтнером уже около 20 лет назад — в ней всего около 200 строк кода. К сожалению, сегодня даже само преобразование пропорционально выросло: в качестве примера взгляните хотя бы на InlineFunction.cpp.

В вышеупомянутом видео я рассказываю, что у встраивания есть свои недостатки. Иными словами, встраивание позиционируется как супер-пупер инструмент в арсенале компиляторщика, но пользоваться этой штукой следует с осторожностью. И следует ли вообще?

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

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

Можно ли встроить всё?

Вообще-то нет. Бывают такие вызовы, которые LLVM встроить просто не в состоянии; о некоторых  из них рассказано в этом видео. Отчасти дело в том, что встраивание — вообще одно из самых важных преобразований, поэтому за последние пару лет многие попытки обойтись без него оказались успешными. Популярный пример такого рода — MLGO. Тем не менее, такие маневры даются только ценой копания в нутрянке компиляторов. Код из примеров, приведённых в этой статье, в основном будет доступен для использования компилятором (за исключением кода стандартной библиотеки), и в нём не будет ни виртуальных функций, ни указателей на функции (определённо, это приёмы не для нашего кода). Таким образом, самое серьёзное осложнение при встраивании — это рекурсия (но и она встречается редко). Короче говоря, абсолютное большинство рассмотренных здесь функций поддаётся встраиванию.

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

int fac(int x) {
  if (x == 1) {
    return 1;
  }
  return fac(x - 1) * x;
}

но нельзя встроить рекурсивную функцию Фибоначчи:

int fib(int x) {
  if (x == 1) {
    return 1;
  }
  if (x == 2) {
    return 1;
  }
  return fib(x - 1) + fib(x - 2);
}

Пусть LLVM встраивает всё (остальное)

 

Казалось бы, это просто — но нет. Сравнительно легко, должно быть, повлиять на отдачу от встраивания — то есть, на ту часть LLVM, которая решает, когда будет полезно что-либо встроить. Если перед нами именно такой случай, то человеку не составит труда изменить анализ такой отдачи, не вникая во внутреннюю организацию процесса встраивания. Такая задача должна быть под силу человеку, не являющемуся экспертом по компиляторам — например, инженеру по машинному обучения. В нашем случае просто изменим анализ отдачи так, чтобы машина всегда отвечала «да»!

К сожалению, в современных компиляторах всё далеко не так просто. Я написал по этому поводу целую диссертацию. В настоящее время код преобразований и анализа отдачи тесно связан, так что невозможно изменить один из этих аспектов, не затрагивая другой. Тем не менее, встраивание в LLVM поставлено хорошо, здесь разделение лучше, чем на других этапах работы с кодом. В данном случае имеем граф, каждый узел которого — это функция в нашей программе, и, если функция A вызывает функцию B, то в графе есть ребро A→B. 

Итак, коротко опишу, как принимается решение о встраивании. Будем работать с новейшей версией LLVM, доступной на момент выхода этой статьи — 20.1.0.

Этап встраивания начинается с Inliner.cpp. Данный этап является сильно связанным компонентом из графа вызовов (CGSCC). Чтобы точнее понять, что это означает, рекомендую посмотреть эту выдержку из Чендлера Каррута, либо вторую половину моего видео. Но, возможно, вас порадует, что в контексте статьи этот момент не столь важен. Можно сказать, что встраиватель посещает каждую функцию отдельно. В общем виде процесс выглядит так: берём граф вызовов, разделяем его на сильно связанные компоненты (SCC), а затем посещаем каждый из этих компонентов в отдельности.

Почему в LLVM применяется разделение на такие сильно связанные компоненты? Потому что SCC — это, в сущности, цикл (возникающий в результате потенциально транзитивной рекурсии), а циклы требуют особого обращения. Как вы уже понимаете, идея встраивания заключается в том, что, если A вызывает B (то есть, в графе вызовов есть ребро A→B), то потенциально можно встроить B в A. Вот почему целесообразно обходить граф вызовов снизу вверх, начиная с листьев графа вызовов — то есть, функций, которые сами не вызывают других функций. Об этом я рассказываю в видео, хотя и должен признать, что в других компиляторах применяется нисходящий подход. Итак, в данном случае сначала посещаем B, встраиваем в B всё, что хотим в нём использовать. Потом у нас появляется и потенциальная возможность встроить «новый» B, в котором, прямо в теле функции, теперь уже A – будет код всех ранее встроенных функций. Но, допустим, у нас есть цикл A→B→C→A; что же с ним делать дальше? Как было сказано, обычно мы начинаем работу «снизу», то есть, с листьев. Но в данном случае листьев нет! Вы понимаете, в чём проблема? Если продвигать такую линию поведения, то мы оказываемся в цикле встраивания, когда A встраивается в C, затем C в B, а B в A, и затем опять A в C и так далее... Теперь вы понимаете, почему так сложно встраивать рекурсивные вызовы.

Как упоминалось выше, сложность встраивания в основном связана с анализом отдачи. Чтобы определить, стоит ли встраивать вызов функции, LLVM задействует так называемый InlineAdvisor. В конце концов, приходится обращаться за советом сюда.

...
std::unique_ptr<InlineAdvice> Advice =
    Advisor.getAdvice(*CB, OnlyMandatory);
...

Если проследите этот вызов, то окажетесь здесь.

std::unique_ptr<InlineAdvice> InlineAdvisor::getAdvice(CallBase &CB,
                                                       bool MandatoryOnly) {
...

Далее, если не пользоваться никакими хитроумными подсказками о встраивании (например, по подбору размера), то мы придём сюда.

std::optional<llvm::InlineCost> static getDefaultInlineAdvice(
    CallBase &CB, FunctionAnalysisManager &FAM, const InlineParams &Params) {
...

Из кода очевидно, что нас в первую очередь интересует следующий вызов к shouldInline().

...
return llvm::shouldInline(
    CB, CalleeTTI, GetInlineCost, ORE,
    Params.EnableDeferral.value_or(EnableInlineDeferral));

Но по-настоящему важным является лямбда-выражение, приведённое здесь.

auto GetInlineCost = [&](CallBase &CB) {
  bool RemarksEnabled =
      Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
          DEBUG_TYPE);
  return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
                        GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
};

Прослеживая вызовы один за другим, постепенно доберёмся именно до той функции в коде, которая нас интересует, а именно, к getInlineCost(). Ещё точнее — к этой строке.

...
InlineResult ShouldInline = CA.analyze();
...

Теперь, изучив оставшийся код в функции getInlineCost(), вы убедитесь, что она возвращает либо успех, либо неудачу. Поэтому может показаться, что заставить LLVM встраивать всё не сложнее, чем всего лишь уважать решение пользователя, но в случае необходимости добавлять return InlineCost::getAlways("Decided by our majesty") вот здесь. Давайте так и сделаем, и посмотрим, что получится.

Чтобы проверить эту гипотезу, я написал на C простой код для обработки изображений, воспользовавшись семейством библиотек stb_image* (они есть в открытом доступе). Код подробно разобран в следующем разделе.

Код для обработки изображений

Перед нами простой конвейер обработки изображений, загружающий картинки в формате JPEG, подбирающий для них подходящий размер и сохраняющий их в формате PNG. Для этого эксперимента я выбрал следующие простые картинки, не защищённые авторскими правами: работа M. Вентера, работа Лукаса Клёппеля, работа Эберхарда Гроссгаштайгера.

#define STB_IMAGE_IMPLEMENTATION
#define STB_IMAGE_RESIZE_IMPLEMENTATION
#define STB_IMAGE_WRITE_IMPLEMENTATION

#include "stb_image.h"
#include "stb_image_resize2.h"
#include "stb_image_write.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define NUM_IMAGES 3
#define MAX_RES_HEIGHT 5000
#define MAX_RES_WIDTH 5000
#define MAX_CHANNELS 3

void load_resize_write(const char *in, const char *out, uint8_t *resized_image) {
  int width, height, channels;

  uint8_t *input_image = stbi_load(in, &width, &height, &channels, 0);
  assert(input_image);
  assert(channels <= MAX_CHANNELS);

  int new_width = width / 1.3;
  int new_height = height / 1.3;

  assert(new_width < MAX_RES_WIDTH);
  assert(new_height < MAX_RES_HEIGHT);

  stbir_resize_uint8_linear(input_image, width, height, 0,
      resized_image, new_width, new_height, 0,
      (stbir_pixel_layout)channels);

  assert(stbi_write_png(out, new_width, new_height, channels, resized_image, new_width * channels));

  stbi_image_free(input_image);
}

int main() {
  uint8_t *resized_image = malloc(MAX_RES_WIDTH * MAX_RES_HEIGHT * MAX_CHANNELS);
  assert(resized_image);
  char in[256];
  char out[256];

  for (int i = 0; i < NUM_IMAGES; ++i) {
    sprintf(in, "./in/input%d.jpg", i);
    sprintf(out, "./out/out%d.png", i);
    load_resize_write(in, out, resized_image);
  }

  return 0;
}

Давайте попробуем скомпилировать наш файл со следующей опцией:

time <path to custom clang build>/bin/clang resize.c -O3 -Rpass=inline

Чтобы активировать встраиватель, наши шаги по оптимизации нужно снабдить таким флагом как -O3. Также мы попросим LLVM сообщить нам, когда он успешно встроит функцию, и передать эту информацию как -Rpass=inline, а в случае, если встроить функцию не удастся — сообщить -Rpass-missed=inline. Если это запустить, то Clang аварийно завершится. Вот какой вывод у меня получился.

Что здесь интересно отметить. Во-первых, на компиляцию тратится уйма времени! Мне на моей Mac Studio на это потребовалось примерно 39 с, что безумно много (обратите внимание: я использую оптимизированную сборку LLVM). Чуть ниже мы будем компилировать файл при помощи тривиального Clang — увидите разницу. Во-вторых, почти все функции оказались встроены; вывод, полученный от -Rpass-missed, уложился всего в 22 строки. Недостающие функции мы скоро вернём, но пока давайте сосредоточимся на тех функциях, что были встроены.

Многие функции были встроены именно потому, что в исходном коде был атрибут __always_inline__ (а это не inline; этот вопрос я подробно разбирал в предыдущей статье.). Интересно, что эти функции не входят в состав stb_image* как такового, а являются внутренними (intrinsics). Например, у меня на Mac я задействовал встроенные включаемые файлы Clang, в которых содержится следующее:

__ai __attribute__((target("neon"))) float32x4_t vreinterpretq_f32_u8(uint8x16_t __p0) {
  float32x4_t __ret;
  __ret = (float32x4_t)(__p0);
  return __ret;
}

В данном случае задачу решает __ai, определяемый как:

#define __ai static __inline__ __attribute__((__always_inline__, __nodebug__))

Если удалить все строки «always inline» (встраивать всегда), то среди оставшихся прочих строк, из которых мы узнаём, что функция была встроена, будет и «Decided by our majesty». Эта строка (a) удостоверяет, что мы добрались до модифицированной части кода и (b) мы действительно встраиваем почти всё.

Но что насчёт недостающих функций? Для всех 22 случаев мы получили одно и то же сообщение: «noinline call site attribute». Подробнее об атрибутах, применяемых при работе с LLVM, рассказано в следующем разделе.

Атрибуты в LLVM

В LLVM атрибуты можно прикреплять к всевозможным объектам — в том числе, инструкциям, функциям и т.д. Атрибут сообщает некоторую информацию —  например, что данную функцию не следует встраивать, либо что данный указатель не должен совмещаться ни с каким другим указателем (внутри LLVM это называется noalias, что соответствует ключевому слову restrict в C). LLVM очень активно использует атрибуты, подробно об этом рассказано в мануале. Даже если скомпилировать совсем небольшой фрагмент кода, LLVM IR сопроводит его множеством атрибутов.

Атрибут noinline можно ставить во многих местах. Добавляя его в определение функции, мы сообщаем оптимизатору, что нельзя встраивать никаких вызовов, направленных к этой функции. Давайте посмотрим, как это выглядит на практике. Вот простой пример. Как видите, даже при сложности -O1 функция square() встраивается. Но теперь давайте вручную сгенерируем код LLVM IR и добавим атрибут noinline — посмотрим, что получится. Вот пример из godbolt. Но, прежде чем к нему перейти, давайте сделаем лирическое отступление и разберём, что представляют собой все эти аргументы командной строки.

Лирическое отступление: получаем LLVM IR из Clang в готовом к оптимизации виде

-emit-llvm приказывает LLVM выдать LLVM IR, но по умолчанию это промежуточное представление выдаётся в двоичном формате (напр., .bc). Это отличный вариант, если такое промежуточное представление не требуется вам в человеко-читаемом виде, поскольку двоичный вариант более удобен с точки зрения обратной совместимости, он компактнее и быстрее грузится. Но, поскольку нам потребуется его читать, также добавим -S, чтобы получить на выходе текстовую версию. Опция -g0 приказывает Clang не выводить никакой отладочной информации, поскольку эти данные лишь замусоривают вывод. Дальше начинается самое интересное.

Напомню, что нам нужен неоптимизированный код, поскольку после добавления нужного атрибута мы хотим сами пропустить этот код через оптимизатор. Но он должен поддаваться оптимизации — то есть, оптимизатор не должен его игнорировать. Если вы не добавляете каких-либо иных аргументов командной строки, то у вас получится код, непригодный для оптимизации. Взгляните на это. У обеих функций есть атрибуты #0, в том числе, optnone. Этот атрибут приказывает оптимизатору вообще не притрагиваться к функции, и он очень полезен, если именно этого вы и хотите. Вот что получится, если мы попытаемся оптимизировать это LLVM IR в имеющемся виде: godbolt. Как видите, даже -O3 ни на что не влияет.

Чтобы это уладить, можно, например, просто удалить optnone вручную: godbolt. В результате остаётся noinline, именно этого мы и хотели.

Но вообще хочется обойтись без ручного вмешательства в код. Обычно в таких случаях используется -O0, но также -Xclang -disable-O0-optnone. Все эти варианты сообщают драйверу Clang, что добавлять optnone не нужно: godbolt. Но проблема в том, что по умолчанию функции всё равно получают атрибут noinline (как было разобрано выше). По сложности эта ситуация не отличается от -O2; подробнее об этом см. здесь. Однако, будет отличаться время компиляции, особенно в сборке, формируемой по принципу «встраивать всегда» — она компилируется примерно за 45 с. Обычно мы не к этому стремимся, поскольку хотим, чтобы поработал встраиватель. Я применил -O1 -Xclang -disable-llvm-passes. В таком случае -O1 позволяет обойтись без optnone и noinline, но затем приказывает драйверу остановиться. Именно это нам и надо.

--- Конец лирического отступления...

Если мы добавляем noinline сами, либо добываем такое LLVM IR, в котором он уже добавлен, эффект один: square() не встраивается, можете сами в этом убедиться: godbolt. Напоследок здесь стоит отметить, что можно добавить noinline в конкретную точку вызова, и это важно в контексте той задачи, которой мы занялись. Вот пример, где square() вызывается в двух местах. Далее добавлю атрибут, который можно будет вызывать внутри bar(): godbolt. Как видите, вызов внутри bar() остался не встроен, тогда как вызов внутри foo() встроился.

Теперь, когда вы достаточно разбираетесь в атрибутах LLVM, пришло время отметить, что можно добавить атрибут noinline в LLVM на уровне C. Для этого воспользуемся расширением GCC  attribute((noinline)), которое поддерживает Clang. Как показано в этом фрагменте, у square() есть noinline, а у foo() нет. Правда, я не знаю, как добавить его к данной конкретной точке вызова (правда, при острой необходимости можно просто предусмотреть на такой случай вспомогательную функцию, которая будет просто вызывать ту функцию, которую вы не хотите встраивать, и тогда добавить этот атрибут к такой вспомогательной функции).

Так или иначе, остро стоит вопрос: кто добавил этот атрибут? В нашем примере включены оптимизации, поэтому, очевидно, дело совсем не в режиме сложности -O0. Кроме того, не забудьте о сообщении «noinline call site attribute». Поскольку невозможно добавить точку вызова вручную, и ни на каком участке нашего кода она не включается на уровне функций, остаётся сделать вывод, что на каком-то этапе компиляции LLVM конвейер добавил её автоматически. Здесь возникает, как минимум, два вопроса. Во-первых, в каком звене конвейера она была добавлена? Во-вторых, почему мы вообще не встроили этот вызов? Разве мы не собирались встраивать всё?

Ответ на второй вопрос прост. Смотрите, это сообщение фигурирует здесь и здесь. Сам факт, что оно встречается дважды, может нас запутать, поэтому давайте сделаем так, чтобы уверенно их различать, например, к одному добавим «1», а к другому «2». Запустив такой новый двоичный файл, видим, что все интересующие нас случаи проистекают из второй точки. Ожидаемо, так как в первой точке проверяется, соседствует ли alwaysinline с noinline. Поскольку stb_image* — серьёзный код, мы не закладываемся на то, что alwaysinline в нём может сопровождать функции, не поддающиеся встраиванию. Короче говоря, все невстроенные точки вызовов возникли потому, что конвейер автоматически добавлял их при работе.

Но, всё-таки, а почему мы не встраиваем вызов? Как помните, здесь мы добавили специальный код, чтобы учитывать решение пользователя. Решение пользователя реализуется в функции getAttributeBasedInliningDecision(), в составе которой и присутствуют те два места с проверкой на noinline, которые мы разбирали выше. Вот почему мы не встраиваем эти вызовы (пусть в данных случаях они явно появились здесь не по решению пользователя, а по решению программиста).

Первый вопрос чуть тоньше: в каком звене конвейера они были добавлены, и почему? Конечно же, LLVM не добавил бы атрибут noinline непроизвольно. Если он добавлен, это должно значить, что данную функцию нельзя встроить. Если обратить внимание на сообщения-ремарки, то видно, что все 22 интересующих нас случая сопряжены с функцией stbi__out_gif_code(). Рассмотрев код этой функции, сразу видим, в чём проблема: она рекурсивная. Посмотрите здесь. Так что, логично предположить, что именно поэтому LLVM и добавил этот атрибут. Но хорошо бы эту гипотезу подтвердить.

Если коротко — она подтверждается: атрибут noinline добавляется здесь. Точную причину объяснить сложно и, поскольку здесь мы будем вынуждены вылавливать своеобразный пограничный случай в работе встраивателя LLVM, полное объяснение я опущу. Но ответ «потому, что функция рекурсивная» недалёк от истины.

Отказ Clang

Но напомню, что Clang вылетел! Необходимо выяснить, почему. У меня в Mac Studio нет прямого доступа к файлу .crash. Но, к счастью, сообщение об ошибке достаточно информативное, и из него вполне можно понять, в чём суть проблемы: мы встроили какую-то функцию с переменным количеством аргументов. У нас в исходном коде действительно есть две функции, использующие переменное количество аргументов: эта и эта. Проблема решается добавлением атрибута attribute((noinline)), но теперь длительность компиляции возрастает примерно до 50 с.

Правда, здесь есть и более серьёзная загвоздка: даже притом, что мы всеми силами старались работать только над анализом отдачи, мы нарушили преобразование, и это лишь подчёркивает проблему, о которой мы говорили выше. Но, к счастью, она легко решается. Думаю, вы помните о том пользовательском решении, которое мы обсуждали. В той функции, если пользователь применит alwaysinline, но в функции также присутствует noinline, мы выдаём первую ремарку «noinline call site attribute». Но, сразу после этого, если у функции нет атрибута noinline, мы проверяем, поддаётся ли эта функция встраиванию!

Здесь LLVM упрощает нам жизнь, предоставляя функцию isInlineViable, проверяющую, может ли функция быть встроена. Как видим здесь, эта функция возвращает false, если в рассматриваемой функции используется va_start(). Теперь можно следующим образом изменить код, чтобы он встраивал всё, что поддаётся встраиванию:

if (isInlineViable(*Callee).isSuccess()) {
  return InlineCost::getAlways("Decided by our majesty");
}

А теперь, ничего не меняя в нашем оригинальном коде, спокойно можем всё скомпилировать! Может быть, вас это даже удивит, но исполняемый файл работает без каких-либо ошибок, а сохранённые изображения, размер которых мы изменили, выглядят нормально. Можно было бы подробнее рассказать и об исполняемом файле, и о том, как долго он выполняется, но в данном случае нам важнее убедиться, что нашему коду под силу скомпилировать сложный материал.

Настоящий краш-тест: компилируем тестовый набор LLVM  

В наборе тестов для LLVM содержатся разнообразные приложения и бенчмарки. Он есть в открытом доступе и используется в качестве краш-теста для проверки компиляторов вообще и LLVM в частности. Я воспользовался следующей конфигурацией на CMake в качестве эксперимента (не считая Mac-специфичного кода):

cmake ../test-suite \
  -DCMAKE_C_COMPILER=<path to custom build>/bin/clang \
  -DCMAKE_CXX_COMPILER=<path to custom build>/bin/clang++ \
  -C../test-suite/cmake/caches/O3.cmake

Если хотите, можете добавить следующее, чтобы убедиться, что внесённые нами изменения вступили в силу, но в результате вывод получится более запутанным:

-DCMAKE_C_FLAGS="-Rpass=inline" \
-DCMAKE_CXX_FLAGS="-Rpass=inline"

Я обычно собираю SingleSource/Benchmarks и MultiSource/Benchmarks, которые в данном случае пригодятся нам и на будущее. В моей конфигурации некоторые бенчмарки не компилируются, но я на это и не рассчитываю в моей простейшей сборке Clang, так что проблемы я здесь не вижу. Они не компилируются, так как в моих вариантах LLVM я не собираю compiler-rt, так как на Mac с этим одна морока. Вот полный список бенчмарков, которые не компилируются в моей конфигурации, для обоих вариантов сборки:

SingleSource/Benchmarks/CoyoteBench/fftbench
MultiSource/Benchmarks/DOE-ProxyApps-C/RSBench

Также я отключил следующие бенчмарки:

MultiSource/Benchmarks/tramp3d-v4/
MultiSource/Benchmarks/PAQ8p

так как в тех сборках, в которых встраивается всё, на их компиляцию уходит слишком много времени.

О сравнении сборок Clang

Не сравнивайте такой Clang, который собрали сами, со встроенным вариантом, так как процедура сборки встроенного могла отличаться от вашей (например, без допущений или с compiler-rt). Сравнение и по этой причине тоже получится некорректным. Чтобы избежать таких сложностей, рекомендую просто скачать исходный код LLVM дважды и использовать для сборки два разных каталога, по одному для каждого варианта. Разумеется, можно обойтись и всего одним каталогом с исходным кодом — создать и сохранить элементарную сборку до того, как будете вносить в код какие-либо изменения, но этот вариант более рискованный. Разделив исходники, вы никогда не станете трогать те, с которыми сейчас не работаете, вот и всё. Даже если случайно нарвётесь на перекомпиляцию элементарной версии, то будете уверены: ничто не пострадало.

Как бы то ни было, следует использовать одинаковую конфигурацию CMake для обеих сборок. В следующих экспериментах я работал с такой:

cmake ../llvm -DLLVM_ENABLE_PROJECTS='clang;clang-tools-extra' -DLLVM_TARGETS_TO_BUILD=host -DCMAKE_BUILD_TYPE='Release' -DLLVM_ENABLE_ASSERTIONS=ON -G Ninja

Что касается производительности, сборка с допущениями в данном случае идёт нормально, так как в данном случае сравнение будет сильно зависеть от издержек на встраивание.

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

В остальном всё компилировалось успешно. Можете попробовать скомпилировать какие-нибудь приложения из MultiSource/Applications, но предупреждаю: если попробуете скомпилировать sqlite3, то на это уйдёт вечность.

Насколько (не)плохо встраивать всё?

Пришло время ответить на ключевой вопрос: вредна ли чем-нибудь практика «встраивать всё» (о чём нас предупреждают разработчики компиляторов)?

Длительность компиляции и размер исполняемого файла 

Во-первых, пусть мы сначала и не уделяли внимания этим параметрам, думаю, всё равно будет интересно их затронуть. Если использовать сборку вида «встраивать всегда» (при -O3), то на компиляцию конвейера для обработки изображений требуется, невероятно, около 50 секунд. Для сравнения: при использовании неусложнённого clang -O3 весь процесс занимает всего примерно 2 секунды. Двадцатипятикратная разница!

Что касается размеров исполняемого файла, при использовании элементарной версии Clang получаем исполняемый файл размером примерно 304 килобайта, а Clang в режиме «встраивать всегда» даёт файл размером 3,4 мегабайта, то есть, примерно вдесятеро больше.

Короче говоря, с точки зрения этих метрик ситуация определённо не лучшая. При этом держим в уме, что и время компиляции, и размер исполняемого файла с увеличением размера исходного кода растут экспоненциально. Дело попросту в том, что, скажем, если A() вызывает такую B(), которая вызывает C(), то при встраивании C() в B() и B() в A() код C() будет компилироваться дважды: один раз при компиляции тела B() и один раз при компиляции тела A(). Аналогично, если X() вызывается в Y() и Z(), и мы встраиваем X()в обеих этих функциях, то, опять же, её код будет компилироваться дважды. Можете себе представить, какой здесь будет взрывной рост.

Вот почему порой бывает возможно скомпилировать большое приложение, если при этом требуется скомпилировать множество мелких единиц, однако совершенно невозможно, если оно содержит немногочисленные, но очень крупные блоки для компиляции. Например, в MultiSource/JM содержится примерно 65 000 строк кода, а в MultiSource/sqlite3 — около 53 000 строк кода. Но в первом случае 65 000 строк кода разнесены в JM на множество единиц компиляции, тогда как в случае с sqlite3 у нас всего одна единица компиляции (состоящая из sqlite3.c и входящего в него заголовочного файла .h). Как правило, на компиляцию JM уходит примерно 25 секунд, а на компиляцию sqlite3... ну, я ждал 4 часа и устал ждать.

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

Наконец, подходим к самому важному вопросу: наблюдается ли при этом какое-либо ухудшение производительности?

Начнём с конвейера обработки изображений. В данном случае кажется очевидным, что нет. Обе версии с -O3 выполняются примерно за 2,9 с. При -O2 разница между двумя сборками также незаметна. При -O1 также не наблюдается разница между двумя рассматриваемыми сборками, однако она очень заметна между опциями -O2 и -O3, так как теперь каждая из двух выполняется примерно за 3,3 с).

Теперь перейдём к сравнению тестовых наборов. Вот этим я пользовался для прогона бенчмарков (по одному разу для каждой сборки):

<path to build>/bin/llvm-lit -sv -j 1 -o results.json ./SingleSource/Benchmarks/ ./MultiSource/Benchmarks/

Если говорить об общем времени, затраченном на все бенчмарки, на неусложнённую сборку ушло примерно 258 секунд, а на сборку, в которой всё встраивалось — примерно 260 секунд. То есть, разницы практически нет (на основании 309 тестов). При помощи двух файлов .json и следующего кода на Python можно проверить, наблюдается ли существенная разница по какому-нибудь конкретному бенчмарку.

Код Python для сравнения результатов

import pandas as pd
import json
from scipy.stats import gmean

def read_json(f):
  with open(f, 'r') as fp:
    d = json.load(fp)
  return d['tests']

def process_tests(tests):
  names = []
  times = []
  for t in tests:
    name = t['name']
    name = name[len("test-suite :: "):]
    name = name[:-len('.test')]
    name = name.replace('MultiSource/Benchmarks', 'MS')
    name = name.replace('SingleSource/Benchmarks', 'SS')
    names.append(name)
    times.append(t['metrics']['exec_time'])
  ### END FOR ###
  return names, times

van = read_json('results_vanilla.json')
inl = read_json('results_inline.json')

names_van, times_van = process_tests(van)
names_inl, times_inl = process_tests(inl)
assert names_van == names_inl

ser_van = pd.Series(times_van, index=names_van)
ser_inl = pd.Series(times_inl, index=names_van)

ser_rel1 = ser_van / ser_inl
ser_rel2 = ser_inl / ser_van
ser_abs = ser_van - ser_inl
df = pd.DataFrame(data={'rel1': ser_rel1, 'rel2': ser_rel2, 'abs': ser_abs, 'van': ser_van}, index=ser_rel1.index)
print('--- 5 fastest benchmarks with always-inline')
print(df.nlargest(50, columns=['rel1']))
print()
print('--- 5 fastest benchmarks with vanilla')
print(df.nlargest(50, columns=['rel2']))
print('-----')
m_perc = (gmean(ser_rel1) - 1) * 100
print(f'Geomean relative speedup of inline vs vanilla: {m_perc:.3}%')

Подробные результаты приведены ниже:

Подробные результаты

--- 5 самых быстрых бенчмарков, когда всё встраивается
                                                        rel1      rel2     abs     van
MS/Prolangs-C++/fsm/fsm                             4.166667  0.240000  0.0019  0.0025
MS/Prolangs-C/unix-tbl/unix-tbl                     3.375000  0.296296  0.0019  0.0027
MS/Prolangs-C++/family/family                       3.000000  0.333333  0.0012  0.0018
SS/Stanford/FloatMM                                 2.904555  0.344287  0.0878  0.1339
MS/Prolangs-C++/deriv2/deriv2                       2.714286  0.368421  0.0012  0.0019
MS/Prolangs-C/simulator/simulator                   2.714286  0.368421  0.0012  0.0019
MS/Prolangs-C/assembler/assembler                   2.666667  0.375000  0.0015  0.0024
MS/Prolangs-C/unix-smail/unix-smail                 2.566667  0.389610  0.0047  0.0077
MS/Prolangs-C++/trees/trees                         2.250000  0.444444  0.0010  0.0018
MS/Prolangs-C/allroots/allroots                     2.166667  0.461538  0.0007  0.0013
MS/Prolangs-C/agrep/agrep                           2.111111  0.473684  0.0050  0.0095
MS/Prolangs-C++/simul/simul                         1.933333  0.517241  0.0014  0.0029
MS/Prolangs-C++/garage/garage                       1.812500  0.551724  0.0013  0.0029
SS/Polybench/linear-algebra/solvers/durbin/durbin   1.800000  0.555556  0.0028  0.0063
MS/MiBench/security-sha/security-sha                1.660000  0.602410  0.0033  0.0083
MS/Prolangs-C/gnugo/gnugo                           1.639269  0.610028  0.0140  0.0359
MS/Prolangs-C/bison/mybison                         1.586207  0.630435  0.0017  0.0046
MS/BitBench/uudecode/uudecode                       1.581395  0.632353  0.0025  0.0068
MS/Prolangs-C++/vcirc/vcirc                         1.571429  0.636364  0.0004  0.0011
MS/mediabench/g721/g721encode/encode                1.533019  0.652308  0.0113  0.0325
MS/TSVC/Symbolics-flt/Symbolics-flt                 1.528159  0.654382  0.1116  0.3229
MS/Prolangs-C++/office/office                       1.500000  0.666667  0.0004  0.0012
MS/mediabench/gsm/toast/toast                       1.500000  0.666667  0.0030  0.0090
SS/Shootout-C++/Shootout-C++-moments                1.469231  0.680628  0.0061  0.0191
MS/MiBench/security-rijndael/security-rijndael      1.469072  0.680702  0.0091  0.0285
SS/McGill/exptree                                   1.400000  0.714286  0.0002  0.0007
MS/Prolangs-C++/employ/employ                       1.393443  0.717647  0.0024  0.0085
MS/mediabench/adpcm/rawcaudio/rawcaudio             1.384615  0.722222  0.0005  0.0018
MS/Prolangs-C/compiler/compiler                     1.380952  0.724138  0.0008  0.0029
MS/MiBench/consumer-jpeg/consumer-jpeg              1.357143  0.736842  0.0005  0.0019
MS/Prolangs-C/cdecl/cdecl                           1.346154  0.742857  0.0009  0.0035
SS/Shootout-C++/EH/Shootout-C++-except              1.320276  0.757417  0.0556  0.2292
SS/BenchmarkGame/n-body                             1.295739  0.771760  0.0354  0.1551
SS/Stanford/Oscar                                   1.285714  0.777778  0.0002  0.0009
SS/Misc-C++-EH/spirit                               1.282140  0.779946  0.2706  1.2297
MS/FreeBench/mason/mason                            1.266839  0.789366  0.0103  0.0489
MS/McCat/08-main/main                               1.253731  0.797619  0.0017  0.0084
MS/MiBench/office-stringsearch/office-stringsearch  1.250000  0.800000  0.0002  0.0010
SS/Misc/flops-8                                     1.233927  0.810421  0.0302  0.1593
SS/Polybench/linear-algebra/blas/gesummv/gesummv    1.200000  0.833333  0.0001  0.0006
SS/Shootout-C++/Shootout-C++-hello                  1.200000  0.833333  0.0001  0.0006
MS/Prolangs-C++/ocean/ocean                         1.185714  0.843373  0.0026  0.0166
MS/DOE-ProxyApps-C/SimpleMOC/SimpleMOC              1.181476  0.846399  0.0578  0.3763
MS/McCat/17-bintr/bintr                             1.174089  0.851724  0.0043  0.0290
SS/Misc/himenobmtxpa                                1.159236  0.862637  0.0175  0.1274
SS/Stanford/Queens                                  1.157895  0.863636  0.0006  0.0044
MS/TSVC/CrossingThresholds-flt/CrossingThreshol...  1.117769  0.894640  0.0684  0.6492
MS/BitBench/uuencode/uuencode                       1.114754  0.897059  0.0007  0.0068
MS/MiBench/consumer-typeset/consumer-typeset        1.107527  0.902913  0.0040  0.0412
SS/Stanford/Bubblesort                              1.103896  0.905882  0.0008  0.0085

--- 5 самых быстрых бенчмарков при неусложнённой сборке
                                                        rel1      rel2     abs     van
SS/Shootout-C++/Shootout-C++-wordfreq               0.206897  4.833333 -0.0023  0.0006
SS/Shootout-C++/Shootout-C++-wc                     0.250000  4.000000 -0.0015  0.0005
MS/MiBench/security-blowfish/security-blowfish      0.625000  1.600000 -0.0003  0.0005
SS/Shootout/Shootout-ackermann                      0.646617  1.546512 -0.0047  0.0086
SS/Stanford/Quicksort                               0.675926  1.479452 -0.0070  0.0146
MS/McCat/05-eks/eks                                 0.692308  1.444444 -0.0004  0.0009
SS/Stanford/Puzzle                                  0.711575  1.405333 -0.0152  0.0375
MS/Prolangs-C++/objects/objects                     0.714286  1.400000 -0.0002  0.0005
MS/mediabench/jpeg/jpeg-6a/cjpeg                    0.725490  1.378378 -0.0014  0.0037
MS/Prolangs-C++/city/city                           0.731707  1.366667 -0.0011  0.0030
SS/Stanford/Perm                                    0.743902  1.344262 -0.0042  0.0122
SS/Stanford/Towers                                  0.750000  1.333333 -0.0028  0.0084
SS/Shootout-C++/Shootout-C++-strcat                 0.755968  1.322807 -0.0092  0.0285
MS/MiBench/network-patricia/network-patricia        0.780992  1.280423 -0.0053  0.0189
SS/Polybench/stencils/jacobi-1d/jacobi-1d           0.785714  1.272727 -0.0003  0.0011
MS/McCat/03-testtrie/testtrie                       0.796610  1.255319 -0.0012  0.0047
MS/Prolangs-C++/NP/np                               0.800000  1.250000 -0.0001  0.0004
MS/Prolangs-C/fixoutput/fixoutput                   0.812500  1.230769 -0.0003  0.0013
SS/Stanford/Treesort                                0.816327  1.225000 -0.0054  0.0240
MS/mediabench/mpeg2/mpeg2dec/mpeg2decode            0.827586  1.208333 -0.0015  0.0072
SS/Shootout-C++/Shootout-C++-objinst                0.833333  1.200000 -0.0001  0.0005
SS/Shootout-C++/Shootout-C++-spellcheck             0.833333  1.200000 -0.0001  0.0005
MS/MiBench/office-ispell/office-ispell              0.857143  1.166667 -0.0001  0.0006
MS/Prolangs-C++/deriv1/deriv1                       0.857143  1.166667 -0.0001  0.0006
MS/Prolangs-C++/shapes/shapes                       0.857143  1.166667 -0.0001  0.0006
SS/Shootout-C++/Shootout-C++-sumcol                 0.857143  1.166667 -0.0001  0.0006
SS/Stanford/IntMM                                   0.857143  1.166667 -0.0001  0.0006
MS/McCat/18-imp/imp                                 0.864130  1.157233 -0.0025  0.0159
MS/MallocBench/gs/gs                                0.866197  1.154472 -0.0019  0.0123
MS/FreeBench/neural/neural                          0.874126  1.144000 -0.0054  0.0375
SS/Shootout-C++/Shootout-C++-reversefile            0.875000  1.142857 -0.0001  0.0007
SS/Polybench/linear-algebra/blas/symm/symm          0.888889  1.125000 -0.0001  0.0008
SS/Dhrystone/fldry                                  0.890285  1.123236 -0.0227  0.1842
MS/Prolangs-C/football/football                     0.894737  1.117647 -0.0002  0.0017
SS/Shootout/Shootout-lists                          0.899421  1.111826 -0.1963  1.7554
MS/Olden/treeadd/treeadd                            0.905782  1.104019 -0.0044  0.0423
SS/CoyoteBench/almabench                            0.915684  1.092080 -0.0872  0.9470
MS/TSVC/Reductions-flt/Reductions-flt               0.928026  1.077556 -0.1179  1.5202
MS/Olden/voronoi/voronoi                            0.930070  1.075188 -0.0050  0.0665
MS/llubenchmark/llu                                 0.935111  1.069392 -0.0993  1.4310
SS/Shootout-C++/Shootout-C++-hash                   0.937424  1.066753 -0.0103  0.1543
MS/Ptrdist/ks/ks                                    0.941482  1.062155 -0.0124  0.1995
MS/Olden/perimeter/perimeter                        0.941704  1.061905 -0.0026  0.0420
SS/Shootout-C++/Shootout-C++-ary2                   0.943396  1.060000 -0.0003  0.0050
SS/Shootout-C++/Shootout-C++-lists1                 0.958273  1.043544 -0.0029  0.0666
MS/TSVC/StatementReordering-dbl/StatementReorde...  0.958845  1.042921 -0.0479  1.1160
SS/Shootout/Shootout-heapsort                       0.959572  1.042132 -0.0370  0.8782
SS/Polybench/linear-algebra/kernels/bicg/bicg       0.961538  1.040000 -0.0003  0.0075
SS/Shootout-C++/Shootout-C++-fibo                   0.964357  1.036960 -0.0267  0.7224
SS/Polybench/linear-algebra/blas/gemver/gemver      0.966102  1.035088 -0.0004  0.0114
-----
Geomean relative speedup of inline vs vanilla: 4.66%

Какой вывод можно из этого сделать? По-моему, различия слишком невелики и не позволяют ничего категорически заявлять об этой конфигурации (но здесь есть, что ещё исследовать, подробнее об этом см. ниже). Но, как бы то ни было, при встраивании код ускоряется. Результаты позволяют заключить, что версия «встраивать всегда» показывает геометрическое среднее ускорение в 4,66%.

Выводы и дальнейшие исследования

Экспериментальные данные, полученные выше, не позволяют уверенно утверждать, что в результате встраивания всегда генерируются более медленные исполняемые файлы. Но мы можем быть уверены, что как время компиляции, так и размер исполняемого файла резко возрастают, если встраивать вообще всё. Лично я делаю из этих экспериментов такой вывод: не бойтесь ставить  attribute((always_inline)). Я заостряю на этом внимание, так как очень авторитетные люди из сообщества разработчиков компиляторов призывают вообще не пользоваться встраиванием! Среди них особенно выделяется Чендлер Каррут. В этом видео он говорит:

При реализации делаются определённые уловки, например, применяется атрибут always_inline поддерживаемый и GCC, и ICC, и Microsoft [т.e., MSVC]. У каждого есть такой атрибут, верно? Настоятельно рекомендую не использовать этот атрибут — никогда не использовать, ладно? Если вы им пользуетесь, это значит, что вы нашли баг во встраивателе, возникший в результате оптимизации. Если вы всё-таки собираетесь применить этот атрибут, то попрошу вас — пожалуйста, пожалуйста, сначала сообщите о баге в оптимизаторе, а потом добавьте атрибут с кратким комментарием примерно следующего содержания: «кстати, этот атрибут стоило бы убрать, как только вот тут будет исправлен баг, из-за которого у нас страдает производительность». Всегда следует отталкиваться от метрик производительности и всегда сообщать о баге с жалобой в адрес оптимизатора: «кстати, а почему вы это не встроили»?  

Не уверен, что могу целиком согласиться с этой аргументацией. Да, безусловно, решения следует принимать на основе метрик производительности. И о багах оптимизатору нужно сообщать. Но утверждать, что встраиванием вообще не следует пользоваться — это другая история. Такой софт как LLVM развивается медленно, и при работе с ним непозволительно дожидаться, пока всё будет исправлено. Особенно это актуально сейчас, когда мы всё сильнее применяем инструменты машинного обучения, при работе с которыми исправить специфический случай сложно — нельзя обойтись добавлением одного if. Поэтому я более склоняюсь к менее резкой формулировке вышеприведённого тезиса. С имеющимся кодом нужно уметь работать — тем не менее, отправляя соответствующие сообщения о багах. Так практичнее.

Не уверен, стоит ли вам комментировать эту статью. Наверняка у вас есть более важные дела, чем доискиваться, исправлен ли уже в LLVM тот или иной баг со встраиванием. Честно говоря, кого это волнует? Это вам говорит компиляторщик-энтузиаст, я же знаю, что нас таких немного. Но абсолютно не сомневайтесь, что добавить  always_inline тут или там — это не конец света, мы убедились в этом на экспериментах. Это тем более верно, если применять такой атрибут точечно, отталкиваясь от данных о производительности, а не ставить его везде где заблагорассудится.