Программирование -> Assembler -> Оптимизация программ на ассемблере.

Часть 2

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

Отказ от универсальности

Операции умножения и деления требуют немалых усилий от почти любого ЦП, поскольку должны быть реализованы (аппаратно или программно) через сдвиги и сложения или сдвиги и вычитания соответственно. Старинные 4- и 8-разрядные процесоры не содержали машинных команд для умножения или деления, так что эти операции приходилось реализовывать при помощи длинных подпрограмм, где явным образом выполнялись сдвиги и сложения или вычитания. Первые 16-разрядные микропроцессоры, такие, как 8086 и 68000, действительно позволяли производить операции умножения и деления аппаратными средствами, но соответствующие процедуры были невероятно медленными: в процессоре 8086, к примеру, для деления 32-разрядного числа на 16-разрядное требовалось примерно 150 тактов.

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

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

          mov    ax, myvar
          mov    bx, 8
          mul    bx
          mov    myvar, ax

В процессорах 8086/88 эта программа может быть преобразована в более "быструю" последовательность сдвигов:

          mov    ax, myvar
          shl    ax, 1        ; * 2
          shl    ax, 1        ; * 4
          shl    ax, 1        ; * 8
          mov    myvar, ax

или даже в такую: shl myvar, 1 shl myvar, 1 shl myvar, 1

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

Но не торопитесь - даже эта простая оптимизация не так тривиальна, как кажется! Очередь команд в процессорах семейства 80x86, конкретная модель процессора, которая используется в вашем компьютере, и наличие или отсутствик кэш-памяти могут в совокупности сыграть самые причудливые шутки. В некотрых случаях и на некоторых моделях ЦП иногда соит использовать эту команду в варианте "сдвиг на указанное в CX число позиций":

          mov    ax, myvar
          mov    cx, 3
          shl    ax, cx
          mov    myvar, ax

А в процессоре 80186 и более поздних имееется вариант "сдвиг на число позиций, заданное непосредственным операндом", что еще удобнее:

          shl    myvar, 3

Если вам требуется умножать на степень двойки числа длиной более 16 разрядов, для организации операций над двумя и более регистрами используется флажок переноса. Например, для умножения 32-разрядного числа в DX:AX на 4 можно записать:

          shl    ax, 1        ; * 2
          rcr    dx, 1
          shl    ax, 1        ; * 4
          rcr    dx, 1

Творчески сочетая сдвиги и умножения, можног организовать быстрое умножение на почти любое конкретное значение. Следующий фрагмент производит умножение значения в регистре AX на 10:

          mov    bx, ax       ; скопировать исходное число
          shl    ax, 1        ; * 2
          shl    ax, 1        ; * 4
          add    ax, bx
          shl    ax, 1        ; * 10

Использование отказа от универсальности для деления несколько болле ограничено. Деление на степень двойки, конечно, очень просто. Вы просто сдвигаете число вправо, следя лишь за выбором родходящей команды сдвига для желаемого типа деления (со знаком или без знака). Например, для выполнения деления без знака на 4 содержимого регистра AX можно написать:

          shr    ax, 1
          shr    ax, 1

а для процессора 80186 и более поздних можно вместо этого использовать команду

          shr    ax, 2

Деление со знаком на 4 обеспечит, например, последовательность

          sar    ax, 1
          sar    ax, 1

или для процессора 80186 и более поздних

          sar    ax, 2

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

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

Деление на степени двойки со сдвигами может быть ваыполнено с помощью флага переноса, и оно ничуть не более сложно, чем умножение. Например, для выполнения деления со знаком на 8 значения, в регистрах DX:AX можно использовать последовательность

          sar    dx, 1        ; / 2
          rcr    ax, 1
          sar    dx, 1        ; / 4
          rcr    ax, 1
          sar    dx, 1        ; / 8
          rcr    ax, 1

Но, в отличие от операции умножения, использование сдвигов для быстрого деления на произволные числа, такие как 3 или 10, а не на степени двойки, на удивление хлопотно. Если вы решите покорпеть над написанием программы быстрого деления на 10, в которой используется метод, аналогичный приведенному выше методу умножения на 10, то вскоре обнаружите, что полученная программа - длинная, работает медленно, и, более того, - вы уже сделали 90 % работы, необходимой для составления обобщенной программы деления, использующей сдвиги и вычитания. Обычно целесообразнее вместо этого обдумать всю ситуацию заново и преобразовать алгоритм или структуру данных так, чтобы избежать деления на "неудобные" числа.

Прежде чем оставить эту тему и двигаться дальше, я должен упомянуть одну изящную оптимизацию, авторство которой приписывают Марку Збиковскому [Mark Zbikovski], одному из авторов версий 2.x и 3.x системы MS-DOS. Приведенный нниже фрагмент делит значение в регистре AX на 512:

          shr    ax, 1
          xchg   ah, al
          cbw

Теперь, когда вы увидели этот нетривиальный прием, у вас наверняка возникло множество идей о том, ка организовать умножение или деление на относительно большие степени двух: 256, 512 и т.д., при помощи последовательностей команд XCHG или MOV.

Оптимизация переходов и вызовов подпрограмм

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

Быстродействие этих процессоров в значительной мере определяется их архитектурой, основанной на простой конвейерной схеме, содержащей три компоненты: шинный интерфейс (BIU - bus interface unit), очередь упереждающей выборки и исполнительный модуль (EU - execution unit). Когда шина памяти находится в нерабочем состоянии (например, прри выполнении команды из многих циклов, операнды которой находятся в регистрах), шинный интерфейс извлекает байты команд из памяти и помещает их в очередь упреждающей выборки, последовательно продвигаясь от текущего положения командного счетчика ЦП. Когда исполнительный модуль завершает исполнение очередной команды, он в первую очередь ищет следующую команду в очереди упреждающей выборки: если она там действительно имеется, то к ее расшифровке можно приступить сразу же, не обращаясь лишний раз к памяти.

Как же при такой реализации конвейерной обработки происходят переходы и вызовы подпрограмм? Всякий раз, когда исполнительный модуль расшифровывает команду перехода, он аннулирует текущее содержимое очереди упреждающей выборки и устанавливает новое содержимое счетчика команд. После этого шинный интерфейс должен снова выбирать байты команд, теперь уже начиная с нового адреса, и заносить их в очередь. исполнительный модуль вынужден в это время "простаивать" до тех пор, пока не будет восстановлена полная команда. Кроме того, все обращения к памяти, которые требуются для исполнения команды перехода по новому адресу, также оказывают влияние на выборку следующих команд из памяти. Может пройти немалое время, прежде чем шина снова заполнит очередь упреждающей выборки так, чтобы исполнительный модуль мог работать с полной скоростью. ситуацию усложняет то, что размер очереди командных байтов разный для разных моделей ЦП. Он составляет всего 6 байтов в ранних моделях и 32 байта в компьютерах последних моделей. Это один из факторов, делающих крайне сложным предсказание времен исполнения для конкретных последовательностей команд исходя из количества тактов и длин в байтах. Кроме того, состояние очереди команд для разных типов ЦП зависит и от "выравнивания" команд. Шинный интерфейс должен выбирать команды в соответствии с разрядностью адресной и информационной частей шины. Поэтому производительность очереди команд может существенно ухудшиться из-за неудачных адресов вызовов или переходов. Например, в процессоре 8086 с 16-разрядной шиной памяти выборка из памяти всегда происходит по 16 бит за один раз, так что если команда, на которую передается управление при вызове подпрограммы, начинается с нечетного адреса, половина первого обращения к памяти пропадает впустую.

Все это подталкивает нас к осознанию первого правила оптимизации переходов и вызовов: проверьте, что их точки назначения попадают в подходящие границы адресов для того типа процессора, на котором ваша программа будет исполняться чаще всего. Сделайте это, добавив подходящий атрибут выравнивания (WORD или DWORD) в объявлении сегментов и вставив директиву ALIGN перед каждой меткой. Процессор 8088 имеет 8-разрядную внешнюю шину, так что он абсолютно нечувствителен к выравниванию. Если потенциальными потребителями вашей программы являются пользователи компьютеров на процессоре 8088, к выравниванию прибегать не стоит, поскольку оно лишь потребует дополнительной памяти, но не увеличит производительность.

В то же время, если программе предстоит главным образом работать на компьютерах с процессорами 8086 или 80286, следует произвести выравнивание в границах WORD, а если она рассчитана на процессоры 80386DX, 80486DX - используйте выравнивание DWORD. (Для процессора 80486, в котором есть внутренняя кэш-память, лучше, когда позиции лежат на 16-байтовых границах, но тратить в среднем 8 байт на каждую метку мне кажется непозволительной роскошью.)

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

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

               cmp    balance, 0
               jl     in_the_read  ; бывает редко

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

               cmp    ax, m        ; наиболее вероятное значение
               jne    L1
               .                   ; действия для m
               .
               .
               jmp    L3
          L1:  cmp    ax, l        ; менее вероятное значение
               jne    L2
               .                   ; действия для l
               .
               .
               jmp    L3
          L2:  cmp    ax, ll       ; наименее вероятное значение
               jne    L3
               .                   ; действия для ll
               .
               .
          L3:

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

          table     dw   routine_00
                    dw   routine_01
                    .
                    .
                    dw   routine_FE
                    dw   routine_FF
                    .
                    .
                    mov  bl, al    ; скопировать символ в BL
                    xor  bh, bh    ; сформировать указатель к таблице
                    shl  bx, 1     ; перейти по таблице
                    jmp  [table+bx]

Есть еще две методики оптимизации, связанные с переходами и вызовами, которые требуют внесения определенной степени "деструктурированности" в во всем остальном верную программу и называются "сращиванием хвостов" и "устранением рекурсивных вызовов". Каждая из них подразумевает преобразование вызовов в переходы: вызовы по самой своей природе требуют большего времени, чем переходы, поскольку помещают в стек адрес возврата и в результате требуют больше обращений к памяти. Сращивание хвостов - это просто преобразование команды CALL, непосредственно за которой следует команда RETURN, в команду JMP. Например, последовательность

          proc1   proc   near
                  .
                  .
                  .
                  call   proc2
                  ret
          proc1   endp

          proc2   proc   near
                  .
                  .
                  .
                  ret
          proc2   endp

преобразуется в более быструю

          proc1   proc   near
                  .
                  .
                  .
                  jmp    proc2
          proc1   endp

          proc2   proc   near
                  .
                  .
                  .
                  ret
          proc2   endp

Такая оптимизация приводит к следующему: поскольку адрес команды, вызывающей PROC1, находится в стеке, на входе в PROC2, процедура PROC2 возвращается прямо к исходной вызывающей программе, тепм самым устраняя лишние команды CALL и RETURN. Если процедура PROC2 физически (в памяти) следует за программой PROC1, то можно обойтись даже без команды JMP PROC2, и за выполнением PROC1 может сразу же следовать PROC2.

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

          proc1   proc   near
                  .
                  .
                  .
                  cmp    ax, some_value
                  je     exit
                  call   proc1
          exit:   ret

          proc1   endp

может быть преобразована в

          proc1   proc   near
                  .
                  .
                  .
                  cmp    ax, some_value
                  jne    proc1
                  ret
          proc1   endp

Такая рекурсивная программа часто может быть еще оптимизирована за счет преобразования рекурсии в цикл.