...
...

Тонкости оптимизации. Практика и результаты эксперимента

В предыдущих двух частях я в мучительных подробностях рассказывал о том, как происходит выполнение программы, какие приемы оптимизации реализованы на аппаратном уровне разработчиками процессоров и почему эти приемы оказываются эффективными. Настало время наконец-то рассказать подробнее об эксперименте «Тонкости оптимизации», проводимом независимой группой специалистов в сфере информационных технологий SASecurity gr.

Предыстория

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

На этот раз поиск касался чего-то, связанного с оптимизацией. Черт по имени Google долго меня водил по лесам и болотам, а затем бросил где-то посреди сайта govnokod.ru. На этом ресурсе выкладываются и обсуждаются (хотя уместнее будет слово «осуждаются») фрагменты кода, которые иначе как дурнопахнущим словом, вынесенным в доменное имя, назвать проблематично. Страница, на которую я забрел в поисках ответа на свои вопросы, была посвящена компилятору среды программирования Delphi 7-й версии и коду, который он генерирует для операции округления вещественных чисел. По утверждению пользователя TarasB, создавшего тему на этом сайте, Delphi-код для этой операции неэффективен и резко снижает производительность.





Те, кому доводилось работать с Delphi хотя бы на четверть ее возможностей, вряд ли станут спорить с тем, что это связка «среда + язык программирования», во многом опередившая свое время. Очень хорошо продуманный в плане синтаксиса Pascal-подобный язык, высокая скорость компиляции, тесная интеграция между средой и библиотекой VCL (о которой, кстати, тоже можно сказать немало хороших теплых слов), расширяемость – эти и еще многие другие черты, присущие Delphi, позволяют ей (и в частности 7-й версии, выпущенной почти 10 лет назад) и до сегодняшнего дня оставаться одним из самых популярных инструментов разработки прикладного ПО. И оптимизации генерируемого кода в ней также было уделено в свое время много внимания.

Из всего вышесказанного становится понятным, почему я решил оставить-таки на сайте со столь неблагозвучным названием свой комментарий. К тому же извлеченная из официальной документации Intel информация по оптимизации кода, вращаясь в голове, подсказывала: «если даже приведенный автором Delphi-код неоптимален, то уж точно он не может давать резкого падения производительности». К тому же, именно на такие сайты часто попадают начинающие программисты, а они, как известно, очень восприимчивы к информации извне, даже непроверенной и высказанной в стиле «это так, и иначе быть не может».

К сожалению, реакция на мой комментарий была, скажем прямо, довольно агрессивной. Последовавшие с моей стороны ссылки на официальные источники так и не были прокомментированы, а дискуссия оказалась затяжной и объемной. Спустя какое-то время она поутихла. А в августе 2010 года на электронную почту пришло уведомление о том, что к моему высказыванию на этой странице кто-то оставил комментарий. Пользователь SharpRazor, оставивший его, отметил, что в ходе обсуждения были затронуты многие вопросы, причем посвященные не только оптимизации, и предложил мне оформить озвученную информацию в виде отдельной статьи.

По итогам обсуждения этого предложения с членами SASecurity gr. нами было принято решение о проведении предварительного тестирования, которое позволило бы получить более или менее объемную базу экспериментальных данных, а затем опубликовать цикл статей, посвященных вопросам оптимизации, который закончится подведением итогов эксперимента. Эта идея была поддержана редакцией «Компьютерной газеты», и мы приступили к организации эксперимента.

Суть эксперимента

TarasB приводит фрагмент кода, который отвечает за округление вещественных чисел в программах, скомпилированных в Delphi. Этот код есть ни что иное, как обычная процедура, принимающая в качестве аргумента округляемое число и возвращающая результат. Для того чтобы увидеть ее код, необязательно даже пользоваться дизассемблером: достаточно просто открыть в Delphi стандартный модуль System и найти в нем процедуру _ROUND().

_Round:
sub esp, 8
fistp qword [esp]
fwait
pop eax
pop edx
ret

Код процедуры записан в синтаксисе FASM, поскольку данный синтаксис наиболее точно и лаконично отражает суть выполняемых программой действий. Как видим, данная процедура выделяет 8 байт в стеке, использует их для приема результата округления вещественного числа, а затем копирует результат в пару регистров EDX:EAX. Округляемое число передается в вершине FPU-стека, для округления используется инструкция FISTP.

Для тех читателей, которые не сильны в ассемблере или не работали с FPU-инструкциями, приведу словесное описание алгоритма:

1. Выделить 8 байт в стеке.
2. Извлечь число из вершины FPU-стека с округлением до ближайшего целого в выделенные 8 байт.
3. Скопировать результат из стека в пару EDX:EAX.

Возврат результата через EDX:EAX производится в соответствии с соглашением вызова STDCALL (то есть так и должна себя вести процедура).

Претензия TarasB к данному коду заключается в том, что для округления производится вызов процедуры, а это якобы крайне неэффективно. Предлагаемый им вариант заключается в использовании инструкции FRNDINT (которая, собственно, производит округление числа в вершине стека) с последующим извлечением результата инструкцией FISTP. Причем выполнять эту операцию автор предлагает прямо в коде, то есть не вынося в отдельную процедуру. То есть что-то вроде:

frndint
fistp [Операнд_в_памяти]

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

Почему в Delphi сделано не так

На самом деле, лучше всего на этот вопрос могут ответить разработчики компилятора. Но поскольку Borland (компания-создатель Delphi) уже несколько лет как перестала существовать, думаю, будет весьма проблематично задать им этот вопрос, да и сами они вряд ли припомнят ответ на него: все-таки округление – лишь одна из множества мелких задач, которые приходится решать разработчикам компилятора. Поэтому я попробую предложить свое видение причин.

Во-первых, надо помнить, что предшественником Delphi был Borland (Turbo) Pascal, среда разработки для MS-DOS. Поскольку во времена, когда разрабатывался Borland Pascal, далеко не все процессоры могли похвастаться поддержкой FPU-инструкций или даже наличием сопроцессора, компилятор позволял использовать эмуляцию сопроцессора, то есть подставлять код, который выполнял операции над вещественными числами, заменяя отсутствующий аппаратный узел. Понятно, что такой код – это далеко не 2 строчки, и его просто необходимо было вынести в отдельную процедуру. Маловероятно, но не исключено, что при создании Delphi эта процедура была просто переписана с учетом возможностей новых процессоров, но так и осталась отдельной процедурой.

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

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

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

Описание эксперимента

Пришло время рассказать о том, что из себя представляет эксперимент «Тонкости оптимизации».

Задача эксперимента заключается в том, чтобы сравнить скорость выполнения округления двумя способами: Delphi-кодом и кодом, предложенным TarasB. Для того чтобы это сделать, мы использовали простой, но наглядный способ: повторить выполнение сравниваемых алгоритмов многократно и сравнить время выполнения.

Была написана базовая программа, в которой реализованы 2 процедуры: Test1 и Test2. Обе процедуры содержат один и тот же цикл с одинаковым количеством повторений, но в Test1 в теле цикла вызывается процедура _Round(), извлеченная из Delphi, а в Test2 вместо вызова процедуры подставлен код, предложенный TarasB. Экспериментальным путем было подобрано минимальное количество повторений тела цикла, при котором различие во времени выполнения циклов становится достаточно большим, чтобы исключить влияние сторонних факторов. Это число: 100.000.000.

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

Кроме того… Наиболее часто применяемый способ измерения временных промежутков при работе в Windows – вызов функции GetTickCount(). Однако ни для кого из Windows-программистов не секрет, что точность этой функции составляет около 60 мс, то есть измерять более короткие промежутки времени с ее помощью бессмысленно. Альтернативный способ – использование инструкции RDTSC. По рекомендации одного из интернет-ресурсов мы рассмотрели также третий способ измерения времени: перед RDTSC помещалась инструкция CPUID, что позволяет повысить точность измерений.

В качестве дополнительного эксперимента мы решили также оценить 2 реализации не-Delphi’йского алгоритма: описанную выше и ее же, но дополненную инструкцией FWAIT. Подробно об этой инструкции можно почитать в соответствующих источниках, здесь же скажем просто о том, что ее
наличие/отсутствие может оказывать влияние на результат, показываемый данным алгоритмом.

Таким образом, мы получили 12 версий тестового приложения. Имя файла каждого из EXEшников строится следующим образом: (номер) X_T_W. Номер – это просто порядковый номер EXE-файла, особой смысловой нагрузки он не несет, но удобен для того, чтобы проверить, все ли версии приложения на месте, и если нет, то какой из них не хватает. X обозначает тип приложения и может иметь такие значения: S – с привязкой потока к одному ядру, M – без привязки. T – способ измерения времени, принимает такие значения: GTC – используется функция WinAPI GetTickCount(), RDTSC – используется инструкция RDTSC, RDTSCCPUID – используется пара инструкций RDTSC+CPUID. W – наличие или отсутствие в реализации не-Delphi’йского алгоритма инструкции FWAIT: W – инструкция FWAIT присутствует, NW – отсутствует.

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

Тестовые приложения – это Win32 native-приложения, то есть Windows-программы, не использующие .NET и другие фреймворки. Цикл обработки сообщений организован посредством функции GetMessage(). Таким образом, разработанные нами приложения по своему типу и внутреннему устройству максимально приближены к Delphi-приложениям.

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

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

Информация, запрашиваемая по каждому из комплектов результатов, включает в себя следующие сведения:

1. Процессор: производитель, модель, тактовая частота, количество ядер, поддержка технологии HyperThreading.

2. RAM (ОЗУ, оперативная память): объем.

3. Тип компьютера: стационарный/нетбук/ноутбук, если портативный – то наличие/отсутствие питания от сети, режим энергопотребления.

4. Операционная система: версия, сервис-паки.

5. Установленное ПО: антивирус (включая режим работы при выполнении измерений), пакеты 3D-моделирования, видеомонтажа и другое «тяжелое» ПО. Запрашивалась также информация о версиях данного ПО, а также о режиме работы во время проведения эксперимента.

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

Собранная информация в кратчайшие сроки публикуется на странице эксперимента http://dimonsoft.ueuo.com/opttest/, проводится ее анализ.

Предсказываем результаты

Прежде чем рассматривать результаты, полученные нами в ходе эксперимента, хочу заметить, что результат округления, получаемый обоими алгоритмами, помещается в операнд в памяти. А это означает, что Delphi-алгоритм ставится в заведомо невыгодные условия. Действительно, рассмотрим последовательность действий для округления Delphi-методом:

1. Вызов процедуры.
2. Округление и помещение результата в стек.
3. Копирование результата из стека в регистры.
4. Возврат из подпрограммы.
5. Копирование результата из регистра в операнд в памяти.
В то же самое время для не-Delphi’йской версии алгоритма последовательность такова:

1. Округление.
2. Помещение результата в операнд в памяти.

Думаю, различие очевидно. В реальных программах результат округления редко помещается в операнд в памяти. Чаще всего он оставляется компилятором в регистрах, поскольку участвует в дальнейших вычислениях, то есть чтобы приспособить алгоритм Delphi к реальности, нужно убрать п. 5 из вышеприведенного списка, а для применения не-Delphi’йского алгоритма – добавить копирование значения из памяти в регистр. Как видим, условия тестирования действительно работают НЕ в пользу Delphi.

Самые любопытные читатели уже наверняка видели опубликованные результаты. Если вы не относитесь к их числу – можете не торопиться. Потому что, как видите, разбор результатов мы откладываем до следующей статьи.

Промежуточные итоги

Итак, в этот раз мы рассмотрели то, каким образом проводился эксперимент «Тонкости оптимизации» и в каких условиях находились сравниваемые алгоритмы. Я рассказал о том, КАКИЕ собственно алгоритмы сравнивались и почему SASecurity gr. занялась этим.

В следующей серии смотрите… В следующий раз читайте о том, какие результаты нами были получены. Поверьте, даже для меня они оказались несколько неожиданными. Ну а пока принимаю письма по адресу info@sa-sec.org с пометкой «Тонкости оптимизации».

Дмитрий Оношко



© Компьютерная газета

полезные ссылки
Обзор банков Кипра
Обзор банков Кипра