Введение.

   Несмотря на все более широкое распространение языков программирования высокого уровня и интегрированных средств программирования,  оптимизация программ на ассемблере  остается  актуальной темой дискуссий программистов.  Можно упомянуть, например, форум программистов,  проведенный сетью 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) эти промахи, к счастью, не были
увековечены  в  книге Джона Бентли.  Однако этот случай из жизни
Высоцкого - хороший пример того,  как время и энергия могут быть
растрачены  в  пустую  на святое дело оптимизации и как рано или
поздно проявляется отказ от методичного исполнения всех основных
процедур профилирования и контроля в процессе оптимизации.

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