|
Miracle
#02
10 августа 1997 |
|
Совет от ГУРУ - Оптимизация программ по времени исполнения.
Сейчас мы предлагаем вам прочитать очень
интересную статью, написаную всем извес-
тным 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 МГц). На этом
этапе полезно завести для себя черный
список и заносить туда команды выполняю-
щиеся за чрезмерно большое количество
тактов,чтобы всегда избегать их примене-
ния.
Если ваша программа работает в каки-
ми-либо другими интеллектуальными партне
рами (дисководами,графическими/арифмети-
ческими/музыкальными и прочими сопроцес-
сорами или другим компьютером по сети),
то работу с ними можно убыстрить также
подробно изучив их логические и времен-
ные параметры. Например не нужно писать
программу рисования векторов с заданными
координатами, если это умеет быстро де-
лать сам видеопроцессор (а "умные" виде-
опроцессоры умеют рисовать не только век
тора, но и трехмерные многоугольники по
заданным картам рисунка, освещенности и
так далее).Другой пример: зачем програм-
ме при печати текста на бумагу выравни-
вать его по краям,когда это может делать
сам принтер не тратя при этом ни времени
ни памяти компьютера. Или к чему контро-
лировать контрольную сумму массива при
передаче данных,суммируя огромный массив
чисел, если это на аппаратном уровне
контролируется портом ввода/вывода и дос
таточно контролировать один бит в его
флаге состояния. Эти и подобные ошибки
приводят к досадным паузам там, где их
можно устранить при грамотном подходе к
скорости работы программы при ее написа-
нии.
Кроме "железа" неплохо также знать и
особенности восприятия человеком если ва
ша программа предусматривает его участие
Например в последних программах с созда-
нием высокореальных вычисляемых изображе
ний используется сильное упрощение вычис
лений сцены при ее быстром движении, так
как человеческий глаз все равно не успе-
вает рассмотреть деталей.Также на подоб-
ных свойствах рассчитаны алгоритмы
сильной упаковки изображений и звука за
счет исчезновения мелких и незаметных де
талей.
Продолжение в следующем номере
Другие статьи номера:
Похожие статьи:
В этот день... 23 апреля