Тонкости оптимизации. Подведение итогов

Окончание. Начало в КГ №№ 36, 37, 38

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

Предупреждение

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

Результаты онлайн

В прошлый раз я приводил ссылку на страницу с описанием и результатами эксперимента. Самые любопытные и догадливые читатели, наверное, уже успели ознакомиться с ними и сделать какие-либо выводы. Тех же, кто этого еще не сделал, приглашаю по адресу http://dimonsoft.ueuo.com/opttest/

Как читать результаты?

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

Каждый участник тестирования присылал комплекты результатов в архивах с именами вида «ник_номер», где ник – выбранный участником псевдоним, а номер – номер комплекта результатов.

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

Первая строка – «M_GTC_NW». В прошлый раз я рассказывал о том, как формируется имя тестовой программы на основании ее внутреннего содержания. M_GTC_NW в этой нотации соответствует приложению, которое не привязывается к конкретному ядру процессора, использует для измерений WinAPI- функцию GetTickCount() и не выполняет инструкцию FWAIT в не-Delphi’йском алгоритме.

Вторая строка: «Delphi» и «NoProc». Это краткие названия двух сравниваемых алгоритмов. Если вспомнить, что изначально речь шла об
эффективности/неэффективности использования вызова процедуры, применяемого Delphi, то с названиями все становится понятно: Delphi – это округление процедурой _Round(), NoProc – это вариант без использования процедур.

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

EndTime – StartTime = UsedTime

то есть значение, полученное при вызове GetTickCount() по окончании измерения, до его начала и разность этих значений – время, затраченное алгоритмом на выполнение цикла из 100.000.000 округлений. Числа представлены в 16-ной системе счисления: для большей компактности. Для остальных приложений формат аналогичен с той лишь разницей, что вместо 32-битного GetTickCount() там используется 64-битное значение, получаемое при выполнении RDTSC.

Таким образом, чтобы ответить на вопрос «Кто победил в этом измерении?», достаточно сравнить 2 числа, стоящих после знаков равенства в одной и той же строке. Большее число соответствует большему количеству затраченного времени, то есть более медленному алгоритму.

В некоторых комплектах результатов встречаются строки «Нет результатов». Дело в том, что инструкция CPUID на некоторых системах может оказаться привилегированной, то есть запрещенной для выполнения обычным приложением, коим является тестовая программа. Соответственно, те тестовые программы, которые эту инструкцию используют (в их именах содержится RDTSCCPUID), не могут получить никаких результатов. Остальные 8 приложений никаких преград на своем пути не встречают.

Выявленные закономерности

1. В ходе дискуссии, давшей жизнь эксперименту «Тонкости оптимизации», звучало утверждение о том, что, якобы, на процессорах Intel Celeron между результатами Delphi и NoProc «разница очень велика». Не скажу, что нам удалось найти много Celeron’ов, но на тех из них, которые поучаствовали, результат прямо противоположен: Delphi уверенно лидирует.

Отрыв Delphi на Celeron’ах варьируется от сравнительно небольшого (почти в пределах погрешности) до 1,8 раза, так что говорить о случайных совпадениях уж точно не приходится.

2. Перейдем от Celeron’ов к другим процессорам Intel. В основном здесь, конечно же, были 2-ядерные Core2Duo, Core i3 и т.п. Поскольку эти модели были выпущены позже, логично предположить, что приемы оптимизации, примененные в них на аппаратном уровне, окажутся еще более эффективными.
Предположение подтверждается практикой. Если у Celeron’ов преимущество в 1,8 раза было максимальным, то у их двухъядерных братьев наблюдается уверенная победа с разницей в 1,6 раза в среднем.

3. К главному конкуренту Intel – небезызвестной AMD. Исторически сложилось так, что этой компании пришлось многое попросту заимствовать у Intel, во многом догонять. Впрочем, об этом предлагаю почитать в Agner’s CPU Blog: http://www.agner.org/optimize/blog/read.php?i=25.

Результаты Delphi на процессорах AMD (в основном – двухъядерных) оказались неутешительными для Borland: до 2,4 раза в пользу NoProc-алгоритма. В среднем, разумеется, проигрыш процедурного варианта несколько меньше.

4. Вынужден сказать несколько слов и о том, какие результаты были получены нами на различных операционных системах. В тестировании участвовали компьютеры с тремя версиями Windows: ’98, XP и 7. Нетрудно заметить, что WinXP и Win7 показали схожие результаты.

Я лично провел эксперимент на нескольких компьютерах с Windows 98, с процессорами Intel. Результаты при измерении GetTickCount() и RDTSC оказались такими же, как и у других версий ОС. Зато связка CPUID-RDTSC повела себя несколько неожиданно: производительность Delphi-версии упала почти в 15 раз.

Как объяснить полученные результаты?

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

1. Победа Delphi на Celeron’ах кажется мне вполне закономерной. Действительно, пролистайте еще раз первые 2 статьи о «Тонкостях оптимизации»: в Delphi-алгоритме есть на чем сэкономить.

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

Во-вторых, затраты на вызовы Delphi’йской _Round() могут очень неплохо сглаживаться применением Return Stack’а. Действительно, код приложения имеет все шансы уложиться хотя бы большей своей частью в 16 вложенных вызовов (по размеру Return Stack). Ведь не с потолка же взяли Intel’овцы это число? Они же, напомню, пишут и о том, что разработчикам можно не слишком беспокоиться о падениях производительности при использовании процедур.

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

Четвертая особенность, которая также оказывает влияние на быстродействие, связана с выравниванием кода. Этот вопрос мы не затрагивали ранее, поскольку больше внимания уделяли «менее раскрученным» приемам, заточенным к тому же для ускорения выполнения кода независимо от его расположения в памяти. Все дело в том, что выравнивая данные и код на границы, кратные 4, 8, 16, 32 и т.д. байтам, можно получать очень неплохие бонусы по производительности. Начало процедуры выравнивается компилятором на такую границу – и чтение производится быстрее. К тому же, код _Round() занимает всего лишь 10 байт, что отлично укладывается в 16-байтные порции, которыми процессор считывает код из памяти.

2. Многоядерные процессоры, очевидно, наследуют все преимущества одноядерных. Рост преимущества Delphi-округления над NoProc можно объяснить еще и тем, что наверняка Intel’овцы не сидели сложа руки, а работали над тем, чтобы еще эффективнее выполнять типичный для приложений код. А таковым является именно код с процедурами небольших размеров: небольшие библиотечные функции, виртуальные методы объектов и т.п.

3. Ситуация с AMD для меня, честно говоря, неожиданна. По сути, единственное существенное отличие Delphi-кода от NoProc – в наличии вызова процедуры. И что-то лично мне подсказывает, что специалисты этой компании недоработали с вопросами аппаратной оптимизации. Все-таки вызов процедуры – далеко не самая редкая инструкция.

Получается, что вынесение кода в процедуру дает на AMD-процессорах почти двукратное падение производительности. Вспомним, что программирование под Windows – это еще и многочисленные вызовы API-функций, которые, в свою очередь, вызывают другие функции.

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

4. В Windows 98 падение производительности происходит только тогда, когда RDTSC предваряется CPUID. Стоит убрать инструкцию CPUID – все результаты снова становятся «нормальными». Документация ненавязчиво намекает на то, что CPUID, по сути, приостанавливает конвейерную обработку и дожидается, пока выполнятся все предшествующие инструкции и т.п. Понятно, что в этом случае среди небольших фрагментов кода преимущество имеют те, которые содержат меньше инструкций.

Если это так, то получается, что приложения в Windows 98 почему-то очень сильно зависят от конвейерной обработки. Можно было бы, разумеется, изучить эту ситуацию детальнее, но вспомним, что в реальных приложениях необходимость использования CPUID возникает не слишком часто.

Так ошиблись ли в Borland?

Скорее нет, чем да. У них действительно были основания сделать этот код именно таким, когда они проектировали первую Delphi. Потери в производительности могут случаться, но в довольно странных случаях: не-Intel’овские процессоры, частные случаи применения отдельных инструкций.

Исходя из того, что Intel на протяжении всей истории Borland’овской Delphi занимала все же лидирующие позиции, позволю себе заметить, что разработчики имели полное моральное право поддерживать именно решения от Intel, иной раз даже полностью или частично игнорируя факт существования других процессоров.

Впрочем, даже окажись процедурный вариант абсолютно проигрышным… В конце концов, есть области применения любых инструментов. И если уж Delphi создавалась как RAD-среда (Rapid Application Development), то, наверное, ей простительно было бы генерировать чуть менее эффективный код: пользовательский интерфейс – не самая критичная к скорости выполнения часть программы.

Каковы итоги эксперимента?

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

Ну, во-первых, мы рассмотрели приемы оптимизации выполнения кода на аппаратном уровне – тему, которая освещена достаточно широко, но в основном в англоязычных источниках и довольно сложным техническим языком. Рассмотрели, последовательно «создавая» гипотетический процессор.

Во-вторых, еще раз показали, что в вопросах оптимизации самые, казалось бы, очевидные вещи могут оказаться не соответствующими действительности. Как совершенно правильно заметил один преподаватель из БГУИР, «смотрите, как ваш код работает в системе, а не в чистом виде».

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

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

Ну и, конечно же, если вскроются новые подробности – мы обязательно об этом расскажем. Ждем ваших писем на info@sa-sec.org: вопросы, замечания, предложения приветствуются.

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


Компьютерная газета. Статья была опубликована в номере 41 за 2010 год в рубрике программирование

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