Miracle #03 16 июля 1999

Программирование

Кто там кодит? - Гуру медитирует: оптимизация программ по времени исполнения и по размеру.

    (c) PSV/Dream Team
    -------------------

    ОПТИМИЗАЦИЯ  ПРОГРАММ
    ПО ВРЕМЕНИ ИСПОЛНЕНИЯ 



            ПРОЛОГ

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

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

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

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

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


         ГЛАВА ПЕРВАЯ
   (о том как писать быстрые программы
      не зная конкретной аппаратуры)


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

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

    В  любой  программе, не ограничиваю-
щейся  переносом  данных, есть алгебраи-
ческие операции. Накопленный программис-
тами  опыт  позволяет  вывести некоторые
правила,   руководствуясь  которыми  эти
операции  можно  писать  так,  чтобы они
работали  быстрее. Например, A=BxB будет
работать всегда быстрее, чем A=B^2 (если
конечно   эти   операции   написаны  как
универсальные процедуры, а не специально
оптимизированы,  о  чем  будет идти речь
дальше).  Также  быстрее  будет работать
A=Bx(C+D)  по сравнению с A=BxC+BxD, так
как даже если в процессоре предусмотрена
команда  умножения  то  она всегда будет
медленнее, чем сложение. Обобщим эту те-
му: вот в каком порядке следует скорость
выполнения  алгебраических  операций (от
быстрых  к медленным): сложение, вычита-
ние,  умножение,  деление,  возведение в
степень,  взятие корня. А если вас заму-
чает  вопрос "что быстрее: два умножения
или  четыре  сложения?", то вам придется
заняться более подробным изучением аппа-
ратуры  (смотрите  потактовое исполнение
команд).  Далее рассмотрим более сложные
функции,  такие  как: COS, SIN, TG, LOG,
EXP.  По  этому поводу следует заметить,
что  в  большинстве  случаев  вычисление
этих  функций можно написать целочислен-
но,  если их промасштабировать, что даст
колоссальный  выигрыш  по скорости. При-
мер:  допустим  что нам необходимо вычи-
слять выражение A=BxSIN(C). При вычисле-
нии синуса мы вычисляем его не в дробных
числах, а в целых (за счет того, что ре-
зультат  будет  меняться не от 0 дo 1, а
от  0  до  допустим 256), умножив все на
256.  Далее после умножения получившийся
результат необходимо поделить на 256 (то
есть просто отбросить младший байт).

    Другой   путь   избежать  применения
сложных   по   вычислению  (а  значит  и
медленных)  функций - вычислить их зара-
нее  и задать в виде массива. Такой путь
находит  в последнее время все более ши-
рокое применение, так как расширение па-
мяти  намного проще и дешевле увеличения
быстродействия. Например вместо вычисле-
ния  синуса  по  разложению  в ряд как в
большинстве универсальных программ можно
заранее  посчитать его значения скажем с
шагом в один градус и точностью 4-5 зна-
ков  после  запятой, что займет каких-то
720 байт памяти, но ускорит работу прог-
раммы в несколько раз.

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

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

    взять очередной байт
    MOVE регистр, (NNNN)
    ADD очередной байт, регистр
    положить очередной байт

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

    взять очередной байт
    MOVE регистр, константа 
    ADD очередной байт, регистр 
    положить очередной байт 

    При этом в одной из команд основного
цикла,  выполняющегося многие тысячи раз
(то есть за быстродействие которого надо
бороться), мы получаем почти 2-х кратный
выигрыш  по  времени  выполнения за счет
удаления  косвенности  обращения к конс-
танте.  Но как же? Ведь по условию конс-
танта не фиксирована, а задается пользо-
вателем, а нам в программе придется впи-
сать  одно  конкретное  число!  А дело в
том, что вместо одного конкретного числа
будет всегда стоять именно та константа,
которую  ввел  пользователь,  ведь,  как
известно,  в памяти  программа находится
как набор чисел (байт) и наше определен-
ное число тоже будет занимать какое - то
количество   байт  в  памяти  по  вполне
конкретному адресу, а чем этот адрес ху-
же  того,  который мы хотели отвести под
хранение константы? Вот и получается что
и  программа  быстрее, и голова не болит
при поиске свободной памяти под констан-
ту,  и  программа  короче,  и памяти под
данные  надо  меньше.  Кроме  констант в
программе  можно  также  менять  сам код
операций,  что гораздо труднее в написа-
нии и требует больших знаний аппаратуры.


         ГЛАВА ВТОРАЯ
(о том как писать под конкретное железо)


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

    Огромную роль в быстродействии прог-
рамм играет скорость обмена с носителями
информации. В большом количестве случаев
программа  работает  медленно  не  из-за
процессора,  а  из-за  медленного обмена
данными с носителями. Как правило даже у
электронных  носителей  (память  на ИМС)
скорость  работы намного ниже чем у про-
цессора, а как нетрудно заметить львиная
доля команд как раз и работает с памятью
(напомню,  что  даже сами команды извле-
каются  процессором  из памяти). У таких
носителей как магнитные и лазерные диски
скорость и вовсе смешная. Отсюда мораль:
не   поленитесь  и  досконально  изучите
характеристики  носителя  вашей информа-
ции, и вы не пожалеете. Как правило сра-
зу  находятся  способы повысить скорость
обмена:  то  окажется что какая-то часть
памяти быстрее, чем другая, то окажется,
что  носитель можно кэшировать (снабдить
быстрой   буферной  памятью),  то  вдруг
обнаружится,   что  с  четными  адресами
работа  быстрее,  чем  с нечетными и так
далее.  При  наличии различий в характе-
ристиках  необходимо наиболее используе-
мые  данные  располагать в более быстрых
участках.  Например, на многих компьюте-
рах  память,  используемую  как видеопа-
мять,  используют для хранения не графи-
ческих данных, что дает увеличение объе-
ма памяти для данных. Но изучив скорость
работы с памятью как правило выясняется,
что  такая  память  намного  медленнее и
хранить   там  желательно  только  редко
используемые данные.

    Следующий шаг - изучение потактового
выполнения   команд  процессором.  Сразу
появляется  численный  критерий  быстро-
действия:  напишешь так - 1200 тактов, а
подумаешь  и  напишешь  проще - 750 так-
тов.  Также  появляется приятная возмож-
ность  оценить  быстродействие программы
даже  не  вводя  ее в машину, а посчитав
необходимое  для  выполнения  количество
тактов. Например, делая программу, обра-
батывающую сигналы с частотами поступле-
ния  до  100 герц бессмысленно вводить в
компьютер  программу  обработки сигнала,
если  один  цикл в ней займет по расчету
более 10000 тактов (при тактовой частоте
1 МГц). На  этом  этапе  полезно завести
для  себя  черный список и заносить туда
команды выполняющиеся за чрезмерно боль-
шое   количество  тактов,  чтобы  всегда
избегать их применения.

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

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

         ГЛАВА ТРЕТЬЯ
 (приемы написания быстрых программ для
  КР580 и недалеко от него ушедший Z80) 


    Несмотря  на  то, что 8-ми разрядные
процессоры  безнадежно  устарели (кстати
уже  устарели  и  16-ти  разрядные)  они
остаются  одними из наиболее распростра-
ненных у нас процессоров, что заставляет
выжимать из них не виданные даже их раз-
работчиками   скорости.  Наиболее  общие
соображения  при написании программ: как
можно большее количество переменных дер-
жать в регистрах, а не в памяти; малень-
кие  подпрограммы  не оформлять как под-
программы,  а  вставлять  в  необходимые
места;  стараться  по возможности приме-
нять   инкременты/декременты   и  сдвиги
влево/вправо вместо сложения/вычитания и
умножения/деления соответственно (DCR B:
DCR B  вместо  MVI A,B: SUB 2: MVI B,A);
применять   при  работе  с  двухбайтовой
переменной   обработку  только  младшего
байта если известно что при двухбайтовой
обработке  старший  байт  все  равно  не
изменится   (например   если  необходимо
обработать  5000  байт  блоками  по 4 то
внутри  одного  блока  у  счетчика будет
меняться  только  младший  байт).  Далее
несколько приемов для конкретных распро-
страненных случаев:

    1. Операторы  ветвления  (только для
Z80): JP на 2 такта быстрее, чем JR (хо-
тя и на байт короче: кому что).

    2. Перенос адреса из одной регистро-
вой пары в другую не подумав пишут так:

         Z-80             КР580

        PUSH HL           PUSH H
        POP BC            POP B

    А  почти в три раза быстрее написать
так:

        LD B,H            MVI B,H 
        LD C,L            MVI C,L

    3. Быстрый цикл по двухбайтной пере-
менной. Обычно пишут так:

       LD BC,числоLXI B,число
    M: цикл           M:  цикл
       DEC BC             DCX B 
       LD A,B             MOV A,B
       OR C               ORA C 
       JP NZ,M            JNZ M 

    В цикле кроме полезного тела тратит-
ся еще 24 такта, поэтому пишем так:

       LD BC,число       LXI B,число
    M: цикл          M:  цикл
       DEC C             DCR C
       JP NZ,M           JNZ M
       DEC B             DCR B
       JP NZ,M           JNZ M

    и   тратим  всего  (14+14/256)=14.05
тактов на цикл.

    4. Побитовая обработка памяти. Обыч-
но  пишут  так (в паре HL - адрес, в ре-
гистре C - маска):

        обработка бита
        RRC C 
        JR NC,M
        INC HL
    M:  зацикливание

    Это   "съедает"   (20x7+21)/8=20.125
тактов  на  каждый  переход к следующему
биту, а я предлагаю писать так:

        обработка бита     для КР580  
        RRC C              этот прием 
        JR C,M2            не очень   
    M1  зацикливание       эффективен 
        ...   
    M2  INC HL
        JP M1

    что   "съедает"   (15x7+36)/8=17.625
тактов,  хотя  на  первый взгляд кажется
хуже.

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

        LD SP,конец_очищаемой памяти
        LD HL,код_заполнения
        LD B,длина/(кол-во PUSH в цикле)/2
    M:  PUSH HL
        PUSH HL
        ...
        DJNZ M

    Чем  больше  написать  PUSH'ей - тем
быстрее  будет заполнение. И не забудьте
восстановить  указатель  стека  в  конце
цикла!  В среднем это в 1.5 раза быстрее
чем  обычное  заполнение.  По  такому же
принципу   пишут  и  программы  переноса
памяти  (опять же таки их быстродействие
получается  максимально  достижимым  для
процессора),   но   они   гораздо  более
громоздки.

    6. Быстрая    процедура    умножения
(параметры:  регистр E - первый сомножи-
тель, регистр A - второй сомножитель, HL
- результат   операции).   Большой  плюс
программы - отбираемое время практически
не зависит от величины сомножителей.

        LD HL,#0000    для КР580 будут
        LD D,L         отличаться только
        RRA            мнемоники команд
        JR NC,M1
        ADD HL,DE
    M1: ADD HL,HL
        RRA
        JR NC,M2
        ADD HL,DE
    M2: ADD HL,HL
        RRA
        JR NC,M3
        ADD HL,DE
    M3: ADD HL,HL
        RRA
        JR NC,M4
        ADD HL,DE
    M4: ADD HL,HL
        RRA
        JR NC,M5
        ADD HL,DE
    M5: ADD HL,HL
        RRA
        JR NC,M6
        ADD HL,DE
    M6: ADD HL,HL
        RRA
        JR NC,M7
        ADD HL,DE
    M7: ADD HL,HL
        RRA
        RET NC
        ADD HL,DE
        RET

    Экономящие   память   могут  собрать
повторяющиеся действия в цикл, но сильно
потеряют в быстродействии.

На этом пока все.
Счастливой оптимизации!