Оптимизация программ на ассемблере.
Часть 1
Несмотря на все более широкое распространение языков программирования и интегрированных сред программирования, оптимизация программ на ассемблере остается актуальной темой дискуссий для программистов. Можно упомянуть, например, форум програамистов, проведенный сетью PC MagNet, который стал ареной многочисленых "дуэлей": то один, то другой участник предлагал всем желающим решить небольшую, но интересную задачу программирования - и рассматривал присылаемые решения, ожидая, кто жее и как решит задачу наименьшей кровью, то есть затратив минимум байтов на программу. Подобно этому проведенная сетью BIX конференция по языку ассемблера для процессора 8088 стала трибуной немалого числа основательных рассуждений по поводу неочевидных аспектов оптимизации ассемблерных программ.
Несмотря на самый общий и широкий интерес к проблеме, литература по оптимизации ассемблерных программ для процессора Intel 80x86 на удивление скудна. Пару лет назад, готовясь к докладу по развитию программного обеспечения, я просмотрел оглавления всех основных журналов по программированию и обнаружил лишь горстку статей на эту тему. С другой стороны, литература по оптимизации программ для компиляторов высокого уровня весьма обширна, и многие концепции, развитые в ней, будут полезны и при программировании на языке ассемблера. Так что говорить, что литературы совсем нет, было бы несправедливо. Ниже мы сначала рассмотрим общие методики оптимизации, а затем обсудим более серьезный вопрос - когда и что стоит оптимизировать.
Оптимизация по быстродействию
Если вы пришли к выводу, что ваша программа работает недостаточно быстро, первое, что надо сделать, - это убедиться, что вы решаете задачу, пользуясь наилучшими алгоритмами и представлениями данных. Замена примитивного или неадекватного алгоритма более подходящим может ускорить выполнение вашей программы на порядок и более. Так что если вы проведете несколько дней, штудируя Кнута или Седжуика (в надежде подобрать алгоритм, до которого вряд ли додумались бы сами), - будьте уверены: вы сделали выгодное вложение своего драгоценного времени. Аналогично переход от "очевидной", но простой структуры данных (такой, как связный список) к более сложной (например, бинарному дереву) может дать такие результаты, которые с лихвой окупят ваши усилия по усовершенствованию программы.
Если вы уверены, что выбрали наилучшие алгоритмы и структуры данных, следующее, на что следует обратить внимание, - это использование программой данных, хранимых в памяти. Даже самые быстрые устройства работы с дисками, используемые в персональных компьютерах, работают несравнимо медленнее, чем такие мощные вычислители, как процессоры 80386 или 80486, так что постарайтесь свести обращения к диску до возможного минимума. Ознакомьтесь со всеми имеющимися типами памяти, доступными программе DOS, - расширяемой и отображаемой памятью, старшими блоками памяти и так далее - и полностью используйте возможности оперативной памяти для хранения в ней данных, с которыми работает ваша программа, чтобы время обращения к ним было минимальным. Полезно также ознакомиться с техникой уплотнения данных, поскольку почти во всех случаях быстрее оказывается сначала уплотнить, а затем распаковать данные, когда в них возникает необходимость, чем по нескольку раз считывать неуплотненную информацию с диска.
Еще одной темой, заслуживающей обсуждения, является уменьшение объема вычислений в программе. Составители компиляторов пользуются забавными терминами - устранение общих подвыражений, сворачивание констант, распространение констант - для того, чтобы, по сути, сказать одно и то же: во время работы программы одно и то же значение ни в коем случае не должно вычисляться дважды. Вместо этого программа должна рассчитать каждое значение лишь один раз и сохранить его для повторного использования. Еще лучше преносить вычисления со стадии исполнения на стадию ассемблирования всякий раз, когда это позволяют ограниченные математические "способности" MASM (или TASM, или OPTASM). Совершенно аналогично вам, возможно, удастся существенно повысить быстродействие программы, преобразовав вычисления в обращения к таблицам, котрые заранее генерируются и сохраняются отдельной программой.
Если вы сделали все возможное на абстрактном уровне по всем названным направлениям, пора спуситься на грешную землю. Осталось немногое - "отжать из программных кодов всю воду" и "прочистить все циклы", особенно, если программа существенно использует работу с дисплеем и выводит на экран графику. Вот некотрые из самых общих процедур этой категории.
- Замещенин универсальных инструкций на учитывающие конкретную ситуацию, например, замена умножения на степень двойки на команды сдвига (отказ от универсальности).
- Уменьшение количества передач управления в программе: за счет преобразования подпрограмм в макрокоманды для непосредственного включения в машинный код; за счет преобразования условных переходов так, чтобы условие перехода оказывалось истинным значительно реже, чем условие для его отсутствия; перемещение условий общего характера к началу разветвленной последовательности переходов; преобразование вызовов, сразу за которыми следует возврат в программу, в переходы ("сращивание хвостов" и "устранение рекурсивных хвостов") и т.д.
- Оптимизация циклов, в том числе перемещение вычислений неизменяющихся величин за пределы циклов, разворачивание циклов и "соединение" отдельных циклов, выполняемых одно и то же количество раз, в единый цикл ("сжатие цикла").
- максимальное использование всех доступных регистров за счет храниения в них рабочих значений всякий раз, когда это возможно, чтобы минимизировать число обращений к памяти, упаковка множественных значений или флагов в регистры и устранение излишних продвижений стека (особенно на входах и выходах подпрограмм).
- Использование специфических для данного процессора инструкций, например, инструкции засылки в стек непосредственного значения, которая имеется в процессоре 80286 и более поздних. Другие примеры - двухсловные строковые инструкции, команды перемножения 32-разрядных чисел, деление 64-разрядного на 32-разрядное число и умножение на непосредственное значение, которые реализованы в процессорах 80386 и 80486. Ваша программа должна, разумеется, вначале определить, с каким типом процессора она работает! Для этого может быть полезна программа, приведенная на рис. 1 и выдающая код, характеризующий тип ЦП. [Содержится в файле ASM_OPT1.ASM - Прим. набивальщика]
В процессорах 80286 и более поздних вам, возможно, также удастся увеличить скорость исполнения программы на несколько процентов за счет выравнивания расположения данных и меток, на которые происходит передача управления, относительно некоторых границ. Процессоры 8088 и 80286 - 16-разрядные и им "удобнее" работать с данными, выровненными относительно 16-битовых границ (размер одного слова); процессор 80386 предпочитает выравнивание в 32 бита (два слова); из-за устройства его внутренней кэш-памяти процессору 80486 легче работать, если произведено выравнивание на параграф (16-байтовое).
Если же все остальное успеха не принесло, а вы пишете некую штучную программу, а не программный пакет, предназначенный для продажи на массовом рынке, проблему быстродействия, может быть, проще "решить" аппаратным путем. При существующих сегодня ценах [О, да!!! - Прим. набивальщика] часто оказывается намного выгоднее заказать новый, более мощный компьютер для работы с вашей специализированной программой, чем тратить время на мучения, связанные с переделкой программы, ее оптимизацией и последующей отладкой заново. К сожалению, безоглядное и некритическое принятие этого подхода такими производителями программных изделий, как Microsoft и Lotus, привело к рождению громоздких монстров, подобных Windows 3.0, Programmer's Workbench и Lotus 1-2-3/G, - но это уже тема другого разговора.
Оптимизация по объему
Если работоспособность вашей программы ограничена ее размером, а не скоростью исполнения, то вам надо вновь подумать над стратегией оптимизации - на этот раз ухищрениями, в точности противоположными тем, что вы использовали для увеличения быстродействия. Тщательно изучите свою программу и определите, что создает основную проблему - размер кода или объем данных.
Если вам приходится работать с болшими блоками данных, то нужный эффект может дать их организация в нетривиальные структуры. Однако замена быстрообрабатываемых, но неплотных массивов и таблиц более компактными структурами типа связных списков или упаковка данных с использованием битовых полей, вероятно, даст не слишком большие преимущества. Примитивное уплотнение таблиц и их последующее, по необходимости, разуплотнение обычно не очень полезно, так как часто требуется разуплотнять все данные лишь для того, чтобы добраться до какого-то одного пункта, а программы уплотнения/разуплотнения сами по себе обычно занимают заметный объем памяти.
Большие просмотровые таблицы и массивы можно поместить в дисковый файл и при необходимости считывать в память малыми частями. Но это может нанести сокрушительный удар по производительности, если данные запрашиваются в случайном порядке. Часто можно вообще отказаться от просмотровых таблиц и производить вычисления значений переменных всякий раз, когда в последних возникает необходимость. Вы также должны искать и устранять константы и переменные, которые реально никогда не используются программой, поскольку вместо них она использует другие величины, вычисленные ранее в процессе разработки и отладки. Во всяком случае, я еще раз хочу подчеркнуть, что чрезвычайно важно усвоить, как пользоваться всеми видами памяти, доступными компьютеру, и сделать программу достаточно гибкой, чтобы она могла использовать все и каждую из них.
Оптимизация программы с целью уменьшения размера - это совсем не то же самое, что оптимизацмя для повышения быстродействия. Во-первых, вы должны просмотреть весь текст программы и устранить все предложения и процедуры, которые никогда не выполняются или недоступны ни из каой точки программы (мертвые коды). Если вы работаете с большой прикладной программой, над которой до вас уже потрудилось несколько программистов, вас, возможно, даже удивит, как много строк можно безболезненно удалить. Во-вторых, проанализируйте программу заново и соберите все идентичные или функционально сходные последовательности кода в подпрограммы, которые могут быть вызваны из любой точки программы. Чем более универсальными вам удастся сделать подпрограммы, тем более вероятно, что их код может быть использован повторно. Если вы будете последовательно придерживаться этого подхода, где только возможно, то получите очень компактную программу модульного типа, состоящую главным образом из вызовов подпрограмм.
Если вы сделали все, что я рекомендовал выше, а вам по-прежнему не хватает памяти, то попробуйте поискать удачи еще на нескольких путях. Вы можете перекомпоновать свою программу в относительно независимые модули, которые могут считываться в память, как оверлеи. Вы можете закодировать функционирование вашей программы в таблицах, "управляющих" ее исполнением. Вы можете прибегнуть к методике "прошитого" кода или псевдокода и представить логику вашей программы с использованием гораздо меньшего объема памяти за счет некторого снижения быстродействия. Можно, наконец, прибегнуть к тяжелой артиллерии современной компьютерной технологии и использовать стандартный интерпретатор или компилятор "малого языка", который, в свою очередь, будет виртуальной машиной для прикладной программы [Подобно Multi-Edit, в котором это набирается - Прим. набивальщика]. Quick Basic, Excel и BRIEF - самые привычные примеры применения соответственно стратегии прошитого кода, псевдокода и малого языка.
В конечном счете, если вы пришете специализированную прикладную программу, преодолеть проблемы памяти, возможно, - снова - удастся объединенным программно-аппаратным путем. Среди многих возможностей есть такие: использование более высоких версий операциооной системы, таких как DOS 5.0 или OS/2, для расширения объема рабочей памяти (в пределах первых 640 Кбайт); установка еще одной платы расширения памяти; пеерход к компьютерам на процессорах 80386 или 80486, котрые поддереживают большую память по сравнению с использовавшейся вами машиной на процессоре 8088 или 80286; и/или запуск вашей программы под управлением расширителя DOS.
А стоит ли оптимизировать?
Оптимизация кодов на любом языке всегда требует идти на компромиссы, среди которых такие, как:
- сокращение потребного объема памяти за счет снижения быстродействия;
- повышение быстродействия за счет ухудшения возможностей сопровождения и доступности текста программы для чтения;
- сокращение времени исполнения программы за счет увеличения времении ее разработки.
Все это кажется очевидным, но в большинстве реальных ситуаций принять решение не так просто, как кажется на первый взгляд. Классическим примером является выбор между двумя приведенными ниже инструкциями, каждая из которых может быть использована для перемещения некоторого значения из регистра DX в регистр AX (конечно, с различными побочными эффектам):
XCHG AX, DX
или
MOV AX, DX
В процессоре 8088 команда MOV занимает 2 байта и требует двух тактов ЦП, тогда как команда XCHG занимает 1 байт, но требует трех тактов. Пока все кажется ясным: надо выбирать между скоростью и памятью. Но реальное время исполнения команды существенно зависит от контекста, размера очереди команд ЦП, размера и характеристик кэш-памяти системы и так далее, тогда как даже число циклов, требуемых для выполнения инструкций, меняется от одной модели ЦП к другой. Как оказывается, практически невозможно предсказать скорость исполнения нетривиальной последовательности инструкций в процеессоре фирмы Intel, особенно в последних моделях 80386 и 80486, в которых интенсивно используется конвейерная обработка, - вам придется составлять различные возможные комбинации инструкций, запускать их и экспериментально определять время их исполнения.
Аналогично, баланс между временем исполнения программы и временем ее разработки и баланс между возможностями сопровождения и ее быстродействием редко бывают столь однозначны, как нам бы хотелось, а долговременные последствия возможных ошибочных решений могут быть весьма неприятными. Вообще же, занимаясь оптимизацией, важнее всего понимать, когда ее делать, а когда лучше оставить все как было. Процитируем Дональда Кнута: "Многие беды программирования проистекают от преждевременной оптимизации". Прежде чем думать о настройке своей программы, убедитесь, что она правильная и полная, что вы используете верный алгоритм для решения поставленной задачи и что вы составили самый ясный, самый прямой, самый структурированный код, который только был возможен.
Если программа удовлетворяет всем этим критериям, то, на самом деле, ее объем и скорость исполнения в болшинстве случаев будут вполне приемлемыми без каких-либо дальнейших усовершенствований. Одно только использование ассемблера само по себе приводит к увеличению скорости исполнения программы в два-три раза и примерно к такому же уменьшению размера по сравнению с аналогичной программой на языке высокого уровня. И еще: если что-то упрощает чтение программы и ее сопровождение, то обычно это же приводит к увеличению скорости исполнения - здесь можно назвать отказ от макаронных кодов со многими ненужными переходами и вызовами подпрограмм (которые являются тяжелой работой для процессора с архитектурой Intel 80x86, поскольку они сбрасывают очередь команд), а также предпочтение простых прямолинейных участков машинных команд аналогичным сложным.
Тем не менее, вашей наиглавнейшей заботой должны быть ощущения потенциального пользователя при работе с вашей программой: насколько производительной покажется программа ему? Прислушаемся к словам Майкла Эбраша: "Всякая оптимизация, ощущаемая пользователем, заслуживает того, чтобы ее сделать". И наоборот, если в массах пользователей о вашей программе складывается мнение, как о тупой и неуклюжей, то очень вероятно, что она не будет должным образом оценена. Примером может служить судьба пакета ToolBook. Следовательно, должно казаться, что ваша программа мгновенно откликается на действия пользователя даже тогда, когда она занята длительными вычислениями иил операциями с диском. Она должна поддерживать экран дисплея в "живом" состоянии, заполняя его чем-то вроде циферблатов, термометров, и позволять пользователю безопасно прерывть длительные операции в любое аремя, если его намерения изменились и он решил заняться чем-нибудь еще.
Если вы действительно вынуждены прибегнуть к шлифовке кода и циклов с помощью методов, о которых я говорил выше, то постарайтесь затратить свои время и силы на действия в правильном направлении. Помните о естественной иерархии временных масштабов: среди операций, перечисленных ниже, каждая следующая требует на порядок больше времени, чем предыдущая. Ита: это операции регистр/регистр, операции с памятью, операции с диском и операции взаимодействия с пользователем. Так что не тратьте силы на то, чтобы сократить несколько машинных циклов в программе, если скорость ее исполнения ограничена операциями с дисковыми файлами: вместо этого попытайтесь найти способы сократить число таких операций. А после того, как вы сделали что-то, что в принципе могло бы быть оптимизацией, проведите дотошную проверку полученных результатов и вообще - проверяйте, проверяйте, проверяйте.
В своей превосходной книге "Пишем эффективные программы" (Writing Efficient Programs - Prentice Hall, 1982) Джон Бентли рассказывает кошмарную историю из жизни фирмы Bell Labs - Историю, которую мы все и всегда должны помнить:
"В начале 60-х годов Виктор Высоцкий [Victor Vysotsky] работал над усовершенствованием компилятора Фортрана, причем в число исходных требований входило отсутствие сколько-нибудь заметного снижения времени компиляции. Одна из подпрограмм исполнялась редко (во время разработки Высоцкий оценил, что она должна вызываться примерно в одном проценте компиляций, причем в каждой лишь однажды), но работала крайне медленно. Поэтому Высоцкий затратил неделю на удаление из нее лишних циклов. Модифицированный компилятор работал достаточно быстро. После двух лет интенсивной эксплуатации компилятор выдал сообение о внутренней ошибке при компиляции одной программы. Когда Высоцкий исследовал компилятор, он обнаружил, что ошибка была в прологе "критической" подпрограммы и что эта ошибка содержалась в данной подпрограмме всегда, с самого начала производства".
Высоцкий совершил три принципиальных ошибки: он не провел полной анализ программы перед тем, как приступить к оптимизации, так что он напрасно тратил время на оптимизацию подпрограммы, не влияющей на быстродействие; он не смог сделать оптимизацию правильно; и он не провел испытаний оптимизированной подпрограммы, чтобы убедиться, что она работает согласно спецификации.
Я совсем не хочу тыкать пальцем в мистера Высоцкого: в своей жизни я совершил множество промахов куда как серьезнее, но (поскольку я не работаю в фирме Bell Labs) эти промахи, к счастью, не увековечены в книге Джона Бентли. Однако этот случай из жизни Высоцкого - хороший пример того, как время и энергия могут быть растрачены впустую на святое дело оптимизации и как рано или поздно проявляется отказ от методичного исполнения всех основных процедур профилирования и контроля в процессе оптимизации.
