Просмотр полной версии : Оптимизация Z80-кода для Мандельброта
У меня вопрос скорее по Z80, чем по Спектруму. Но предположил, что лучших знатоков z80 скорее можно встретить только тут.
Недавно на pouet было выложено интро для БК, размером 242 байта, которое шустро строит Мандельброты - https://www.pouet.net/prod.php?which=87739
Решил портануть этот код на Амстрад. Получилось почти 500 байт и процентов на 60% медленнее, чем БК0010. На Спек не получится, так как интро использует весь экран БК, реализуя 128х256 графику с 2х1 текстурами. Для Амстрада сделал два кода. Аналогичный с текстурами и с 16 цветами. Oбращение к видеопамяти на Амстраде существенно сложнее и поэтому несколько тормознее, чем на многих других платформах. Но главный тормоз не здесь, а в самом алгоритме расчета Мандельброта. На БК главный цикл занимает 14 строк
1$:
mov sqr(r1), r3 ; r3 = y^2
add r0, r1 ; r1 = x+y
mov sqr(r0), r0 ; r0 = x^2
add r3, r0 ; r0 = x^2+y^2
cmp r0, r6 ; if r0 >= 4.0 then
bge 2$ ; overflow
mov sqr(r1), r1 ; r1 = (x+y)^2
sub r0, r1 ; r1 = (x+y)^2-x^2-y^2 = 2*x*y
add r5, r1 ; r1 = 2*x*y+b, updated y
sub r3, r0 ; r0 = x^2
sub r3, r0 ; r0 = x^2-y^2
add r4, r0 ; r0 = x^2-y^2+a, updated x
sob r2, 1$ ; to next iteration
Для Z80 у меня получилось кода заметно больше
loc1:
r1 equ $+1
ld hl,0
ld a,l
and $fe
ld l,a
ld a,high(sqrbase)
add a,h
ld h,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a
ex de,hl ;de = r3 = sqr[r1&0xfffe]
pop bc ;r0
ld hl,(r1)
add hl,bc
ld (r1),hl ;r1 += r0
ld h,b
ld a,c
and $fe
ld l,a
ld a,high(sqrbase)
add a,h
ld h,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;r0 = sqr[r0&0xfffe]
add hl,de
push hl ;r0 += r3
ld a,h
cp 8
jr nc,loc2
ld hl,(r1)
ld a,high(sqrbase)
add a,h
ld h,a
ld a,l
and $fe ;sets C=0
ld l,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;r1 = sqr[r1&0xfffe]
pop bc ;r0
push bc
sbc hl,bc ;C=0
r5 equ $+1
ld bc,0
add hl,bc
ld (r1),hl
pop hl
r4 equ $+1
ld bc,0
add hl,bc ;r0 += r4
sbc hl,de ;r0 -= r3
sbc hl,de
push hl ;r0 -= r3
ld hl,tniter
dec (hl) ;r2
jr nz,loc1
На 8-битных вычислениях Спек обычно несколько быстрее БК. Но на интенсивных 16-битных расчётах БК похоже заметно быстрее при гораздо лучшей компактности кода. Могу ещё предположить, что на таких расчётах 6502 будет выглядеть совсем бледно. Буду очень признателен, если кто-нибудь найдет способ сделать главный цикл расчёта Мандельброта быстрее и/или компактнее.
В архиве исходники и бинарники для Амстрада. В эмуляторе запуск через RUN"M4 или RUN"M16 :)
76547
ld a,l
and $fe
ld l,a
ld a,high(sqrbase)
Если имелось в виду and #fe - достаточно одной команды res 0,l вместо трех.
ld a,high(sqrbase)
add a,h
ld h,a
ld a,l
and $fe ;sets C=0
ld l,a
ld a,(hl)
Здесь аналогично. Флаг переноса и так будет сброшен после команды add a, h - ведь там, полагаю, переполнения не происходит никогда, раз устанавливается смещение к таблице, а значение регистра h перед этим сбрасывается, если превысило 8. Если правильно понял этот момент - можно упростить ещё одну проверку:
push hl ;r0 += r3
ld a,h
cp 8
jr nc,loc2
Если значение h не должно превышать восемь - достаточно команды bit 3,h ну и переход по jr nz вместо jr nc.
Это не вникая в тонкости алгоритма, просто по конкретным кускам кода.
Если имелось в виду and #fe - достаточно одной команды res 0,l вместо трех.
ld a,high(sqrbase)
add a,h
ld h,a
ld a,l
and $fe ;sets C=0
ld l,a
ld a,(hl)
Здесь аналогично. Флаг переноса и так будет сброшен после команды add a, h - ведь там, полагаю, переполнения не происходит никогда, раз устанавливается смещение к таблице, а значение регистра h перед этим сбрасывается, если превысило 8. Если правильно понял этот момент - можно упростить ещё одну проверку:
push hl ;r0 += r3
ld a,h
cp 8
jr nc,loc2
Если значение h не должно превышать восемь - достаточно команды bit 3,h ну и переход по jr nz вместо jr nc.
Это не вникая в тонкости алгоритма, просто по конкретным кускам кода.
Благодарю вас. Оптимизации 1 экономит 8 тактов - очень ценная подсказка. К сожалению, оптимизация 2 даст только 4 такта, так как придется специально сбрасывать перенос - индексы могут быть отрицательными. Оптимизация 3 не сработает, так как в h может быть, например, возможно 16.
индексы могут быть отрицательными. Оптимизация 3 не сработает, так как в h может быть, например, возможно 16.
Ясно. Писал, не вникая в алгоритм. А какой вообще размер таблицы корней? Если возможно растянуть ее в два раза - действие со сбросом бита 0,L вообще не потребуется.
Еще можно ускорить "регистр R0", и уже побольше, чем на 8 тактов. В исходном коде он сохраняется в BC через стек, строки обмена со стеком выделены красным:
loc1:
r1 equ $+1
ld a,l
and $fe
ld l,a
ld a,high(sqrbase)
add a,h
ld h,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a
ex de,hl ;de = r3 = sqr[r1&0xfffe]
pop bc ;r0
ld hl,(r1)
add hl,bc
ld (r1),hl ;r1 += r0
ld h,b
ld a,c
and $fe
ld l,a
ld a,high(sqrbase)
add a,h
ld h,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;r0 = sqr[r0&0xfffe]
add hl,de
push hl ;r0 += r3
ld a,h
cp 8
jr nc,loc2
ld hl,(r1)
ld a,high(sqrbase)
add a,h
ld h,a
ld a,l
and $fe ;sets C=0
ld l,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;r1 = sqr[r1&0xfffe]
pop bc ;r0
push bc
sbc hl,bc ;C=0
r5 equ $+1
ld bc,0
add hl,bc
ld (r1),hl
pop hl
r4 equ $+1
ld bc,0
add hl,bc ;r0 += r4
sbc hl,de ;r0 -= r3
sbc hl,de
push hl ;r0 -= r3
ld hl,tniter
dec (hl) ;r2
jr nz,loc1
Кроме одной пары push-pop, все остальные можно убрать, заменив прямой загрузкой регистров, это быстрее. Модификация будет выглядеть так (зеленым замены and #fe на res 0,l):
loc1:
r1 equ $+1
ld hl,0
res 0,l
ld a,high(sqrbase)
add a,h
ld h,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a
ex de,hl ;de = r3 = sqr[r1&0xfffe]
;pop bc не нужно вообще - в конце цикла значение остается в паре, убираем
ld hl,(r1)
add hl,bc
ld (r1),hl ;r1 += r0
ld h,b
ld l,c
res 0,l
ld a,high(sqrbase)
add a,h
ld h,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;r0 = sqr[r0&0xfffe]
add hl,de
ld b,h ;r0 += r3
ld c,l
ld a,h
cp 8
jr nc,loc2
ld hl,(r1)
ld a,high(sqrbase)
add a,h
ld h,a
res 0,l
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;r1 = sqr[r1&0xfffe]
;pop bc убираем - значение уже в паре. push придется оставить ;r0
push bc
and a ;sets C=0
sbc hl,bc
r5 equ $+1
ld bc,0
add hl,bc
ld (r1),hl
pop hl
r4 equ $+1
ld bc,0
add hl,bc ;r0 += r4
sbc hl,de ;r0 -= r3
sbc hl,de
ld b,h ;r0 -= r3, загружаем регистры вместо push
ld c,l
ld hl,tniter
dec (hl) ;r2
jr nz,loc1
Кроме того, цикл задается переменной в ячейке (hl), это значит, что он 256 или меньше. Можно задавать цикл в половинке регистра IX, а конец цикла оптимизировать:
;ld hl,tniter - убираем вообще
dec lx ;r2
jr nz,loc1
Останется подкорректировать код вне приведенного алгоритма, т.к. в его начале делается pop, и как-то значение туда попадало перед циклом.
И, возможно, при срабатывании условного перехода на loc2 тоже нужно что-то поменять, если там дальше работа со стеком.
Ясно. Писал, не вникая в алгоритм. А какой вообще размер таблицы корней? Если возможно растянуть ее в два раза - действие со сбросом бита 0,L вообще не потребуется.
Убрать R0 из стека - это реально круто, сам бы не догадался. Использовать IXL тоже хорошая идея, но это было просто - подправил ещё вчера. Итак, внес предложенные оптимизации и добавил некоторые свои - это разогнало на примерно 15%. Теперь код основного цикла такой:
loc1:
ld d,h
ld e,l
res 0,l
ld a,high(sqrbase)
add a,h
ld h,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a
ex de,hl ;de = r3 = sqr[r1&0xfffe]
add hl,bc ;r1 += r0
ld a,b
ld b,h
ld h,a
ld a,c
ld c,l
ld l,a
res 0,l
ld a,high(sqrbase)
add a,h
ld h,a
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;r0 = sqr[r0&0xfffe]
add hl,de
ld a,h
cp 8
jr nc,loc2
push hl ;r0 += r3
ld h,b
ld l,c
ld a,high(sqrbase)
add a,h
ld h,a
res 0,l
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;r1 = sqr[r1&0xfffe]
r5 equ $+1
ld bc,0
add hl,bc ;add r5, r1 ;sets C=0
pop bc ;r0
sbc hl,bc ;sub r0, r1
push hl
r4 equ $+1
ld hl,0
add hl,bc ;r0 += r4
sbc hl,de ;r0 -= r3
sbc hl,de
ld b,h ;r0 -= r3
ld c,l
pop hl
dec ixh
jr nz,loc1
Теперь Амстрад строит первые картинки даже быстрее БК0010, но с ростом числа итераций "букашка" опять выходит вперед. Например, восьмую картинку Амстрад строит за 12.0 сек (11.9 для варианта в 16 цветах), а БК за 9.8 сек. А вот и сами картинки N8 (litwr2.github.io/mandelbrot8/mandelbrot.html).
Я несколько изменил исходный код для БК, сделал так, чтобы теперь текстуры рисовались без изъяна - это сделало код на несколько байт больше и немного замедлило. Кроме того, добавил остановку после отрисовки очередной картинки.
Таблицы квадратов занимают 11К и если их увеличить вдвое, то вместо зануления бита придётся делать сдвиг.
76583
Таблицы квадратов занимают 11К
Какая-то "некруглая" цифра =) Обычно выравнивают по блокам: 4К, 8К и т. д. Я к тому, что растянуть бы её на блок 16К или 32К, если память не жмет - это может упростить выборку. Вернее, фиксацию диапазона сразу через биты hl.
Какая-то "некруглая" цифра =) Обычно выравнивают по блокам: 4К, 8К и т. д. Я к тому, что растянуть бы её на блок 16К или 32К, если память не жмет - это может упростить выборку. Вернее, фиксацию диапазона сразу через биты hl.
Не понял, как можно упростить выборку? Таблица для FP-величин, поэтому наверное и не имеет нормального целого размера, на самом деле там почти 11.5 К. У Амстрада дополнительные 11 К - это не проблема, знать бы только как их задействовать...
Похоже код уже заоптимизирован до предела, пришлось даже несколько его притормозить, так как нужно сбрасывать перенос перед SBC...
как можно упростить выборку?
Ну тут два пути. Не вдаваясь в подробности алгоритма, т.к. все равно в этом дельброте не секу.
Допустим, таблица данных (пока условная) занимает 32К и лежит с #8000 до верха. Приращение (прыжок по таблице) может быть любым числом, как в плюс, так и в минус.
Чтобы значение не опускалось ниже #8000, в т.ч. при переходе выше #FFFF, достаточно дать команду SET 7,H вместо нескольких команд проверок через аккумулятор.
Основная задача при таком подходе - корректные адреса выборки данных: массив должен быть "подогнан" под размер блока, в данном случае это 32Кб.
Второй вариант - данные распределены так, что получаемые значения всегда четные (данные идут по 2 байта). Тогда не нужна команда RES 0,L - а она три раза есть в коде.
Подойдет ли что из этого для реализации - сказать не могу, но прикинуть стоит.
Можете выложить арихив с автосборкой (исходники + ассебмлер + эмуль) ?
По алгоритму. мне кажется или можно одну команду res выкинуть? ещё jr в конце заменить на jp + 2 такта даст.
Ну тут два пути. Не вдаваясь в подробности алгоритма, т.к. все равно в этом дельброте не секу.
Допустим, таблица данных (пока условная) занимает 32К и лежит с #8000 до верха. Приращение (прыжок по таблице) может быть любым числом, как в плюс, так и в минус.
Чтобы значение не опускалось ниже #8000, в т.ч. при переходе выше #FFFF, достаточно дать команду SET 7,H вместо нескольких команд проверок через аккумулятор.
Основная задача при таком подходе - корректные адреса выборки данных: массив должен быть "подогнан" под размер блока, в данном случае это 32Кб.
Второй вариант - данные распределены так, что получаемые значения всегда четные (данные идут по 2 байта). Тогда не нужна команда RES 0,L - а она три раза есть в коде.
Подойдет ли что из этого для реализации - сказать не могу, но прикинуть стоит.
Но вроде к нашему случаю так не получится...
- - - Добавлено - - -
Можете выложить арихив с автосборкой (исходники + ассебмлер + эмуль) ?
По алгоритму. мне кажется или можно одну команду res выкинуть? ещё jr в конце заменить на jp + 2 такта даст.
Проверил все три RES - они нужны все. По циклам в Амстраде всё просто - там Z80 всегда получает такты ровно по 4, поэтому 10- и 12-тактовые команды исполняются за 12 тактов.
Требуемого архива, к сожалению, нет. Могу только дать ссылки на используемые компоненты:
1) ассемблер pasmo6, он довольно популярен среди амстрадовцев - https://pasmo.speccy.org/ - он даже пакетом в Ubuntu есть;
2) эмулятор, использую не самые популярный, но весьма неплохой - https://www.emutopia.com/index.php/emulators/item/311-amstrad-cpc/515-ep128emu .
И больше ничего и не надо. Компилируем командой pasmo6 FILE.asm FILE.bin - этот bin потом грузим в дебаггер эмулятора командой l "FILE.bin" 0 4000, затем запускаем там же через G4000. Таким образом, ничего амстрадовского знать и не нyжно. :) Но если возникнут вопросы, готов помогать. Хотя почти уверен, что лучше код уже сделать невозможно. Доделываю код для Коммодора - там и по размеру и по скорости всё раза в два хуже, чем на Амстраде, - это верный признак, что код для Z80 очень хорошо оптимизирован.
Но вроде к нашему случаю так не получится...
2) эмулятор, использую не самые популярный, но весьма неплохой - https://www.emutopia.com/index.php/emulators/item/311-amstrad-cpc/515-ep128emu .
"Из коробки" эмуль не заработал... видимо нехватает каких-то ромов. Вопрос был в том, чтобы автосборка была с автозапуском. Выходить в дебаггер и загружать через него для отладки не очень удобно. Есть такая возможность?
"Из коробки" эмуль не заработал... видимо нехватает каких-то ромов. Вопрос был в том, чтобы автосборка была с автозапуском. Выходить в дебаггер и загружать через него для отладки не очень удобно. Есть такая возможность?
Извиняюсь, почему-то сложилось впечатление, что ромы были включены. Сейчас немало эмуляторов идут с встроенными ромами. Прикреплю файлик - распаковать в папку roms. Автазапуска у Amstrad CPC нет - загрузку с диска надо делать через команду, которую приводил ранее. Более того такой путь потребует работы с образами дисков... Честно, озадачили вы меня фразой, что через дебаггер неудобно. Наберите приведенную команду в блокноте и копипастите её в дебаггер одним кликом - что ещё может быть удобнее, совершенно не могу представить.
Наберите приведенную команду в блокноте и копипастите её в дебаггер одним кликом - что ещё может быть удобнее, совершенно не могу представить.
Спасибо за roms, порой найти их непросто.
По сборке проекта, на спектруме, для примера, популярен кросс-ассемблер sjasm. Он позволяет сохранить откомпилированный образ в формате снапошота, который эмулятор может запускать автоматически. Т.к. программа может быть довольно объёмной и загружать бинарники вручную после каждой компиляции крайне не удобно. Может ли pasmo создавать такие спапшот образы?
- - - Добавлено - - -
76619
Чего-то ещё нехватает, не запускается эмулятор к сожалению. Видимо придётся искать более dev ориентированный эмулятор :(
Спасибо за roms, порой найти их непросто.
По сборке проекта, на спектруме, для примера, популярен кросс-ассемблер sjasm. Он позволяет сохранить откомпилированный образ в формате снапошота, который эмулятор может запускать автоматически. Т.к. программа может быть довольно объёмной и загружать бинарники вручную после каждой компиляции крайне не удобно. Может ли pasmo создавать такие спапшот образы?
Чего-то ещё нехватает, не запускается эмулятор к сожалению. :( Видимо придётся искать более dev ориентированный эмулятор :(
Извиняюсь, прямо беда какая-то с этими ромами. Архив получился битый - как такое могло случиться?! :( Там всего два файла cpc6128.rom и cpc_amsdos.rom - с ними всё должно работать. Только там эмуль не только Амстрада, а ещё и Спека и Энтерпрайза. По умолчанию запускается Энтерпрайз, для Амстрада надо указывать опцию -cpc. Эмулятор возможно не лучший для начинающих Амстрадовцев. :) Сам то я с Амстрадами знаком с 1988... Но меня этот эмуль устраивает, пробовал ещё MAME/MESS - вроде работает, но там много всякого лишнего и эмуляция иногда для некоторых платформ с проблемами. Люди хвалят Арнольда, но с ним не работал.
Конечно, получить снэпшот сразу это наверное оптимально, но пасмо так не умеет. Это не чисто Амстрадовский ассемблер. С другой стороны, то что вам предложил - это практически одно и то же. Со снэпшотом: 1) щелкаем на load snapshot; 2) выбираем его и активируем. Мой вариант: 1) щелкаем на дебаггер; 2) копипастим текст. Выбирать мышкой снапшот дольше, чем копипастить. :) Конечно, снапшот можно указать и в командной строке - тут мы можем сэкономить 1-2 секунды, но если захотим перезапустить, то через дебаггер быстрее.
Oчень сомневаюсь, что после reddie кто-то что-то сможит что-то улучшить...
76641
Кстати, выложил все исходники на гитхабе (https://github.com/litwr2/rosetta-mandelbrot/tree/main/cpc) - там в главном цикле ничего нового нет, только добавил сбросы переносов.
Ещё добавлю, что в состав эмулятора ep128emu входит и отличный конвертор картинок - весьма вкусная плюшка. :)
сомневаюсь, что после reddie кто-то что-то сможит что-то улучшить...
А вдруг =) тем более я не вникал алгоритм, а лишь оптимизировал то, что видел "лишнее" в коде. Зная размеры таблиц, получаемые значения и прочие тонкости, вполне возможно, получится переработать сам алгоритм, а не сокращать кусочки кода. Желающие могут попробовать.
Выложил Мандельброта на амстрадовский форум. Они там даже видео сделали с реальной машинки или точнее даже с двух одновременно - https://www.youtube.com/watch?v=zCm-6tUHJzM :) А тут всем спасибо за поддержку, почти догнали существенно более дорогой компик, BBC Micro.
Так что дальнейшая оптимизация потребует нового релиза... Но чисто спортивно интересно, что можно тут максимально выжать из Z80. Оптимизация кода Z80, по моему опыту, может длиться почти бесконечно. :)
Удалось сделать код возможно совершенным. Кстати, понял как можно использовать болеe быстрый доступ к массиву через SET - пришлось переконфигурировать Амстрад для этого, превращать его в почти Спектрум.
loc1:
push hl
res 0,l
set 7,h
ld c,(hl)
inc l
ld b,(hl) ;mov sqr(r1), r3
pop hl
add hl,de ;add r0, r1
ex de,hl ;de - r1, hl - r0, bc - r3
res 0,l
set 7,h
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;mov sqr(r0), r0
add hl,bc ;add r3, r0
ld a,h
and $f8
jr nz,loc2
push hl
sbc hl,bc ;x^2 ;set C=0
sbc hl,bc ;x^2-y^2
r4 equ $+1
ld bc,0
add hl,bc ;x^2-y^2+x0
ex de,hl ;de - r0, hl - r1
set 7,h
res 0,l
ld a,(hl)
inc l
ld h,(hl)
ld l,a ;(x+y)^2
r5 equ $+1
ld bc,0
add hl,bc ;sets C=0
pop bc ;r0
sbc hl,bc ;2xy+y0
dec ixh
jr nz,loc1 ;sob r2,1$
Предполагаю, улучшить тут что-то уже скорее невозможно. Даже по размерам (54 байта) код стал близок к кодам для x86 и 68k (46 байт). Этот код обгоняет даже код для Спектрума автора исходной программы, где используется SP - https://github.com/smaslovski/foobar
Но БК0010 всё ещё быстрее, но только на 1.5%. Зато BBC Micro теперпь отстаёт от Амстрада почти на 10%.
Таким образом, с помощью знатоков Z80 удалось разогнать код для Амстрада более, чем на 20%. Всем спасибо.
понял как можно использовать болеe быстрый доступ к массиву через SET
Да, про это и говорил: подгоняем таблицу данных до определённых адресов, взамен получая "ограничитель" всего из одной команды SET. Что куда быстрее и компактнее проверок через аккумулятор с перезагрузками.
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot