Hello, Guest the thread was viewed7.7k times and contains 18 replies

last post from atomcode at the

Assembler Tricks

    Ich habe schon einige 6502 Betriebssysteme (8296, 8032, C64, VC20, Microprofessor II, Apple II) disassembliert und dabei noch einiges an Optimierungspotential gefunden.
    Deshalb würde ich gern in einem Thread mit Euch über Otimierungen und Tricks diskutieren.


    Ein kleines Beispiel: Am Schleifenende wird ein 16 bit Zähler dekrementiert, um die Schleife n mal durchlaufen zu lassen.
    Der Counter selbst wird in der Schleife nicht benutzt.


    Der konventionell Ansatz sieht so aus:



    Wenn der Zähler selbst nicht benötigt wird, kann man einen "jagged countdown" benutzen, der nicht die Werte von n bis 0 in der korrekten Reihenfolge durchläuft, aber trotzdem n Iterationen (n > 0 und n < 32768) erlaubt:

    Code
    1. LDA #<n
    2. STA Countdown_Lo
    3. LDA #>n
    4. STA Countdown_Hi
    5. LOOP JSR Mach_Was
    6. DEC Countdown_Lo
    7. BNE LOOP
    8. DEC Countdown_Hi
    9. BPL LOOP

    Auch diese Schleife wird n mal durchlaufen, sie ist aber kürzer und schneller.
    Dieser "jagged countdown" lässt sich einsetzen, wenn der Indexwert selbst nicht benutzt wird. Er durchläuft z.B. bei n=515 die Werte:
    515, 514, 513, 256, 511, 510, ... 258, 257, 0, 255, 254, ... 2, 1, -256 (deshalb auch die letzte Abfrage BPL und nicht BNE).

    Quote from zrs1

    Nur damit ich es richtig verstehe -- soll das jetzt eine Sammlung solcher Optimierungen werden? Und geht es darum, auf Größe oder auf Laufzeit zu optimieren, was sich ja manchmal beißt (im ersten Beispiel hier allerdings nicht)?

    Ja, richtig. Das war meine Absicht. Speicher- und Laufzeit Optimierungen sind gleichermaßen wichtig, je nach Anwendung.
    Und in den meisten Fällen widersprechen sie sich nicht, außer bei der intensiven Anwendung von Tabellen,
    wie z.B. die Tabelle der Zeilenanfangsadressen, die für jede Bildschirmzeile zwei Bytes verbraucht.
    Das Problem kann man viel kürzer durch Code erledigen, aber der braucht mehr Zeit, als der Tabellenzugriff.

    Quote from Bit Shifter

    Wenn der Zähler selbst nicht benötigt wird, kann man einen "jagged countdown" benutzen, der nicht die Werte von n bis 0 in der korrekten Reihenfolge durchläuft, aber trotzdem n Iterationen (n > 0 und n < 32768) erlaubt:

    Noch einfacher ist: Man startet mit "minus n" und zählt dann hoch bis zum Überlauf auf Null. Das funktioniert für den vollen Zahlenbereich und ist auch noch deutlich einfacher zu durchschauen und als korrekt funktionierend zu erkennen.

    Quote from Mac Bacon

    Noch einfacher ist: Man startet mit "minus n" und zählt dann hoch bis zum Überlauf auf Null. Das funktioniert für den vollen Zahlenbereich und ist auch noch deutlich einfacher zu durchschauen und als korrekt funktionierend zu erkennen.

    Das ist richtig, wenn n eine Konstante, wie in meinem Beispiel ist. Dann kann man den Zähler auch wie folgt implementieren:

    Code
    1. LDA #<-n
    2. STA Countdown_Lo
    3. LDA #>-n
    4. STA Countdown_Hi
    5. LOOP JSR Mach_Was
    6. INC Countdown_Lo
    7. BNE LOOP
    8. INC Countdown_Hi
    9. BNE LOOP

    Diese Methode ist exakt genauso schnell und groß wie der jagged countdown und leichter zu verstehen.
    Wenn n allerdings als variabler 16 bit Wert in zwei Speicherstellen steht und nicht "immediate" geladen werden kann, hängt die Wahl der Methode wohl vom Vorzeichen ab,
    denn n zu negieren würde wieder viele zusätzliche Bytes erfordern. Da wäre dann bei positivem n der jagged countdown besser
    und bei negativem n die INC Methode.

    Quote from Bit Shifter

    Wenn n allerdings als variabler 16 bit Wert in zwei Speicherstellen steht [...]

    ... dann fällt entweder das "Vorladen" in Countdown_Lo/Hi weg, bzw. ist schon erfolgt, sofern der Wert im Anschluß entbehrlich ist.


    Andernfalls müßte der beliebige Wert auch erstmal aus der Vorgabe in die "jagged"-Zählweise konvertiert werden. Mit der Hochzählmethode geht das mit wenig Extra-Code zur Vorzeichenumkehr einfach so:

    Code
    1. SEC
    2. LDA #$00
    3. SBC n
    4. STA Countdown_Lo
    5. LDA #$00
    6. SBC n+1
    7. STA Countdown_Hi


    P.S. (auch Mac Bacon) korrekterweise müßte die Zählvariable ja jetzt Countup_XX heißen. ;)

    Der Countdown (Countup) ist jetzt, glaube ich, ausreichend diskutiert.
    Deshalb hier ein neues Beispiel, die Anfangsadressen der Textzeilen im Bildschirmspeicher am Beispiel eines 80 Zeichen PET/CBM.
    Man kann zwar die ROM-Tabellen verwenden, aber leider liegen die bei verschiedenen Editor-ROMs an verschiedenen Adressen.
    Die hier vorgestellte Methode ist zwar langsamer, als Tabellen, aber schön kurz:


    Bei jedem Algorithmus, jeder Routine, jeder Berechnung und jeder Schleife sollte man sich zuvor genau überlegen, wie zeitkritisch das sein wird. Wenn die Routine in kürzester Zeit viel leisten muss oder sehr oft aufgerufen wird und somit jeder überflüssige Taktzyklus das Geschehen verlangsamt, muss man sich was einfallen lassen. Wenn dazu spezialisierte Codevarianten und üppige Tabellen gebraucht werden, muss man an anderen Stellen, wo man genügend Zeit hat, eben einsparen, etwa so wie mit dem letzten Beispiel. Ich habe dazu auch noch ein Beispiel, das möglichst klein sein sollte (One-Block-Contest) und eben nicht zeitkritisch ist: Die Ermittlung von Lottotipps. Ich hab einfach den Aufwand gespart, die 256 Möglichkeiten aus dem Rauschgenerator umzurechnen und stattdessen nur gefiltert, also die 0, die 50 bis 255 und alle, die schon "gezogen" wurden. Dadurch plätschern die 6 Zahlen dahin, als wäre es in BASIC geschrieben, aber wirklich warten muss man dennoch nicht. lotto.prg

    Quälcode im Uralt-Format. Werde aber demnächst mit ACME weitermachen. Der Text enthält Steuercodes, die hier nicht sichtbar sind.

    Hehe, gut, dass Ihr euch um die Adressierung kabbelt. So hat wenigstens noch keiner gemerkt, dass ich bzgl. des Lotto-Programms was Falsches erzählt hatte. Die Verlangsamung kommt wohl in dem Fall noch nicht durch die Filterung. Die bewirkt dabei nämlich nur eine Verlangsamung um etwa Faktor 5,5. Das würde man bei den paar Befehlen kaum merken. Würde man die Filtermethode aber anwenden, wenn es nicht um 44-49 Zahlen ginge, sondern nur um bspw. 5, dann hätte man schon einen Verlangsamungsfaktor von 51,2. Bei zeitkritischen Aufgaben könnte man das also vergessen. Man könnte allerdings die Zufallszahl durch Shiften halbieren und bekommt einen kleineren Zufallsbereich zur Filterung. Ob beim Weißen Rauschen auch in Frage kommt, den benötigten Bereich einfach mit AND zu maskieren, also ob dabei die Werteverteilung immer noch gleichmäßig ist, weiß ich noch nicht. Das würde die Ermittlung natürlich am meisten beschleunigen.


    Vielleicht kann diese Frage hier ein Elektroniker, Physiker oder Sonstwiewissender beantworten.


    Im Lotto-Programm sind es hier eher die genutzten System-Routinen, die das Programm so langsam machen.


    Das wäre dann auch schon der nächste Trick Tipp: Niemals Kernal- und BASIC-Aufrufe in zeitkritischen Aufgaben verwenden, sondern selbst programmieren. Und andersherum, wenn man eben Platz sparen muss und es nicht auf Zeit ankommt, kann man damit wunderbar Speicherplatz gewinnen. Das ist für langjährige Coder natürlich trivial und eher was für Einsteiger, aber die muss man auch berücksichtigen.

    Quote from atomcode

    Hehe, gut, dass Ihr euch um die Adressierung kabbelt. [...]

    Na, ja. Sagt derjenige, der das Problem erstmal überhaupt benannt hat. ;)


    Zu deinem Lotto-Beitrag: die Filter-Methode ist durchaus gängig und jedenfalls besser, als z.B. mit MOD die untersten Bits eines PRNG herauszufiltern. Gerade bei linear-kongruenten Generatoren kann man damit prima auf die Schnauze fallen ...!


    In deinem Beispiel könntest Du vorher aber 2 Stellen nach rechts shiften (also 0..63 "ziehen"), damit ist der "Ausschuß" nicht mehr so anteilig hoch.


    Problem beim SID ist dann noch, daß er zum Nachliefern neuer Zahlen dann doch ein paar mehr Taktzyklen braucht.


    Zum Schluß: das Lotto-Programm lohnt nicht wirklich zur Implementierung in Assembler. Probier' mal die Variante in BASIC aus, die tut's genauso:

    Code
    1. 1 DIMB(49)
    2. 2 FORT=1TO6
    3. 3 X=INT(RND(1)*49)+1:IFB(X)=1THEN3
    4. 4 B(X)=1:NEXT
    5. 5 FORT=1TO49:IFB(X)=1THENPRINTT
    6. 6 NEXT
    Quote from Bit Shifter


    Wenn der Zähler selbst nicht benötigt wird, kann man einen "jagged countdown" benutzen, der nicht die Werte von n bis 0 in der korrekten Reihenfolge durchläuft, aber trotzdem n Iterationen (n > 0 und n < 32768) erlaubt:

    Code
    1. LDA #<n
    2. STA Countdown_Lo
    3. LDA #>n
    4. STA Countdown_Hi
    5. LOOP JSR Mach_Was
    6. DEC Countdown_Lo
    7. BNE LOOP
    8. DEC Countdown_Hi
    9. BPL LOOP

    Auch diese Schleife wird n mal durchlaufen, sie ist aber kürzer und schneller.
    Dieser "jagged countdown" lässt sich einsetzen, wenn der Indexwert selbst nicht benutzt wird. Er durchläuft z.B. bei n=515 die Werte:
    515, 514, 513, 256, 511, 510, ... 258, 257, 0, 255, 254, ... 2, 1, -256 (deshalb auch die letzte Abfrage BPL und nicht BNE).

    Ich bin etwas spät zur Party gekommen ... dazu hätte ich noch etwas. Ich weiß nicht, ob das auch unter den Begriff "jagged countdown" läuft. Ich kannte den Ansatz auch lange Zeit nicht, aber wunderte mich schon, dass dies nicht deutlich mehr Verbreitung gefunden hat. Ok, wenn man den Wert an sich für etwas anderes braucht, aber ich habe genug Code gesehen, wo man das hätte locker einsetzen können und man sich dennoch mit dem Standard-Code LDA/BNE/DEC/DEC/LDA/ORA/BNE abquält.
    Ich hab's in einem Betrag bereits erwähnt und beschrieben. Den vollen 16-Bit-Zähler erhält man dadurch, wenn der Zähler so angepasst wird, dass der High-Byte-Rollover beim Übergang von 1 auf 0 (statt 0 auf FF) erfolgt. Mit einer kleinen initialen Korrektur des Zählers sieht das dann so aus:


    Code
    1. lda CL
    2. beq +
    3. inc CH
    4. + ...
    5. loop
    6. ...
    7. dec CL
    8. bne loop
    9. dec CH
    10. bne loop

    Der Wert 0/0 entspricht dann 65536 Durchläufe. ;)
    Das Setup ist hier auch deutlich schlanker, als beim Ansatz mit der Negation und dem Raufzählen auf 0 ...

    Was hier an emotionaler Disonanz wegen einer einfachen Definitionssache erzeugt wird, ist einfach Kindergarten-Niveau.
    Soll der Thread gleich in Laberecke-->Kindergartenecke?


    Koennen wir hier also bitte zurueck zum Topic - Assembler Tricks und Optimierungen - kommen.

    @Haubitze Das könnte man als Tipp verallgemeinern: Benutze immer Branches, wenn es um Platzersparnis geht, nicht zu weit ist und man genau weiß, welche Flags welchen Status nur haben können. Wenn man bspw. zuletzt eine Addition hatte und genau weiß, dass der Wertebereich nicht überlaufen kann, springt man mit BCC anstatt mit JMP. Sollte man dann unbedingt ordentlich dokumentieren, damit man später nicht irrtümlich meint, der nachfolgende Teil hätte irgendwas mit dem Branch-Befehl bei gesetztem Carry zu tun. Zeitlich hat man zwar nichts gewonnen, bei Pageübertritt sogar verloren, aber wenn das keine Rolle spielt und man das konsequent anwendet, gilt "Kleinvieh macht auch Mist".


    Genauso kann man sich auch ein CLC/SEC für Addition, Subtraktion oder evtl. beim Rollen sparen, wenn der Status an der Stelle eh bekannt ist. Das bewirkt dann neben Platz- auch Zeitersparnis.


    @JeeK Ich schau mir deinen anderen Beitrag später an. Hab bis jetzt noch nix kapiert. ;)


    @daybyter >"falls möglich würd ich den 'Nutzcode' in der Schleife nicht per jsr aufrufen, sondern als Makro aufrufen. Das gibt eine besseres Verhältnis von Sprüngen zu Nutzcode."
    Das stimmt, aber bei richtig zeitkritischen Sachen benutze ich Macros allerdings meist auch nicht, sondern blanken 1:1-Code. Ich muss den im Ganzen vor Augen haben, weil sich dann auch die weiteren Tricks leichter anwenden lassen, wie eben die Nutzung der Kenntnis über den Status der Flags oder anderes.

    Zum Thema Definitionen geht's hier weiter: Definitionen und Standards zu ASM Adressierungen, Syntax und Mnemonics [OT aus 'Assembler Tricks']

    Quote from NoobTracker aus "C64 Studio - Entwicklungsumgebung"
    Quote from atomcode

    NoobTracker Man kann doch auch durch zusätzliche (also vermeintlich unnötige) Indizierung einen Taktzyklus verzögern. Oder so, dass man einen NOP einbaut und dafür an anderer Stelle einen Zyklus spart, z.B. mit einem Illegal Opcode an passender Stelle, der dann oft auch direkt wieder das Byte fürs NOP herausholt.

    Irgendwie verstehe ich davon nix. Was soll man indizieren?

    Bsp. 1: Wenn es bei der Programmierung in der ZP irgendwo im Code eine unmittelbare Adressierung gibt, wie etwa LDX #nn oder AND #nn, dann im Programm nach diesem Operanden schauen und dessen Speicherstelle angeben, sodass es eine ZP-Adressierung wird, die 3 anstatt 2 TZ braucht. Ob der Operand dabei dann aus einem Befehlscode, Operandencode oder Datencode kommt, ist egal; es ist nur wichtig, dass dieser Code nicht verändert wird, weil ja sonst der Inhalt in der ZP-Adresse nicht mehr passt.


    Angenommen, man braucht für eine Schleife eine 24 im X-Register, z.B. wegen der 25 Textzeilen (0-24). 24 ($18) ist der Code von CLC. Kommt CLC im Programm vor, so kann man dessen Speicheradresse angeben, um die 24 über eine ZP-Adressierung zu erhalten.



    Bsp. 2: Ein STA $nnnn braucht 4 TZ, ein STA $nnnn,x oder STA $nnnn,y braucht 5 TZ. /oder/ Ein STA $nn braucht 3 TZ, ein STA $nn,x braucht 4 TZ. / usw.

    Wenn an der Stelle der Wert eines entsprechenden Index-Registers (mit Sicherheit) bekannt ist, kann man das einsetzen. Wenn das Index-Register nicht 0 ist, muss man die Adresse natürlich anpassen.



    Bsp. 3: Code umschreiben, z.B. für die Aufgabe: X=X+20, A/Y untouched. Statt ...

    Code
    1. sta $02 ; 2B 3TZ
    2. txa ; 1 2
    3. clc ; 1 2
    4. adc #20 ; 2 2
    5. tax ; 1 2
    6. lda $02 ; 2 3
    7. ;-------------------
    8. ; 9 14

    so was ...

    Code
    1. pha ; 1B 3TZ
    2. txa ; 1 2
    3. clc ; 1 2
    4. adc #20 ; 2 2
    5. tax ; 1 2
    6. pla ; 1 4
    7. ;-------------------
    8. ; 7 15

    oder auch so was; dann kann man die NOP-Zeit evtl. noch anderweitig nutzen ...

    Code
    1. pha ; 1B 3TZ
    2. txa ; 1 2
    3. sbx #256-20; 2 2
    4. pla ; 1 4
    5. nop ; 1 2
    6. nop ; 1 2
    7. ;-------------------
    8. ; 7 15