Оптимизация с использованием данных профилятора. Часть 1

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

Как вы знаете clang является оптимизирующим компилятором. То есть он пытается перепаковать исходный код в нечто наиболее эффективное для конкретной архитектуры процессора. И для большей части оптимизаций знания самого кода вполне достаточно. Однако существует ряд оптимизаций, которые могут работать эффективнее в случае если на этапе компиляции известно как код используется во время исполнения. К таким оптимизациям относятся к примеру: девиртуализация вызовов виртуальных методов (devitualization of virtual methods), порядок расположения блоков кода в исполняемом файле (instructions memory layout) и подстановка функций (functions inling). Для простоты статьи я остановлюсь подробнее на последней оптимизации, про первые две есть неплохое видео на ютуб, ссылку на которое я оставлю в конце статьи.

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

int foo(int arg) {
   return arg + 1;
}


int main(int argc, char*argv[]) {
   return foo(argc); // Место вызова функции
}

При прямолинейной компиляции этого кода мы получим что-то типа:

foo(int):
       lea     eax, [rdi + 1] // Логика функции
       ret


main:
       ... // Инициализация аргументов
       call    foo(int) // Прыжок в область кода с реализацией функции
       ret

Недостаток этого кода в том, что прыжок (call) является накладной операцией, так как переходы по сегментам исполняемого файла влияют на эффективность исполнение и компиляторы стараются сводить их к минимуму.

Если мы соберем этот пример с флагом -O2 мы увидим следующий код:

main:
       lea     eax, [rdi + 1]
       ret

То есть компилятор подставил код самой функции вместо ее вызовы.

У вас скорее всего возник вопрос “а почему бы тогда не подставлять вообще все функции в программе?”. Хороший вопрос, однако большинство функций в реальном коде достаточно большие и вызываются во многих местах кода, если подставлять их всех везде размер исполняемого файла очень быстро станет слишком большим. Компиляторы стараются соблюдать некий компромисс между скоростью исполнения и размером бинарного файла. Для этого есть понятие квоты подстановок и при обычных условиях компилятор руководствуется рядом эвристик для того чтобы решить какой из методов подставить. Допустим в следующем примере:

int foo(int arg) {
  return arg + 1;
}

int bar(int arg) {
  int c = arg * 2;
  int d = c + arg * 3;
  return c + d;
}

int main(int argc, char*argv[]) {
   int result;
   for (int i = 0; i < 1000000000; i++) {
       if (argc > 2) {
           result += foo((int)argv[2][0]);
       } else {
           result += bar((int)argv[1][0]);
       }
   }


   return result;
}

При прочих равных если у компилятора осталась одна квота на подстановку, то он выберет функцию foo так как она короче (я сейчас игнорирую остальные оптимизации).
Однако что если в реальной жизни пользователь намного чаще вызывает эту программу с одним аргументом? Проще говоря, если функция bar вызывается намного чаще, чем функция foo то ее подстановка становится более выгодной. Но что бы понять это компилятору нужна информация о том как программа используется пользователем.

Способов получения этой информации несколько, один из них – использование стороннего профилятора во время выполнения для сбора семплирования. В линуксе таким профилятором для CPU служит утилита perf.

Оптимизация с использованием данных профилятора. Часть 2

Давайте посмотрим как это может работать.

Шаг 1: Компилируем программу с несколькими флагами позволяющими сопоставить собранные метрики с исходным кодом:

clang++ -O2 -gline-tables-only -fdebug-info-for-profiling -funique-internal-linkage-names sample.cc -o sample

Шаг 2: Исполняем собранную программу с профилятором:

sudo perf record -b -e BR_INST_RETIRED.NEAR_TAKEN:uppp ./sample 1

Шаг 3: Так как perf это внешняя для llvm утилита, нам нужно сконвертировать результат ее работы в формат понятный для компилятора. Для этого в llvm есть утилита llvm-profgen:

llvm-profgen --binary=./sample --output=sample.prof --perfdata=perf.data

Шаг 4: Перекомпилируем исходную программу с собранной статистикой:

clang++ -O2 -fprofile-sample-use=sample.prof sample.cc -o sample_pgo

Давайте глянем на собранную статистику профилятора. Для этого в llvm есть другая утилита llvm-profdata которая позволяет объединять статистики, смотреть их содержимое и многое другое:

llvm-profdata show --sample sample.prof

Команда выше покажет нам следующее:

Function: main: 1965000, 0, 7 sampled lines
Samples collected in the function's body {
  …
  6: 82500, calls: _Z3bari:82500 
  …
}

Имея эту информацию на руках компилятор может понять что функция bar вызывается намного чаще чем функция foo и проработать эффективнее. Важное замечание: Если сценарий использования программы в реальной жизни резко меняется, то результат сбора PGO данных может повлиять негативно на производительность программы, так что чаще всего в реальной жизни PGO данные пере-собираются в реальном времени.

В следующей части я попробую собрать сам clang вместе и без PGO и сравню производительность сборки какого нибудь примера.

На последок видео о котором я говорил в начале: https://www.youtube.com/watch?v=3RtMMHkVsDg