Компиляция на форсаже с турбонаддувом

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

Наверное, всем известно, что компилятор GCC поддерживает несколько уровней оптимизации (O1 – минимальная, O2 – умеренная, O3 – агрессивная), но не каждый догадывается, что даже на уровне O3 задействуются далеко не все режимы оптимизации и до максимальной производительности еще пилить и пилить.

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

Разумеется, в рамках короткой журнальной статьи мыщъх не в силах рассказать обо всех ключах компилятора и потому вынужден остановиться лишь на самых проблемных техниках оптимизации, не описанных ни в документации на GCC, ни в популярных FAQ. Заинтересованных в углублении своих знаний мыщъх отсылает к книге «Техника оптимизации: эффективное использование памяти» и к серии статей «Техника оптимизации под Linux», электронные версии которых можно скачать с http://nezumi.org.ru/optimization.zip и http://nezumi.org.ru/optimization-pack.zip соответственно. Ну а мы сейчас отправимся в
орбитальный полет. Главным образом мы будем говорить о самой последней версии GCC — 4.2.1 (описание которой можно найти на http://gcc.gnu.org/onlinedocs/gcc-4.2.1/gcc), что же касается остальных версий, то... сверяйся с документацией!

Разворот циклов

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

Циклы (особенно компактные) содержат небольшой участок линейного кода, за которым следует крутой поворот, тормозящий процессор и не дающий ему как следует разогнаться. Последние модели Penium 4, благодаря значительным архитектурным улучшениям, намного лучше справляются с циклами, чем процессоры предыдущих поколений, но потери в скорости все равно очень значительны, и для повышения производительности необходимо расчистить трассу от ветвлений, что может сделать либо программист, либо компилятор.

Циклы, состоящие из нескольких команд («for(a = 0; a < n; a++) *dst++ = *src++;»), исполняются очень медленно, и для повышения быстродействия оптимизаторы задействуют технику, именуемую разворотом циклов (loops unrolling), в процессе которой происходит многократное дублирование тела цикла, реализуемое приблизительно так:

Цикл до разворота

for (i = 1; i < n; i++)
k += (n % i);

Цикл после разворота

// Разворот цикла на 4 итерации;
// выполняем первые n – (n % 4) итераций
for(i = 1; i < n; i += 4)

{
k += (n % i) + \
(n % i + 1) + \
(n % i + 2) + \
(n % i + 3);

}
// Выполняем оставшиеся итерации
for(i = 4; i < n; i++) k += (n % i);

Размер программы при этом, естественно, возрастает, а вместе с ним возрастает и риск вылететь за пределы кэша первого (и даже второго!) уровня, после чего производительность упадет так, что не поднимешь и домкратом.

Компилятор GCC разворачивает циклы только при использовании ключа '-funroll-loops' (действует применительно к циклам типа for) или '-funroll-all-loops' (как и следует из названия, развертывание выполняется для всех видов циклов, например do/while).

Если постоянное количество итераций, известное на стадии компиляции, не превышает 32, то циклы разворачиваются полностью. При значении, большем 32, кратность разворота сокращается до приблизительно четырех (точное значение зависит от размера цикла, смотри ключи 'max-average-unrolled-insns' и 'max-unroll-times'). Циклы с неизвестным количеством итераций не разворачиваются вообще! Хотя другие компиляторы (такие, например, как Intel C++) их преспокойно разворачивают.

Для тонкой настройки оптимизатора существуют следующие ключи (задаются с помощью конструкции «--param key=value»):

• 'max-unrolled-insns': максимальное количество инструкций, при котором цикл может быть развернут; оптимальное значение зависит как от типа процессора, так и от конструктивных особенностей компилируемой программы, поэтому определять это значение приходится экспериментальным путем; мыщъх рекомендует начинать «плясать» от max-unrolled-insns=69;
• 'max-average-unrolled-insns': максимальное оценочное количество инструкций, которое цикл будет иметь после разворота; это число также подбирается экспериментальным путем, возьми за старт значение 96;
• 'max-unroll-times': максимальная степень разворота, по умолчанию равная четырем; это довольно разумное значение, но в некоторых случаях выбор двух или восьми существенно увеличивает быстродействие программы.

Остальные ключи, связанные с разворотом циклов, описаны в документации на GCC. Они не имеют решающего значения, и потому к ним прибегают только умудренные опытом гуру, да и то лишь время от времени.

Выравнивание

Вплоть до появления Pentium Pro процессоры крайне болезненно относились к невыровненным переходам и вызовам функций, чей адрес не был кратен 4 байтам, и давали за это штрафные такты (называемые «пенальти»), что объяснялось несовершенством микропроцессорной архитектуры тех лет.

Начиная с Pentium II+ и AMD K6+ процессоры уже не требуют постоянного выравнивания переходов/вызова функций, за исключением случая, когда целевая инструкция или команда перехода, пересекая границу линейки кэш-памяти первого уровня, расщепляется напополам, за что выдается пенальти. Причем Pentium 4, компилирующий x86-инструкции в микрокод, выдает его значительно реже и совершенно непредсказуемым образом - микроинструкции абсолютно недокументированы, их длина неизвестна, следовательно, управлять их выравниванием мы не можем.

Несмотря на то что Pentium 4 де-факто является самым популярным процессором и непоколебимым лидером рынка, большинство компиляторов упорно продолжают заниматься выравниванием, располагая инструкции перехода по кратным адресам и заполняя образующиеся дыры незначащими инструкциями, такими как NOP, MOV EAX,EAX и другими. Естественно, это увеличивает размер кода, снижая его производительность.

Применительно к Pentium II/Pentium III и AMD K6+ машинная команда требует выравнивания только в тех случаях, когда следующее условие становится истинным: ((addr % cache_len + sizeof(ops)) > cache_len). Здесь addr – линейный адрес инструкции, cache_len - размер кэш-линейки (в зависимости от типа процессора равный 32, 64 или 128 байтам), ops – целевая машинная инструкция или инструкция перехода/вызова функции. Количество выравнивающих байт рассчитывается по формуле: (cache_len - (addr % cache_len)).
Компилятор Intel C++ вообще не выравнивает ни переходы, ни циклы, что является лучшей стратегией для Pentium 4, а вот на более ранних процессорах мы получаем неустойчивый код с плавающей производительностью, быстродействие которого зависит от того, расщепляются ли глубоко вложенные переходы или нет. А это, в свою очередь, зависит от множества трудно прогнозируемых обстоятельств, включая фазу луны и количество осадков.

Компилятор GCC задействует выравнивание уже на уровне оптимизации O2, автоматически отключая его при задании ключа '-Os' (оптимизация размера программы), причем осуществляет его по ужасно бездарной схеме. Вышеприведенная формула остается незадействованной. Функции, циклы, метки (labels) и условные переходы выравниваются по фиксированной границе, управляемой следующими ключами: '-falign-functions', '-falign-loops', '-falign-labels' и '-falign-jumps' соответственно.

Каждый ключ принимает целочисленный аргумент, равный степени двойки и задающий кратность выравнивания. Например, '-falign-functions=32' форсирует выравнивание функций по границе 32 байт. Значение 1 отключает выравнивание, а 0 задает выравнивание по умолчанию, специфичное для этого типа процессора.

Для Pentium 4 все виды выравнивания лучше всего отключить, естественно, убедившись, что это не вызовет падения производительности. Для остальных процессоров имеет смысл задействовать выравнивание циклов по величине, кратную 4 байтам, однако в некоторых случаях отключение выравнивания позволяет увеличить производительность на 30%.

Компиляция с обратной связью

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

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

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

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

Ключ '-fprofile-use' задействует обратную связь (profile feedback) и оказывает воздействие на следующие ключи оптимизации, которые обязательно должны быть указаны в командной строке (или заданы уровнем оптимизации от O1 до O3), иначе вместо ожидаемого выхлопа мы получим «пшик»:

• 'funroll-loops': разворот циклов будет выполняться на оптимальное количество итераций или не будет выполняться вообще, если для конкретно взятого цикла это невыгодно;
• 'fpeel-loops': «шелушение циклов» (разновидность разворота) будет выполняться в соответствии с показаниями профилировщика;
• 'fvpt': заставляет профилировщик запоминать значения переменных, собираемые по ходу выполнения программы, которые в дальнейшем могут быть использованы для более эффективной оптимизации;
• 'fbranch-probabilities': в комбинации с ключом '-fvpt' форсирует подсчет частоты каждого условного перехода, записывая полученные данные в файл sourcename.gcda, после чего оптимизатор сможет реорганизовать код таким образом, чтобы сократить накладные расходы на ветвления и уменьшить трассу выполнения (примечание: в текущих версиях GCC оптимизатор ограничивается лишь более эффективным распределением переменных по регистрам, но даже это дает существенный прирост производительности);
• 'ftracer': форсирует хвостовую дубликацию (tail duplication) — довольно прогрессивный и, кстати говоря, запатентованный метод оптимизации, подробнее о котором можно прочитать на www.freepatentsonline.com/20050183079.html.

Ключ '-fprofile-generate' задействует дополнительные возможности, заставляя профилировщик собирать еще больше данных, что позволяет использовать следующие ключи оптимизации:

• 'fprofile-arcs': собирает информацию о ходе выполнения программы, записывая ее в AUXNAME.da, и воздействует на следующие ключи оптимизатора, позволяющие генерировать более эффективный код: '-fno-guess-branch-probability', '-fbranch-probabilities' и '-freorder-functions' — все эти ключи автоматически задействуются на уровнях оптимизации от O2 и выше, а потому нет никакой необходимости дописывать их вручную;
• 'fprofile-values': в комбинации с ключом '-fprofile-arcs' форсирует сбор значений переменных и выражений, позволяя отыскивать инварианты (то есть значения, независимые от обрабатываемых программой данных) и оптимизировать процедуру вычисления многих вещественных выражений.

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

Быстрая вещественная математика

Вещественная математика (особенно двойной точности) до сих пор остается одним из узких мест, с которым не могут справиться даже современные сопроцессоры с их улучшенной архитектурой. Компилятор GCC поддерживает ряд ускоренных методик вещественных вычислений, однако не задействует их даже на уровне оптимизации O3, поскольку они отклоняются от стандартов ISO и IEEE, а потому потенциально небезопасны и в некоторых случаях приводят к развалу программы.

С другой стороны, программы, интенсивно перемалывающие вещественные числа, могут существенно повысить свою производительность. А потому стоит попробовать задать параметр '-ffast-math', активирующий '-ffloat-store', '-fno-math-errno', '-funsafe-math-ptimizations', '-fno-trapping-math', '-ffinite-math-only', '-fno-rounding-math', '-fno-signaling-nans' и '-fcx-limited-range', после чего выполнить полный цикл тестирования программы, и если что-то пойдет не так, то забыть о '-ffast-math' и начать перебирать различные комбинации вышеупомянутых ключей по отдельности. В некоторых случаях это дает двух-, трехкратный прирост производительности.

Заключение

Вот мы и рассмотрели наиболее значимые ключи оптимизации, получив широкий оперативный простор для экспериментов. Конечно, кто-то может резонно возразить: а стоит ли корпеть над какой-то программой несколько дней, чтобы увеличить ее производительность на 30%-60%?! Если измерять время деньгами, то дешевле купить более быстрый процессор, но Linux всегда привлекал большое количество энтузиастов, проводящих дни и ночи напролет в бессмысленных (для окружающих) ковыряниях системы. Так что, дерзай! Тебя ждут великие дела!