Inferno #07
31 мая 2005

For Coderz - Основы оптимизации под процессор Z80.

   Основы оптимизации под Z80  Существует 4 направления оптимизации:по
размеру, по скорости, по сжатому размеру и 
по объёму исходника. На последнем останав─ 
ливаться здесь не будем. 

          Оптимизация по размеру

                    1.

   Если  структура  программы  определена,
следует подсчитать  количество обращений к
каждой  процедуре (это очень легко - изме─
нить метку её названия и попытаться оттра─
нслировать), а на  основании этого числа и
её,процедуры,размера можно решить вопрос о
лишении её статуса подпрограммы и внесении
в вызывающий фрагмент. Иногда подпрограмма
от этого не выигрывает. Например, в случае
множества  условных  возвратов (они короче
 условных переходов) в ней.
   CALL addr : RET  заменяется на  JP addr
или, если возможно, JR addr. Ещё лучше пе─
ренести  фрагмент  с JP к указанному в нём
 адресу.
   CALL addr:JP addr2 упрощается аналогич─
но: переносом вплотную к указанному в CALL
адресу и заменой упомянутой конструкции на
LD BC,addr2:PUSH BC. 
   Крупный  цикл наподобие опроса клавиш -
с большим количеством  переходов на одну и
ту  же  точку - логично  сократить так же,
занося адрес точки на стек и пользуясь ус─
ловными возвратами.

   Сложную  систему  условий часто удаётся
привести  к какому-либо  виду, содержащему
таблицу, возможно, обрабатываемую командой
CPIR. 

   Окончания  циклов  вида JR NZ,exit:CALL
addr:JR Z,loop:exit приводятся к виду CALL 
Z,addr:JR Z,loop. Иногда  для этого прихо─ 
дится менять признаки завершения в подпро─
грамме addr, а подчас и создавать эту под─
программу, если её нет :)
   Разумным  распределением  соглашений  о
флагах  на  выходе из разных процедур (не─
плохо использовать факты, что п/п такая-то
всегда устанавливает CY, а другая п/п пре─
дпочитает  сбрасывать Z ). можно  добиться
более частого использования условных вызо─
вов  и сэкономить  тем самым немало байт и
строчек кода.

   Полезно время от времени прогуляться по
исходнику и записать самые популярные фра─
гменты  вызова  некоторых  процедур. Часто
перед  CALL  стоят однотипные команды. Это
позволяет внести их в начало процедуры,по─
льзуясь тем, что в ассемблере,в отличие от
ЯВУ, возможно сколько угодно точек входа в
процедуру! В конце концов процедуры склеи─
ваются в ёлки наподобие такой:
 OUT0    LD A,16 
        JR $+4
OUT7    LD A,23 
OUTME   LD (pg),A 
 OUTNO   PUSH BC 
         LD BC,32765
         OUT (C),A
         POP BC
        RET
   И это ещё не самый крупный экземпляр!:)
   Если же,например,после CALL часто стоит
какая-либо операция, которая в других слу─
чаях  безвредна (что-то  вроде OR A или LD
HL,(addr) ), можно подставить эту операцию 
в конец самой процедуры. Бывают случаи,ко─
гда ничего подставить нельзя,но оказывает─
ся выгодным сделать промежуточную вызывал─
ку процедуры - с самыми частыми командами,
сопутствующими этому вызову.

   Приведённые  рекомендации  относятся  к
организации  программы и почти не касаются
её  внутреннего  устройства. На  следующей
странице мы поговорим и об устройстве. По─
путно отметим здесь, что существует способ
программирования  без использования команд
CALL, а также средство экономии памяти пу─ 
тём создания интерпретируемой или компили─
руемой системы команд (скрипта).

                    2.

   Есть  ряд  конструкций, неоптимальных с
точки  зрения размера / скорости / регист─
ров практически всегда.Вот несколько таких
 "запрещённых конструкций":
    SLA A (заменяется на ADD A,A );
    SLA L:RL H (заменяется на ADD HL,HL );
   RL L:RL H (заменяется на ADC HL,HL );
   Два последних совета  можно применить к
другим похожим случаям, если перераспреде─
лить регистры;
    Полная альтернатива вида
         JR C,cy
         LD reg,число
        JR ok
cy      LD reg,число2 
 ok 
   (заменяется на  LD reg,число2: JR C,ok:
LD reg,число: ok или, если reg - аккумуля─ 
 тор: SBC A,A:AND число!число2:XOR число ); 
   PUSH HL:SBC HL,DE:POP HL (заменяется на
SBC HL,DE : ADD HL,DE - проверьте: флаги в 
 том же состоянии!); 
   DEC B:JR NZ,loop (заменяется  на  DJNZ,
если не важен флаг Z ) - можно перераспре─ 
 делить регистры ради такой оптимизации; 
         LD L,(IX)
         INC HX
         LD H,(IX)
         DEC HX
        INC IX
(заменяется на  LD L,(IX-128):INC IX:LD H, 
 (IX+127) с другим нач. значением IX ); 
   LD A,reg:OR A (кроме индексных; заменя─
ется на INC reg:DEC reg ); 
   В дальнейшем вы найдёте и другие.

   Попадаются возможности избежать счётчи─
ка  цикла, если  выходить  по переполнению
младшего байта адреса: INC L:JR NZ,loop.

   Многие условные вычисления, связанные с
инкрементом (и не только), удобнее органи─
зовать арифметически.

   Самым  эффективным  способом  размещать
переменные  программы  почти  всегда будут
встроенные в текст переменные вида:
 var1=$+1 
        LD DE,0
   Из всех мест, где переменная упоминает─
ся, для этого следует выбирать место,в ко─
тором  выигрыш  максимален  (например, где
рассматриваемую переменную вычитают).
   Другой вариант размещения - в блоке си─
стемных переменных Бейсика (IY+disp) - вы─
годен  при большом количестве таких же эк─
зотических действий с переменной, как упо─
мянутое вычитание.Тем более, IY часто про─
стаивает. Понятно, что  вариант с IY будет
короче, чем  LD HL,var1:SUB (HL), но длин─
нее LD HL,var1:LD A,(HL):XOR 1:LD (HL),A.

   Подпрограмма  с возможностью  затыкания
входа реализуется подставлением или убира─
нием команды RET в её начале, без каких бы
то ни было переменных.

   Часто  можно  посчитать  сплошной кусок
программы состоящим из нескольких последо─
вательных  действий. Обычно бессознательно
мы  пишем эти секции независимыми от резу─
льтатов друг друга. Это важно для "быстро─
го" (или  "экстремального") программирова─
ния (термин для программирования без опти─
мизации и поиска ошибок - когда на это нет
времени,нужно гарантировать их изначальное
отсутствие). Но  противопоказано для опти─
мизации. Как правило,после какого-либо ци─
кла ряд регистров содержит нуль.Между тем,
нули могут потребоваться ниже (возможно,не
в других  регистрах  и не  в соседних эта─
пах). Перестановкой регистров и этапов мо─
жно выигрывать значительные объёмы.
   За  счёт  перестановки  регистров можно
перенести  большинство 16-разрядных опера─
ций  в регистровую пару HL, освободить ин─
дексные  регистры, получить дополнительный
операнд в стеке  через  EX (SP),HL, свести
операции память-память к команде LDI (LDD)
и т.п.

   Обращайте внимание на команды инициали─
зации регистров и флагов.На всякий случай,
вписывая  их, всегда  выделяйте (например,
сдвигом строки текста влево).Это будет на─
поминанием,что при удачном стечении обсто─
ятельств  команды  можно закомментировать.
Одинаковые  инициализации можно также про─
водить через PUSH...POP.

   При  оптимизации  используют и свойства
циклов:они бывают разнонаправленные;бывают
со входом в середину,с выходом из середины
или со стандартным входом-выходом; параме─
трические  и по условию; с прединкрементом
и постинкрементом (можно  переносить часть
операций  из конца цикла в начало и наобо─
рот).
   Допустимо  использовать  фрагменты ПЗУ,
которые вам понравятся. В ПЗУ 48k реализо─
ваны  многие полезные действия, не послед─
ними из которых являются LDDR : RET (адрес
5729=#1661 ) и  LDIR : RET  (адрес  13251= 
=#33C3 ), идеальные для условных вызовов и 
условных переходов. Но несовместимость,ко─
торая может получиться, если вы программи─
руете по ВАШЕ нестандартное ПЗУ, будет це─
ликом  именно на ВАШЕЙ совести :). Базовый
вариант ПЗУ - 1982 года, далее происходили
дополнения (следует, впрочем,отличать 1982 
от SOS 128k, тоже помеченного этой датой).
   С точки зрения памяти, часто бывает вы─
годно хранить упакованными отдельные редко
используемые  части  программы - пусть  не
код, а описание, или часть шрифтов, карт и
т.п.При последующем "склеивании" программы
есть  резон  не  паковать уже сжатые таким
образом части.

      Оптимизация по сжатому размеру

   Во  многих случаях важен не объём памя─
ти, занимаемый  программой, а её размер на
диске или в ПЗУ (будь она прошивкой). Гра─
мотное использование упаковщиков позволяет
решить многие аспекты этой проблемы.
   Большинство применяемых для сжатия кода
упаковщиков  основано  на  методах  LZ (A.
Lempel, J.Ziv) - копирования повторяющихся 
участков  из  уже  распакованной  половины
файла  в ещё  не распакованную. Желательно
знать и точный  формат упакованных данных,
но и основных представлений достаточно.
   Важную  роль  в определении физического
размера программы будет играть загрузчик и
детали,ему сопутствующие: распаковщик,блок
SETUP (настройки программы),процедуры ини─
циализации.Инициализация тоже вошла в этот
список,поскольку хранение её в памяти ПОС─
ЛЕ запуска программы  чаще не обосновано -
наравне с другими частями загрузчика.Но не
всегда:распаковщик может использовать сама
программа для извлечения  нужных её данных
из файлов, а загрузчиком (если он турбиро─
ванный) тоже  не грех воспользоваться сно─
ва,без его повторения в рабочей части про─
граммы. Встречаются,конечно,и случаи,когда
программа  должна иметь возможность сохра─
нять  саму себя, и ей приходится держать в
памяти все свои части.
   Для  достижения наибольшей компрессии и
оптимального  использования хвостов секто─
ров  лучше всего иметь единственный упако─
ванный  блок (если не один упакованный, то
по крайней мере загружаемый - один),с дан─
ными, разбрасываемыми впоследствии по раз─
ным  частям памяти. Число перебросок лучше
продумать  и сократить ещё на этапе разра─
ботки  программы. Впрочем, столкнувшись  с
этим, нетрудно  лишний раз исправить прог─
рамму с точки зрения распределения памяти,
изменив пару констант.
   При  компрессии музыкальных и графичес─
ких  данных нужно выбирать наиболее подхо─
дящие форматы и компрессоры.Однако при ма─
лом количестве таких данных общий компрес─
сор/декомпрессор выгоднее.
   Оптимизация  кода для сжатия являет со─
бой особую проблему. Здесь помогает только
метод проб и ошибок. Но, в частности, оче─
 видно, что:
  - похожие блоки программы следует разме─
 щать рядом; 
  - некоторые  циклы  выгодно раскрывать в
 конструкцию DUP...EDUP ; 
  - серия JP на один адрес пакуется лучше,
 чем серия таких же JR ; 
  - все  области с необязательным содержи─
мым  (переменные)  лучше  заполнить нулями 
 или кодами соседних команд; 
  - области буферов лучше исключать из ко─
дового блока. 
   Для  экспериментов  с  упаковкой  проще
всего  отассемблировать и выгрузить неско─
лько вариантов программы,после чего пооче─
рёдно сжимать их компрессором(ами).

         Оптимизация по скорости

   Перед проведением оптимизации по скоро─
сти  не  мешает  провести оптимизацию и по
размеру - с целью удаления паразитных кус─
ков кода,но избегая добавления лишних вло─
женностей CALL...RET.
   В дальнейшем оптимизируемая по скорости
программа  может как уменьшаться по длине,
так и увеличиваться.
   Изначально оптимизации подвергаются ал─
горитмы. Многие вещи можно производить ты─
сячей способов: сортировку, умножение,про─
крутку экрана,спектральные преобразования,
декодирование Хаффмана, геометрические по─
строения, чтение байтов с диска и т.д. Тот
способ, который  может быть менее оправдан
с точки зрения размера и простоты реализа─
ции, порой оказывается более быстрым.
   Например,умножение через "квадрат полу─
суммы  минус квадрат полуразности" требует
предварительной  генерации таблицы квадра─
тов и,соответственно,выделения под неё па─
мяти, быстрая сортировка может быть вообще
не наглядной, а быстрое декодирование Хаф─
фмана - не  только  не наглядным, но ещё и
труднопроверяемым. Но тем не менее,они вы─
годны по скорости.

   Разумеется,всё ускорять не надо,тем бо─
лее  варварскими методами табличного вида,
заполняющими  всю  память. Нужно  выбирать
именно  те части программы, которые влияют
на время  её выполнения особенно сильно. В
простейших случаях  такая  часть одна: она
называется  "внутренний цикл" (inner loop)
и находится легко - в месте самой глубокой
вложенности многоярусного цикла.Как прави─
ло, циклы, число проходов которых исчисля─
ется тысячами, а то и миллионами, сводят к
табличным  операциям и раскрывают в первую
очередь.(Раскрытие цикла заключается в за─
мене его повторами типа DUP...EDUP.) Кроме
того,продумывают всевозможные варианты за─
писи  с разными регистрами и в каждом слу─
чае считают такты.
   Может, однако,оказаться,что цикл второй
вложенности (если  считать изнутри) содер─
жит  так много команд, что замедляет прог─
рамму сильнее внутреннего. Между тем,о нём
часто забывают и потому не учитывают.
   Более  сложный  вариант - программа  со
множеством поочерёдно проводимых операций.
Если  операции заключены  в серию  циклов,
затруднительно  даже выяснить, сколь долго
в сумме выполняется каждая из них. Подсчи─
тать число проходов можно,поставив в любом
 месте:
         PUSH AF
         LD A,0
         ADD A,1
         LD ($-3),A
         LD A,0
         ADC A,0
         LD ($-3),A
         LD A,0
         ADC A,0
         LD ($-3),A
         (и т.д.)
        POP AF
   Если  найдётся  способ  оценить среднее
количество тактов в каждой операции,то,уз─
нав количество проходов, мы получим и вре─
мя. Можно попытаться подсчитывать и преры─
вания.Можно исключать процедуры по одной и
сравнивать общее время.

   В зависимости от вклада, вносимого каж─
дой процедурой,можно выбрать две-три-деся─
ток самых неторопливых  и заняться ускоре─
нием именно их.Ускорение заключается в вы─
боре разных реализаций простейших операций
и удобного  для  них  разделения регистров
процессора. Желательно содержать все обра─
батываемые данные, сколько возможно, в ре─
гистрах - с минимальным использованием па─
мяти.Используйте альтернативные наборы. IX
и IY здесь лучше  к применению в роли сум─
маторов или счётчиков цикла, поскольку об─
ращение  через них к памяти дольше обычно─
го. (Опять-таки,бывают и обратные случаи.)
Будьте  также  осторожны с IY - при режиме
прерываний IM 1 или вызовах RST 56 модифи─
цировать его опасно.
   Данные  удобно размещать по круглым ад─
ресам, что упростит расчёт этих адресов, а
заодно  сможет  позволить заменять что-ни─
будь вроде INC HL на, скажем, INC L.
   После  внедрения семейства таблиц можно
перейти к рассмотрению  возможностей ОБХО─
ДОВ процедур в каких-либо случаях, с соот─
ветствующей  подменой  результата. В конце
концов запретите прерывания и задействуйте
стек - либо как хранилище потока данных на
ввод или вывод,либо как дополнительное 16-
разрядное слагаемое при вычислениях.
   Если показалось, что близок тупик,ищите
другой алгоритм. Как правило,он находится.
Больше заранее просчитанных данных;исполь─
зование особенностей стека ( LD SP,HL, ав─
тоинкремент,таблицы процедур,цепочки вызо─
вов в стеке); другие форматы таблиц,умень─
шающие количество упоминаемых констант;для
визуальных  эффектов - огрубление вычисле─
ний,поблочный вывод...и вообще ЛЮБЫЕ дикие
идеи, какие  только  придут в вашу голову.
Далеко  не все варианты испробованы, велик
шанс найти что-то новое, ни с кем не сове─
туясь!

              Процедуры ПЗУ
      для использования в программах

   Добавляю  несколько интересных процедур
ПЗУ  к списку уже известных 8880,8020,3584
и т.д.
   Некоторые из этих процедур очень корот─
кие,и можно задаться вопросом:зачем их ис─
пользовать?Однако даже такие очень полезны
для оставления в качестве адресов на стеке
- этакий Форт. Список публикуется впервые.

#e88: 
 ;HL=экранный адрес с прибавлением #800 
         LD A,H
         RRCA*3
         DEC A
         OR #50
         LD H,A
         EX DE,HL ;DE=атрибутный адрес
        LD H,C,L,B ;B=например, число
                   ;атрибутных строк,
                    ;C=например, 0
         ADD HL,HL*5
         LD B,H,C,L ;BC=HL=CB*32
        RET

 #e9b: 
         LD A,24
        SUB B
 #e9e: 
         LD D,A
         RRCA*3
         AND #E0
         LD L,A
         LD A,D
         AND #18
         OR #40
         LD H,A ;HL=адрес A-й знакоместной
                                    ;строки
        RET

 #1117: 
         INC HL
         LD (HL),E
         INC HL
         LD (HL),D
         SCF
        RET

 #1660: 
         EX DE,HL
         LDDR
        RET

 #169a: 
         LD D,(HL)
         INC HL
         LD E,(HL)
        RET

 #16fd: 
         LD (HL),C
         INC HL
         LD (HL),B
        RET

 #172d: 
         LD C,A
         LD B,0
         ADD HL,BC
         LD C,(HL)
         INC HL
         LD B,(HL)
         DEC HL
        RET

 #18b9: 
         INC HL*6
         LD A,(HL)
        RET

 #19f5: 
         ADD HL,DE
         PUSH DE
         LDIR
         POP HL
        RET

 #1bb0: 
         RST 8
        DB #FF ;"0 OK..."

 #1c19: 
         LD C,(HL)
         INC HL
         LD B,(HL)
         EX DE,HL
         PUSH BC
        RET

 #1e7d: 
         OUT (C),A
        RET

#229b: 
устанавливает цвет бордюра и 23624 по A 

 #231a: 
         LD C,1
         RET Z
         LD C,-1
        RET

 #2aee: 
         EX DE,HL
         INC HL
         LD E,(HL)
         INC HL
         LD D,(HL)
        RET

 #2ba6: 
         EX DE,HL
         LD A,B
         OR C
         RET Z
         PUSH DE
         LDIR
         POP HL
        RET

 #2f8b: 
         PUSH DE
         LD L,A,H,0
         LD E,L,D,H
         ADD HL,HL
         ADD HL,HL
         ADD HL,DE
         ADD HL,HL ;HL=A*10
         LD E,C
         ADD HL,DE ;HL=A*10+C
         LD C,H,A,L
         POP DE
        RET

 #3406: 
         A=BC=A*5
         ADD HL,BC
        RET

 #350b: 
         PUSH HL
         LD A,0
         LD (HL),A
         INC HL
         LD (HL),A
         INC HL
         RLA
         LD (HL),A
         RRA
         INC HL
         LD (HL),A
         INC HL
         LD (HL),A
         POP HL
        RET

A. Coder 



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

Классика - Альманашник. А. С. Пушкин.

For Coderz - Распознавание и вычисление арифметических выражений по их символьной записи.

Inferno - Авторы журнала.

For Coderz - О дисциплине при создании больших проектов.

Интервью - Вопросы Константину Свиридову (Conan) о сайте zxnext.narod.ru.

Ликбез - Принципы конвертирования графики PC-ZX.

For Coderz - Программирование смены диска/дисковода на Скорпионе.

Sofтинка - DNA_OS v0.431 - пакет утилит для работы с винчестерами, RAM-дисками и дискетами.

For Coderz - Программирование под DNA_OS ZET-9, пакет утилит для работы с устройствами хранения данных.

Sofтинка - Проблемы и недоработки пакета утилит для работы с устройствами хранения данных DNA_OS.

Ликбез - Подробно о дисковых форматах, имеющих FAT.

Inferno - Вступление от редактора.

Inferno - Ошибки в предыдущих номерах.

For Coderz - Маленькие программерские хитрости.

Gameland - О новых играх: Oneyroid, Dizzy forever, Dridlock.

For Coderz - Пишем архиватор. Практические принципы LZ упаковки.

Gameland - Прохождение новых отгрузок для игры "Чёрный Ворон".

For Coderz - Программирование для видеорежима 384x304.

Inferno - Письма в редакцию.

Звук - Идеи Megus'а по поводу трекера для AY/YM.

Inferno - Об оболочке.

For Coderz - Основы оптимизации под процессор Z80.

Ликбез - Расположение разделов на винчестере.

Gamedev - 3D проецирование пола/трассы в играх.

Звук - Дикие идеи для AY трекеров.

Реклама - Реклама от Романа Чунина.

Реклама - Реклама от В. Богдановича

For Coderz - Как делается крупная перемещаемая программа.

Ремонт - Неисправности Pentagon 128+ и их ремонт.

Inferno - Содержание номера.

Разное - Мысли о конкурсе на лучший софт.

Others - Перенос программного обеспечения на ZX Spectrum с PC.

Видео - Об упаковке видео для ZX Spectrum.


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

Похожие статьи:
От редакции - Презентация первого номера газеты.
20 Useless tips
Живой уголок - Hачалось зто семнадцатого числа. Год и месяц не помню, но то, что двадцать третьего сентября, - это точно...

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