Программирование на языке ассемблера

занятую на момент начала работы процедуры (отсюда происходит название регистра EBP – указатель базы кадра стека). При таком подходе первый параметр процедуры всегда находится по адресу [EBP + 8]. Адреса локальных переменных отсчитываются от регистра EBP с отрицательным смещением. По окончании работы процедуры значение регистра ESP восстанавливается по регистру EBP, а значение регистра EBP – из стека.

Такой способ позволяет также отводить различное количество места под локальные данные, и при необходимости не заботится о парности команд PUSH и POP.

7.9. Рекурсивные процедуры

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

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

Для примера рассмотрим рекурсивную процедуру вычисления факториала целого беззнакового числа. Процедура получает параметр через стек и возвращает результат через регистр EAX.

factorial proc

Выбор оптимального алгоритма для решения задачи всегда приводит к лучшим результатам, чем любой другой вид оптимизации. Действительно, при замене пузырьковой сортировки, время выполнения которой пропорционально n2, на быструю сортировку, время выполнения которой пропорционально n * log(n), вторая программа будет выполняться быстрее в подавляющем большинстве случаев, как бы она ни была реализована. Поиск лучшего алгоритма – универсальная стадия, и она относится не только к ассемблеру, но и к любому языку программирования, поэтому будем считать, что оптимальный алгоритм уже выбран.

8.2. Оптимизация среднего уровня

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

8.2.1. Вычисление констант вне цикла

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

8.2.2. Перенос проверки условия в конец цикла

Циклы типа while или for, которые так часто применяются в языках высокого уровня, оказываются менее эффективными по сравнению с циклами типа until из-за того, что в них требуется лишняя команда перехода.

; i = start_i; do { <тело цикла> } while (i < n);

Предположим, в цикле должен быть один шаг. Тогда в цикле с предусловием будет выполнено сравнение, тело цикла, безусловный переход к началу цикла, сравнение и переход за цикл. В цикле с постусловием будет выполнено тело цикла, сравнение и нереализованный переход. Таким образом, в цикле с предусловием выполняется одно лишнее сравнение и два реализованных перехода (2 * 3 такта = 6 тактов) вместо одного нереализованного (1 такт). Вроде бы и немного, но если цикл окажется внутри другого цикла, то все эти лишние такты будут повторяться многократно. Кроме того, цикл с постусловием содержит на одну команду меньше.

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

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

8.2.3. Выполнение цикла задом наперёд

Циклы, в которых значение счётчика растёт от единицы или нуля до некоторой величины, можно реализовать вообще без операции сравнения, выполняя цикл в обратном направлении. Флаги меняются не только командой сравнения, но и многими другими. В частности, команда DEC меняет флаги AF, OF, PF, SF и ZF. Команда сравнения кроме этих флагов меняет также флаг CF, но для сравнения с нулём можно обойтись флагами SF и ZF.

; Цикл от 10 до 1

mov edx, 10

loop_start:

; Цикл от 10 до 0

mov edx, 10

loop_start:

Циклы от 0 и от 1 являются, наверное, самыми распространёнными. Конечно, не все циклы можно заставить выполняться в обратном направлении сразу. Например, иногда приходится изменять формат хранения массива данных также на обратный, иногда приходится вносить другие изменения, но в целом, если это возможно, всегда следует стремиться к циклам, выполняющимся задом наперёд.

8.2.4. Разворачивание циклов

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

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

8.3. Низкоуровневая оптимизация

8.3.1. Основные принципы

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

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

Перечислим основные рекомендации.

Используйте регистр ЕАХ всюду, где возможно. Команды с непосредственным операндом, с операндом – абсолютным адресом переменной и команды XCHG с регистрами занимают на один байт меньше, если другой операнд – регистр ЕАХ.

Если к переменной в памяти, адресуемой со смещением, выполняется несколько обращений – загрузите её в регистр.

Не используйте сложные команды – ENTER, LEAVE, LOOP, строковые команды, если аналогичное действие можно выполнить небольшой последовательностью простых команд.

Не используйте умножение или деление на константу – его можно заменить другими командами (см. раздел 6.3).

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

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

Используйте короткую форму команды JMP, где возможно (jmp short <метка>).

Команда LEA быстро выполняется и имеет много неожиданных применений (см. раздел 8.3.2).

Многие одиночные команды, как это ни странно, выполняются дольше, чем две или три команды, приводящие к тому же

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

8.3.3).

Старайтесь выравнивать данные и метки по адресам, кратным

2/4/8/16 (см. раздел 8.3.4).

Если команда обращается к 32-битному регистру, например ЕАХ, сразу после команды, выполнявшей запись в соответствующий частичный регистр (АХ, AL, АН), может происходить пауза в один или несколько тактов.

8.3.2. Использование команды LEA

Команда LEA может использоваться для сложения значения регистра с константой или вычитания константы из значения регистра. В данном случае вычитание возможно, т.к. оно рассматривается как сложение с отрицательной константой. Результат может быть помещён в тот же или другой регистр (кроме регистра ESP). Такой способ используется для сохранения флагов, т.к. команда LEA, в отличие от команд ADD, SUB, INC и DEC, не меняет флаги.

Команда LEA может использоваться для быстрого умножения на константы 2, 3, 4, 5, 7(?), 8, 9. Адрес, загружаемый командой LEA, может быть суммой двух регистров, один из которых может быть умножен на константу 2, 4 или 8. Поэтому комбинируя умножение и сложение можно получить вышеперечисленные константы. Третье слагаемое может быть константой.

8.3.3. Замена команд

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

test eax, eax

Если за командой CALL сразу же следует команда RET, замените эти команды командой JMP. Вызываемая процедура осуществит возврат по адресу возврата, переданному вызывающей процедуре.

ret

Команду CBW можно заменить засылкой нуля, если расширяемое число положительное. Команду CDQ можно заменить засылкой нуля, если расширяемое число положительное, или парой команд MOV + SAR, если знак расширяемого числа не известен. Недостаток – команды XOR и SARменяют флаги.

Вместо команд инкремента и декремента можно использовать команду LEA.

Сложение и вычитание с константой можно заменить командой LEA.

Вместо умножения и деления на степень числа 2 используйте

сдвиги.

Умножение и деление на константу можно заменить командой LEA или сочетанием команд сдвига и команд сложения и вычитания.

Деление на константу можно заменить умножением на константу.

Обнуление регистров производится с помощью команды XOR.

Не используйте команду MOVZX для чтения байта – это требует 3 тактов для выполнения. Заменой может служить такая пара команд, выполняющаяся за 2 такта:

xor еах, еах

mov al, <источник>

Засылку непосредственного операнда в ячейку памяти можно производить через регистр – такие команды лучше спариваются.