...
...

Тонкости оптимизации. Кратко для новичков. Часть 2

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

Предсказание переходов

Как вы, надеюсь, помните, в процессорах Intel (а именно на их примере мы рассматриваем вопросы оптимизации) на аппаратном уровне реализована возможность одновременной обработки нескольких инструкций: пока выполняются действия, описываемые одной, следующая за ней уже декодируется, чтобы вскоре также быть выполненной.

Однако давайте представим себе, что в программе встречается инструкция, нарушающая нормальный (линейный) порядок выполнения команд. Это может быть условный или безусловный переход. Чтобы говорить более предметно, приведу мнемоники этих инструкций: Jcc (условный переход, вместо “cc” записываются одна или две буквы, обозначающие условие выполнения перехода) и JMP (безусловный переход).





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

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

Обратим внимание на то, что JMP, если его выполнение уже началось, выполнится всегда, не зависимо от каких-либо условий. То есть здесь и предсказывать-то нечего, «к гадалке не ходи». О том, что это именно безусловный переход, процессор «знает» уже после того, как произведено декодирование этой инструкции. Таким образом, встретив JMP, процессор мог бы сразу переходить к декодированию инструкции, находящейся в том месте, куда происходит переход. Здесь мы в худшем случае теряем лишь время на то, чтобы загрузить в декодер новую инструкцию. Если переход происходит не слишком далеко (что отнюдь не редкость), то новая инструкция может даже оказаться в кэше. В любом случае, немного времени выполнения мы сэкономим.

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

Статическое предсказание переходов

Суть статического предсказания переходов заключается в том, что процессор пользуется простыми правилами для принятия решения о том, какую инструкцию декодировать следующей. Открываем «IA-32 Intel® Architecture Optimization» и читаем:

• Predict unconditional branches to be taken.
• Predict backward conditional branches to be taken. This rule is suitable for loops.
• Predict forward conditional branches to be NOT taken.
• Predict indirect branches to be NOT taken.
Таким образом, процессоры Intel при предсказании переходов руководствуются следующими правилами:
• Безусловные переходы выполняются.
• Условные переходы назад (к предыдущим командам) выполняются.
• Условные переходы вперед не выполняются.
• Косвенные переходы (например, когда адрес перехода хранится в памяти, а не указан явно) не выполняются.

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

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

Динамическое предсказание переходов

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

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

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

Идея динамического предсказания предельно проста. Информация о выполняемых процессором переходах помещается в специальный буфер – BTB (Branch Target Buffer). В нем сохраняется информация о переходах, которые уже встречались процессору. Когда в коде программы встречается инструкция, соответствующая переходу, процессор пытается выполнить предсказание на основании содержимого BTB. Если это не удается сделать (например, в BTB не оказалось информации об этом переходе), применяется статическое предсказание.

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

Аппаратная реализация предсказания переходов (особенно динамического) может отличаться для разных моделей процессоров: объемом BTB, например, – но суть данного приема оптимизации от этого не меняется.

Оптимизация подпрограмм

На самом деле, вызов подпрограммы и возврат из нее – это самые обычные безусловные переходы. Действительно, инструкция CALL (вызов подпрограммы) может быть заменена помещением в стек адреса возврата и последующим JMP’ом, а RET (возврат из подпрограммы) – извлечением адреса возврата из стека и JMP’ом по этому адресу. С этим, напомню, и связана основная причина падения производительности при злоупотреблении подпрограммами.

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

Подпрограммы используются в программировании слишком широко, чтобы игнорировать их при решении вопросов оптимизации. И Intel’овцы это прекрасно понимали, когда вводили такое понятие, как «Return Stack», или «стек возврата». Двумя абзацами ранее мы выяснили, что возврат из подпрограммы (инструкция RET) – это, по сути, безусловный переход по адресу, хранящемуся в памяти. Предсказать безусловный переход – не проблема: он выполняется всегда. Но вот тот факт, что при этом процессору приходится читать адрес возврата из памяти, – это и есть самая большая загвоздка.

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

В принципе, единственное условие, которое просят соблюдать программистов для эффективной работы Return Stack, – это чтобы каждому CALL’у соответствовал свой RET. Компиляторы для языков высокого уровня вряд ли поступают иначе, да и низкоуровневые программисты, пишущие на ассемблере, не особенно стремятся усложнять себе жизнь, так что это условие не создает каких-либо неудобств.

Наоборот, упрощает жизнь программиста. «It also mitigates the need to put certain procedures inline since the return penalty portion of the procedure call overhead is reduced» – говорят в Intel. «Это [использование Return Stack] также снижает потребность в размещении кода процедур в месте их вызова, поскольку плата производительностью за возврат из процедуры уменьшается».

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

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

Регистры и проблемы с их использованием

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

Самые часто используемые регистры – это регистры общего назначения. На сегодняшний день наиболее широко распространены 32-битные процессоры. В них каждый регистр общего назначения имеет размер 32 бита – 4 байта. Названия этих регистров: EAX, ECX, EDX, EBX, ESP, EBP, ESI, EDI. Как правило, инструкции работают с одним или несколькими такими регистрами целиком. Но есть возможность также обращаться к их младшим 2-байтовым частям, по таким именам: AX, CX, DX, BX, SP, BP, SI, DI. Для первых 4 регистров также возможно использование их 1-байтовых частей. Старшие их байты имеют имена AH, CH, DH и BH, а младшие – AL, CL, DL и BL.

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

Суровая практика такова, что если N-я инструкция изменяет содержимое, например, регистра EAX, а N+1-ая использует это, уже измененное, значение, то параллельное выполнение этих двух инструкций затруднительно. Потому что N+1-й инструкции придется подождать, пока значение в регистре будет изменено. В противном случае при чтении из этого регистра она бы могла получить значение, измененное лишь частично, то есть некорректное.
Понятно, что подобные ситуации снижают выигрыш от конвейерной обработки. Способы избежать этого есть. Например, иногда можно поменять местами несколько инструкций, порядок выполнения которых не важен с точки зрения логики программы, причем поменять так, чтобы рассмотренная нами ситуация не возникала.

Развитие этого приема – смешение инструкций разных типов. Например, если программа работает с вещественными числами, это предполагает использование инструкций так называемого FPU – Floating-Point Unit (устройство обработки чисел с плавающей точкой). Поскольку большинство инструкций FPU работает со своими собственными регистрами, они идеально подходят на роль «прослойки» между двумя другими командами, работающими с регистрами общего назначения.

Измерение производительности

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

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

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

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

Другими словами, иногда намного целесообразнее подвергнуть оптимизации операцию сложения чисел, чем вычисление, например, синуса.

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

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

Напоминаю, вопросы по теме (и не по теме тоже :-) ) приветствуются. E-mail, как и раньше: info@sa-sec.org.

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



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

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