Оптимизация программ на ассемблере
Рэй Дункан
Введение.
Несмотря на все более широкое распространение языков програм-
мирования высокого уровня и интегрированных средств программиро-
вания, оптимизация программ на ассемблере остается актуальной
темой дискуссий программистов. Можно упомянуть, например, форум
программистов, проведенный сетью PC MagNET, который стал ареной
многочисленных "дуэлей": то один, то другой участник предлагал
всем желающим решить небольшую, но интересную задачу программи-
рования - и рассматривал присылаемые решения, ожидая, кто-же и
как решит задачу наименьшей кровью, т.е. затратив минимум байтов
на программу. Подобно этому проведенная сетью BIX конференция по
языку ассемблера для процессоров 80x86 и 80x88 стала трибуной
немалого числа основательных рассуждений по поводу неочевидных
аспектов оптимизации ассемблерных программ.
Несмотря на самый общий и широкий интерес к проблеме, литера-
тура по оптимизации ассемблерных программ для процессоров 80x86
и 80x88 на удивление скудна. В 1989 году, готовясь к докладу на
эту тему для конференции по развитию программного обеспечения, я
просмотрел оглавления всех основных журналов по программированию
и обнаружил лишь горстку статей на эту тему. С другой стороны,
литература по оптимизации программ для компиляторов высокого
уровня весьма обширна, и многие концепции, развитые в ней, будут
полезны и при программировании на языке ассемблера. Так что го-
ворить, что литературы совсем нет, было бы несправедливо. Ниже
мы сначала рассмотрим общие методики оптимизации, а затем обсу-
дим более серьезный вопрос - когда и что что стоит оптимизиро-
вать.
В этом документе будут обсуждаться некоторые общие вопросы и
концепции оптимизации. Будет разговор и компромиссах, на которые
приходится идти оптимизируя быстродействие и размер программы.
Будут рассмотрены конкретные методы, относящиеся к переходам и
вызовам подпрограмм, а также метод отказа от универсальности.
Ниже мы подробнее рассмотрим некоторые классические образцы "ло-
кальной" оптимизации. В том числе: оптимизацию циклов, примене-
ние таблиц управляющих параметров, а также об ориентированных на
конкретные модели процессоров командах. Но важно помнить, что
эти частные методики следует использовать только при определен-
ных обстоятельствах - а именно: после того, как вы убедитесь,
что применили правильные алгоритмы и структуры данных, что пол-
ностью отладили программу и что средства профилирования показали
вам те самые фрагменты программы, которые ограничивают произво-
дительность. Стоит еще раз повторить мудрое изречение доктора
Кнута: "Многие беды программирования проистекают от преждевре-
менной оптимизации".
¦ Чтобы ваши программы на ассемблере принесли максимум пользы, ¦
¦ иногда стоит оптимизировать размер, иногда - быстродействие, ¦
¦ а иногда - лучше оставить все как было. ¦
1. Оптимизация по быстродействию.
Если вы пришли к выводу, что ваша программа работает недоста-
точно быстро, первое, что надо сделать, это убедится, что вы ре-
шаете задачу, пользуясь наилучшими алгоритмами и представлениями
данных. Замена примитивного или неадекватного алгоритма более
подходящим может ускорить выполнение вашей программы на порядок
и более. Так что если вы проведете несколько дней, штудируя зна-
менитые книги Кнута или Седжуика (в надежде подобрать алгоритм,
до которого вряд ли додумались бы сами), - будьте уверены: вы
сделали выгодное вложение своего драгоценного времени. Аналогич-
но переход от "очевидной", но простой структуры данных (такой,
как связный список) к более сложной (например, бинарному дереву)
может дать такие результаты, которые с лихвой окупят ваши усилия
по усовершенствованию программы.
Если вы уверены, что выбрали наилучшие алгоритмы и структуры
данных, следующее, на что следует обратить внимание, - это ис-
пользование программой данных, хранимых в памяти. Даже самые
быстрые устройства работы с дисками, используемые в персональных
компьютерах, работают несравнимо медленнее, чем такие мощные вы-
числители, как процессоры 80386 или 80486, так что постарайтесь
свести обращения к диску до возможного минимума. Ознакомьтесь со
всеми имеющимися типами данных, доступными программе DOS, - рас-
ширяемой и отображаемой памятью, старшими блоками памяти и так
далее - и полностью используйте возможности оперативной памяти
для хранения в ней данных, с которыми работает ваша программа,
чтобы время обращения к ним было минимальным. Полезно также поз-
накомиться с техникой уплотнения данных, поскольку почти во всех
случаях быстрее оказывается сначала уплотнить, а затем распако-
вать данные, когда в них возникает необходимость, чем по нес-
кольку раз считывать неуплотненную информацию с диска.
Еще одной темой, заслуживающей обсуждения, является уменьше-
ние объема вычислений в программе. Составители компиляторов
пользуются забавными терминами - устранение общих подвыражений,
сворачивание констант, распространение констант - для того что-
бы, по сути, сказать одно и то же: во время работы программы од-
но и то же значение ни в коем случае не должно вычисляться дваж-
ды. Вместо этого программа должна рассчитывать каждое значение
лишь один раз и сохранять его для повторного использования. Еще
лучше переносить вычисления со стадии исполнения на стадию ас-
семблирования, всякий раз, когда это позволяют ограниченные ма-
тематические "способности" MASM, TASM или OPTASM. Совершенно
аналогично вам, возможно, удастся существенно повысить быстро-
действие программы, преобразовав вычисления в обращения к табли-
цам, которые заранее генерируются и сохраняются отдельной прог-
раммой.
Если вы сделали все возможное на абстрактом уровне по всем
названным направлениям, пора спускаться на грешную землю. Оста-
лось немногое - "отжать из программных кодов всю воду" и "про-
чистить все циклы", особенно если программа существенно исполь-
зует работу с дисплеем и выводит на экран графику. Вот некоторые
из самых общих процедур этой категории.
- Замещение универсальных инструкций на учитывающие конкрет-
ную ситуацию, например замена команды умножения на степень
двойки на команды сдвига (отказ от универсальности).
- Уменьшение количества передач в программе: за счет преобра-
зования подпрограмм в макрокоманды для непосредственно
включения в исполнимый код; за счет преобразования условных
переходов, так чтобы условие перехода оказывалось истинным
относительно реже, чем условие для его отсутствия; переме-
щение условий общего характера к началу разветвленной пос-
ледовательности переходов; преобразование вызовов, сразу за
которыми следует возврат в программу, в переходы ("сращива-
ние хвостов" и "устранение рекурсивных хвостов") и так да-
лее.
- Оптимизация циклов, в том числе перемещение вычислений не
изменяющихся величин за пределы циклов, разворачивание цик-
лов и "соединение" отдельных циклов, выполняемых одно и то
же число раз, в единый цикл ("сжатие цикла").
- Максимальное использование всех доступных регистров, за
счет хранения в них рабочих значений всякий раз, когда это
возможно, чтобы минимизировать число обращений к памяти,
упаковка множественных значений или флагов в регистры и
устранение излишних продвижений стека (особенно на входах и
выходах подпрограмм).
- Использование специфических для данного процессора инструк-
ций, например инструкции засылки в стек непосредственного
значения или умножения числа на непосредственный операнд,
которые имеются в процессорах 80186, 80188, 80286, 80386 и
80486. Другие примеры - двухсловные строковые инструкции,
команды перемножения 32-разрядных чисел и деления 64-раз-
рядного на 32-разрядное число, которые реализованы в про-
цессорах 80386 и 80486. Ваша программа должна, разумеется,
вначале определять с каких типом процессора она работает.
В процессорах 80x86, но не 80x88, вам, возможно, также удаст-
ся увеличить скорость исполнения программы на несколько процен-
тов за счет выравнивания расположения данных и меток, на которые
происходит передача управления, относительно некоторых границ.
Процессоры 8088 и 80188 - с 8-разрядной шиной и им без разницы
на какую границу выровнены данные, поэтому выравнивание можно
отключить или установить на границу байта (1 байт, 8 бит); про-
цессоры 8086, 80186 и 80286 - с 16-разрядной шиной и им "удоб-
нее" работать с данными, выровненными на границу слова (2 байта,
16 бит); процессор 80386 - с 32-разрядной шиной, поэтому он
предпочитает выравнивание на границу двойного слова (4 байта, 32
бита); из-за устройства его внутренней кэш-памяти процессору
80486, то же с 32-разрядной шиной, легче работать, если произве-
дено выравнивание на границу параграфа (16 байт, 96 бит).
Если же все остальное успеха не принесло, а вы пишите некую
штучную, специальную программу, а не программный пакет, предназ-
наченный для продажи на массовом рынке, проблему быстродействия,
может быть, проще "решить" аппаратным путем. При существующих
сегодня ценах часто оказывается намного выгоднее заказать новый,
более мощный компьютер для работы с вашей специализированной
программой, чем тратить время на мучения, связанные с переделкой
программы, ее оптимизацией и последующей отладкой заново. К со-
жалению, безоглядное и некритическое принятие этого подхода та-
кими производителями программных изделий, как Microsoft, Borland
и Lotus, привело к рождению громоздких монстров, подобных таким
как Windows 3.0 и 3.1, Programmer's Workbench, Microsoft C 6.0,
и Microsoft C++ 7.0, Borland C++ 3.0 и Borland C++ 3.1, Borland
Pascal 7.0, а также и Lotus 1-2-3 3/G, - но это уже тема другого
разговора.
+--------------------------------------------------------------+
¦ Почти все, что облегчает чтение программы и содействует ее ¦
¦ сопровождению, обычно повышает и быстродействие. ¦
+--------------------------------------------------------------+
2. Оптимизация по размеру.
Если работоспособность вашей программы ограничена ее разме-
ром, а не скоростью исполнения, то вам надо вновь подумать над
стратегией оптимизации - на этот раз над ухищрениями, в точности
противоположными тем, что вы использовали для увеличения быстро-
действия. Тщательно изучите свою программу и определите, что
создает основную проблему - размер кода или объем данных.
Если вам приходится работать с большими блоками данных, то
нужный эффект может дать их организация в нетривиальные структу-
ры. Однако замена быстрообрабатываемых, но неплотных массивов и
таблиц более компактными структурами типа связных списков или
упаковка данных с использованием битовых полей, вероятно, даст
не слишком большие преимущества. Примитивное уплотнение таблиц и
иных структур данных и их последующее, по необходимости, разуп-
лотнение обычно не очень полезно, так как часто требуется разуп-
лотнять все данные лишь для того, чтобы добраться до какого-то
одного пункта, а программы уплотнения/разуплотнения сами по себе
обычно занимают заметный объем памяти.
Большие просмотровые таблицы и массивы можно поместить в дис-
ковый файл и при необходимости считывать его в память малыми
частями. Но это может нанести сокрушительный удар по производи-
тельности, если данные запрашиваются в случайном порядке. Часто
можно вообще отказаться от использования просмотровых таблиц и
производить вычисление значений переменных заново всякий раз,
когда в последних возникает необходимость. Вы также должны ис-
кать и устранять константы и переменные, которые реально никогда
не используются программой, поскольку вместо них она использует
другие величины, вычисленные ранее во время разработки и отлад-
ки. Во всяком случае, я еще раз хочу подчеркнуть, что чрезвычай-
но важно усвоить, как пользоваться всеми видами памяти, доступ-
ными компьютеру, и сделать программу достаточно гибкой, чтобы
она могла использовать все и каждую из них.
Оптимизация программы с целью уменьшения размера - это совсем
не то же самое, что оптимизация для повышения быстродействия.
Во-первых, вы должны просмотреть весь текст программы и устра-
нить все предложения и процедуры, которые никогда не выполняются
или недоступны ни из какой точки программы (мертвые коды). Если
вы работаете с большой прикладной программой, над которой до вас
уже потрудились несколько программистов, вас, возможно, даже
удивит, как много строк можно безболезненно удалить. Во-вторых,
проанализируйте программу заново и соберите все идентичные или
функционально сходные последовательности кода в подпрограммы,
которые могут быть вызваны из любой точки программы. Чем более
универсальными вам удастся сделать подпрограммы, тем более веро-
ятно, что их код может быть использован повторно. Если вы будете
последовательно придерживаться этого подхода, где только возмож-
но, то получите очень компактную программу модульного типа, сос-
тоящую главным образом из вызовов подпрограмм.
Если вы сделали все, что я рекомендовал выше, а вам по-преж-
нему не хватает памяти, то попробуйте поискать удачи еще на нес-
кольких путях. Вы можете перекомпилировать свою программу в от-
носительно независимые модули, которые могут поодиночке считы-
ваться в память как оверлеи. Вы можете закодировать функциониро-
вание вашей программы в таблицах, "управляющих" ее исполнением.
Вы можете прибегнуть к методике "прошитого" кода или псевдокода
и представить логику вашей программы с использованием гораздо
меньшего объема памяти за счет некоторого снижения быстродейс-
твия. Можно, наконец, прибегнуть к тяжелой артиллерии современ-
ной компьютерной технологии и использовать стандартный интерпре-
татор или компилятор "малого языка", который в свою очередь бу-
дет служить виртуальной машиной для прикладной программы. Quick
BASIC, Excel и Brief - самые привычные примеры применения соот-
ветственно стратегии прошитого кода, псевдокода и малого языка.
В конечном счете, если вы пишете специализированную приклад-
ную программу, преодолеть проблемы памяти возможно (снова)
удастся объединенным программно-аппаратным путем. Среди многих
возможностей есть такие: использование более высоких версий опе-
рационной системы, таких как DOS 5.0 или OS/2 2.0 для расширения
объема рабочей памяти (в пределах первых 640 Кбайт); установка
еще одной платы расширения памяти, переход к компьютерам на про-
цессорах 80386 и 80486, которые поддерживают большую память по
сравнению с использовавшейся вами машиной на процессоре 8086,
8088, 80186, 80188 или 80286; и/или запуск вашей программы под
управлением расширителя DOS.
+--------------------------------------------------------------+
¦ Оптимизация размера программы - это совсем не то же самое, ¦
¦ что оптимизация ее быстродействия. ¦
+--------------------------------------------------------------+
3. А стоит ли оптимизировать?
Оптимизация кодов на любом языке всегда требует идти на комп-
ромиссы, среди которых такие, как:
- Сокращение потребного объема памяти за счет снижения быст-
родействия;
- Повышение быстродействия за счет ухудшения возможностей
сопровождения и доступности текста программы для чтения;
- Сокращение времени исполнения программы за счет увеличения
времени ее разработки.
Все это кажется очевидным, но в большинстве реальных ситуаций
принять оптимальное решение не так просто, как кажется на первый
взгляд. Классическим примером является выбор между двумя приве-
денными ниже инструкциями, каждая из которых может быть исполь-
зована для перемещения некоторого значения из регистра DX в ре-
гистр AX (конечно, с различным побочными эффектами):
xchg ax,dx
или
mov ax,dx
В процессорах 80x86 и 80x88 команда MOV занимает 2 байта и
требует 2 тактов центрального процессора, тогда как команда XCHG
занимает 1 байт, но требует 3 тактов. Пока все кажется ясным:
надо выбирать между скоростью и памятью. Но реальное время ис-
полнения команды существенно зависит от контекста, размера оче-
реди команд центрального процессора, размера и характеристик
кэш-памяти системы и так далее, тогда как даже число циклов,
требуемых для исполнения инструкций, меняется от одной модели
центрального процессора к другой. Как оказывается, практически
невозможно предсказать скорость исполнения нетривиальной после-
довательности инструкций в процессоре фирмы Intel, особенно в
последних моделях 80386 и 80486, в которых более интенсивно ис-
пользуется конвейерная обработка, - вам придется составлять раз-
личные возможные комбинации инструкций, запускать их и экспери-
ментально определять время их исполнения.
Аналогично баланс между временем исполнения программы и вре-
менем ее разработки и баланс между возможностями сопровождения
программы и ее быстродействием редко бывают столь однозначны,
как нам бы хотелось, а долговременные последствия ошибочных ре-
шений могут быть весьма неприятными. Вообще же, занимаясь опти-
мизацией, важнее всего понимать, когда ее делать, а когда лучше
оставить все как было. Процитируем Дональда Кнута: "Многие беды
программирования проистекают от преждевременной оптимизации".
Прежде чем думать о настройке своей программы, убедитесь, что
она правильная и полная, что вы используете верный алгоритм для
решения поставленной задачи и что вы составили самый ясный, са-
мый простой, самый структурированный код, который только был
возможен.
Если программа удовлетворяет всем этим критериям, то, на са-
мом деле, ее объем и скорость исполнения в большинстве случаев
будут вполне приемлемыми без каких-либо дальнейших усовершенс-
твований. Одно только использование ассемблера само по себе при-
водит к увеличению скорости исполнения программы в 2-3 раза и
примерно к такому же уменьшению размера по сравнению с аналогич-
ной программой на языке высокого уровня. И еще: если что-то уп-
рощает чтение программы и ее сопровождение, то обычно это же од-
новременно приводит к увеличению скорости исполнения - здесь
можно назвать отказ от макаронных кодов со многими ненужными пе-
реходами и вызовами подпрограмм (которые являются тяжелой рабо-
той для процессоров с архитектурой 80x86 или 80x88, поскольку
они сбрасывают очередь команд), а также предпочтение простых
прямолинейных машинных команд аналогичным сложным.
Тем не менее, вашей наиглавнейшей заботой должны быть ощуще-
ния потенциального пользователя при работе с вашей программой:
насколько производительной покажется программа ему? Прислушаемся
к словам Майкла Эбраша: "Всякая оптимизация, ощущаемая пользова-
телем, заслуживает того, чтобы ее сделать". И наоборот, если в
массах пользователей о вашей программе складывается мнение, как
о тупой и неуклюжей, то очень вероятно, что она не будет должным
образом оценена. Примером может служить судьба пакета ToolBook.
Следовательно, должно казаться, что ваша программа мгновенно
откликается на действия пользователя, даже тогда, когда она за-
нята длительными вычислениями или операциями с диском. Она долж-
на поддерживать экран дисплея в "живом" состоянии, заполняя его
чем-нибудь вроде циферблатов, термометров, и позволять пользова-
телю безопасно прерывать длительные операции в любое время, если
его намерения изменились и он решил заняться чем-нибудь еще.
Если вы действительно вынуждены прибегнуть к шлифовке кода и
циклов с помощью методов, о которых я говорил выше, то постарай-
тесь затратить свои время и силы на действия в правильном нап-
равлении. Помните о естественной иерархии временных масштабов:
среди операций, перечисленных ниже, каждая следующая требует на
порядок больше времени, чем предшествующая. Итак, это операция
регистр/регистр, операции с памятью, операции с диском и опера-
ции взаимодействия с пользователем. Так что не тратьте силы на
то, чтобы сократить несколько машинных циклов в программе, если
скорость ее исполнения ограничена операциями обращения к диско-
вым файлам: вместо этого попытайтесь найти способы сократить
число таких операций. А после того, как вы сделали что-то, что в
принципе могло бы быть оптимизацией, проведите дотошную проверку
полученных результатов и вообще - проверяйте, проверяйте, прове-
ряйте.
В своей превосходной книге "Пишем эффективные программы" Джон
Бентли рассказывает кошмарную историю из жизни фирмы Bell Labs -
историю, которую мы все и всегда должны помнить:
"В начале 60-х годов Виктор Высоцкий работал над усовершенс-
твованием компилятора Фортрана, причем в число исходных требова-
ний входило отсутствие сколько-нибудь заметного снижения времени
компиляции. Одна из подпрограмм исполнялась редко (во время раз-
работки Высоцкий оценил, что она должна вызываться в одном про-
центе компиляций, причем в каждой из них лишь однажды), но рабо-
тала крайне медленно. Поэтому Высоцкий затратил неделю на удале-
ние из нее лишних циклов. Модифицированный компилятор работал
достаточно быстро. После двух лет интенсивной эксплуатации ком-
пилятор выдал сообщение о внутренней ошибке при компиляции одной
программы. Когда Высоцкий исследовал компилятор, он обнаружил
что ошибка была в прологе "критической" подпрограммы и что эта
ошибка содержалась в данной подпрограмме всегда, с самого начала
производства".
Высоцкий совершил 3 принципиальных ошибки: он не провел пол-
ный анализ программы перед тем, как приступить к оптимизации,
так что он напрасно тратил время на оптимизацию подпрограммы, не
влияющей на быстродействие; он не смог сделать оптимизацию пра-
вильно; и он не провел испытаний оптимизированной подпрограммы,
чтобы убедится, что она работает согласно спецификации.
Я совсем не хочу тыкать пальцем в мистера Высоцкого: в своей
жизни я совершил множество промахов куда как серьезнее, но (пос-
кольку я не работаю в Bell Labs) эти промахи, к счастью, не были
увековечены в книге Джона Бентли. Однако этот случай из жизни
Высоцкого - хороший пример того, как время и энергия могут быть
растрачены в пустую на святое дело оптимизации и как рано или
поздно проявляется отказ от методичного исполнения всех основных
процедур профилирования и контроля в процессе оптимизации.
+--------------------------------------------------------------+
¦ Когда вы сделали все возможное для оптимизации своей прог- ¦
¦ раммы на глобальном уровне, попробуйте оптимизировать дальше ¦
¦ за счет классического уплотнения кода и "прочистки" циклов. ¦
+--------------------------------------------------------------+
4. Отказ от универсальности.
Операции умножения и деления требуют немалых усилий от почти
любого центрального процессора, поскольку должны быть реализова-
ны (аппаратно или программно) через сдвиги и сложения или сдвиги
и вычитания соответственно. Старинные 4-разрядные и 8-разрядные
процессоры не содержали машинных команд для умножения или деле-
ния, так что эти операции приходилось реализовывать при помощи
длинных подпрограмм, где явным образом выполнялись сдвиги и сло-
жения или вычитания. Первые 16-разрядные процессоры, такие, как
8086, 8088 и 68000, действительно позволяли производить операции
умножения и деления аппаратными средствами, но соответствующие
процедуры были невероятно медленными: в процессорах 8086 и 8088,
к примеру, для деления 32-разрядного числа на 16-разрядное тре-
бовалось примерно 150 тактов.
Поэтому маленькие хитрости для ускорения или устранения опе-
раций умножения и деления были и пока остаются среди первых при-
емов, которые изучает любой программист, стремящийся к совер-
шенству. Большинство из этих хитростей относится к категории,
которую называют "отказ от универсальности". Под этим понимается
замена рассчитанных на общий случай команд умножения и деления
(или вызов соответствующих подпрограмм) последовательностями
сдвигов и сложений или вычитаний для случая конкретных операн-
дов.
Давайте сначала рассмотрим простейшую процедуру оптимизации
умножения. Чтобы умножить число на степень двойки, его достаточ-
но просто сдвинуть влево на необходимое число двоичных (битовых)
позиций. Вот так, например, выглядит, некоторая общая, но мед-
ленная последовательность команд для умножения значения перемен-
ной MyVar на 8:
mov ax,MyVar
mov bx,8
mul bx
mov MyVar,ax
В процессорах 8086 и 8088 эта программа может быть преобразо-
вана в более "быструю" последовательность сдвигов:
mov ax,MyVar
shl ax,1
shl ax,1
shl ax,1
mov MyVar,ax
или даже в такую:
shl MyVar,1
shl MyVar,1
shl MyVar,1
Если требуется сдвиг на одну или две позиции, то обычно проще
всего выполнить эти операции над операндами в памяти. Если нужен
сдвиг на много позиций, то повышенная скорость операций над ре-
гистровыми операндами вполне компенсирует дополнительную команду
для загрузки числа в какой-либо регистр и извлечения его оттуда
после сдвига.
Но не торопитесь - даже эта простая оптимизация не так триви-
альна, как кажется! Очередь команд в процессорах семейства 80x86
и 80x88, конкретная модель процессора, которая используется в
вашем компьютере, и наличие или отсутствие кэш-памяти могут в
совокупности сыграть самые причудливые шутки. В некоторых случа-
ях и на некоторых моделях центрального процессора иногда стоит
использовать эту команду в варианте "сдвиг на указанное в CL
число позиций":
mov ax,MyVar
mov cl,3
shl ax,cl
mov MyVar,ax
А в процессорах 80186, 80188, 80286, 80386 и 80486 имеется
вариант "сдвиг на число позиций, заданное непосредственным опе-
рандом", что еще удобнее:
shl MyVar,3
Если вам требуется умножать на степень двойки числа длиной
больше 16 разрядов, для организации операций над двумя и более
регистрами используется флажок переноса. Например, для умножения
32-разрядного числа в DX:AX на 4 можно записать:
shl ax,1
rcl dx,1
shl ax,1
rcl dx,1
Творчески сочетая сдвиги и сложения, можно организовать быст-
рое умножение на почти любое конкретное значение. Следующий
фрагмент производит умножение значения в регистре AX на 10:
mov bx,ax
shl ax,1
shl ax,1
add ax,bx
shl ax,1
Использование отказа от универсальности для деления несколько
более ограничено. Деление на степень двойки, конечно, очень
просто. Вы просто сдвигаете число вправо, следя лишь за выбором
подходящей команды сдвига для желаемого типа деления (со знаком
или без знака). Нахождение же остатка от деления на степень
двойки для чисел без знака еще проще. Для этого надо просто вы-
полнить просто одну команду операции логического И над операндом
и непосредственным значением, которое, в свою очередь, должно
быть представлено в виде уменьшенного на единицу значения дели-
теля. Для чисел со знаком тут дела обстоят не так просто, так
как. знак остатка от деления должен быть равен знаку делителя и
не зависит от знака делимого. Реализация этих операций потребует
обязательного присутствия условных переходов, а это уже плохо.
Например, для выполнения деления без знака на 4 содержимого ре-
гистра AX можно написать:
shr ax,1
shr ax,1
а для процессоров 80186, 80188, 80286, 80386 и 80486 можно вмес-
то этого использовать команду:
shr ax,2
Нахождение остатка от деления числа без знака на 4 произво-
дится следующим образом:
and ax,0003h
не правда ли слишком просто!
Деление со знаком на 4 обеспечит, например, последователь-
ность:
sar ax,1
sar ax,1
или для процессоров 80186, 80188, 80286, 80386 и 80486:
sar ax,2
Единственная разница между командой логического (без знака)
сдвига SHR и командой арифметического (со знаком) сдвига SAR
состоит в том, что SHR копирует старший, знаковый разряд в сле-
дующий, а затем заменяет знаковый разряд нулем, тогда как SAR,
после копирования знакового разряда в следующий, оставляет его
значение неизменным.
Выбор правильной команды сдвига для быстрого деления очень
важен, особенно, если вы имеете дело с адресами. Если вы случай-
но использовали арифметическое деление (со знаком) вместо деле-
ния без знака, которое предполагали сделать, последствия этого
иногда проявляются сразу же - а иногда и нет; образовавшаяся
"блоха" может до поры притаиться и укусить вас позже, когда ка-
кое-нибудь изменение размера или порядка компоновки прикладных
программ выпустит ее на волю. (Между прочим не забывайте, что
мнемоническое обозначение SHL и SAL транслируются в одну и ту же
машинную команду и не без причины, не так ли?)
Деление на степени двойки со сдвигами может быть выполнено с
помощью флага переноса, и оно ничуть не более сложно, чем умно-
жение. Например, для выполнения деления со знаком на 8 значения
в регистрах DX:AX можно использовать последовательность:
sar dx,1
rcr ax,1
sar dx,1
rcr ax,1
sar dx,1
rcr ax,1
Но, в отличие от операции умножения, использование сдвигов
для более быстрого деления или нахождения остатков от деления на
произвольные величины, такие как 3 или 10, а не на степени двой-
ки на удивление хлопотно. Если вы решите покорпеть над написани-
ем программы быстрого деления на 10, в которой используется ме-
тод, аналогичный приведенному выше методу умножения на 10, то
вскоре обнаружите, что полученная программа - длинная, работает
медленно, и, более того, - вы уже сделали 90% работы, необходи-
мой для составления обобщенной программы деления, использующей
сдвиги и вычитания. Обычно целесообразнее вместо этого обдумать
всю ситуацию заново и преобразовать алгоритм или структуру дан-
ных, так чтобы избежать деления на "неудобные" числа.
Прежде чем оставить эту тему и двигаться дальше, я должен
упомянуть одну изящную оптимизацию, авторство которой приписыва-
ют Марку Збиковскому, одному из авторов версий 2.x и 3.x системы
MS-DOS. Приведенный ниже фрагмент делит без знаковое значение в
регистре AX на 512:
shr ax,1
xchg ah,al
cbw
Теперь, когда вы увидели этот нетривиальный прием, у вас на-
верняка возникло множество идей о том, как организовать умноже-
ние или деление без знаковых чисел на относительно большие сте-
пени двойки: 256, 512 и так далее, при помощи последовательнос-
тей команд XCHG или MOV.
5. Оптимизация переходов и вызовов подпрограмм.
Макаронные программы, изобилующие ветвлениями и переходами во
всех направлениях, нежелательны во всех смыслах, а при работе с
процессорами серий 80x86 и 80x88 - особенно. Можете считать это
утверждение напутствием, цель которого - побудить программистов
на ассемблере и тех, кто занимается оптимизацией компиляторов,
должным образом структурировать программы. Тут есть свои пробле-
мы, но прежде, чем обсуждать оптимизацию переходов и вызовов,
давайте обсудим некоторые особенности процессоров фирмы Intel.
Быстродействие этих процессоров в значительной мере определя-
ется их архитектурой, основанной на простой конвейерной схеме,
содержащей три компоненты: шинный интерфейс (BIU - Bus Interface
Unit), очередь упреждающей выборки и исполнительный модуль (EU -
Execution Unit). Когда шина памяти находится в нерабочем состоя-
нии (например, при выполнении команды из многих циклов, операнды
которой находятся в регистрах), шинный интерфейс извлекает байты
команд из памяти и помещает их в очередь упреждающей выборки,
последовательно продвигаясь дальше от текущего положения команд-
ного счетчика центрального процессора. Когда исполнительный мо-
дуль завершает выполнение очередной команды, он в первую очередь
ищет следующую команду в очереди упреждающей выборки: если она
там действительно имеется, то к ее расшифровке можно приступать
сразу же, не обращаясь лишний раз к памяти.
Как же при такой реализации конвейерной обработки происходят
переходы и вызовы подпрограмм? Всякий раз, когда исполнительный
модуль расшифровывает команду перехода или вызова, он аннулирует
текущее содержимое очереди упреждающей выборки и устанавливает
новое содержимое счетчика команд. После этого шинный интерфейс
должен снова выбирать байты команд, теперь уже начиная с нового
адреса, и заносить их в очередь. Исполнительный модуль в это
время вынужден "простаивать" до тех пор, пока не будет восста-
новлена полная команда. Кроме того, все обращения к памяти, ко-
торые требуются для исполнения команды перехода по новому адре-
су, также оказывают влияние на выборку следующих команд из памя-
ти. Может пройти немалое время, прежде чем шина снова заполнит
очередь упреждающей выборки, так, чтобы исполнительный модуль
мог работать с максимальной скоростью. Ситуацию усложняет то,
что размер очереди командных байтов разный для разных моделей
центральных процессоров. Он составляет всего 4 байта в ранних
моделях и 32 байта в компьютерах последних моделей. Это один из
факторов, делающий крайне сложным предсказание времен исполнения
для конкретных последовательностей команд исходя из количества
тактов и длин в байтах. Кроме того, состояние очереди команд для
различных типов центральных процессоров зависит и от "выравнива-
ния" команд. Шинный интерфейс должен выбирать команды в соот-
ветствии с разрядностью адресной и информационной частей шины.
Поэтому производительность очереди команд может существенно
ухудшиться из-за неудачных адресов вызовов или переходов. Напри-
мер, в процессоре 8086 с 16-разрядной шиной памяти выборка из
памяти всегда происходит по 16 битов за один раз, так что если
команда, на которую передается управление пре переходе или вызо-
ве подпрограммы начинается с нечетного адреса, половина первого
обращения к памяти пропадает впустую.
Все это подталкивает нас к осознанию первого правила оптими-
зации переходов и вызовов: проверьте, что их точки назначения
попадают в подходящие границы адресов для того типа процессора,
на котором ваша программа будет исполняться чаще всего. Сделайте
это, добавив подходящий атрибут выравнивания (WORD или DWORD) в
объявления сегментов и вставив директиву ALIGN перед каждой мет-
кой. Процессоры 8088 и 80188 имеют 8-разрядную внешнюю шину, так
что они абсолютно нечувствительны к выравниванию. Если потенци-
альными потребителями вашей программы являются пользователи
компьютеров на процессорах 8088 или 80188, к выравниванию прибе-
гать не стоит, поскольку оно лишь потребует дополнительной памя-
ти, но не увеличит производительность.
В то же время, если программе предстоит работать главным об-
разом на компьютерах с процессорами 8086, 80186 или 80286, сле-
дует произвести выравнивание в границах WORD, а если она рассчи-
тана на процессоры 80386 или 80486 - используйте выравнивание в
границах DWORD. (Для процессора 80486, в котором есть внутренняя
кэш-память, лучше, когда позиции лежат на 16-байтовых границах,
но тратить в среднем по 8 лишних байт на каждую метку мне кажет-
ся непозволительной роскошью.)
Следующее эмпирическое правило, относящееся к переходам и вы-
зовам, очень простое: избавляться от них везде, где только мож-
но. По крайней мере в частях программы, где быстродействие опре-
деляется лишь в основном процессором. Для этого организуйте
программу так, чтобы она исполнялась прямым, последовательным
образом, с минимальным числом точек принятия решения. В резуль-
тате очередь команд будет почти всегда заполнена, а вашу прог-
рамму будет легче читать, сопровождать и отлаживать. После того,
как вы улучшили программу насколько возможно за счет структури-
рования, следует решить, надо ли двигаться дальше, и постараться
увеличить производительность введением в программу "плохой
структуры", например преобразовав переходы к общим точкам выхода
из подпрограмм в множественные выходы. В крайних случаях корот-
кие подпрограммы можно преобразовать в макрокоманды, тогда ко-
манды процессора будут исполняться последовательно и дополни-
тельных затрат времени на передачу и возврат управления не бу-
дет.
Если в программе требуется условный переход, проанализируйте
точку принятия решения и организуйте программу так, чтобы веро-
ятность перехода была ниже, чем его отсутствия. Таким образом вы
уменьшите количество сбросов очереди команд. Например, если
программа производит проверку знака переменной, которая может
быть отрицательной только в редких случаях, при особых обстоя-
тельствах, то сделайте так, чтобы ваша программа "проскакивала"
через точку разветвления при положительном значении переменной:
cmp Balance,0
jl Lab1
Аналогично, если разные значения некой переменной инициируют
разные действия и вам требуется произвести множественные, за ко-
торыми следуют условные переходы, то попытайтесь переместить
сравнения с наиболее вероятным значением ближе к началу цепочки:
cmp ax,High
jne Lab1
...
jmp Lab3
Lab1: cmp ax,Medium
jne Lab2
...
jmp Lab3
Lab2: cmp ax,Low
jne Lab3
...
Lab3: ...
Если требуется произвести сравнения с многими значениями,
разбросанными по диапазону с большими разрывами, реализовать
множественные сравнения можно по принципу бинарного дерева, сна-
чала сделав рассечение всего диапазона значений каким-то одним
значением из середины всего диапазона, а затем проверяя, в каком
отношении к этому значению находится контролируемая переменная
(больше, меньше, равно), затем (если переменная больше или мень-
ше параметра сравнения) деля оставшийся интервал другим значени-
ем, и так далее. Такая стратегия чрезвычайно эффективна, если
значения распределены более или менее однородно и редко. Если же
они распределены плотно, то часто наилучшим решением является
использование "таблицы переходов". Например, представьте себе,
что в переменной AL находится ASCII-символ и есть набор подпрог-
рамм, запускаемых при некоторых определенных символах. Сначала
мы составим таблицу адресов подпрограмм в позициях, соответству-
ющих численным значениям ASCII-кодов символов, а затем реализуем
разветвления через таблицу следующим образом:
Table dw Routine_00
dw Routine_01
...
dw Routine_FE
dw Routine_FF
...
mov bl,al
xor bh,bh
shl bx,1
jmp Table[bx]
Есть еще две методики оптимизации, связанные с переходами и
вызовами, которые требуют внесения определенной степени "дест-
руктурированности" во всем остальном верную программу и называ-
ются "сращиванием хвостов" и "устранением рекурсивных хвостов".
Каждая из них подразумевает преобразование вызовов в переходы:
вызовы по самой своей природе требуют большего времени, чем пе-
реходы, поскольку помещают в стек адрес возврата и в результате
требуют больше обращений к памяти. Сращивание хвостов - это
просто преобразование команды CALL, непосредственно за которой
следует команда RET, в команду 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 и RET. Если
программа PROC2 физически (в памяти) следует за программой
PROC1, то можно обойтись даже без команды JMP PROC2, и за выпол-
нением PROC1 может сразу же следовать PROC2.
Устранение рекурсивных хвостов очень похоже на сращивание
хвостов. Когда программа последовательно вызывает сама себя и
этот вызов расположен непосредственно перед последней командой
RET в программе, вызов может быть преобразован в переход, что и
увеличит скорость, и уменьшит необходимый объем памяти в стеке.
Например, программа:
Proc1 proc near
...
cmp ax,MyVar
je Exit
call Proc1
Exit: ret
Proc1 endp
может быть преобразована в:
Proc1 proc near
...
cmp ax,MyVar
jne Proc1
ret
Proc1 endp
Такая рекурсивная программа часто может быть еще оптимизиро-
вана за счет преобразования рекурсии в цикл.
6. Оптимизация циклов.
Литература о компиляторах переполнена обсуждением методов оп-
тимизации циклов, которым присваивают самые экзотические назва-
ния: "разгрузка циклов", "вывод инвариантов за циклы", "устране-
ние индуктивных переменных", сращивание циклов", "разматывание
циклов" и тому подобное. На самом деле все перечисленные методы
можно свести к двум простым эмпирическим правилам:
- Никогда не делайте в цикле ничего такого, что можно сделать
за его пределами.
- Везде, где это возможно, избавляйтесь от передач управления
внутри циклов.
Первое из правил следует из старинной истины, гласящей, что
90% времени исполнения программы приходится на 10% ее кода. Если
вы попытаетесь найти роковые 10%, скорее всего окажется, что это
циклы того или иного рода. Поэтому первое, что следует сделать,
когда вы пытаетесь ускорить выполнение программы, - это найти в
ней "горячие точки" и проверить все циклы в них в качестве по-
тенциальных объектов оптимизации. Цикл отнюдь не всегда предс-
тавляет собой изящную конструкцию, завершающуюся командами LOOP,
LOOPZ или LOOPNZ (в особенности, разумеется, если программу пи-
сали не вы, а кто-то другой); часто это просто серия команд, ис-
полнение которых повторяется в зависимости от значения некоторой
управляющей переменной или флажка.
Циклы можно подразделить на две категории: к первой относятся
циклы, время исполнения которых определяется какими-то внешними
механизмами синхронизации, ко второй - те, в которых работает
только процессор. В качестве примера цикла первой разновидности
можно привести, скажем, такой, в котором набор символов переда-
ется на параллельный порт. Скорость исполнения программы ни при
каких обстоятельствах не будет превышать темпа приема байтов па-
раллельным портом, а быстродействие этого порта по крайней мере
на два порядка ниже, чем время исполнения любой приемлемой кодо-
вой последовательности управления портом. Вы, конечно, можете
ради собственного удовольствия заняться оптимизацией подобных
циклов с внешней синхронизацией, но для дела лучше поискать точ-
ку приложения сил в другом месте. Такой точкой вполне могут
стать циклы второй категории - свободные от взаимодействия с
"внешним миром".
Для полной оптимизации циклов необходим методический подход к
проблеме. Прежде всего тщательно проверьте каждый из циклов с
целью отыскания операций, которые никак не связаны с переменной
цикла, и разгрузите цикл от этих вычислений (в большинстве слу-
чает соответствующие команды удается разместить перед циклом).
Проанализируйте оставшиеся коды и по возможности упростите их,
применяя просмотр управляющих таблиц, ориентированных на конк-
ретную модель процессора команды, отказ от универсальности и лю-
бые другие известные вам приемы, которые позволяют сократить ко-
довые последовательности и избавиться от "дорогостоящих" команд.
Если в каких-то вычислениях используется текущее значение пере-
менной цикла, попытайтесь вывернуть ситуацию на изнанку, рассчи-
тывая нужные величины из начального и конечного значений пере-
менной цикла, т.е. без перебора.
В качестве примера рассмотрим не слишком удачную программу,
которая суммирует все кратные 5 элементы массива со словной точ-
ностью и оставляет результат в регистре AX:
Items equ 100
Array dw Items dup(?)
xor cx,cx
xor ax,ax
Lab1: mov bx,cx
add bx,bx
add bx,bx
add bx,bx
add bx,bx
add ax,Array[bx]
inc cx
cmp cx,Items/5
jne Lab1
Упростив этот цикл, мы получим:
Items equ 100
Array dw Items dup(?)
xor ax,ax
mov bx,offset Array
Lab1: add ax,[bx]
add bx,10
cmp bx,offset Array + Items/5
jb Lab1
После того как вы оптимизировали содержимое цикла насколько
это было возможно, стоит посмотреть, не удастся ли где-то изба-
виться от управляющих циклом операций перехода или вызова подп-
рограмм. Идея здесь та же, что и при оптимизации переходов и вы-
зовов, которые мы обсуждали в предыдущей главе. Суть дела в том,
что в микропроцессорах серий 80x86 и 80x88 фирмы Intel интенсив-
но используется простая конвейерная система, состоящая из шинно-
го интерфейса, очереди упреждающей выборки, в которую поступают
ждущие исполнения и извлекаемые из памяти команды, и исполни-
тельного устройства, получающего информацию из очереди для деко-
дирования и исполнения. При обнаружении перехода или вызова
подпрограммы очередь очищается и все циклы памяти, которые пот-
ребовались для заполнения позиций в ней после команды передачи
управления, пропадают зря. При этом исполнительное устройство
должно ожидать, пока шинный интерфейс извлечет и передаст в оче-
редь новые команды из новых адресов. Так что переходы и вызовы
подпрограмм обходятся гораздо "дороже", чем может показаться,
если просто подсчитать нужное для них число тактов, руководству-
ясь документацией фирмы Intel.
Один из способов избавиться от сравнений и условных переходов
называется объединением, или сращиванием циклов. При этом коды
реорганизуются так, чтобы сделать один цикл из нескольких повто-
ряющихся одинаковое число раз. Например, из двух циклов вида:
mov cx,100
Lab1: xor ax,ax
...
loop Lab1
mov cx,100
Lab2: xor bx,bx
...
loop Lab2
часто можно сделать один:
mov cx,100
Lab1: xor ax,ax
...
xor bx,bx
...
loop Lab1
Другой способ избавиться от циклов - "размотать" их, т.е.
устранить управляющие циклом кодовые последовательности, просто
повторив содержимое цикла нужное число раз. Это дает особенно
хорошие результаты в тех случаях, когда время, необходимое для
исполнения содержимого цикла, оказывается меньше, чем время вы-
полнения операций, управляющих циклом. Например цикл:
mov cx,3
Lab1: mov ax,[bx]
add bx,2
loop Lab1
можно переписать так:
add ax,[bx]
add bx,2
add ax,[bx]
add bx,2
add ax,[bx]
или даже так:
add ax,[bx+0]
add ax,[bx+2]
add ax,[bx+4]
"Разматывание" циклов - классический пример повышения быстро-
действия за счет объема необходимой памяти. Каждый раз, когда вы
решаете, стоит ли прибегнуть к данному приему, следует посмот-
реть, насколько это оправдано с точки зрения длины цикла и числа
его повторений с учетом доступных для вашей программы вычисли-
тельных ресурсов. Иногда "разматывание" удается применить в са-
мых неожиданных точках программы. К примеру, те из нас, кому до-
водилось составлять программы на языке ассемблера для процессо-
ров 80x86 или 80x88, научились распознавать ситуации, в которых
можно использовать специальные команды обработки символьных пос-
ледовательностей. Достаточно часто мы включали в свои программы
примерно такие коды:
mov cx,3
mov si,offset String1
mov di,offset String2
rep movsw
В приведенной последовательности имеется цикл, хотя и неяв-
ный. При обработке префикса REP требуется определенное время на
установку начальных параметров, а результат исполнения REP в
точности таков же, как если бы мы написали:
Lab1: movsw
loop Lab1
При работе на некоторых процессорах фирмы Intel и при неболь-
шом числе итераций часто оказывается лучше не пользоваться пре-
фиксом REP, а написать команды обработки строк подряд:
movsw
movsw
movsw
Но это один из случаев, когда требуется выяснить, насколько
хорош будет тот или иной вариант в условиях вашей конкретной
программы. Время исполнения любого из вышеприведенных фрагментов
невозможно точно определить, подсчитывая такты и байты команд,
так как это время зависит еще и от программного контекста, а
также аппаратных характеристик системы: разрядности шины памяти,
глубины упреждающей очереди команд, наличия (или отсутствия) и
объема кэш-памяти процессора и так далее.
¦ Если из цикла производится обращение к внешним устройствам, ¦
¦ заниматься его оптимизацией можно только для забавы. ¦
7. Управляющие таблицы.
Мы уже отмечали, что почти всегда бывает целесообразно пере-
нести вычисления из цикла за его пределы (или из "глубоко" вло-
женного цикла во внешний цикл), а также отсрочить вычисления до
тех пор, пока их результаты реально не потребуются. Еще более
эффективный вариант оптимизации состоит в том, чтобы приурочить
вычисления не ко времени исполнения программы, а к моменту ее
компиляции или ассемблирования, либо выполнять вычисления с по-
мощью специализированной программы, сохранять результаты в про-
межуточном файле и извлекать их оттуда по мере необходимости.
Особенно удобная категория оптимизации этого типа называется
просмотром управляющих таблиц.
Рассмотрим прикладную систему, в которой будет особенно целе-
сообразно использовать управляющие таблицы. Представьте себе
программу, в которой требуется поворачивать и перемещать отрезки
линий, чтобы создавать у пользователя иллюзию объемного изобра-
жения. Такая программа, естественно, должна определять синусы и
косинусы углов. Для вычисления этих функций обычно применяют
числа с плавающей точкой и разложение в ряды, расчет которых
влечет за собой многократные умножения и деления, а эти операции
с точки зрения времени счета "стоят" недешево. Кроме того, полу-
чаемые таким способом величины имеют значительно более высокую
точность, чем это реально требуется для обычных графических
адаптеров персональных компьютеров: даже числа с плавающей точ-
кой одинарной точности (32 разряда) вычисляются до 8 десятичных
знаков, из которых нужны только 4 или 5 (разрешение графики в
лучшем случае 1024x768 элементов изображения).
Именно здесь и можно воспользоваться преимуществами таблицы,
в которую можно занести синусы углов с шагом в 1 градус и с точ-
ностью до 4 десятичных знаков.
Прежде всего образуем структуру данных, в которой номер каж-
дого элемента будет соответствовать углу в градусах, а значение
- синусу этого угла, умноженному на 10.000:
Table label word
dw 0
dw 175
dw 349
...
Подготовив такую таблицу, мы без особых затруднений можем
составить небольшую подпрограмму, которая будет принимать значе-
ние угла в диапазоне от 0 до 359 градусов в регистре AX, а в от-
вет выдавать в вызывающую программу значение синуса этого угла в
том же регистре:
Sine proc near
push bx
mov bx,ax
add bx,bx
mov ax,Table[bx]
pop bx
ret
Sine endp
Для дополнительного ускорения работы своей программы мы можем
преобразовать подпрограмму в макроопределение, чтобы коды встав-
лялись в программу везде, где это потребуется. На рис. 1 показа-
ны более общая форма данной процедуры и соответствующая процеду-
ра расчета косинуса.
Рис. 1. Исходный текст модуля, содержащего подпрограммы для це-
лочисленного вычисления синуса и косинуса. В подпрог-
раммах используется просмотр управляющих таблиц и три-
виальные тригонометрические тождества для расчета три-
гонометрических функций углов в интервале от 0 до 359
градусов.
----------------------------------------------------------------
;
; ITRIG.ASM - целочисленные тригонометрические функции.
; (C) Copyright 1991 Ray Duncan
;
title ITRIG - Integer Trig Lookup
name ITRIG
model small,c
dataseg
Table label word
dw 0, 175, 349, 523, 698
dw 872, 1045, 1219, 1392, 1564
dw 1736, 1908, 2079, 2250, 2419
dw 2588, 2756, 2924, 3090, 3256
dw 3420, 3584, 3746, 3907, 4067
dw 4226, 4384, 4540, 4695, 4848
dw 5000, 5150, 5299, 5446, 5592
dw 5736, 5878, 6018, 6157, 6293
dw 6428, 6561, 6691, 6820, 6947
dw 7071, 7193, 7314, 7431, 7547
dw 7660, 7771, 7880, 7986, 8090
dw 8192, 8290, 8387, 8480, 8572
dw 8660, 8746, 8829, 8910, 8988
dw 9063, 9135, 9205, 9272, 9336
dw 9397, 9456, 9511, 9563, 9613
dw 9659, 9703, 9744, 9781, 9816
dw 9848, 9877, 9903, 9925, 9945
dw 9962, 9976, 9986, 9994, 9998
dw 10000
codeseg
public Cosine
public Sine
;
; TRIG - рабочая подпрограмма для функций SIN и COS.
;
; Входные данные:
; AX - угол в градусах от 0 до 180.
; Выходные данные:
; AX - значение функции.
; Используемые данные:
; BX - промежуточные расчеты.
;
Trig proc near
mov bx,ax
cmp bx,90
jle @@1
sub bx,180
neg bx
@@1: sal bx,1
mov ax,Table[bx]
ret
Trig endp
;
; COSINE - вычисление косинуса угла.
;
; Входные данные:
; AX - угол в градусах от 0 до 360.
; Выходные данные:
; AX - косинус угла умноженный на 10.000.
; Используемые данные:
; ничего
;
Cosine proc near
add ax,90
Cosine endp
;
; SINE - вычисление синуса угла.
;
; Входные данные:
; AX - угол в градусах от 0 до 360.
; Выходные данные:
; AX - синус угла умноженный на 10.000.
; Используемые данные:
; ничего
;
Sine proc near
push bx dx
cwd
mov bx,360
idiv bx
mov ax,dx
or ax,ax
jns @@1
add ax,360
@@1: cmp ax,180
jle @@2
sub ax,180
call Trig
neg ax
jmp short @@3
@@2: call Trig
@@3: pop dx bx
ret
Sine endp
end
----------------------------------------------------------------
Иногда управляющие таблицы можно весьма эффективно использо-
вать в ситуациях, где мысль о них просто не приходит в голову.
Пусть, например, вам поручено составить подпрограмму, которая
будет подсчитывать число ненулевых разрядов в байте. Первое по-
буждение обычно состоит в том, чтобы составить цикл со сдвигами
и действительно подсчитать ненулевые разряды. Но ведь значитель-
но быстрее будет воспользоваться таблицей, позиции в которой бу-
дут соответствовать значениям байта - от 0 до 255, а значения в
этих позициях - числу ненулевых разрядов для каждого из таких
значений байта:
Table label byte
db 0
db 1
db 1
db 2
...
Bits proc near
push bx
mov bl,al
xor bh,bh
mov ax,Table[bx]
pop bx
ret
Bits endp
И снова, чтобы еще более повысить быстродействие, можно офор-
мить эту подпрограмму как макроопределение и встраивать в прог-
рамму везде, где требуется. Для байтовых таблиц можно еще повы-
сить производительность, замещая команды MOV на специальные ко-
манды XLAT. Вместе с тем здесь необходимо подчеркнуть, что таким
образом можно будет обрабатывать не только байтовые таблицы. Мне
довелось познакомиться с великолепной программой подсчета слов
(ее автор Терье Матисен), в которой использовалась таблица из 64
Кбайт для просмотра всех двусимвольных комбинаций в поиске раз-
делителей слов. Утверждается также, что Гордон Летуин применил
аналогичную методику для сканирования битовой карты свободного
пространства на диске в подсистеме обработки файлов HPFS опера-
ционной системы OS/2.
8. Оптимизация для конкретных моделей процессоров.
Если ваша программа будет работать на компьютерах с конкрет-
ным моделями процессоров или вы считаете, что есть смысл подго-
товить несколько версий программы для работы на разных машинах,
можно попытаться воспользоваться ориентированными на определен-
ные модели процессоров командами.
По сравнению с процессорами 8086 и 8088, набор команд процес-
соров 80186, 80188 и 80286 ощутимо дополнен. Многие из новых ко-
манд позволяют повысить производительность программы:
- Линейные и циклические сдвиги с непосредственным аргумен-
том, отличным от единицы.
- Команда PUSH с непосредственным операндом.
- Команды ввода и вывода символьных строк.
- Команды обмена со стеком содержимым всех регистров - PUSHA
и POPA.
- Команды ENTER и LEAVE для выделения и освобождения кадра
стека.
- Команды проверки соблюдения границ массива BOUND.
- Команды умножения числа на непосредственный операнд.
Если ваша программа будет исполняться только на компьютерах с
процессорами 80186, 80286, 80386 или 80486, можно также выров-
нять по границе слов все элементы данных и целевые адреса для
команд передачи управления. Таким образом можно повысить произ-
водительность на несколько процентов за счет относительно не-
большого объема памяти. (При работе на процессорах 8086 выравни-
вание по границам слов также дает определенный выигрыш, но для
процессоров 80188 и 80188 - с 8-разрядной шиной - это бессмыс-
ленно.)
Составляя программу для процессоров 80386 и 80486 и их разно-
видностей, можно повысить производительность 16-разрядной прог-
раммы, пользуясь всеми вышеперечисленными командами для процес-
соров 80188, 80188 и 80286 и, кроме того, выравнивания данные и
адреса передачи управления по границам 32-разрядных слов, а так-
же с помощью следующих дополнительных особенностей:
- 32-разрядных регистров (но пользоваться ими следует с осто-
рожностью, так как их содержимое не сохраняется при работе
с некоторыми эмуляторами системы DOS, например модулем сов-
местимости с DOS системы OS/2 версий до 1.3).
- Команд пересылки с распространением нуля или знакового бита
(MOVZX или MOVSX).
- 64-разрядных сдвигов (в сдвоенных регистрах) - команды SHLD
и SHRD.
- Установки в байте значений "истина" или "ложь" в зависимос-
ти от содержимого флажков центрального процессора, что поз-
воляет избавиться от команд условного перехода (SETZ, SETC
и так далее).
- Команд проверки, установки, сброса, инвертирования и прос-
мотра битов (BT, BTC, BTR, BTS, BSF и BSR).
- Обобщенной индексной адресации и режимов адресации с масш-
табированием индексов.
- Быстрого умножения при помощи команды LEA с использованием
масштабированной индексной адресации.
- "Дальних" условных переходов.
- Перемножения 32-разрядных чисел и деления 64-разрядного
числа на 32-разрядное.
- Дополнительных сегментных регистров (FS и GS).
- Команд загрузки сегментных регистров SS, FS и GS (LSS, LFS
и LGS).
Естественно, выжать максимум из архитектуры 80386 или 80486
можно при помощи расширителей DOS или системы OS/2 2.0, переводя
вашу программу в 32-разрядный защищенный режим. В результате вы
получите доступ ко всем 32-разрядным регистрам, расширенной ад-
ресации и к адресному пространству до 4 Гбайт.
В процессоре 80486 предусмотрено всего три дополнительных ко-
манды, которых нет у процессора 80386 и к которым можно обра-
щаться из прикладной программы:
- Изменение порядка расположения четырех байтов в 32-разряд-
ном слове на противоположный (BSWAP).
- Сравнение и обмен (CMPXCHG).
- Обмен и сложение (XADD).
Вместе с тем длительность команд, выраженная в числе тактов,
у процессоров 80486 совсем не такая, как у процессоров 80286 и
80386. В общем, можно сказать, что время исполнения простейших
команд было сокращено за счет более сложных. Это означает, что
программа, первоначально составленная для процессора 8086 или
8088, возможно, будет работать быстрее на процессоре 80486, чем
ее аналог, в исходном варианте предназначавшийся для процессоров
80286 и 80386. Такова жизнь. И, еще кое-что, о чем стоит поду-
мать, работая с процессорами 80486: встроенная кэш-память объ-
емом 8 Кбайт, которая работает лучше всего, если информация вы-
ровнена по границам параграфов, а также встроенный математичес-
кий сопроцессор. К сожалению, недавний выпуск фирмой Intel про-
цессоров 80486SX без математического сопроцессора означает, что
гарантированной возможности работать с числами с плавающей точ-
кой на самых высокопроизводительных моделях компьютеров у нас
по-прежнему нет.