Программирование -> Assembler -> Оптимизация программ на ассемблере.

Часть 3

В предыдущих двух статьях данной серии мы обсуждали некоторые общие концепции оптимизации, а затем рассматривали конкретные методы, относящиеся к переходам и вызовам подпрограмм, а также метод отказа от универсальности. В этой статье мы поговорим еще о нескольких методиках "локальной" оптимизации: об оптимизации циклов, о применении таблиц управляющих параметров, а также об ориентированных на конкретные модели процесоров командах. Но сначала я хотел бы еще раз подчеркнуть: обращаться к оптимизации следует только после тщательного выбора алгоритма и структур данных, после того, как вы полностью реализовали, проверили и отладили свою программу и локализовали все "узкие места" при помощи соответствующих тестовых примеров и инструментальных средств профилирования. Стоит еще раз повторить мудрое изречение д-ра Кнута: "Многие беды программирования проистекают от преждевременной оптимизации".

Оптимизация циклов

Литература о компиляторах переполнена обсуждением методов оптимизации циклов, которым присваивают самые экзотические названия: "разгрузка циклов", "вывод инвариантов за циклы", "устранение индуктивных переменных", "сращивание циклов", "разматывание циклов" и т.п. На самом деле все перечисленные методы можно свести к двум простым эмпирическим правилам:

• никогда не делайте в цикле ничего такого, что можно сделать за его пределами;
• везде, где это возможно, избавляйтесь от передач управления внутри циклов.

Первое из правил следует из старинной истины, гласящей, что 90 % времени исполнения программы приходится на 10 % ее кода. Если вы попытаетесь найти роковые 10 %, скорее всего окажется, что это циклы того или иного рода. Поэтому первое, что следует сделать, когда вы пытаетесь ускорить исполнение программы, - это найти в ней "горячие точки" и проверить все циклы в них в качестве потенциальных объектов оптимизации. Цикл отнюдь не всегда представляет собой изящную конструкцию, завершающуюся командами LOOP, LOOPZ или LOOPNZ (в сосбенности, разумеется, если программу писали не вы, а кто-то другой!); часто это просто серия команд, исполнение которых повторяется в зависимости от значения некоторой управляющей переменной или флажка.

Циклы можно подразделить на две категории: к первой относятся циклы, время исполнения которых определяется какими-то внешними механизмами синхронизации, ко второй - те, в которых работает только процессор. В качестве примера цикла первой разновидности можно привести, скажем, такой, в котором набор символов передается на параллельный порт [обычно принтер - Прим. набивальщика]. Скорость исполнения программы ни при каких обстоятельствах не будет превышать темпа приема байтов параллельным портом, а быстродействие этого порта по крайней мере на два порядка ниже, чем время исполнения любой приемлемой кодовой последовательности управления портом. Вы, конечно, можете ради собственного удовольствия заняться оптимизацией подобных циклов, но для дела лучше поискать точку приложения сил в другом месте. Такой точкой вполне могут стать циклы второй категории - свободные от взаимодействия с "внешним миром".

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

В качестве примера рассмотрим не слишком удачную программу, которая суммирует все кратные 5 элементы массива с однократной точностью и оставляет результат в регистре AX:

          items     equ   100
          array     dw    items dup (?)
                    .
                    .
                    xor    cx, cx       ; инициализация счетчика
                    xor    ax, ax       ; инициализация суммы

          L1:       mov    bx, bx       ; формирование указателя
                    add    bx, bx       ; * 2
                    add    bx, bx       ; * 4
                    add    bx, bx       ; * 5
                    add    bx, bx       ; * 10
                    add    ax, [bx+array]
                    inc    cx
                    cmp    cx, (items / 5)
                    jne    L1

Упрстив этот цикл, мы получим:

          items     equ   100
          array     dw    items dup (?)
                    .
                    .
                    xor    ax, ax       ; инициализация суммы
                    mov    bx, offset array

          L1:       add    ax, [bx]
                    add    bx, 10
                    cmp    bx, offset array + (items * 2)
                    jb     L1

После того, как вы оптимизировали содержимое цикла насколько это было возможно, стоит посмотреть, не удастся ли где-то избавиться от управляющих циклом операций перехода и вызова подпрограмм. Идея здесь та же, что и при оптимизации переходов и вызовов, которые мы обсуждали в предыдущей статье. Суть дела в том, что в процессорах серии 80x86 фирмы Intel интенсивно используется простая конвейерная система, состоящая из шинного интерфейса, очереди упреждающей выборки, в которую поступают ждущие исполнения и извлекаемые из памяти команды, и исполнительного устройства. получающего информацию из очереди для декодирования и исполнения. При обнаружении перехода или вызова подпрограммы очередь очищается и все циклы памяти, котрые потребовались для заполнения позиций в ней после командв передачи управления, пропадают зря. При этом исполнительное устройство должно ожидать, пока шинный интерфейс извлечет и передаст в очередь новые команды из новых адресов. Так что переходы и вызовы подпрограмм обходятся гораздо "дороже", чем может показаться, если просто подсчитать нужное для них число тактов, руководствуясь документацией фирмы Intel.

Один из способов избавиться от сравнений и условных переходов называется объединением или сращиванием циклов. При этом коды реорганизуются так, чтобы сделать один цикл из нескольких повторяющихся одинаковое число раз. Например, из двух циклов вида

               mov  cx, 100
          L1:                 ; что-то делаем
               loop L1

               mov  cx, 100
          L2:                 ; делаем что-то lheujt
               loop L2

часто можно сделать один:

               mov  cx, 100
          L1:                 ; что-то делаем
                              ; делаем что-то lheujt
               loop L1

Другой способ избавится от циклов - "размотать" их, т.е. устранить управляющие циклом кодовые последовательности, просто повторив содержимое цикла нужное число раз. Это дает особенно хорошие результаты в тех случаях, когда время, необходимое для исполнения содержимого цикла, оказывается меньше, чем время выполнения операций, управляющих циклом. Например, цикл

               mov  cx, 3
          L1:  add  ax, [bx]
               add  bx, 2
               loop L1

можно переписать так:

               add  ax, [bx]
               add  bx, 2
               add  ax, [bx]
               add  bx, 2
               add  ax, [bx]
               add  bx, 2

или даже так:

               add  ax, [bx]
               add  ax, [bx+2]
               add  ax, [bx+4]

"Разматывание" циклов - классический пример повышения быстродействия за счет объема необходимой памяти. Каждый раз, когда вы решаете, стоит ли прибегнуть к данному приему, следует посмотреть, насколько это оправдано с точки зрения длины цикла и числа его повторений с учетом доступных для вашей программы вычислительных ресурсов. Иногда "разматывание" удается применить в самых неожиданных точках программы. К примеру, те из нас, кому доводилось составлять программы на языке ассемблера для процессоров Intel 80x86, научились распознавать ситуации, в которых можно использовать специальные команды обработки символьных последовательностей. Достаточно часто мы включали в свои программы примено такие коды:

               mov  cx, 3
               mov  si, offset string1
               mov  di, offset string2
          rep  movsw

В приведенной последовательности иммется цикл, хотя и неявный. При обработке префикса REP требуется определенное время на установку начальных параметров, а результат исполнения REP в точности такой же, как если бы мы написали:

          L1:  movsw
               loop L1

При работе на некоторых процессорах фирмы Intel и при небольшом числе итераций часто оказывается лучше не пользоваться префиксом REP, а выписать команды обработки строк подряд: movsw movsw movsw

Но это один из случаев, когда требуется выяснить, насколько хорош будет тот или иной вариант в условиях вашей конкретной программы. Время исполнения любого из вышеприведенных фрагментов невозможно точно определить, подсчитывая такты и байты команд, так как это время зависит еще и от программного контекста, а также от аппаратных характеристик системы: разрядности шины памяти, глубины упреждающей очереди команд, наличия или отсутствия и объема кэш-памяти процессора и т.д.

Управляющие таблицы

Мы уже отмечали, что почти всегда бывает целесообразно перенести вычисления из цикла за его пределы (или из "глубоко" вложенного цикла во внешний цикл), а также отсрочить вычисления до тех пор, пока их результаты реально не потребуются. Еще более эффективный вариант оптимизации состоит в том, чтобы приурочить вычисления не ко времени исполнения программы, а к моменту ассемблирования, либо выполнять вычисления с помощью специализированной программы, сохранять результаты в промежуточном временном файле и извлекать их оттуда по мере необходимости. Особенно удобная категория оптимизации этого типа называется просмотром управляющих таблиц.

Рассмотрим прикладную систему, в которой будет особенно целесообразно использовать управляющие таблицы. Представьте себе программу, в которой требуется поворачивать и перемещать отрезки линий, чтобы создать у пользователя иллюзию объемного изображения. Такая программа, естественно, должна определять синусы и косинусы углов. Для вычисления этих функций обычно применяют числа с плавающей точкой и разложение в ряды, расчет которых влечет за собой многократные умножения и деления, а эти операции с точки зрения времени счета "стоят" недешево. Кроме того, получаемые таким способом величины имеют значительно более высокую точность, чем это реально требуется для обычных графических адаптеров персональных компьютеров: даже числа с плавающей точкой одинарной точности (32 разряда) вычисляются с точностью до восьми десятичных знаков, из которых нужны только четыре или пять (разрешение графики в лучшем случае 1024 x 768 элементов изображения [требует адаптера SuperVGA с объемом памяти 1 Мбайт - Прим. набивальщикаъ).

Именно здесь и можно воспользоваться преимуществами таблицы, в которую можно занести синусы углов с шагом в 1 градус и с точностью до четырех десятичных знаков.

Прежде всего образуем структуру данных, в которой номер каждого элемента будет соответствовать углу в градусах, а значение - синусу этого угла, умноженного на 10000:

          table     dw   0000 ; sin(0)
                    dw   0175 ; sin(1)
                    dw   0349 ; sin(2)
                    .
                    .

Подготовив такую таблицу, мы без труда можем составить неболшую подпрограмму, которая будет принимать значение угла в диапазоне 0 - 359 градусов в регистре AX, а в ответ выдавать значение синуса этого угла в том же регистре:

          ; Функция SINE
          ; При вызове AX = угол в градусах
          ; При возврате управления AX = 10000 * sin
          sine      proc near
                    push bx
                    mov  bx, ax
                    add  bx, bx
                    mov  ax, [bx+table]
                    pop  bx
                    ret
          sine      endp

Для дополнительного ускорения работы своей программы мы можем преобразовать подпрограмму в макроопределение, чтобы коды вставлялись в программу везде, где это потребуется. На рис. 2 показана более общая форма данной процедуры и ссответствующая процедура расчета косинуса.

Иногда управляющие таблицы можно весьма эффективно использовать в ситуациях, где мысль о них просто не приходит в голову. Пусть, например, вам поручено составить подпрограмму, которая будет подсчитывать число ненулевых разрядов в байте. Первое побуждение обычно состоит в том, чтобы составить цикл со сдвигами и действительно подсчитывать ненулевые разряды. Но ведь значительно быстрее будет воспользоваться таблицей, позиции в которой будут соответствовать значениям байта - от 0 до 255, а значения в этих позициях - числу ненулевых разрядов для каждого из таких значений байта:

          table     db   0    ; ненулевые разряды в 00h
                    db   1    ; ненулевые разряды в 01h
                    db   1    ; ненулевые разряды в 02h
                    db   2    ; ненулевые разряды в 03h
                    .
                    .
                    .
                    db   8    ; ненулевые разряды в FFh

          ; Функция BITS
          ; При вызове AL = значение байта
          ; При возврате AL = число ненулевых разрядов
          bits      proc near
                    push bx
                    mov  bl, al
                    xor  bh, bh
                    mov  ax, [table+bx]
                    pop  bx
                    ret
          bits      endp

И снова, чтобы еще более повысить быстродействие, можно оформить эту подпрограмму как макроконструкцию и встраивать в программу везде, где требуется. Для байтовых таблиц можно еще повысить производительность, замещая команды MOV на специальные команды обработки строк XLAT. Вместе с тем здесь необходимо подчеркнуть, что таким образом можно будет обрабатывать отнюдь не только байтовые таблицы. Мне довелось познакомиться с великолепной программой подсчета слов, (ее автор Терье Матисен), в которой использовалась таблица из 64 Кбайт для просмотра всех двухсимвольных комбинаций в поисках разделителей слов. Утверждается также, что Гордон Летуин применил аналогичную методику для сканирования битовой карты свободного пространства на диске в подсистеме обработки файлов HPFS [High-Performance File System - Прим. набивальщика] операционной системы OS/2.

Оптимизация для конкретных моделей ЦП

Если ваша программа будет работать только на компьютерах с конкретными моделями процессоров или вы ситаете, что есть смысл подготовить несколько версий программы для работы на разных машинах, можно попытаться воспользоваться ориентированными на конкретные модели процессоров командами.

По сравнению с процессорами 8086 и 8088, набор команд процессора 80286 ощутимо дополнен. Многие из новых команд позволяют повысить производительность программы:

• линейные и циклические сдвиги с непосредственным аргументом, отличным от единицы;
• команда PUSH с непосредственным операндом;
• команды обмена со стеком содержимым всех регистров - PUSHA и POPA;
• команды ENTER и LEAVE для выделения и освобождения кадра стека;
• команда проверки соблюдения границ массива BOUND.

Если ваша программа будет исполняться только на компьютерах с процессорами 80286 и более мощных, можно также выравнять по границе слов все элементы данных и целевые адреса для команд передачи управления. Таким образом можно повысить производительность на несколько процентов за счет относительно небольшого объема памяти. (При работе на процессорах 8086 выравнивание по границам слов также дает определенный выигрыш, но для процессоров 8088 с 8-разрядной шиной - это бессмысленно.)

Составляя программу для процессорв 80386DX и их разновидностей, можно повысить производительность 16-разрядной программы, пользуясь всеми вышеперечисленными командами для процессоров 80286 и, кроме того, выравнивая данные и адреса по границам 32-разрядных слов [т.е. DWORD], а также с помощью следующих дополнительных особенностей:

• 32-разрядных регистров (но пользоваться ими следует с осторожностью, так как их содержимое не сохраняется при работе с некоторыми эмуляторами системы DOS, например, модулем совместимости с DOS системы OS/2 версий до 1.3);
• команд пересылки с распространением нуля или знакового бита (MOVZX или MOVSX);
• установки в байте значений "истина" или "ложь" в зависимости от содержимого флажкоы центрального процессора, что позволяет избавиться от команд условного перехода (SETZ, SETC и т.д.);
• команд проверки, установки сброса и просмотра битов (BT, BTC, BTR, BTS, BSP, BSR);
• обобщенной индексной адресации и режимов адресации с масштабированием индексов;
• быстрого умножения при поможи команды LEA с использованием масштабированной индексной адресации;
• "дальних" условных переходов;
• перемножения 32-разрядных чисел и деления 64-разрядного числа на 32-разрядное;
• дополнительных сегментных регистров (FS и GS).

Естественно, выжать максимум из архитектуры 80386 можно при помощи расширителей DOS или операционной системы OS/2 2.0, переводя вашу программу в защищенный режим. В резульате вы получите доступ ко всем 32-разрядным регистрам, расширенной адресации и к адресному пространству до 4 Гбайт.

В процессоре 80486 предусмотрено всего две дополнительных команды, которых нет у процессоров 80386 и к которым можно обратиться из прикладной программы:

• BSWAP (изменение порядка расположения 4 байтов в 32-разрядном слове на противоположное);
• CMPXCHG (сравнение и обмен - для работы с семафорами).

Вместе с тем длительность команд, выраженная в числе тактов, у процессоров 80486 совсем не такая, как у процессоров 80386 и 80286. В общем, можно сказать, что что время исполнения простейших команд было сокращено за счет более сложных [RISC-архитектура (Reduced Instruction Set Computing - вычисления с сокращенным набором команд) - Прим. набивальщика]. Это означает, что программа, первоначально составленная для процессора 8088, возможно, будет работать быстрее на процессоре 80486, чем ее аналог, в исходном варианте предназначавшийся для процессоров 80286 или 80386. Такова жизнь. И еще кое-что, о чем стоит подумать, работая с процессором 80486: встроенная кэш-память объемом 8 Кбайт, которая работает лучше всего, если данные выравнены по ганицам 16-байтных параграфов, а также встроенный математический сопроцессор. К сожалению, недавний выпуск фирмой Intel процессоров 80486SX без (функционирующего) математического сопроцессора означает, что гарантированной возможности работать с числами с плавающей точкой на самых высокопроизводительных моделях компьютеров у нас по-прежнему нет.