Ещё раз про DOWN_HL.

DOWN_HL является, скорее всего, самой ходовой стандартной процедурой для графики на спектруме. Не буду объяснять что она делает, потому что если вы вдруг не знаете, то разговор у нас в любом случае не заладится. Поэтому я предпочитаю считать, что она вам хорошо знакома. Выглядит она чаще всего вот так:

DOWN_HL:	inc h : ld a,h : and 7 : jr nz,next
		ld a,l : add 32 : ld l,a
		jr c,next
		ld a,h : sub 8 : ld h,a
next:		; 27/59/49

Если шагая вниз мы остаёмся в том же знакоместе, условный переход произойдёт уже в первой строке, поэтому время исполнения кода будет 4+4+7+12 = 27т. Если поменяется треть экрана, произойдёт условный переход в третьей строке, и код исполнится за 4+4+7+7 + 4+7+4+12 = 49т. Наконец, при пересечении кромки знакоместа без смены трети экрана оба перехода будут пропущены, и код исполнится за 4+4+7+7 + 4+7+4+7 + 4+7+4 = 59т.

Чаще всего мы не знаем, сколько пересечений границ знакомест и третей экрана произойдёт при выводе, поэтому обычно скорость DOWN_HL удобно оценивать временем, которое потратится при выводе ВСЕХ строк экрана (это примерно то же самое, что посчитать среднее время исполнения DOWN_HL на строку). Всего на экране 192 строки, поэтому 168 раз DOWN_HL шагнёт оставаясь в том же знакоместе, 21 раз шагнёт из одного ряда знакомест в следующий, и, наконец, 3 раза сменит треть. Поэтому итоговое время исполнения DOWN_HL можно вычислить как 168*27т + 21*59т + 3*49т = 5922т. Запомните это число, оно не раз пригодится нам в дальнейшем.

Сегодня мне хочется поговорить о том, как выглядит DOWN_HL в современном коде, оптимизированном для эффективного вывода графики. Поскольку я говорю об эффективном выводе, лучше сразу забыть о DOWN_HL как подпрограмме вызываемой с помощью CALL DOWN_HL. Объясняю:

DOWN_HL:	inc h : ld a,h : and 7 : ret nz
		ld a,l : add 32 : ld l,a
		ret c
		ld a,h : sub 8 : ld h,a : ret
		; 43/82/63

С учётом того, что сам CALL занимает 17 тактов, шаг вниз внутри знакоместа займёт в этом случае 17 + 4+4+7+11 = 43t, шаг от знакоместа к знакоместу 17 + 4+4+7+5 + 4+7+4 + 5 + 4+7+4+10 = 82т, и шаг в следующую треть 17 + 4+4+7+5 + 4+7+4 + 11 = 63т. Наше общее время для вывода 192 строк выйдет в этом случае 168*43т + 21*82т + 3*63т = 9135т, что в полтора раза медленнее нашей стартовой точки в 5922т. Поэтому в любом быстром коде нужно включать DOWN_HL инлайн, например, задав для этого макрос.

В декабре 2002 года в номере #125 газеты Nicron вышла довольно известная статья Е.Б.Голякова (Spencer Winset, Diamond group, Москва), в которой он показал, что DOWN_HL можно улучшить:

DOWN_HL+:	inc h : ld a,h : and 7 : jr nz,next
		ld a,l : sub -32 : ld l,a
		sbc a
		and #F8 : add h : ld h,a
next:		; 27/56

Время шага вниз внутри знакоместа в этом случае не поменялось — те же самые 4+4+7+12 = 27т. Зато шаг в следующее знакоместо (в т.ч. при смене трети экрана) занимает теперь 4+4+7+7 + 4+7+4+4+7+4+4 = 56т. Итого, при выводе экрана DOWN_HL займёт 168*27т + 24*56т = 5880т. Выигрыш новой процедуры по сути копеечный, 1 — 5880/5922 ~ 0.7%, но факт остаётся фактом. (Стоит отметить, что оценки скорости в статье Голякова подразумевают экран с 167 шагами внутри знакомест, 22 шагами в следующее знакоместо и 2 шагами из трети в треть. Ага, я тоже удивился. Поэтому цифры у меня немного отличны от его цифр, но сути происходящего это не меняет.)

Почему новый вариант DOWN_HL оказался быстрее? В основном потому, что более распространённый случай (переход в следующее знакоместо) ускорен на 3 такта. И хотя самый редкий случай (смена трети) оказался при этом на 7 тактов замедлен, в общей сложности мы выигрываем (в среднем) на каждой трети экрана 3*7т-7т = 14т.

Давайте теперь думать более систематически. Какой случай у нас наиболее важен? Переход вниз внутри знакоместа.

Можно ли ускорить этот случай? Можно, например, сменив первый JR на JP:

DOWN_HL_a:	inc h : ld a,h : and 7 : jp nz,next
		ld a,l : sub -32 : ld l,a
		sbc a
		and #F8 : add h : ld h,a
next:		; 25/59

За один байт мы ускорили шаг внутри знакоместа на 2 такта: 4+4+7+10 = 25т, и замедлили шаг в следующее знакоместо на 3 такта: 4+4+7+10 + 4+7+4+4+7+4+4 = 59т. В случае вывода экрана имеем 168*25т + 24*59т = 5616т, что на 1 — 5616/5922 ~ 5.2% быстрее чем наша стартовая точка.

Как видите, это НАМНОГО существеннее чем выигрыш из статьи Голякова. Можно ли сделать ещё лучше? Разумеется, можно. Чтобы сделать лучше нужно в первую очередь ещё больше ускорить случай шага вниз внутри знакоместа. Например вот так:

DOWN_HL_b:	inc h : ld a,h : and 7 : jr z,nextchar
next:
		...

nextchar:	ld a,l : sub -32 : ld l,a
		sbc a
		and #F8 : add h : ld h,a
		jr next
		; 22/73

Я согласен, что это выглядит не очень красиво, и сделать макрос у нас больше не получится. Но давайте сравним числа: шаг внутри знакоместа 4+4+7+7 = 22т, шаг в следующее — 4+4+7+12 + 4+7+4+4+7+4+4 + 12 = 73т. Итого, для целого экрана получаем 168*22т + 24*73т = 5448т (уже 1 — 5448/5922 ~ 8% быстрее чем было).

Разумеется, с командой JP next вместо команды JR next всё будет ещё быстрее (168*22т + 24*71т = 5400t, быстрее на 8.8%), но по сути от JR next часто можно избавится совсем (я приведу пример чуть ниже), так что мы ещё тут не закончили.

По сути, дальнейшее ускорения шага вниз внутри знакоместа потребует избавления от ld a,h: and 7. Это можно сделать в общем случае развёрнутым кодом для каждой строки знакоместа и хитрым входом в середину такого кода из преамбулы. Такой код не очень сложен, но он перестанет быть DOWN_HL в том смысле, что мы тут обсуждаем, поэтому давайте отложим это упражнение на другой раз.

Лучше подумать о второй по распространённости ситуации: переход через границу знакоместа. При смене знакоместа нам обычно нужно восстанавливать значение H для текущей трети. Именно поэтому DOWN_HL+, ускорившая этот случай, оказалась слегка быстрее чем классическая DOWN_HL. К сожалению, узнать точно, нужно ли восстанавливать H, можно только после того, как мы сдвинем L на следующую строку знакомест, поэтому порядок команд изменить можно едва ли. Тем не менее, слово «восстановить» подсказывает и изящное решение. Давайте сохраним значение H для текущей трети экрана в одном из регистров? Лично мне очень нравится регистр C. Много ли это даст?

DOWN_HL_c:	inc h : ld a,h : and 7 : jr z,charedge
next:
		...

charedge:	ld a,l : add 32 : ld l,a
		jr c,newthird
		ld h,c : jr next	; в C должно лежать "правильное" значение H для текущей трети

newthird:	ld c,h : jr next	; треть сменилась, нужно положить в C новое "правильное" значение
		; 22/65/70

В преамбуле процедуры с таким вариантом DOWN_HL нужно инициализировать C:

ld a,h : and #F8 : ld c,a

Шаг внутри знакоместа так и остался 4+4+7+7 = 22т. Переход в следующее знакоместо происходит теперь на 8 тактов дешевле: 4+4+7+12 + 4+7+4+7 + 4+12 = 65т. Смену трети мне пришлось снова выделить в отдельную ветку, но даже и так она делается быстрее на 3 такта: 4+4+7+12 + 4+7+4+12 + 4+12 = 70т. Итого имеем 168*22т + 21*65т + 3*70т = 5271т (выигрыш на 1 — 5271/5922 ~ 11%). Если сменить обе команды JR next на JP next, получится ещё лучше: 168*22т + 21*63т + 3*68т = 5223т (выигрыш на 1 — 5223/5922 = 11.8%). Т.е., почти ничего не делая, мы ускорили старый замшелый DOWN_HL почти на 12%!

Но и это не совсем ещё предел, потому что мы ещё не обсудили как избавиться от команд JR next. Это проще объяснить на каком-то конкретном примере. Допустим, нам нужно скoпировать в экран достаточно крупный спрайт из линейного буфера. Пусть в DE будет адрес верхнего левого угла спрайта в экране, в HL адрес буфера и в B — количество строк в спрайте. Выводить будем читая данные стеком (это очень поможет в плане освобождения регистра C). Вот вариант решения:

blit_sprite:	ld (.savedsp),sp : ld sp,hl
		ex de,hl
		ld a,h : and #F8 : ld c,a
		jr .mainloop			; 20+6+4 + 4+7+4 + 12 = 57т

.nextthird	ld c,h				; запомнили новую треть
		djnz .mainloop			; тут, кстати, лишний JR тоже по сути пропадает
		jr .theend

.nextchar	ld a,l : add 32 : ld l,a
		jr c, .nextthird
		ld h,c				; восстановили текущую треть
		
		dec b : jr z,.theend		; видите почему не нужен ещё один JR?

.mainloop		ld a,l			; в А удобно хранить младший байт адреса в экране

			DUP N			; N - ширина спрайта в парах знакомест
			pop de
			ld (hl),e : inc l
			ld (hl),d : inc l
			EDUP
			ORG $-1

        	        ld l,a			; адрес восстановлен

	        	inc h : ld a,h : and 7 : jr z, .nextchar

		        djnz .mainloop

.theend		ld sp,0
.savedsp	EQU $-2
		ret

Обработка шага внутри знакоместа тут опять занимает 4+4+7+7 = 22 такта. Шаг в следующее знакоместо потребует 4+4+7+12 + 4+7+4+7 + 4 = 53 такта (причём dec b: jr z,.theend ещё и сберегает такт по сравнению с DJNZ .mainloop). Смена трети обходится дороже, но несущественно: 4+4+7+12 + 4+7+4+12 + 4 = 58 тактов. Что мы получаем в итоге? 168*22т + 21*53т + 3*58т = 4983т. Барьер в 5К тактов на экран пробит. При выводе спрайта высотой с экран такой «размазанный» вариант DOWN_HL сработает на 1 — 4983/5922 ~ 15.6% быстрее чем классический вариант.

В заключение, хочу сказать, что часто предлагают писать процедуры вывода спрайтов используя таблицы адресов строк экрана. Скажу честно, я не очень понимаю, как такие таблицы могут окупаться, если ваш DOWN_HL написан «правильно», как выше. Пусть даже у нас есть такая таблица. Чтобы оправдать отказ от DOWN_HL нужно успевать читать адрес из таблицы (и добавлять к нему сдвиг в экране) менее чем за 4983/192 ~ 26 тактов на строку. 26 тактов — это довольно мало чтобы прочесть адрес и добавить к нему константу. Особенно с учётом того, что тут понадобится найти не один регистр для хранения текущей трети, а два — для текущего адреса в таблице. Особенно с учётом того, что направить на таблицу стек будет расточительно, так как сильно замедлит копирование. Буду рад если кто-то расскажет, как работать с такой таблицей, потому что у меня не получается.

Приложение (или 10 часов спустя).

Нам в редакцию написал RST7 и сообщил, что мы не рассмотрели ещё одну полезную опцию: такой DOWN_HL, при котором во внутреннем цикле остаётся только inc h.

Как такое может быть? Легко, если поручить внутреннему djnz .mainloop всегда рисовать только внутри знакоместа. Конечно, это потребует второго счётчика строк в спрайте, я положу его в C, и это потребует обновления обоих счётчиков по мере движения по экрану. Кроме того, преамбула усложнится из-за того, что нам придётся ловить случай, когда спрайт тонкий, и целиком сидит в текущем знакоместе. Но игра стоит свеч. Вот новая процедура вывода крупного спрайта, реализующая описанный подход:

rst7_sprite:	ld (.savedsp),sp : ld sp,hl : ex de,hl

	; этот метод требует сравнительно сложной преамбулы. требуется следующее:
	; в B должно лежать кол-во строк, которые нужно отрисовать в текущем знакоместе.
	; в C должно лежать кол-во строк, которые нужно отрисовать после отрисовки текущего знакоместа.
	
	ld c,b

	; сколько всего строк осталось в текущем знакоместе?
	ld a,h : or #07 : sub h : inc a : ld b,a

	cp c : jr nc,.thinsprite
	ld a,c : sub b : ld c,a : jr .initloop	; 20+6+4 + 4+4+7+4+4+4 + 4+7 + 4+4+4+12 = 92т
.thinsprite
	ld b,c : ld c,0 : jr .initloop		; 20+6+4 + 4+4+7+4+4+4 + 4+12 + 4+7+12 = 96т

.lastchar	ld b,a : xor a			; счётчики для рисования последних строк

.nextchar	ld c,a
		ld a,l : sub -32 : ld l,a
		sbc a : and #F8 : add h : ld h,a

.initloop	ld a,l

.mainloop		DUP N			; N - ширина спрайта в парах знакомест
			pop de
			ld (hl),e : inc l
			ld (hl),d : inc l
			EDUP
			ORG $-1

        	        ld l,a			; адрес восстановлен

	        	inc h : djnz .mainloop

		ld b,8

		ld a,c : sub b : jp nc,.nextchar	; >=8 строк можно рисовать сразу,
		add b : jr nz,.lastchar			; а вот <8 строк требуют особого подхода

.theend		ld sp,0
.savedsp	EQU $-2
		ret

При шагании внутри знакоместа мы тратим здесь 4 такта. Смена знакоместа, даже с учётом обновления обоих счётчиков, обходится в 4+7+4+4+10 + 4+4+7+4+4+7+4+4 = 67т (как видите, она сделана на базе DOWN_HL+). Конечно, у этого кода более дорогая преамбула (в худшем случае она может потратить до 96-57 = 39 дополнительных тактов). Кроме того, обработка перехода в последнее знакоместо потребует дополнительно 4+12+4+4 = 24т.

Но. При отрисовке спрайта высотой в экран этот блиттер потратит на DOWN_HL всего 168*4 + 24*67 + 39 + 24 = 2343т. Это на 1 — 2343/5922 ~ 60% быстрее чем то, где мы начали, и, кстати, в 2 раза быстрее чем последний вариант приведённый в статье выше. RST7, спасибо, ты рулишь и в 2020 году! :)

31 комментарий

avatar
Как же мы скучали!)
  • sq
  • 0
avatar
Нам повезло получить комментарий по этому поводу от RST7:

«Я думаю, что регистр С надо использовать не для сохранения старшего байта, а в качестве счетчика до перехода на .nextchar. Т.е. в .nextchar будет

LD C,0xF8

a в основном цикле

INC H
INC C
JR Z,.nextchar

Ну и преинит

LD A,H
OR 0xF8
LD C,A

Оно, конечно, ухудшит вариант nextchar на 18 тактов, т.е. суммарно 21*18=378 тактов, но зато 168*7=1176 тактов выиграет на основном переходе.»
avatar
Кроме того, RST7 предложил ещё один подход к реализации DOWN_HL, разбивающий счётчик строк в спрайте на два и в итоге ускоряющий DOWN_HL ещё в 2 раза. Это решение показано в только что добавленном приложении к статье.
avatar
Следующий шаг — постоянный по тактам down_hl без таблиц :)
avatar
Ты у нас сейчас главный мультиколорщик, давай, делись!
avatar
Однозначно круто!
  • VBI
  • 0
avatar
А если так? ;)

        ...

_main1: inc h
_main2: ...
        djnz _main1
        ld b,c        ; c = $20
        add hl,bc
        ld h,(hl)     ; таблицы кусками по 256 байт @ ... $6700, $6800, $6F00, $7000, $7700 ...
        ld b,8
        dec xl        ; счётчик символьных строк вместо занятого c
        jp nz,_main2
        exa           ; zf сохранён на повторный приход сюда
        ld b,a        ; длина хвоста и флаги после and7 при первом входе
        jp nz,_main2  ; если ненулевой хвост и не повторно сюда попали

_end:   ld sp,0
        ret        


Это адаптация из опытов по быстрой отрисовке отрезка (где sp вместо bc применяется) — где-то рядом уже как-то упоминал. Хотя для реальных небольших спрайтов (а не фантастичных на полэкрана) разница по скорости незаметна. Более весомая выгода подобных таблиц на практике — бесплатный вертикальный wrap или clip (перенаправлением в ПЗУ) для окна из 1-3 сегментов.
avatar
Ты конечно знатный извращенец. Действительно, с таблицами такого размера спрайты на полэкрана для тебя и правда фантастичны. На каждом ряде знакомест вместо 67 тактов у тебя выходит 4+11+7+7+8+10 = 47 тактов. 24*20т = 480т (на самом деле, меньше, из-за обработки хвоста). Я бы не стал так делать. Разворот DJNZ даст намного больше скорости и займёт намного меньше памяти.

Но я рад любым идеям, потому что, как ты знаешь сам, приходит день и всё это обязательно пригождается, м.б. в каком-то другом виде.
avatar
Ачо размер? Умеренный, как по мне, плюс еще и генерить очень быстро, где-то даже динамически будет выгодно. Развороту djnz перпендикулярно и не мешает, наоборот — даже чуть проще и быстрее станет после него.
avatar
Вариант без таблиц, но с разбросанными по памяти одиночными байтами, 55 тактов:

    ld b,c
    add hl,bc
    ld b,h
    ld a,(bc)
    ld h,a


Вариант с байтами, собранными рядом в мини-табличку, 57 тактов:

    ld de,$XX20
    add hl,de
    exd
    ld l,d
    ld h,(hl)

(регистр c здесь освободился под счётчик и -4 такта префикса учтены в сумме)
avatar
Спасибо за напоминание, что у нас свободен DE! Но таблица не нужна совсем:
ld de,-8*256+32
add hl,de
bit 0,h : jr nz,.newthird
; 10+11+8+7 = 36t
avatar
Ну т.е. общая скорость та же, что и во втором твоём решении.
avatar
статистически «общая» — всё же чуть помедленнее, и не факт еще, что в сумме короче
avatar
«Чуть помедленнее» — это jr + ld a,h: add 7: ld h,a + jr = 5+15+12 = 32 такта на каждой трети. 3*32т=96т. Ты сейчас всерьёз упарываешься из-за меньше чем 100 тактов?

И что означает «не факт ещё, что в сумме короче»?
avatar
какой смысл в оптимизации вообще, если не упарываться всерьёз? 8)

расстояние в таблице (для всего экрана) от первого нужного байта до последнего 16 байт
с заворачиванием или обрезкой по низу — еще плюс один байт, с обрезкой по верху — еще плюс 8
в твоём случае +7 байт на обработку перехода с обратным jr и больше без него (дубль хвоста)
еще больше с проверкой обрезки, еще больше с заворачиванием
avatar
Обрезки в условиях задачи не было. Поэтому выходят мои 6 байт против твоих 24, прибитых посередине одного из секторов памяти. За 100 тактов. Really?
avatar
у тебя не +6, а +7 без обрезки; у меня 26 с обрезкой, 17 без обрезки
но из них нужны реально лишь 8/5, а промежутки можно использовать
то есть у тебя реально больше места даже без обрезки уйдёт

проиграть и в скорости, и в размере, лишь бы не планировать таблицу, really?

это даже без учёта, что вероятность перехода сегмента может сильно изменяться от геймдизайна
например, сайдскроллер на 2/3 экрана, где в основном движуха по центральной оси
avatar
Тут я, кстати, всё ещё не догоняю, как ты насчитал +7 байт? Я ещё раз посчитал, никак у меня 7 не выходит: ld a,h: add 7: ld h,a: jr…

Про таблицу дошло. Но твой код, где ты будешь пихать байты между байтами своей таблицы я даже представлять себе не хочу. Я бы заплатил и 200 тактов, только чтобы никогда у себя такого не видеть. Но как решение, вообше, ок, почему нет, действительно может пригодиться когда всё будет совсем плохо.
avatar
сравнивай длину, начиная с «ld de,$»

а как любые переменные пихают куда-нибудь, между процедурами, например?
кстати, там рабочую инфу по спрайтам можно хранить — снаружи цикла половина адреса уже в d
avatar
зато нужен лишний код для перехода сегмента, сопоставимый по размеру с таблицей

и да, чтоб не нужно было выполнять лишний inc, прибавлять следует 32-7*256
avatar
Во-первых, мы пока ещё цикл не разворачивали.
Во-вторых, у меня некоторое недоумение. Уточни пожалуйста, сколько точно байт понадобится для таблицы во втором из твоих вариантов кода.
avatar
разворачивание цикла ничего не меняет
avatar
Если бы разворачивание цикла ничего не меняло, ты бы не поправлял мои 32-8*256 на свои 32-7*256.
avatar
совершенно нету связи с поправкой
avatar
Хорошо. Допустим, связи нет. У тебя цикл, делающий inc h внутри (см. последние 2 примера кода в заметке). Почему мой выбор константы в de неправильный?
avatar
потому что 7*inc+add лучше, чем 8*inc+add хоть в развёрнутом, хоть в неразвёрнутом варианте
но если ты к $47XX прибавишь $F820, то получишь $3FZZ/$40ZZ, а не $40ZZ/$48ZZ
avatar
* $40ZZ/$41ZZ
avatar
Я всё ещё не догоняю, как ты собираешься сделать 7 инков внутри цикла который повторяется 8 раз.
avatar
не заметил штоле две точки входа?
avatar
Конечно не заметил; смотрел применительно к своему коду, а не к твоему. Забавная идея про 2 точки входа!
avatar
кошкин ёж, не тот код запостил во втором варианте, там должно быть

	ld de,$XX20☺
	add hl,de
	ld e,h
	ld a,(de)
	ld h,a

Хотя уже неважно, ведь оказалось, можно еще быстрее. Я как-то проглядел, что там же в аккумуляторе хранится исходный младший байт адреса! В связи с этим можно переписать:

		...
		ld a,l
		jp _loop3

_xrow1		ld b,8
_xrow2		add 32
		ld l,h
		ld h,$XX
		ld h,(hl)
		jp nc,_loop2
		ld h,l

_loop1		inc h
_loop2		ld l,a
_loop3		DUP...EDUP
		djnz _loop1

		dec c
		jp p,_xrow1
		ld l,a
		exa
		ld b,a
		ld a,l
		jr nz,_xrow2

		ld sp,0
		ret

«чистый» код down_hl (с _xrow2 по _loop1 включительно) на всю высоту экрана сожрёт 1493 такта
если жаба не задушит продублировать кусок _loop2...djnz — можно сократить заменой jp на jr до 1398
это с маленькой таблицей, а без таблиц у меня теперь получилось 1556 «чистых» тактов:

		...
_xrow2		add 32
		jr c,_loop1
		ld l,a
		ld a,h
		sub b
		ld h,a
		ld a,l

_loop1		inc h
		...
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.