Ирина Козлова - Программирование
Кроме того, самой главной заботой должны быть ощущения потенциального пользователя при работе с данной программой: насколько производительной покажется программа ему? Если о полученной программе складывается мнение, как о неуклюжей, то есть вероятность, что она не будет должным образом оценена. Примером является судьба пакета ToolBook.
45. Отказ от универсальности
Для операции умножения и деления необходимы значительные усилия от почти любого центрального процессора, так как они должны быть осуществлены (аппаратно или программно) через сдвиги и сложения или сдвиги и вычитания соответственно. Традиционные 4-разрядные и 8-разрядные процессоры не имели машинных команд для умножения или деления, так что данные операции приходилось осуществлять при помощи длинных подпрограмм, где явно осуществляются сдвиги и сложения или вычитания. Первые 16-разрядные процессоры, среди которых 8086, 8088 и 68000, действительно дают возможность осуществить операции умножения и деления аппаратными средствами, но соответствующие процедуры были очень медленными: в процессорах 8086 и 8088, например, для деления 32-разрядного числа на 16-разрядное было необходимо около 150 тактов.
Поэтому небольшие хитрости для увеличения скорости или устранения операций умножения и деления были и остаются одними из первых приемов, которые рассматривает каждый программист, который стремится к совершенству. Большинство из данных хитростей относится к категории, которую именуют «отказ от универсальности». Это замена рассчитанных на общий случай команд умножения и деления (или вызов соответствующих подпрограмм) рядом сдвигов и сложений или вычитаний для конкретных операндов.
Рассмотрим одну из простых процедур оптимизации умножения. Для умножения числа на степень двойки его следует просто сдвинуть влево на необходимое число двоичных (битовых) позиций. Вот такой, например, имеет вид некоторая общая, но медленная последовательность команд для умножения значения переменной MyVar на 8:
mov ax,MyVar mov bx,8 mul bx
mov MyVar,ax
Применение отказа от универсальности при выполнении деления несколько более ограничено. Деление на степень двойки, безусловно, очень просто. Для этого следует сдвинуть число вправо, следя только за выбором соответствующей команды сдвига для желаемого типа деления (со знаком или без знака). Определение остатка от деления на степень двойки для чисел без знака еще проще. Для этого следует осуществить просто одну команду операции логического И над операндом и непосредственным значением, которое должно быть записано в виде уменьшенного на единицу значения делителя. Деление чисел со знаком не так просто, так как знак остатка от деления должен соответствовать знаку делителя и не зависит от знака делимого. Реализация данных операций потребует непременного присутствия условных переходов, а это уже плохо.
46. Оптимизация переходов и вызовов подпрограмм
Программы, которые изобилуют ветвлениями и переходами во всех направлениях, нежелательны во всех смыслах, а в случае работы с процессорами серий 80 х 86 и 80 х 88 – особенно. Это является напутствием, цель которого – побудить программистов на ассемблере и тех, кто оптимизирует компиляторы, должным образом структурировать программы. В этом случае существуют свои проблемы, но сначала рассмотрим некоторые особенности процессоров фирмы Intel.
Быстродействие данных процессоров в значительной мере зависит от их архитектуры, основанной на простой конвейерной схеме, которая содержит три компоненты: шинный интерфейс (BIU – Bus Interface Unit), очередь упреждающей выборки и исполнительный модуль (EU – Execution Unit). Если шина памяти в нерабочем состоянии, например в случае выполнения команды из многих циклов, с операндами, находящимися в регистрах, шинный интерфейс получает байты команд из памяти и располагает их в очередь упреждающей выборки, последовательно продвигаясь дальше от текущего расположения командного счетчика центрального процессора. Когда исполнительный модуль заканчивает выполнение очередной команды, он ищет следующую команду в ряде упреждающей выборки: если она есть, к ее расшифровке можно приступать непосредственно, не обращаясь лишний раз к памяти.
Каждый раз, когда исполнительный модуль уточняет команду перехода или вызова, он аннулирует теку46б щее содержимое очереди упреждающей выборки и определяет новый счетчик команд. Затем шинный интерфейс снова выбирает байты команд, начиная при этом с нового адреса, и заносит их в очередь. Исполнительный модуль в это время должен «простаивать», пока не будет определена полная команда. При этом все обращения к памяти, необходимые для исполнения команды перехода по новому адресу, тоже влияют на выборку следующих команд из памяти. Может пройти много времени, прежде чем шина опять заполнит очередь упреждающей выборки, так, чтобы применяемый модуль мог работать с наибольшей скоростью. Кроме того, размер очереди командных байтов не одинаков для разных моделей центральных процессоров. Он составляет только 4 байта в ранних моделях и 32 байта в современных компьютерах. Таким образом, крайне сложно предсказать время исполнения для данных последовательностей команд исходя из количества тактов и длин в байтах. Также состояние очереди команд для разных типов центральных процессоров определяется «выравниванием» команд. Шинный интерфейс обязан выбирать команды по разрядности адресной и информационной частей шины.
Исходя из всего вышесказанного, можно сформулировать первое правило оптимизации переходов и вызовов: необходимо проверить, что их точки назначения попадают в подходящие границы адресов для того типа процессора, на котором данная программа будет работать чаще всего. При этом следует добавить подходящий атрибут выравнивания (WORD или DWORD) в объявления сегментов, а также вставить директиву ALIGN перед каждой меткой.
47. Оптимизация циклов
Существует большое число методов оптимизации циклов с самыми экзотическими названиями: «разгрузка циклов», «вывод инвариантов за циклы», «устранение индуктивных переменных», «сращивание циклов», «разматывание циклов» и т. д. В действительности все эти методы можно объединить в два эмпирических правила.
1. Никогда не следует делать в цикле ничего такого, что можно сделать вне его.
2. Где это можно, следует избавиться от передач управления внутри циклов.
Первое правило следует из истины, по которой 90 % времени исполнения программы приходится на 10 % ее кода. Эти 10 % чаще всего оказываются циклами того или иного рода. Таким образом, первое, что необходимо сделать для ускорения выполнения программы, – это определить в ней «горячие точки» и проверить все циклы в них в качестве потенциальных объектов оптимизации. Цикл далеко не всегда представляет собой изящную конструкцию, которая завершается командами LOOP, LOOPZ или LOOPNZ; часто это просто серия команд, выполнение которых повторяется в зависимости от величины некоторой управляющей переменной или флажка.
Циклы можно разделить на два вида: к первому относятся циклы со временем исполнения, которое определяется некоторыми внешними механизмами синхронизации, ко второму – те, в которых участвует только процессор. Примером первого вида цикла служит такой, в котором набор символов передается на параллельный порт. Скорость выполнения программы никогда не будет выше темпа приема байтов параллельным портом, а быстродействие данного порта на два порядка ниже, чем время выполнения любой приемлемой кодовой последовательности управления портом. Оптимизация подобных циклов с внешней синхронизацией не часто применяется. Циклы второй категории – свободные от взаимодействия с «внешним миром».
Для полной оптимизации циклов нужен методический подход к проблеме. Сначала следует тщательно проверить все циклы для отыскания операций, которые абсолютно не связаны с переменной цикла, и разгрузить цикл от этих вычислений. Следует проанализировать оставшиеся коды и по возможности упростить их, используя просмотр управляющих таблиц, которые ориентированы на определенную модель процессора команды, отказ от универсальности и любые другие известные приемы, позволяющие уменьшить кодовые последовательности и убрать «дорогостоящие» команды.
Если в некоторых вычислениях применяется текущее значение переменной цикла, следует вывернуть ситуацию наизнанку, определяя нужные величины из начального и конечного значений переменной цикла, т. е. без перебора.
После оптимизации содержимого цикла, насколько это возможно, необходимо посмотреть, можно ли где-то убрать управляющие циклы операций перехода или вызова подпрограмм.
48. Управляющие таблицы
Очень часто целесообразно перенести вычисления из цикла за его пределы и отсрочить вычисления, пока их результаты реально не потребуются. Еще более эффективный вариант оптимизации заключается в том, чтобы приурочить вычисления не ко времени выполнения программы, а к моменту ее компиляции или ассемблирования либо выполнять вычисления, применяя специализированные программы, сохранять результаты в промежуточном файле и вытаскивать их оттуда при необходимости.
