Издательский дом ООО "Гейм Лэнд"ЖУРНАЛ ХАКЕР #100, АПРЕЛЬ 2007 г.

Подводные камни оптимизации

Крис Касперски

Хакер, номер #100, стр. 106

Раскрываем секреты компиляции программ

Как правило, программы под *nix распространяются в исходных текстах и предусматривают возможность компиляции под различные ЦП с задействованием инструкций MMX, MMXext, SSE, SSE2, SSE3, SSE4, 3DNow!, 3DNow!Ext и т.д. Зачастую от применяемого компилятора и его ключей принципиальным образом зависят быстродействие и стабильность программы. Во всех этих тонкостях не так-то просто разобраться, как кажется на первый взгляд. В некоторых случаях попытка форсировать компиляцию под SSE4, круче которого пока ничего нет, заканчивается чуть ли не катастрофой — от полного нежелания запускаться до падения производительности в десятки раз. Давай посмотрим, почему же так происходит.

Архитектура кремниевых сооружений

Учет архитектурных особенностей конкретных ЦП теоретически способен дать огромный выигрыш, но практически языки высокого уровня абстрагируют программиста от деталей конкретной реализации, перекладывая все заботы на плечи компилятора. Но что может сделать компилятор? Переупорядочить инструкции, выровнять структуры данных по кратным адресам, избавиться от ветвлений, заменить медленные команды (например, инструкцию целочисленного деления DIV, также отвечающую за взятие остатка) их более быстрыми аналогами и т.д. Во времена господства Intel 80486, Intel Pentium-I/II и AMD K5/K6, когда архитектура и правила оптимизации под каждую модель процессора существенно отличались, оптимизирующие компиляторы временами увеличивали производительность в несколько раз.

Но, начиная с Pentium Pro, процессоры научились оптимизировать код самостоятельно, разбивая поток машинных команд на микроинструкции, распределяемые по функциональным устройствами (типа АЛУ или блока вещественной арифметики), и выполняя их с максимальной эффективностью. Сейчас, в начале XXI века, производительность в основном определяется крутостью оптимизатора и, естественно, опциями компилятора, отвечающими за глубину разворота циклов, агрессивность встраивания функций, удаление «хвостовой» рекурсии и т.д.

Многообразие ключей оптимизации затрудняет работу с компилятором, и потому разработчикам последних пришлось заложить в них специальные шаблоны - программист просто указывает тип целевого процессора и компилятор автоматически выставляет оптимальные (с его точки зрения!) параметры оптимизации по умолчанию. В частности, выбор -march=pentium4 (кавычки надо? это ключ вроде, это ключи, просто длинные, хз) обычно ведет к крайне агрессивному развороту циклов и встраиванию функций, что приводит к неоправданному разбуханию кода и, как следствие, падению производительности (особенно если интенсивно выполняемые циклы вылетают за пределы кэш-памяти первого уровня).

Экспериментируя с различными ключами оптимизации на своем Prescott'е, работающем под ядром Linux версии 2.4.27, мыщъх пришел к выводу, что большинство программ, компилируемых GCC 3.4.3, показывает значительно лучший результат при выборе обобщенной унипроцессорной архитектуры i686 (-march=i686 -mtune=prescott), чем при -march=prescott, уступающем в производительности… даже -march=i386. Ключи -march=pentium3 и -march=pentium4 не обнаружили (на Prescott'е!) никакой заметной невооруженным взглядом разницы (правда, с использованием -march=pentium4 компиляция иногда проваливается).

Сначала мыщъх списывал этот эффект на глюк этой версии GCC и кривизну своих лап, умноженную на градиент упругости хвоста. Но поиск по форумам показал, что глюк носит характер призрака, блуждающего по всем континентам и оставляющего следы не только на форумах, но и в солидных исследовательских статьях наподобие «Intel Hyper-Threading on Linux: Fact or Myth», переведенный мной отрывок из которой следует ниже:

«Одна-единственная опция компилятора способна погубить весь выигрыш в производительности, которого вы ожидаете от технологии Hyper-Threading, и в некоторых случаях проигрыш становится поистине драматическим. Например, ядро Linux версии 2.4 с опцией -march=i686 выполняется на 33% быстрее, нежели с -march=pentium4. В худшем случае (при выборе неправильных ключей компиляции) прирост производительности будет 16%, что составляет лишь половину ожидаемого ускорения.

Ядро версии 2.6 ведет себя прямо противоположным образом. Использование опции -march=i686 вызывает снижение производительности. Таким образом, мы можем вывести следующее эмпирическое правило (по крайней мере, для дистрибутива Fedora): надо использовать опцию -march=i686 на ядрах семейства 2.4 и опцию -march=pentium4 на ядрах семейства 2.6.

Сперва я думал, что это связано с компилятором, и протестировал три версии GCC на каждом из ядер, но… не выявил никакой корреляции между версией компилятора и опцией -march, зато обнаружилась корреляция между ядрами. Переход на ядра семейства 2.6 в среднем давал 10%-ный прирост производительности, по сравнению с ядрами семейства 2.4, при условии что Hyper-Threading был активирован».

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

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

Соображение номер два: программа, откомпилированная под новейшую модель процессора, становится немобильной и нетранспортабельной. Перенос на соседнюю (морально устаревшую) машину потребует повторной перекомпиляции, а это время… К чему создавать себе лишние проблемы, соблазнившись незначительным выигрышем в производительности?

Векторные команды

Помимо наращивания тактовой частоты, расширения посевной площади кэш-памяти всех уровней и других архитектурных изысков, разработчики процессоров предлагают нам наборы векторных команд, ориентированные на работу с графикой, цифровым звуком и видео. Естественно, сами по себе производительности они никак не добавляют и воздействуют только на те приложения, которые их явным образом используют. Причем компиляторы до векторных команд еще не доросли. В лучшем случае они вообще не подозревают об их существовании, в худшем же — пытаются векторизовать циклы (особенно этим славится Intel C++), но делают это наугад и абы как. Поэтому мы будем рассматривать лишь примеры ручной оптимизации приложений под заданный набор векторных команд.

Исторически первым таким набором оказался MMX, реализованный корпорацией Intel в «первопне» и получивший дальнейшее развитие в своем расширении MMXext (где «ext» - сокращение от «extension»).

Компания AMD, находясь в тяжелых условиях конкурентной борьбы, нанесла ответный удар в виде своего собственного векторного набора команд, зарегистрированного под торговой маркой 3DNow!, что, по замыслу маркетологов, символизировало трехмерную графику и должно было привлечь игроманов всех мастей. На самом же деле, одной лишь трехмерной графикой 3DNow! ничуть не ограничивался и распространял свое влияние также и на обработку цифрового видео со звуком, то есть, фактически, представлял собой тот же MMX, только реализованный в другой манере.

С этого момента между Intel и AMD произошел раскол, положивший конец совместимости, к которой так стремилась AMD, а вместе с ней и все программисты. Впрочем, несмотря на все протесты со стороны Intel, AMD скопировала набор MMX, сделав его на долгие годы стандартом де-факто.

В процессе разработки Pentium III корпорация Intel добавила в его лексикон 70 новых векторных инструкций и 8 128-битных регистров, упакованных в аббревиатуру торговой марки SSE. Позднее AMD перенесла SSE в поздние модели процессоров Athlon XP, поскольку без сохранения совместимости с лидером рынка она была бы обречена на поражение.

С выходом Pentium IV появился и новый набор векторных инструкций, получивший название SSE2 (а SSE во избежание путаницы был переименован в SSE1). Помимо команд, оперирующих плавающими числами двойной точности (64 бита), и 8-, 16-, 32-битных целочисленных инструкций, Intel наконец-то устранила досадное ограничение, связанное с побочным влиянием SSE-команд на MMX-регистры. Программисты вздохнули с облегчением, и многие из них окрестили SSE2 «должным образом реализованным SSE1».

Очередная реконструкция состоялась в Prescott'ах, добавивших инструкции, ориентированные на сигнальную обработку, прежде доступную только в специальных DSP-процессорах (Digital Signal Processor — процессор, обрабатывающий цифровые сигналы), плюс команды управления виртуальными процессорами (а точнее, их ядрами). Обновленный набор, не мудрствуя лукаво, обозвали SSE3.

Процессорная архитектура, разрекламированная под торговой маркой Core, принесла с собой 16 новых векторных инструкций, зарегистрированных под грифом SSSE3, часто воспринимаемым редакторами популярных журналов как случайная опечатка.

Писком моды стал набор SSE4, представляющий собой кардинально доработанный SSSE3, с кучей целочисленных инструкций (так полезных аудио- и видеокодекам) и прочими соблазнительными новшествами. Первым процессором, поддерживающим SSE4 в железе, а не на бумаге, оказался Penryn, построенный по архитектуре Core 2. Более подробную информацию обо всех вышеперечисленных типах инструкций можно получить у самой Intel: www.intel.com/technology/architecture/new_instructions.htm.

Хвосту понятно, что SSE4 круче, чем SSE3, а SSE3 круче, чем MMX. Подчеркиваю еще раз: это обстоятельство понятно только хвосту, то есть оболваненному рекламой пользователю, уже научившемуся компилировать чужие программы, но никогда не программировавшему самостоятельно. Весь вопрос в том, какие именно векторные команды выбирает программист для решения поставленной перед ним задачи. Если набора SSE2 оказывается вполне достаточно, то заручаться поддержкой SSE3/SSE4 совершенно необязательно, тем более что это ограничивает круг потенциальных пользователей программы.

Сами по себе векторные команды — это просто лексический балласт, а, как известно, искусство владения языком (все равно каким — машинным или человеческим) определяется, в первую очередь, не количеством известных слов, а умением выразить свою мысль теми немногочисленными словами, которые крутятся в голове. В практическом плане это означает, что большинство разработчиков крайне скептически относятся к новым наборам инструкций и неохотно включают их в свои программы. Но мы живем не в девяностых годах, и MMX активно вытесняется SSE1/SSE2.

Критичные к быстродействию программы либо определяют тип процессора автоматом, либо предоставляют пользователю возможность выбрать используемый набор (наборы) векторных инструкций самостоятельно (такой режим получил название «форсированного»). Тут-то большинство пользователей и совершают роковую ошибку, выбирая один единственный набор — самый «крутой» из всех имеющихся. Вот только производительность от этого никак не увеличивается и даже, наоборот, уменьшается. Почему? Потому что то, что в программе заявлена поддержка «оптимизации под SSE4», ровным счетом ничего не значит! Откуда мы знаем, какая именно часть кода реально написана под SSE4?! Это может быть всего пара особо критичных функций. Очень часто именно так и происходит. Программа на 90% написана на Си, 9% приходится на ассемблерные MMX-модули и 1% — на SSEx. Несмотря на то что SSEx включает в себя подмножество MMX, утилита configure этого не знает и, при выборе одного лишь SSEx, отключает оптимизированные MMX-модули, заменяя их неоптимизированными Си-аналогами.

От теории к практике

Возьмем какую-нибудь мультимедийную программу, например кодек XviD (последнюю версию исходных текстов которого можно скачать с www.xvid.org/Downloads.43.0.html), и посмотрим, как теория сочетается с практикой.

Распаковав архив, ищем контекстным поиском что-нибудь вроде «SSE2» или «3DNow» и находим в файле config.c следующий фрагмент кода, позволяющий пользователю форсировать выбор конкретного набора векторных инструкций, включающих в себя MMX, MMXext, SSE, SSE2, 3DNow! и 3DNow!Ext:

$ vi xvidcore-1.1.2/vfw/src/config.c

case IDD_COMMON :

cpu_force = IsDlgChecked(hDlg, IDC_CPU_FORCE);

EnableDlgWindow(hDlg, IDC_CPU_MMX, cpu_force);

EnableDlgWindow(hDlg, IDC_CPU_MMXEXT, cpu_force);

EnableDlgWindow(hDlg, IDC_CPU_SSE, cpu_force);

EnableDlgWindow(hDlg, IDC_CPU_SSE2, cpu_force);

EnableDlgWindow(hDlg, IDC_CPU_3DNOW, cpu_force);

EnableDlgWindow(hDlg, IDC_CPU_3DNOWEXT, cpu_force);

break;

А теперь откроем каталог ./src и посмотрим, что у нас там: 26 файлов, оптимизированных под MMX; 6 — под MMXext; 5 — под SSE2; 2 — под 3DNow!; 6 — под 3DNow!Ext. Еще наблюдается некоторое количество модулей, написанных для архитектур Intel Itanium, AMD x86-64 и Power PC, но о них сейчас разговор не идет (поскольку они не являются ни подмножеством, ни надмножеством рассматриваемых нами наборов векторных инструкций).

Количество функций, написанных на том или ином наборе инструкций, подсчитать несложно, но утомительно, да и без этого видно, что SSE отдыхает, и если вырубить MMX, то XviD будет работать ну очень медленно… С другой стороны, наличие функций, оптимизированных под SSE, еще не доказывает их превосходства над MMX. Ведь это разные функции, зачастую написанные разными программистами с непредсказуемой квалификацией (или отсутствуем таковой). Допустим, в некотором проекте содержится большое количество годами вылизываемого MMX-кода, написанного талантливыми людьми, прекрасно владеющими техникой профилировки. А теперь представим, что в ряды разработчиков вливается красноглазый пионер, прочитавший руководство по SSE-командам по диагонали и написавший чудовищно тормозной код, включенный в финальный проект по недосмотру координатора.

Короче говоря, возникает тупиковая ситуация. Доверять программе автоматический выбор векторных команд мы не можем, так как никто не знает, насколько хорошо они реализованы, а применение форсированной оптимизации ограничено неполнотой наших представлений о структуре программы. До тех пор пока мы не распотрошим исходные тексты и не прикинем, какая часть кода на каких наборах реализована, форсированный режим будет давать непредсказуемый результат.

Что же остается? А остается Его Величество Эксперимент! Поскольку наборов векторных инструкций существует не так уж и много, выбор оптимального сочетания не займет большого количества времени. В одних случаях более быстрым окажется SSEx, в других — MMX. Про 3DNow! мы помним, но в силу малой рыночной доли процессоров AMD скромно промолчим.

Заключение

*nix-системы предоставляют пользователю практически неограниченную свободу для творчества, оставляя его наедине с массой рычагов управления, многие из которых вообще никак не подписаны, а подписанные содержат магические аббревиатуры, расшифровываемые в совершенно других местах. Документация (даже если она и присутствует) покрывает лишь малую часть вопросов. Это и есть расплата за свободу. Если Windows/Mac OS X – это «кадиллак», то *nix скорее похож на трактор, водитель которого способен разобрать мотор с закрытыми глазами и собрать его обратно. Многих это коробит. Трудно представить, чтобы какая-нибудь семнадцатилетняя Анастасия читала Intel Manual и курила спецификации на MPEG-2 перед запуском фильма на DVD, но… другие просто не представляют себе, как можно ездить на машине, не внеся в нее пару десятков конструктивных изменений. Это два мира, и умение компилировать программы не гарантирует умение компилировать их хорошо.

Оптимизация за счет флагов компилятора

-O — базовая оптимизация. Значительно увеличивает скорость исполнения программы.

-O2 — стандартный уровень оптимизации. По сравнению с '–O' несущественно увеличивает как размер бинарика, так и скорость исполнения программы.

-O3 — более агрессивный режим. Это оптимизация уровня '-O2' и некоторые (зло)ухищрения в виде флагов '-finline-functions' и '-frename-registers'.

-Os — оптимизация уровня '-O2' в совокупности с флагами, уменьшающими размер.

-fomit-frame-pointer — указываем компилятору не сохранять указатель на кадр стека (так мы избегаем временных затрат на его сохранение и восстановление). Использование этого флага может благотворно повлиять на скорость исполнения программы.

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

INFO

MMX – Matrix Math eXtension (матричное математическое расширение).

SIMD — Single Instruction, Multiple Data (одна инструкция, много данных). Это торговая марка, объединяющая под своим крылом различные наборы векторных инструкций, обрабатывающих более одной порции данных одновременно, например складывающих два массива чисел.

SSE — в девичестве ISSE: Internet Streaming SIMD Extensions (расширение потоковых SIMD-инструкций интернета). Позднее было переименовано в Streaming SIMD Extensions (потоковое SIMD-расширение), кодовое название KNI – Katmai New Instructions (новые инструкции процессора Katmai, официально выпущенного под торговой маркой Pentium III).

SLOGAN

«Мы будем рассматривать примеры ручной оптимизации приложений под заданный набор векторных команд»

«Эмпирические правила срабатывают далеко не всегда, и определить оптимальную комбинацию ключей можно только экспериментально»

«До тех пор пока мы не распотрошим исходные тексты и не прикинем, какая часть кода на каких наборах векторных инструкций реализована, форсированный режим будет давать непредсказуемый результат»

WWW

www.linuxelectrons.com/News/HowTO/20040226231747944;

www.xvid.org;

en.wikipedia.org/wiki/MMX;

en.wikipedia.org/wiki/Streaming_SIMD_Extensions;

guru.multimedia.cx/category/optimization;

gcc.gnu.org/onlinedocs/gcc/i386-and-x86_002d64-Options.html.

Содержание
ttfb: 50.060987472534 ms