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