1

Temat: quiz Maroka

Marok na sasiednim forum zaproponowal konkurs:

https://atarionline.pl/forum/comments.p … amp;page=1

ktos ma jakies inne rozwiazanie?

1 poke 1536,0:x=2
2 f.y=0 to x-1:a=not(peek(1536+y)):poke(1536+x+y),a:n.y:x=x*2:if x<128 then g.2
3 f.x=0 to 128:? peek(1536+x);:n.x

---
i zgrabniej:

1 dim a(255):x=1:c=0:a(0)=c
2 f.y=0 to x-1:b=a(y):c=c+1:a(c)=not(b):? chr$(a(c-1)*128+32);:n.y:x=x*2:if c<128 then g.2

Ostatnio edytowany przez xxl (2022-12-24 19:49:10)

Post's attachments

Bez tytułu.png 15.12 kb, nikt jeszcze nie pobierał tego pliku. 

Tylko zalogowani mogą pobierać załączniki.
http://atari.pl/hsc/ad.php?i=1.

2

Odp: quiz Maroka

Ja tak na to patrzyłem, i stwierdziłem, że to może być wszystko. No i było:)
Jest to bit nieparzystości dla danych 0..255.

3

Odp: quiz Maroka

zwykly xor od poczatku lancucha, kazdy kolejny czastkowy lancuch ma dlugosc kolejnej potegi 2. nie takie rzeczy.... ;-)

ten drugi program sprawdzilem a pierwszy napisalem z pamieci i pewnie nie dziala ;-)

http://atari.pl/hsc/ad.php?i=1.

4

Odp: quiz Maroka

Kiedyś... dawno, dawno temu... w czasach gdy na ziemi jeszcze pamięci FLASH nie było i gdy mikrokontrolery (MCU) miały okienko do kasowania promieniami UV, a 6502 było całkim szybkim CPU parzystość liczyłem w ten sposób:

parity  sta    v
    
        lda    #0
        sta    p
    
        lda    v
        beq    endp

loop    inc    p
        lda    v
        dec    v
        and    v
        sta    v
        bne    loop
    
endp    lda    p
        and    #1
        rts

a jak trzeba było mieć wynik ultra-szybko to się robiło look_up_table (LUT):

        ldy    #0

l0      tya
        jsr    parity
        sta    p_lut,y
    
        iny
        bne l0

i potem obliczenie parzystości danego bajtu było trywialne i szybkie, bo wystarczyło sięgnąć do tabelki.

Aby uzyskać wzór który wygenerował marok wystarczy albo skorzystać z p_lut, albo skorzystać z procedury parity:

        ldy    #0

l1      tya
        lda    p_lut,y

;       jsr    parity         ; --> gdy nie chcemy korzystać z look-up-table

        lsr    @
        ror    @
        sta    ($58),y
    
        iny    
        bne    l1

        lda    #$21
        sta    $22f

Jeżeli nie używamy LUT, to czas wykonania procedury "parity" jest oczywiście zależny od liczby "ustawionych" bitów w bajcie.

Oczywiście pomysł algorytmu nie był mój, podpatrzyłem go w jakimś artykule o programowaniu w C i przeniosłem sobie ten kod na assembler 6502. O ile dobrze pamiętam to powyższy algorytm bazował na sposobie liczenia bitów zaproponowany przez Brian-a Kernigan-a, a tenże algorytm (zliczania bitów) był opublikowany w książce "C Programming Language 2nd Ed." (by Brian W. Kernighan and Dennis M. Ritchie). Książka pochodziła chyba z okolic 1988 roku.

5

Odp: quiz Maroka

Wewnętrzna pętla parity musi być jak najszybsza, więc lepiej nie używać pamięci, tylko wewnętrznego cache procesora
Moja procka parity. wejście - bajt w A, wyjśćie - bit C.

parity

        ldy #0
?loop
        cmp #0   ;2
        beq ?end ;2
        lsr           ;2     
        bcc ?loop ;2/3
        iny          ;2
        bne ?loop ;3
?end
        tya     ;2
        lsr     ;2
        rts

Jakoś nie przychodzi mi do głowy teraz jak pozbyć się jednego ze skoków i czy w ogóle można zmniejszyć ich ilość przy tym podejściu.

Ostatnio edytowany przez qbahusak (2022-12-27 11:40:09)

6

Odp: quiz Maroka

Wersja bez petli, czas wykonania staly niezaleznie od ilosci ustawionych bitow.
Kazdy dodatkowy bajt to dodatkowe 3-4 instrukcje w zaleznosci od implementacji(przyklad: parity16)


        org $600
p       equ $80      

start   ldy #0
l1      tya

        jsr parity8  

        lda #0
        ror @
        sta ($58),y

        iny    
        bne l1

        lda #$21
        sta $22f
l0      jmp l0


parity16 sta p   ;16b argument in A,X  
         txa
         eor p

parity8 sta p    ;8b argument in A
        lsr
        lsr
        lsr
        lsr
        eor p
        sta p
        lsr
        lsr
        eor p
        sta p
        lsr
        eor p
        lsr
        rts        ;parity in c
"tatusiu zobacz, narysowałam tobie takie same coś jak na twojej koszulce" 
https://github.com/willyvmm/mouSTer
jmp $e477

7

Odp: quiz Maroka

qbahusak napisał/a:

Jakoś nie przychodzi mi do głowy teraz jak pozbyć się jednego ze skoków i czy w ogóle można zmniejszyć ich ilość przy tym podejściu.

Możliwość 1:

parity
    ldy #$00
    clc
?lp bcc ?s     ; 2/3
    iny        ; 2
?s  lsr        ; 2
    bne ?lp    ; 3 = 8/9
    tya
    adc #$00
    lsr
    rts

Możliwość 2:

parity
    sta zp
    clc
    lda #$00
?lp adc #$00    ; 2
    lsr zp      ; 5
    bne ?lp     ; 3 = 10
    adc #$00
    lsr
    rts

Ostatnio edytowany przez Lizard (2022-12-27 12:20:36)

Zawsze mam rację, tylko nikt mnie nie słucha.

8

Odp: quiz Maroka

hi hi hi... wiedziałem że to się tak skończy :D nie wklejałem swojego wiekowego kodu aby udowadniać jaki jest szybki... to tak jak pisałem "kalka" algorytmu Kernigan-a przepisana bez jakichś specjalnych optymalizacji, bo i tak użycie LUT o wielkości 256 bajtów jest nie do pobicia, ale skoro zaczyna się "walka na cykle", to ja będę uparty jak osioł :D tzn. będe obstawał przy swoim (żartuję oczywiście), ale w ramach eksperymentu myślowego wyobraźmy sobie następującą procedurę testową:

st      sei
        inc    $d40e
        lda    $d40b
        bne    *-3
        sta    $d400

m_loop  lda    $d40b
        bpl    *-3
        lda    $d40b
        bmi    *-3
        lsr    $d01a

        ldx    #$00
l1      txa

        jsr    parity

        inx
        bne    l1

        inc    $d01a
        lda    $d40b
        cmp    vc_max
        bcc    l_nup
        sta    vc_max

l_nup    jmp    m_loop

A więc synchronizujemy się z VBL (powrót pionowy), obliczamy parzystość dla wszystkich bajtów od $00 do $FF, po czym odczytujemy wartość vcount ($D40B) sprawdzamy czy jest ona mniejsza czy większa niż poprzednio odczytana i zapamiętujemy ową wartość tylko jeżeli jest większa niż poprzednio odczytana (czyli zapamiętujemy najbardziej pesymistyczny przypadek)... i tak pętlimy w kółko (wartość vc_max) można odczytać pod debuggerem/emulatorem.

I teraz skoro już mamy procedurę testową zaproponuje swoje "zoptymalizowane" rozwiązanie, skoro użyłeś rej. Y (moja stara procka nie używała rejestrów X,Y, tylko A i lokacji na stronie zerowej) to zakładam że również mogę a więc:

parity  sta    v
    
        ldy    #0
    
        ora    #0
        beq    endp

loop    iny
        sec
        sbc    #1

        and    v
        sta    v
        bne    loop
    
endp    tya
        lsr    @
        rts

^^^ a więc tak jak u Ciebie, wejście rej. A, wyjście C.

I teraz prezentacja wyników: (mniej --> lepiej)

     LUT: $0D
   willy: $40
lizard_1: $6A
   seban: $6F
lizard_2: $78
qbahusak: $85

nie sądziłem że wyjdą z tego wyścigi na cykle! Ale skoro się zaczeło to czemu nie! Na pewno wyjdzie z tego coś fajnego! :)

EDIT1: o widzę że szybko się dzieje, willy dopisał wersję xor-based :D że tak powiem mocno HDL-owo się zrobiło! i szybko! :D uzupełniam zatem tabelkę.
EDIT2: dodałem do tabelki wyniki procek zaproponowanych przez Lizarda.

Ostatnio edytowany przez seban (2022-12-27 12:42:18)

9

Odp: quiz Maroka

@seban - lepiej wykonać 3 testy: optymistyczny, średni i pesymistyczny, wtedy będziecokolwiek obiektywniej :)

10

Odp: quiz Maroka

Oczywiście że wszystko można, nawet zrobić benchmark tak aby faworyzował dany algorytm, zresztą to i tak nie istotne... willy zapodał taki algo który nie zależy od ilości zapalonych/zgaszonych bitów. Zresztą każdy może powalczyć, do tego posta dodaję źródła na prędce skleconego "benchmarka"... to czy liczymy wszystkie wartości ($00-$FF) czy też sekwencję pseudo-losową ($D20A) ma niewielkie znaczenie, tzn. nie zamienia miejsc na liście w tym moim pseudo-benchmarku ;D

Jeżeli chodzi o ten mój ślimakowaty algo bazujący na pomyśle Kernigana, to podobało mi się w nim to że nie był zależny czasowo od wartości, np. czas wykonania obliczeń zarówno dla wartości $AA,$55,$0F,$F0 będzie identyczny... tzn. pętla skończy się po 4 przebiegach ... Zresztą różnice (w porównaniu z Twoją implementacją) są niewielkie... i całe te nasze wyścigi są czysto "akademickie", to takie udowadnianie wyższości jednych świąt nad drugimi ;-)

http://seban.pigwa.net/aa/parity_bench.png

EDIT: Wyniki w tabelkach się nieco zmieniły (na wyższe) ponieważ w stosunku do wersji pierwotnej przybyło kodu w pętli pomiarowej, a nie chciało mi się już bawić w kompensację tegoż, gdyż wszystkie algo zostały ponownie uruchomione w "nowych warunkach". Drastycznie przybyło czasu dla wersji LUT, ponieważ proste LDA parity_table,X zostało zastąpione skokiem do procedury (a jak wiadomo JSR/RTS kosztują sporo czasu ;P)

Ostatnio edytowany przez seban (2022-12-27 16:17:59)

Post's attachments

parity_bench.zip 3.03 kb, liczba pobrań: 1 (od 2022-12-27) 

Tylko zalogowani mogą pobierać załączniki.

11

Odp: quiz Maroka

Nie jest w tradycji pisać zbyt obszernie na tym forum, więc tym chętniej skupię się wyłącznie na podziękowaniach.

@Xxl: Dzięki za podjęcie tematu. Dzięki Tobie temat zaistniał i wypowiedziały się tutaj pewne znakomitości. Czuję się troszkę zobowiązany.

@JHusak: Za czujność i aktywność. (Z reguły zawsze pierwszy i można na niego liczyć, że się do czegoś wypowie, nawet jeśli nie ma innych chętnych. Nie gardzi niczym i nikim.)

@Seban: Jak się za coś bierzesz to raczej już "do spodu". Szacunek, bo solidnym podejściem i ogólną sprawnością bywa że imponujesz. Masz też przyjazne podejście do innych i szacunek. To tak przy okazji tej sytuacji sobie pozwalam. Przepraszam, jeśli to mało stosowne.

@Lizard: Człowiek, któremu osobiście zawdzięczam pewien postęp w sztuce programowania, z czego może nie zdawać sobie sprawy. Wcale tu nie zmyślam, ale tak się składa. Coś z tych lekcji i porad na tym forum zresztą zamieszczanych (w odleglejszej już przeszłości) sądzę że wyciągnąłem. (Specjalnie dla mnie to pisał.)

@Willy: Nie wiem do końca jak z tą Twoją wersją było, ale wygląda na to, że obmyśliłeś ją szybciej niż mnie się udało dojść do analogicznego rezultatu (tak twierdzę, że niezależnie mi także, ale prawem jest wątpić). A przecież "szybkość ma znaczenie" (tu byłbyś górą). Gratulacje - jeśli właściwie rozumiem tą sytuację (że to Twoje). (Bo na 100% z tekstu tego nie umiem stwierdzić. Na 99% już tak. Nie mam podstaw i powodów wątpić, chociaż kolegi nie znałem że umie w 6502. Ale to tym lepiej dla "społeczności", że… gdybym teraz napisał coś pochlebnego, to w jakimś sensie mogłoby to zostać zinterpretowane, że pisałbym też o sobie, więc musimy to sobie tym razem darować.)

12

Odp: quiz Maroka

Wersja Willyego opisana tu: http://graphics.stanford.edu/~seander/b … tyParallel

Willy, znałeś, czy wymyśliłeś?

Ostatnio edytowany przez qbahusak (2022-12-28 01:10:44)

13

Odp: quiz Maroka

Ani nie znałem ani nie wymyśliłem,  wiedziałem :) i tylko na asembler przełożyłem.

Ale skoro zainspirowaliście mnie szukania po innych stronach to znalazłem to:

    sta  p
    asl
    eor  p
    and  #b10101010
    adc  #b01100110
    and  #b10001000
    adc  #b01111000

Prościej na 6502 chyba się już nie da.
Tym razem wynik w najstarszym bicie.

Kod pochodzi z 6502.org

"tatusiu zobacz, narysowałam tobie takie same coś jak na twojej koszulce" 
https://github.com/willyvmm/mouSTer
jmp $e477

14

Odp: quiz Maroka

No to mamy nowego króla wydajności (pomijając LUT na który trzeba zmarnować 256 bajtów pamięci :P)

http://seban.pigwa.net/aa/parity_bench2.png

ja metodę xor-based znałem ze świata HDL-owego (dlatego pisałem o tym że HDL-owo się zrobiło jak ją Willy zaprezentował), tzn. stosowałem ją np. w kodzie verilogowym dla SlightSID-a, tyle że w verilogu to jeszcze prościej, w przypadku rej. konfiguracyjnego SlightSID-a musi się zgadzać parzystość danych, tylko wtedy rej konf. będzie "zaktualizowany":

inout [7:0]            ata_DAT;            // ATARI data bus
...
...
if (atr_str[7:0]==8'h41 && ~(^ata_DAT)) cfg_reg  <= ata_DAT;

a więc jak widać całe "obliczenie" parzystości sprowadza się do wykonania operacji XOR na wszystkich bitach i zanegowaniu wyniku:

parity = ~(^ata_DAT)

I to jest własnie piękno "języków opisu sprzętu!" :D

W sumie po tych moich przygodach z parzystością na początku lat '90 nigdy potem nie miałem potrzeby obliczania parzystości na 6502 i zaprezentowałem te moje wykopalisko z przeszłości bez większego zastanawiania się nad problemem, nawet nie chodziło mi o żaden wyścig na cykle, a temat potraktowałem jako ciekawostkę, która koniec końców dzięki waszym postom przekształciła się całkiem ciekawy wątek. W dodatku QbaHusak zainspirował mnie to optymalizacji i napisania tego mini-bechmarka, wiem że nie jest on doskonały ani jakiś "pro", ale mniej więcej spełnia swoje zadanie pozwalając zweryfikować czy każda z procedur działa poprawnie i ile czasu się wykonuje.

Ostatni kod zaprezentowany przez Willy-iego (ten z 6502.org) pokazuje jak bardzo ekstremalnie można zoptymalizować każdy problem! :) To się nazywa pomysłowe wykorzystanie dostępnych instrukcji CPU aby osiągnąć efekt końcowy :D Ten fragment kodu w zestawieniu z verilogową implementacją bardzo fajnie pokazuje jak rozbić problem natury typowo równoległej na coś co da się wykonać etapami, i co ciekawe nie krok po kroku (metodą zliczania poszczególnych jedynek) ale jak wykorzystać możliwości prymitywnego ALU którym dysponuje 6502 do "zrównoleglenia" operacji.

@marok: dzięki za miłe słowa, jednak uważam że nie robię nic wyjątkowego, a to że czasami mi coś wyjdzie można chyba tłumaczyć tylko tym że jak mnie jakaś rzecz zainteresuje to staram się poznać dany temat jak najlepiej, czy też na tyle na ile pozwala moja możliwość percepcji. Sądzę że inni są o wiele bardziej sprawni w różnych kwestiach. Dla mnie niektóre rzeczy są po prostu poza zasięgiem bo wymagają jakiegoś mega abstrakcyjnego myślenia, co w moim przypadku jest chyba jakimś problemem... mój mózg działa chyba w ten sposób że wszystko dla niego musi być logiczne i wytłumaczalne w prosty sposób, jeżeli problem jest natury abstrakcyjnej trudno zainteresować moją mózgownicę tego rodzaju problemami, tak już mam i nic na to nie poradzę :D

Ostatnio edytowany przez seban (2022-12-28 13:13:20)

15

Odp: quiz Maroka

Wow, ta ostatnia wersja z 6502.org miażdży.

"Was powinny uzbrojone służby wyciągać z domów do punktów szczepień, a potem zamykać do pi* za rozpowszechnianie zagrożenia epidemicznego" - Epi 2021
"Powinno się pałować tylko tych co tego nie rozumieją. No i nie szmatki i nie chirurgiczne tylko min FFP3, to by miało jakiś sens. U mnie we firmie, to jak przychodzi bezmaskowiec, to stoi w deszczu przed firmą" - Pin 2021