Важная информация

User Tag List

Страница 1 из 2 12 ПоследняяПоследняя
Показано с 1 по 10 из 18

Тема: Оптимизация Z80-кода для Мандельброта

  1. #1
    Master
    Регистрация
    16.12.2014
    Адрес
    г. Ожерелье
    Сообщений
    530
    Спасибо Благодарностей отдано 
    153
    Спасибо Благодарностей получено 
    17
    Поблагодарили
    17 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию Оптимизация 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

  2. Этот пользователь поблагодарил litwr за это полезное сообщение:

    Oleg N. Cher (29.11.2021)

  3. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  4. #2
    Master
    Регистрация
    03.07.2021
    Адрес
    г. Кировск
    Сообщений
    510
    Спасибо Благодарностей отдано 
    40
    Спасибо Благодарностей получено 
    86
    Поблагодарили
    76 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от litwr Посмотреть сообщение
    Код:
        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.
    Это не вникая в тонкости алгоритма, просто по конкретным кускам кода.

  5. Эти 2 пользователя(ей) поблагодарили reddie за это полезное сообщение:

    ALS (02.12.2021), litwr (01.12.2021)

  6. #3
    Master
    Регистрация
    16.12.2014
    Адрес
    г. Ожерелье
    Сообщений
    530
    Спасибо Благодарностей отдано 
    153
    Спасибо Благодарностей получено 
    17
    Поблагодарили
    17 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от reddie Посмотреть сообщение
    Если имелось в виду 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.

  7. #4
    Master
    Регистрация
    03.07.2021
    Адрес
    г. Кировск
    Сообщений
    510
    Спасибо Благодарностей отдано 
    40
    Спасибо Благодарностей получено 
    86
    Поблагодарили
    76 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от litwr Посмотреть сообщение
    индексы могут быть отрицательными. Оптимизация 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 тоже нужно что-то поменять, если там дальше работа со стеком.
    Последний раз редактировалось reddie; 02.12.2021 в 14:53.

  8. Эти 2 пользователя(ей) поблагодарили reddie за это полезное сообщение:

    ALS (02.12.2021), litwr (02.12.2021)

  9. #5
    Master
    Регистрация
    16.12.2014
    Адрес
    г. Ожерелье
    Сообщений
    530
    Спасибо Благодарностей отдано 
    153
    Спасибо Благодарностей получено 
    17
    Поблагодарили
    17 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от reddie Посмотреть сообщение
    Ясно. Писал, не вникая в алгоритм. А какой вообще размер таблицы корней? Если возможно растянуть ее в два раза - действие со сбросом бита 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.
    Я несколько изменил исходный код для БК, сделал так, чтобы теперь текстуры рисовались без изъяна - это сделало код на несколько байт больше и немного замедлило. Кроме того, добавил остановку после отрисовки очередной картинки.
    Таблицы квадратов занимают 11К и если их увеличить вдвое, то вместо зануления бита придётся делать сдвиг.
    mandelbrot-amstrad.zip
    Последний раз редактировалось litwr; 02.12.2021 в 22:26.

  10. #6
    Master
    Регистрация
    03.07.2021
    Адрес
    г. Кировск
    Сообщений
    510
    Спасибо Благодарностей отдано 
    40
    Спасибо Благодарностей получено 
    86
    Поблагодарили
    76 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от litwr Посмотреть сообщение
    Таблицы квадратов занимают 11К
    Какая-то "некруглая" цифра =) Обычно выравнивают по блокам: 4К, 8К и т. д. Я к тому, что растянуть бы её на блок 16К или 32К, если память не жмет - это может упростить выборку. Вернее, фиксацию диапазона сразу через биты hl.

  11. #7
    Master
    Регистрация
    16.12.2014
    Адрес
    г. Ожерелье
    Сообщений
    530
    Спасибо Благодарностей отдано 
    153
    Спасибо Благодарностей получено 
    17
    Поблагодарили
    17 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от reddie Посмотреть сообщение
    Какая-то "некруглая" цифра =) Обычно выравнивают по блокам: 4К, 8К и т. д. Я к тому, что растянуть бы её на блок 16К или 32К, если память не жмет - это может упростить выборку. Вернее, фиксацию диапазона сразу через биты hl.
    Не понял, как можно упростить выборку? Таблица для FP-величин, поэтому наверное и не имеет нормального целого размера, на самом деле там почти 11.5 К. У Амстрада дополнительные 11 К - это не проблема, знать бы только как их задействовать...
    Похоже код уже заоптимизирован до предела, пришлось даже несколько его притормозить, так как нужно сбрасывать перенос перед SBC...

  12. #8
    Master
    Регистрация
    03.07.2021
    Адрес
    г. Кировск
    Сообщений
    510
    Спасибо Благодарностей отдано 
    40
    Спасибо Благодарностей получено 
    86
    Поблагодарили
    76 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от litwr Посмотреть сообщение
    как можно упростить выборку?
    Ну тут два пути. Не вдаваясь в подробности алгоритма, т.к. все равно в этом дельброте не секу.
    Допустим, таблица данных (пока условная) занимает 32К и лежит с #8000 до верха. Приращение (прыжок по таблице) может быть любым числом, как в плюс, так и в минус.
    Чтобы значение не опускалось ниже #8000, в т.ч. при переходе выше #FFFF, достаточно дать команду SET 7,H вместо нескольких команд проверок через аккумулятор.
    Основная задача при таком подходе - корректные адреса выборки данных: массив должен быть "подогнан" под размер блока, в данном случае это 32Кб.
    Второй вариант - данные распределены так, что получаемые значения всегда четные (данные идут по 2 байта). Тогда не нужна команда RES 0,L - а она три раза есть в коде.
    Подойдет ли что из этого для реализации - сказать не могу, но прикинуть стоит.

  13. #9
    Veteran
    Регистрация
    01.03.2005
    Адрес
    Новосибирск
    Сообщений
    1,841
    Спасибо Благодарностей отдано 
    35
    Спасибо Благодарностей получено 
    143
    Поблагодарили
    51 сообщений
    Mentioned
    4 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Можете выложить арихив с автосборкой (исходники + ассебмлер + эмуль) ?

    По алгоритму. мне кажется или можно одну команду res выкинуть? ещё jr в конце заменить на jp + 2 такта даст.

  14. #10
    Master
    Регистрация
    16.12.2014
    Адрес
    г. Ожерелье
    Сообщений
    530
    Спасибо Благодарностей отдано 
    153
    Спасибо Благодарностей получено 
    17
    Поблагодарили
    17 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от reddie Посмотреть сообщение
    Ну тут два пути. Не вдаваясь в подробности алгоритма, т.к. все равно в этом дельброте не секу.
    Допустим, таблица данных (пока условная) занимает 32К и лежит с #8000 до верха. Приращение (прыжок по таблице) может быть любым числом, как в плюс, так и в минус.
    Чтобы значение не опускалось ниже #8000, в т.ч. при переходе выше #FFFF, достаточно дать команду SET 7,H вместо нескольких команд проверок через аккумулятор.
    Основная задача при таком подходе - корректные адреса выборки данных: массив должен быть "подогнан" под размер блока, в данном случае это 32Кб.
    Второй вариант - данные распределены так, что получаемые значения всегда четные (данные идут по 2 байта). Тогда не нужна команда RES 0,L - а она три раза есть в коде.
    Подойдет ли что из этого для реализации - сказать не могу, но прикинуть стоит.
    Но вроде к нашему случаю так не получится...

    - - - Добавлено - - -

    Цитата Сообщение от drbars Посмотреть сообщение
    Можете выложить арихив с автосборкой (исходники + ассебмлер + эмуль) ?

    По алгоритму. мне кажется или можно одну команду res выкинуть? ещё jr в конце заменить на jp + 2 такта даст.
    Проверил все три RES - они нужны все. По циклам в Амстраде всё просто - там Z80 всегда получает такты ровно по 4, поэтому 10- и 12-тактовые команды исполняются за 12 тактов.

    Требуемого архива, к сожалению, нет. Могу только дать ссылки на используемые компоненты:

    1) ассемблер pasmo6, он довольно популярен среди амстрадовцев - https://pasmo.speccy.org/ - он даже пакетом в Ubuntu есть;
    2) эмулятор, использую не самые популярный, но весьма неплохой - https://www.emutopia.com/index.php/e...c/515-ep128emu .

    И больше ничего и не надо. Компилируем командой pasmo6 FILE.asm FILE.bin - этот bin потом грузим в дебаггер эмулятора командой l "FILE.bin" 0 4000, затем запускаем там же через G4000. Таким образом, ничего амстрадовского знать и не нyжно. Но если возникнут вопросы, готов помогать. Хотя почти уверен, что лучше код уже сделать невозможно. Доделываю код для Коммодора - там и по размеру и по скорости всё раза в два хуже, чем на Амстраде, - это верный признак, что код для Z80 очень хорошо оптимизирован.
    Последний раз редактировалось litwr; 07.12.2021 в 21:56.

Страница 1 из 2 12 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Оптимизация Conway's Game of Life для Z80
    от blackmirror в разделе Программирование
    Ответов: 1
    Последнее: 10.01.2022, 20:47
  2. Ответов: 28
    Последнее: 01.01.2017, 14:28
  3. Ответов: 22
    Последнее: 30.03.2015, 04:52
  4. Оптимизация в HL
    от drbars в разделе Программирование
    Ответов: 33
    Последнее: 22.08.2013, 17:56
  5. Шифр AES-128: компактная реализация для Z80 (1001 байт кода)
    от Barmaley_m в разделе Программирование
    Ответов: 7
    Последнее: 18.03.2013, 00:30

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •