Miracle #02
10 августа 1997

Совет от ГУРУ - Оптимизация программ по времени исполнения.

<b>Совет от ГУРУ</b> - Оптимизация программ по времени исполнения.
Сейчас мы предлагаем вам прочитать очень
интересную статью, написаную всем извес-
тным PSV из DREAM TEAM GROUP. Возможно  
эта статья решить не одну вашу проблему 
в плане кодинга, а также сможет повысить
ваш профессиональный уровень. Стоит за- 
метить, что очень скоро выйдет в свет - 
SECOND BREATH - хит сезона демомэйкерс- 
тва 1997 года. Это будет последнее тво- 
рение DREAM TEAM на ZX-SPECTRUM'е.      
----------------------------------------
                                        
     ОПТИМИЗАЦИЯ ПРОГРАММ ПО ВРЕМЕНИ    
               ИСПОЛНЕНИЯ               
                                        
                 ПРОЛОГ                 
                                        
                                        
    На нынешнем  этапе  развития науки и
техники невозможно  себе  представить ни
одну область  их применения, куда посте-
пенно  не проникала бы микропроцессорная
техника.  Причем прошли те времена когда
результата несложных вычислений приходи-
лось ждать утомительно долго.Современные
задачи требуют решений не просто быстрых
а выдаваемых  "в  реальном  времени", то
есть  скорость решений  должна быть выше
скорости постановки задач в режиме непре
рывных во времени процессов.В наши двери
уже стучаться устройства, распознающие и
генерирующие человеческий разговор и    
движущиеся изображения реальных объектов
                                        
...К сожалению гигантские скорости обра-
ботки информации доступны пока только су
пер-компьютерам и показывают не сегодня-
шний день, а завтрашний. Пока доступная 
большинству микропроцессорная техника   
работает на скоростях примерно несколь- 
ких миллионов простейших операций в се- 
кунду (для наглядности скажу,что при    
приемлемых для глаза параметрах экрана и
таком быстродействии компьютеру не до   
вычислений: он только-только успевает за
отведенное на один кадр время просто по-
казать на экране заранее заданную карти-
нку). Поэтому не вызывает удивления стре
мление улучшить возможности программ за 
счет их грамотного написания. Причем    
иногда получаются поразительные резуль- 
таты: скорость работы программы увеличи-
вается иногда в несколько раз просто за 
счет некоторых небольших изменений, а уж
на 5 - 10 % можно ускорить любую "сырую"
программу (конечно речь идет о програм- 
мах на ассемблере, так как первый шаг   
ускорения программы - писать ее на низ- 
коуровневом языке).                     
                                        
   Принципиально различаются два подхода
к процессу оптимизации:эвристический ме-
тод основан  на логическом мышлении и не
требует специальных  знаний ни языка, ни
процессора,ни аппаратного окружения, за-
то требует  глубокого знания алгоритмов;
метод аппаратной  подгонки  более точный
(его реализацию  даже можно возложить на
компьютер)и основан на фактических очень
глубоких знаний всех свойств тех устрой-
ств, с которыми работает программа.     
                                        
   Оптимизация  программ проходит обычно
в два этапа:первый - первоначальное сос-
тавление программы с учетом некоторых со
ображений скорости; второй - модификация
отлаженной программы для улучшения пара-
метров.                                 
                                        
    Далее приводятся некоторые из извес-
тных мне приемов оптимизации программ в 
соответствии с приведенной классификаци-
ей. Сразу необходимо заметить, что из-за
скудного освещения этого вопроса в лите-
ратуре почти все было разработано небо- 
льшим кругом элитных программистов (хак-
керов) а также мной и моими знакомыми.  
В результате чего материал имеет сумбур-
ный характер.                           
                                        
                                        
              ГЛАВА ПЕРВАЯ              
  ( о том как писать быстрые программы  
     не зная конкретной аппаратуры )    
                                        
                                        
   Прежде всего, если ваша программа ра-
ботает недостаточно  быстро,  необходимо
продумать все  другие способы достижения
поставленной цели и,может быть, найдутся
априорно более быстрые алгоритмы. Напри-
мер, пересчет  координат объекта в трех-
мерном пространстве необязательно делать
по эйлеровским  формулам,  этого  же ре-
зультата можно добиться несколькими раз-
ными методами  и  выбрать  из  них опти-
мальный.  Другой пример - автоматическая
прокладка проводников при разработке пе-
чатной  платы,   которую   можно  делать
несколькими  известными  способами.  Все
способы необходимо изучить и выбрать    
опять-таки самый быстрый.               
                                        
   Если  алгоритм  уже выбран и реализо-
ван, то  самый  простой  способ  сделать
программу  быстрее - убрать из нее циклы
за счет многократного повторения в прог-
рамме самого  тела цикла. Когда цикл вы-
полняется менее  100  раз  то тело цикла
просто вставляют столько раз,сколько раз
должен выполниться цикл. Если цикл длин-
нее 100  раз,  то  его повторяют столько
раз, сколько можно,а внешний цикл остав-
ляют,но выполняющимся меньшее количество
раз.Таким методом выигрыш в скорости по-
лучается за  счет  убирания из программы
таких процессов как изменение переменной
цикла, ее контроля и операторов перехода
к началу  цикла. Также освобождается ре-
гистр, занятый ранее под переменную цик-
ла.                                     
                                        
   В любой программе, не ограничивающей-
ся переносом данных, есть алгебраические
операции.Накопленный программистами опыт
позволяет вывести некоторые правила, ру-
ководствуясь которыми эти операции можно
писать  так, чтобы они работали быстрее.
Например, А=ВxВ  будет  работать  всегда
быстрее,чем А=В^2 (если конечно эти опе-
рации написаны как универсальные проце- 
дуры,а не специально оптимизированы,о   
чем будет идти речь дальше). Также быс- 
трее будет работать А=Вx(С+Д) по сравне-
нию с А=ВxС+ВxД,так как даже если в про-
цессоре предусмотрена команда умножения 
то она всегда будет медленнее,чем сложе-
ние. Обобщим эту тему:вот в каком поряд-
ке следует скорость выполнения алгебраи-
ческих операций (от быстрых к медленным)
сложение, вычитание, умножение, деление,
возведение в степень, взятие корня.А ес-
ли вас замучает вопрос "что быстрее: два
умножения  или четыре сложения?", то вам
придется заняться более подробным изуче-
нием аппаратуры (смотрите потактовое ис-
полнение команд). Далее рассмотрим более
сложные функции, такие как COS, SIN, TG,
LOG,  EXP. По этому поводу следует заме-
тить, что в большинстве случаев вычисле-
ние этих функций можно написать целочис-
ленно, если  их  промасштабировать,  что
даст колоссальный  выигрыш  по скорости.
Пример: допустим  что нам необходимо вы-
числять выражение А=В SIN(С). При вычис-
лении синуса мы вычисляем его не в дроб-
ных числах, а в целых (за счет того, что
результат будет меняться не от 0 дo 1, а
от 0  до  допустим  256), умножив все на
256. Далее после умножения получившийся 
результат необходимо поделить на 256 (то
есть просто отбросить младший байт).    
                                        
   Другой путь избежать применения слож-
ных по вычислению (а значит и медленных)
функций- вычислить их заранее и задать в
виде массива. Такой путь находит в пос- 
леднее время  все более широкое примене-
ние, так  как  расширение памяти намного
проще  и   дешевле   увеличения  быстро-
действия. Например вместо вычисления си-
нуса  по   разложению   в   ряд   как  в
большинстве универсальных программ можно
заранее посчитать  его значения скажем с
шагом в один градус и точностью 4-5 зна-
ков  после  запятой, что займет каких-то
720 байт памяти, но ускорит работу прог-
раммы в несколько раз.                  
                                        
   Другая  область приложения ускоряющих
усилий  - программы,  в  которых большая
часть времени  работы не требует быстро-
действия, но жизнь портят редкие моменты
когда требуется быстро что-то сделать (к
такому типу относятся почти все интерак-
тивные программы - сначала они ничего не
делают и  ждут  команды от медленного по
сравнению с ними человека,а потом, когда
команда подана, они заставляют ждать че-
ловека, пока выполнится какое-то сложное
действие). В таком случае помогает такое
средство- пока программа имеет свободные
такты (допустим клавиатуру можно опраши-
вать не  чаще чем 100 раз в секунду, что
не  займет  и  одного  процента  быстро-
действия процессора),она пытается преду-
гадать какая последует работа и все под-
готовить к  мгновенной  обработке: найти
свободное место  на  носителе, вычислить
нужные константы,проверить ошибки и тому
подобные  вещи. Даже  если приготовления
окажутся напрасными, вреда от них не бу-
дет. Но зато если пригодятся - требуемая
работа совершится гораздо быстрее.      
                                        
   Перечисленные выше приемы усложняют и
удлинняют программу, но есть один прием,
позволяющий сократить не только время ис
полнения процедуры,но и уменьшить требу-
емую ей память.Речь идет о самомодифици-
рующихся программах.Рассмотрим следующий
пример:допустим программе необходимо пе-
ренести некоторую  информацию  из одного
носителя на другой, прибавляя при этом к
каждому байту константу,значение которой
каждый раз при запуске задается пользова
телем. Естественно при этом отвести под 
константу какую-нибудь ячейку памяти где
нибудь в незанятой области. Пусть ее ад-
рес будет  NNNN.  При  этом  необходимое
действие будет написано примерно так:   
                                        
    взять очередной байт                
    MOVE регистр,(NNNN)                 
    АДД очередной байт, регистр         
    положить очередной байт             
                                        
   При этом во-первых в команде MOVE фи-
гурирует какой-то не имеющий значения   
для работы алгоритма адрес,а кроме самой
программы в  памяти  необходимо  отвести
место под константу. Используя же методы
самомодификации можно написать так:     
                                        
    взять очередной байт                
    MOVE регистр,константа              
    АДД очередной байт, регистр         
    положить очередной байт             
                                        
   При  этом в одной из команд основного
цикла, выполняющегося  многие тысячи раз
(то есть за быстродействие которого надо
бороться), мы получаем почти 2-х кратный
выигрыш по  времени  выполнения  за счет
удаления косвенности обращения к констан
те. Но как же? Ведь по условию константа
не фиксирована,а задается пользователем,
а нам  в программе придется вписать одно
конкретное число! А дело в том,что вмес-
то одного конкретного числа будет всегда
стоять именно та константа, которую ввел
пользователь, ведь, как известно,в памя-
ти программа  находится  как набор чисел
(байт)и наше определенное число тоже бу-
дет занимать  какое-то количество байт в
памяти по  вполне  конкретному адресу, а
чем этот адрес хуже того, который мы хо-
тели отвести под хранение константы? Вот
и получается  что и программа быстрее, и
голова не болит при поиске свободной па-
мяти под константу,и программа короче, и
памяти под  данные  надо  меньше.  Кроме
констант в  программе можно также менять
сам код  операций, что гораздо труднее в
написании и требует больших знаний аппа-
ратуры.                                 
                                        
                                        
              ГЛАВА ВТОРАЯ              
(о том как писать под конкретное железо)
                                        
                                        
   Для  применения методов типа изложен-
ных ниже  необходимо  полностью  изучить
специфику работы всех аппаратных средств
с которыми  будет  работать программа, и
прежде всего,конечно процессор и носите-
ли информации. Причем изучение не должно
ограничивать логикой работы устройств, а
должно включать в себя изучение времен- 
ных характеристик.                      
                                        
   Огромную  роль в быстродействии прог-
рамм играет скорость обмена с носителями
информации. В большом количестве случаев
программа работает медленно не из-за про
цессора,а из-за медленного обмена данны-
ми с  носителями.  Как  правило  даже  у
электронных носителей  (память  на  ИМС)
скорость работы намного ниже чем у про- 
цессора, а как нетрудно заметить львиная
доля команд как раз и работает с памятью
(напомню, что даже сами команды извлека-
ются процессором из памяти). У таких но-
сителей как  магнитные  и лазерные диски
скорость и вовсе смешная. Отсюда мораль:
не поленитесь  и досконально изучите ха-
рактеристики носителя вашей информации,и
вы не пожалеете. Как правило сразу нахо-
дятся способы  повысить скорость обмена:
то окажется  что  какая-то  часть памяти
быстрее, чем другая, то окажется что но-
ситель можно кэшировать(снабдить быстрой
буферной памятью), то вдруг обнаружится,
что с  четными  адресами работа быстрее,
чем с нечетными и так далее. При наличии
различий в характеристиках необходимо на
иболее используемые данные располагать в
более быстрых участках. Например,на мно-
гих компьютерах память, используемую как
видеопамять,используют для хранения нег-
рафических данных,  что  дает увеличение
объема памяти для данных. Но изучив ско-
рость работы с памятью как правило выяс-
няется, что такая память намного медлен-
нее и хранить там желательно только ред-
ко используемые данные.                 
                                        
   Следующий  шаг - изучение потактового
выполнение команд процессором.Сразу поя-
вляется  численный  критерий  быстродей-
ствия: напишешь так - 1200 тактов, а по-
думаешь и  напишешь  проще - 750 тактов.
Также  появляется  приятная  возможность
оценить быстродействие программы даже не
вводя ее в машину,а посчитав необходимое
для выполнения количество тактов. Напри-
мер,делая программу, обрабатывающую сиг-
налы с частотами поступления до 100 герц
бессмысленно вводить в компьютер програм
му обработки  сигнала,  если один цикл в
ней займет по расчету более 10000 тактов
(при тактовой  частоте  1  МГц). На этом
этапе полезно  завести  для  себя черный
список и заносить туда команды выполняю-
щиеся за чрезмерно большое количество   
тактов,чтобы всегда избегать их примене-
ния.                                    
   Если  ваша программа работает в каки-
ми-либо другими интеллектуальными партне
рами (дисководами,графическими/арифмети-
ческими/музыкальными и прочими сопроцес-
сорами или  другим компьютером по сети),
то работу  с  ними можно убыстрить также
подробно изучив  их логические и времен-
ные параметры.  Например не нужно писать
программу рисования векторов с заданными
координатами, если  это умеет быстро де-
лать сам видеопроцессор (а "умные" виде-
опроцессоры умеют рисовать не только век
тора, но  и трехмерные многоугольники по
заданным картам  рисунка, освещенности и
так далее).Другой пример: зачем програм-
ме при  печати текста на бумагу выравни-
вать его по краям,когда это может делать
сам принтер не тратя при этом ни времени
ни памяти компьютера. Или к чему контро-
лировать контрольную  сумму  массива при
передаче данных,суммируя огромный массив
чисел, если  это  на  аппаратном  уровне
контролируется портом ввода/вывода и дос
таточно контролировать  один  бит  в его
флаге  состояния. Эти  и подобные ошибки
приводят к  досадным  паузам там, где их
можно устранить  при грамотном подходе к
скорости работы программы при ее написа-
нии.                                    
                                        
    Кроме "железа" неплохо также знать и
особенности восприятия человеком если ва
ша программа предусматривает его участие
Например в последних программах с созда-
нием высокореальных вычисляемых изображе
ний используется сильное упрощение вычис
лений сцены при ее быстром движении, так
как человеческий глаз все равно не успе-
вает рассмотреть деталей.Также на подоб-
ных свойствах рассчитаны алгоритмы      
сильной упаковки изображений и звука за 
счет исчезновения мелких и незаметных де
талей.                                  
                                        
                                        
                                        
                                        
                                        
                                        
                                        
     Продолжение в следующем номере     
                                        



Другие статьи номера:

От авторов - Новая оболочка у журнала.

Игрофилия - Секреты и пароли к играм: Adams Famaly , Astro Marine Corp, Black Magic, Bubble Bobble, Chicago , Cybernoid Part 1&2 , Double Xinox, Dynasty Wars, Fargo,Freestyle Bmx, Garfield, Grand Prix-2, Herbert'S Dummy Run, Impossamole, Mad Mix-2, Indiana Jones And Last Crusade, Jet Bike Simulator, Kraal, Kgb Superspy, Last Mission , Line Of Fire , Magic Stripes, Monty Python Flying Circuit, New Zeland Story, Predator-2, Power Piramids , Rau Recruits , Road Runner , Score 3020, Task Force, Ulises, War Machine, Wild West Seymour, Zona0.

Слухи и новости - Кто что делает: Dream Team Group, OHG, Pungency, Величутин Николай, Virtual vision group, Golden Disk Group, KDF Soft, X-Project, Mafia, Flash Inc.

Совет от ГУРУ - Оптимизация программ по времени исполнения.

Знакомые лица - Интервью с DJ.IRONMAN'ом.

Видеоглобус - "Человек с тысячей лиц". Фильмография Джимми Керри.

Видеоглобус - Oбзор новинок видеопроката.

Видеоглобус - обзор последних поступлений электронной музыки.

Комната смеха - Торжество прогресса.

Комната смеха - "Без пива-жизнь не красива" рассказ Blade.

Обзор - Обзор новинок ПО: N.M.W.C., Mortal Combat, Kombatris,Feodal Wars, Tetroid, Babbona, Santa Claus,The Fury,Star Control, Pinc Floyd, Test Ramdoctor V2, Total Commander V1.4.

Мир ПЦ - О играх: KRUSH KILL'N'DESTROY; DOMINION, MYTH.

Мир ПЦ - Подскзки к играм: Heroes of Migic 2&3, Mission Force, Cyber Storm, Leisure Suit Larry 7 , Death Rally , NBA Full Court Press, XS, Tomb Raider, Redneck, Rampage, NHL'1997.

Частные уроки - PRO TRACKER для начинающих от Ironman'a.

Прогресс - История хоумтайпинга.

Прогресс - музыкальная вечернка в Грозном.

Библиотека - Рассказ "Ореол", Генри Каттнер.

Вам в подарок - О приложении к журналу: Empire Demo Version , Rom Track Copyer, Dynamite Dux, Treble Player, Snoopy and peanuts, INSANE, Vicomm Modem 2.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Беседы при свечах - Интервью, взятое у Бориса Натановича Стругацкого.
Разное - Погода.
Наш гость - Интервью SHOTGUN-a.
TAEDIUM VITAE - "Вы слышали тишину? Слышали когда-нибудь тишину?"
Рассказы - Бортжурнал.

В этот день...   25 июня