Оптимизация программ на Assembler
Страница 2. Оптимизация по быстродействию

Оптимизация по быстродействию

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

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