Profile-guided optimization (далее PGO) — техника оптимизации программы компилятором, нацеленная на увеличение производительности выполнения программы. В отличии от традиционных способов оптимизации анализирующих исключительно исходные коды, PGO использует результаты измерений тестовых запусков оптимизируемой программы для генерации оптимального кода. Тестовые запуски выявляют какие части программы исполняются чаще, а какие реже. Преимущество такого подхода в том что компилятор не строит предположений при выборе способа оптимизации, а базируется на реальных данных, собранных во время выполнения программы. Необходимо учитывать то, что тестовые запуски программы должны выполнятся по наиболее типичному сценарию, что бы статистика была репрезентативной, иначе производительность программы может даже уменьшиться.PGO может включать следующие типы оптимизаций (источник):
- Inlining – например, если функция A часто вызывает функцию B, и функция B достаточна мала, тогда функция B встраивается в A. Это делается на основе реальной статистике запусков программы.
- Virtual Call Speculation – если виртуальный вызов, или вызов через функцию указатель часто указывает на конкретную функцию, то он может быть заменён на условно-прямой (срабатывающий при выполнении условия) вызов конкретной функции, и даже функция может быть встроена (inline).
- Register Allocation – оптимизация распределения регистров на основе собранных данных.
- Basic Block Optimization – эта оптимизация позволяет поместить совместно вызываемые блоки кода в общую страницу памяти, что минимизирует количество используемых страниц и перерасход памяти.
- Size/Speed Optimization – функции в которых программа тратит значительную часть времени могут быть оптимизированы по скорости выполнения.
- Function Layout – на основе графа вызовов, функции которые принадлежат одной цепочки исполнения будут помещены в одну и ту же секцию.
- Conditional Branch Optimization – оптимизация ветвлений и switch выражений. На основе тестовых запусков, PGO помогает определить какие условия в switch выражении выполняются чаще других. Эти значения затем могут быть вынесены из switch выражения. То же самое относится к if/else — компилятор может упорядочить ветви на основе того какая из них вызывается чаще.
- Dead Code Separation – код который не вызывался во время тестовых запусков может быть перемещён в специальную секцию, что бы исключить его попадание в часто используемые страницы памяти.
- EH Code Separation – код обработки исключения, выполняющийся в исключительных случаях, может быть перенесён в отдельную секцию, если возможно определить что исключения срабатывают в конкретно определённых условиях.
- Memory Intrinsics – (затрудняюсь правильно перевести, привожу оригинал) The expansion of intrinsics can be decided better if it can be determined if an intrinsic is called frequently. An intrinsic can also be optimized based on the block size of moves or copies.
Я расскажу о самом простом способе выполнения PGO при использовании компилятора GCC. Поддержка PGO в GCC осуществляется за счет двух флагов -fprofile-generate и -fprofile-use. Общая схема компиляции при этом выглядит так:
- Скомпилировать программу со всеми оптимизационными флагами и флагом -fprofile-generate. Этот флаг необходимо установить как компилятору так и компоновщику (linker). Например, так:
g++ -O3 -march=native -mtune=native -fprofile-generate -Wall -c -fmessage-length=0 -MMD -MP -MF«src/pgo-1.d» -MT«src/pgo-1.d» -o «src/pgo-1.o» "../src/pgo-1.cpp"
g++ -fprofile-generate -o «pgo-1» ./src/pgo-1.o
- После успешной компиляции, необходимо выполнить тестовый запуск программы с наиболее типичным вариантом её использования. Если все сделано верно, то в результате тестового запуска появится файл статистики с расширением gcda.
- Скомпилировать программу со всеми оптимизационными флагами и флагом -fprofile-use. Этот флаг необходимо установить как компилятору так и компоновщику (linker). Например, так:
g++ -O3 -march=native -mtune=native -fprofile-use -Wall -c -fmessage-length=0 -MMD -MP -MF«src/pgo-1.d» -MT«src/pgo-1.d» -o «src/pgo-1.o» "../src/pgo-1.cpp"
g++ -fprofile-use -o «pgo-1» ./src/pgo-1.o
При этом gcc воспользуется файлом статистики созданном в пункте 2, либо сообщит о том что файл не найден.
Вот такая несложная схема. Впрочем, никогда не стоит бездумно применять какие-либо оптимизации. Всегда прежде чем что-то оптимизировать необходимо первоначально создать тестовую среду, которая позволит эффективно оценить полезность тех или иных оптимизационных флагов.
Рассмотрим эффективность PGO на простом примере. Код исследуемой программы:
#include <iostream>
#include <algorithm>
#include <stdlib.h>
const size_t MB = 1024*1024;
size_t MOD = 0;
unsigned char uniqueNumber () {
static unsigned char number = 0;
return ++number % MOD;
}
int main(int argc, char** argv) {
if (argc < 3) {
return 1;
}
size_t BLOCK_SIZE = atoi(argv[1]) * MB;
MOD = atoi(argv[2]);
unsigned char* garbage = (unsigned char *) malloc(BLOCK_SIZE);
std::generate_n(garbage, BLOCK_SIZE, uniqueNumber);
std::sort(garbage, garbage + BLOCK_SIZE);
free(garbage);
return 0;
}
Программа создает массив unsigned char в несколько мегабайт в зависимости от первого передаваемого параметра. Затем заполняет его последовательностью повторяющихся символов в зависимости от второго передаваемого параметра. После этого сортирует полученный массив. Например:
./prog 32 3 — создаст массив размером 32MB, заполненный по схеме: {1, 2, 1, 2,… }. Затем выполнит его сортировку.
./prog 16 7 — создаст массив размером 16MB, заполненный по схеме: {1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6,… }. Затем выполнит его сортировку.
Таким образом, задавая разные параметры мы можем влиять на частоту срабатываний условных переходов при выполнении сортировки данного массива и на размер обрабатываемых данных. Благодаря этому мы сможем протестировать Conditional Branch Optimization описанную ранее. Написав не хитрый скрипт, я провел 1792 теста с различными параметрами и свел их в графики ниже. Варьировался размер массива: {2, 4, 8, 16, 32, 128, 256}, и делитель {1..256}.
Процент прироста производительности (накопленный)
На этом графике проценты накладываются друг на друга. Нужно смотреть на площадь залитую конкретным цветом, а не на абсолютные значения приведённые на оси y. Чем площадь больше тем больше прирост производительности. График наглядно показывает прирост производительности для разных значений размера массива.
Процент прироста производительности (простой)
На оси y приведены проценты прироста производительности относительно не оптимизированной программы. На оси x приведены используемые делители.
Абсолютные значения производительности
На графиках приведённых ниже на оси y приведено время выполнения программы в секундах, а на оси x используемый делитель. В легенде -PGO значит без оптимизации, +PGO с оптимизацией.
Выводы
Для данной конкретной программы оптимизация на базе PGO чрезвычайно полезна и дает стабильный прирост производительности на уровне 5-25%.
Файл с исходным кодом, скриптом тестирования и скриптом построения графиков можно скачать.
Структура архива такова:
pgo-1/fprofile-generate — make скрипт для сборки с флагом -fprofile-generate
pgo-1/fprofile-use — make скрипт для сборки с флагом -fprofile-use
pgo-1/Release — make скрипт для сборки обычной версии
pgo-1/src — исходный код
pgo-1/graph.pl — скрипт генерации графиков (читает файл super_log)
pgo-1/run.sh — скрипт для запуска цикла тестирования
graph.pl работает с лог файлом, формат которого соответствует выводу команды run.sh
Например, запустить можно так:
./run.sh > log 2>&1
tail log |grep -A2 PGO
UPD. Тестовый проект собирался с флагами -O3 -march=native -mtune=native без PGO, и -O3 -march=native -mtune=native с PGO. Все графики показывают прирост относительно -O3 -march=native -mtune=native.
Зеркало статьи
