GCC Profile-guided optimization

    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. Общая схема компиляции при этом выглядит так:
    1. Скомпилировать программу со всеми оптимизационными флагами и флагом -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

    2. После успешной компиляции, необходимо выполнить тестовый запуск программы с наиболее типичным вариантом её использования. Если все сделано верно, то в результате тестового запуска появится файл статистики с расширением gcda.
    3. Скомпилировать программу со всеми оптимизационными флагами и флагом -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.

    Зеркало статьи
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 26

      +1
      > Memory Intrinsics
      это всякие memmove, memcpy,…
      Вместо вызова функции они могут быть заинлайнены.
      Ну и оптимизация по параметру размера копируемого/перемещаемого блока памяти.
      Грубо говоря, если размер всегда кратен 4, то добивку остатка от деления на 4 можно не делать, а просто копировать 4байтовыми словами.
        +3
        ах да, и график с нулём в -5 это эпично.
          0
          Там есть пару точек где было незначительное уменьшение производительности, поэтому я взял шакалу от -5%. Хотя согласен выглядит странно, надо было наверное взять от 0%. Но перестраивать графики уж мочи нет.
          +1
          Не знаю как GCC, а вот clang инлайнит и простые вызовы mem*(), если сочтет это нужным.
          +1
          Когда я работал над GCC, PGO не очень хорошо поддерживался и на тот момент (4.6.0), не рекомендовался к использованию для сборки серьезных приложений.
          –1
          сделав профайлинг PGO должен был увидеть, что вы запоняете массив одними и теми же числалами и сразу выдавать правильный результат сортировки )

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

          почему вы собираете проект без -O3 хорошо бы сравнить, только оптимизации по-умолчанию (-O0), -O3( возможно еще и 1-2), PGO и PGO+-O3, тогда можно сказать: «Вот добавили PGO и это нам дало дополнительные Х процентов к уже оптимизированному коду -O3»
            0
            Я как раз собираю проект с -O3 -march=native -mtune=native без PGO, и -O3 -march=native -mtune=native с PGO. Просто забыл указать это в статье. Все графики показывают прирост к -O3 -march=native -mtune=native.

            Может быть стоит проверить ещё и с другими флагами.
              0
              торможу ) у меня MacOS subdir.mk открыл пустым, какойто левой софтиной… просмотрел его текстовым вьювером — все на месте )
            +2
            PGO это просто невероятная штука. Использовал ее для сборки эмулятора генезиса Picodrive для Dingoo A320, получил двойной прирост в скорости. Есть одна особенность — когда кросс-компилируете, ну или просто компилируете с profile-generate, gcda файлы будут сохраняться в папке, где программа была скомпилирована, поэтому есть такая хорошая переменная GCOV_PREFIX.
              0
              Ага. А я не знал про GCOV_PREFIX и по старинке просто копировал gcda в место где ожидает его GCC. :)
              +1
              Всё-таки есть ложка дёгтя. Если вы используете PGO, то процесс полной сборки у вас существенно замедляется, а также требует дополнительных тестовых данных (на которых вы запускаете программу, чтобы собрать статистику). Чтобы решить эту проблему возникает естественное желание на билдовой машине собирать готовую версию с PGO (и хранить там тестовые данные), а на локальных — обходиться «по старинке». Но в этом случае становится весьма трудно измерить эффект от других оптимизаций, которые тоже, конечно же, нужно делать.
                +1
                Я сейчас планирую попробовать PGO на VC и GCC на реальном проекте. Изначально думал о том, чтобы данные для профиля собрать один раз, хранить в репозитории, и, скажем, обновлять раз в месяц (проект не сильно активно изменяется).
                Получится ли такое? Или это как файлы с символами — должно быть абсолютное совпадение?
                  +1
                  Возможно есть какой-то обходной путь решения этой проблемы, который мне не известен. Но даже если просто поменять оптимизационные флаги компилияции, то GCC уже начинает ругаться. Если скомпилировать программу для генерации статистики (флаг -fprofile-generate) с одними оптимизационными флагами, например -O0. И передать полученный gcda файл для компиляции с флагом -O3 и PGO оптимизацией (флаг -fprofile-use), то GCC начинает валить предупреждения вроде того что не могу найти функцию в статистике и прочее.
                    0
                    проект не сильно активно изменяется

                    С вашей точки зрения проект не сильно меняется, потому что вы правите мало строк. Но ваши правки строк могут очень сильно влиять на код. Например, вы правите «один жалкий макрос», а этот макрос разворачивается в десятках тысяч мест в коде. Или вы правите одну строку в шаблоне, а шаблон — не конечный код, это только заготовка, которая используется десятки и сотни раз с разными параметрами и каждый раз получается новый класс или новая функция — правка на них повлияет. Так что одна правка может очень сильно повлиять на выходной файл. Учтите, что PGO управляет генерацией машинного кода — т.е. самой последней стадией. Если что-то там отъедет, вы будете это отлаживать до конца дней. На мой взгляд, это очень рискованная затея.
                      0
                      Это-то я понимаю. Правку общей библиотеки, которая используется десятком проектов, не назовешь мелкой правкой.
                        0
                        Точно так же в пределах одного проекта можно исправить «чуть-чуть» — и код заметно поменяется.
                          0
                          Ну, автор статьи уже выше ответил, что даже если изменится один проект из восьмидесяти, то на этот проект будет достаточная пачка warning'ов, чтобы отпугнуть делать такие эксперименты.

                          Хотя я еще попробую как-то оптимизировать этот процесс, когда буду прикручивать PGO к проекту :)
                    +1
                    Для выпуска релизных версий это вполне нормально. Их не каждый день собирают.
                    0
                    Я думаю имело смысл протестировать с менее регулярными данными для сортировки (во имя рандома!).
                    Ещё неплохо было бы указать использованное железо. Ну и из разряда высшего пилотажа — посмотреть результаты на процессоре с другим объёмом кэша.
                      0
                      Интересно вот что. Предположим, я собираю программу с PGO и в моем профилировочном пакете данные немного не такие (насколько не такие — не знаю), как будут у реальных пользователей. Станет ли моя программа работать у реальных пользователей медленнее, чем если бы она была собрана без PGO? Если да, то какого ухудшения мне ждать?
                        0
                        Не думаю, что такого эффекта можно добиться случайно.
                          0
                          Тут можно только гадать. Полезность любой оптимизации можно оценить через тесты. По моему мнению, PGO лишь предоставляет данные компилятору для более осознанного выбора оптимизаций. Без PGO при оптимизации компилятор будет исходить из других предпосылок. Возможно он оптимизирует программу, абсолютно так же, а может и нет. Результат может быть разный.

                          Ну в источниках которые я читал пред написание статьи сказано весьма гладко, мол при не типичном сценарии возможность уменьшения производительности есть, не каких реальных фактов не встречал. Так что только тестирование…
                            0
                            Туманно получается. Я же не могу предугадать все возможные реальные пакеты.
                              0
                              Ну почему туманно-то? Вполне соответствует ожиданиям:
                              1. Если есть понимание, что за прграмму мы пишем и на каких сценариях оно работает, даём типичный сценарий и PGO поможет;
                              2. Если это понимание есть, но хочется найти пример, когда PGO вредит, будучи обученным на неудачных данных — скорее всего и эту задачу можно решить;
                              3. Если такого понимания нет, то прежде всего стоит разобраться с собственной программой, чем с настройками PGO.

                        Only users with full accounts can post comments. Log in, please.