Info Guide #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