Letzte Änderung: 26.01.98

ASM86FAQ - Optimierung



(Übersicht)

Grundsätzliches zur Optimierung

Thomas-Ivo Heinen 2:2449/533:

Einmal ein Kurzdurchlauf durch die wichtigsten Grundlagen:

- Oft lassen sich gleiche Ergebnisse mit unterschiedlichen Befehlen realisieren. Dabei gilt i.d.R.: je kürzer, desto besser. Dement- sprechend sind z.B. 5 Byte den 8 Byte vorzuziehen.

- Speicherzugriffe sind langsam ! Lieber alle Register ausnutzen. Einige Variablen sind auch machbar, da diese bei häufigem Gebrauch im Cache liegen ...

- Bleibt nicht auf 8086/80286er Niveau! Schaut Euch lieber einmal die 386er Instruktionen an ... <g>

- Wozu gibt es denn 32-Bit Register ...

Nun etwas Prozessorinternas, bei deren Kenntnis noch einiges herausgeholt werden kann. Im Folgenden ist öfters die Rede von Ticks, Clocks und Cycles. Damit sind interne Prozessortakte gemeint. So hat z.B. ein 66 Mhz-Prozessor pro Sekunde 66 Mio. Ticks...

- AGI - der Address Generation Interlock < alle CPUs >

Ein sehr unsympathischer Zeitgenosse, der einem oft bei Laufzeit- optimierungen dazwischenfunkt, da er einen Befehl 1 Tick lang ver- zögert. Ein AGI tritt auf, wenn in zwei aufeinanderfolgenden Be- fehlen dasselbe Register verwendet wird. So zum Beispiel:

ADD EDX,4 < AGI > MOV ESI, [EDX]

Bei Prozessoren bis zum 486 muß man damit nur bei aufeinanderfol- genden Befehlen rechnen, der Pentium dagegen kann auch über bis zu drei Befehle hinweg einen AGI generieren. Hierfür ein Beispiel:

ADD ESI,4 -> 486: 4 Ticks POP EBX -> 586: 3 Ticks statt 2 wegen AGI DEC EBX MOV EDX, [ESI]

Vorsicht übrigens vor "versteckten" AGIs:

MOV ESP,EBP < AGI > -> POP benutzt EBP als Pointer... POP EBP

Dazu eine kleine Skizze:

Schritt der Pipe Pipe1 Pipe2 Address Calculate/Fetch Operand C D | Execute B A | V

Falls C das Ergebnis von A benötigt, muß Pipe 1 einen Tick verzögert werden, um auf A zu warten. Falls C das Ergebnis von D benötigt, muß Pipe 2 ZWEI Ticks verzögert werden.

ACHTUNG:

Bei AGIs bildet der Cyrix 5x86 sozusagen eine Ausnahme, da er ein Feature namens Register Renaming beherbergt. Nehmen wir folgende Befehlsfolge:

MOV BX,AX SHL AX,8

Sieht nach einem AGI aus ? Falsch ! Es kann auch so gehen:

MOV BX,AX SHL EX,8

Hier wurde also AX in EX umbenannt, die Befehle könnten beide in EINEM Tick, statt in zweien, ausgeführt werden. Der Cyrix 5x86 ist dazu in der Lage, da er intern 32 statt 8 Register verwendet. So werden einige AGIs verhindert ... warum macht Intel das eigentlich nicht !?

- IDS - der Instruction Decoding Stall < bis 486 >

Bei Instruktionen mit einer Konstanten od. einem konstanten Displa- cement müssen alle CPUs bis zum 486 einen Tick warten. Beispiele:

º MOV LOOPVAR, 248 º MOV DWORD PTR [ESP+4], 1

Die Decode-Stage dieser CPU kann nämlich immer nur EINE Konstante bearbeiten. Der Pentium hat keine IDSs, da er die Befehle anders abarbeitet.

- RACS - der Register Access CPU Stall < bis 486 >

Wenn bis zu einem 486 das untere Word eines Doublewords modifiziert wird, daß unmittelbar benötigt wird, wartet ein 486 einen Tick. Ein Pentium braucht dies nicht. Beispiel:

MOV AL,0 MOV [EBP], EAX

Der schnelle Spass am Stück - Quickies Marke ASM86FAQ:

- Vermeidet Multiplikationen ! Mit den Shiftinstruktionen, ADDs und SUBs geht es oft viel schneller (und mit LEA - siehe OPT0004).

MOV EAX,10 MUL ECX

braucht nahezu ewig. Besser ist da:

MOV ESI,ECX SHL ESI,3 SHL ECX,1 ADD ECX,ESI

Das ist zwar länger, braucht aber weniger Zeit. Selbst auf einem Cyrix ist dies schneller - obwohl dieser generell nur 3 Ticks für eine Multiplikation benötigt, denn hier werden nur 2 Ticks verbraucht. Will man allerdings mit einer Zahl multipli- zieren, die mehr als 2 Bits gesetzt hat (-> 11d = 1011b), dann ist auf dem 5x86 ein Mul schneller.

- Vermeidet "LOOP"...

Statt: Besser: LOOP @B DEC ECX JNZ @B

Das Resultat ist dasselbe, aber es arbeitet weitaus schneller ! Beispiel von einem Pentium: Variante 1 braucht 8 Ticks, Variante 2 dagegen nur 5 ...

- MOV statt STOSB

Auf 486ern ist MOV ES:[DI],?A? einem STOS? vorzuziehen, da dies WENIGER Taktzyklen benötigt...

Lektüre: - C't zu Pentium und Cy5x86 - "Optimizing" von M.Munstelj und L.Micheletto


(Übersicht)

Code Alignment

Juergen Thelen 2:2450/55.5:

Intel empfiehlt bei der Programmierung von universellem Code (ein- und der- selbe Code soll auf 386, 486 und P5 laufen) die Ausrichtung von Sprungzielen auf 0MOD16-Boundaries (Adresse MODULO 16 = 0), falls das Sprungziel 8 Bytes oder weniger von einer solchen Boundary entfernt ist.

Bei exklusivem Code für 386er bringt Code Alignment gar nichts, da i386er ja keinen On-Chip-Cache besitzen (decoupled Prefetch-Unit). Die größten Perfor- mance-Gewinne hat das 0MOD16-Alignment auf 486ern, da sich das Alignment da direkt auf die Effizienz der Prefetchbuffer auswirkt (ein 486er besitzt zwei 16-Byte-Prefetchbuffer). Auf P5ern bringt das Alignment zwar so gut wie gar nichts, man sollte den 486ern zuliebe ;) aber trotzdem 0MOD16 fahren...

Joerg Kubitz 2:240/9301.12:

386er von AMD prefetchen jeweils 4 Bytes auf einmal. Daher bringen Sprünge zu 0MOD4 Adressen auf diesen CPUs Performancegewinne.

Auf einem 486er braucht es bis zu 5 extra Taktzyklen, wenn der Befehl am Ziel eines Sprunges auf zwei Paragraphen (Paragraph = 16 Bytes) aufgeteilt ist.

Zum manuellen Alignment eignen sich z.B. folgende NOPs (auf 486ern jeweils nur 1 Taktzyklus):

16bit Code:

Instruction Bytes Opcodes

nop (1) ; 90H xchg ax, ax (1) ; 90H mov ax, ax (2) ; 89H c0H lea bx, [bx+00] (3) ; 8dH 5fH 00H lea bx, [bx+0000] (4) ; 8dH 9fH 00H 00H

32bit Code:

nop (1) ; 90H mov eax, eax (2) ; 8bH c0H lea eax, [eax+00] (3) ; 8dH 40H 00H add eax, 00000000 (5) ; 05H 00H 00H 00H 00H (ändert FLAGS!) lea eax, [eax+00000000] (6) ; 8dH 80H 00H 00H 00H 00H


(Übersicht)

Data Alignment

Juergen Thelen 2:2450/55.5:

Weitere Performancesteigerungen lassen sich durch gezieltes Ausrichten von Daten erreichen. Wie ausgerichtet werden muss, ist dabei von der Datengröße abhängig:

1 Byte (Byte, ShortInt) egal... ;) 2 Byte (Word, Integer) innerhalb 0MOD4-Boundary (Offset 0, 1 oder 2) 4 Byte (DWord, Longint) auf 0MOD4-Boundary 8 Byte (QWord, Real) auf 0MOD8-Boundary

Wird das Data Alignment nicht eingehalten, verliert man auf 486ern und P5ern mindestens 3 Clocks...


(Übersicht)

Register-Optimierung

Juergen Thelen 2:2450/55.5

Nachfolgend einige Optimierungen, die den Umgang mit Registern betreffen. In der Hauptsache handelt es sich um Tips für 32bit-Prozessoren (386+):

- Register löschen:

Hier ist "XOR reg, reg" empfehlenswert, da die Instruction kürzer ist als ein "MOV reg, 0". Allerdings beeinflusst XOR die Flags. Werden die Flags noch gebraucht, ist "MOV reg, 0" besser.

- Vorzeichenlose Erweiterung eines Byte:

Speziell ab 486ern ist "XOR EAX, EAX / MOV AL, ?" dem "MOVZX" vorzu- ziehen, da "MOVZX" länger dauert.

Bei P5ern kommt hinzu, daß "MOVZX" auch nicht pairable ist, was einen weiteren Geschwindigkeitsverlust bedeutet.

Außerdem kann innerhalb von Schleifen eventuell auch das "XOR" entfal- len, bzw. nach aussen verlagert werden, falls die oberen 24 Bits von E?X nicht von anderen Instructions in der Schleife verändert werden. Die Auslagerung bringt natürlich weiteren Performancegewinn.

- Konstanten in Register laden:

Müssen Konstanten innerhalb von Schleifen verwendet werden, empfiehlt es sich, die Konstante nach Möglichkeit in einem Register zu halten, da ein "MOV reg, reg" bei mehrfacher Verwendung schneller als ein "MOV reg, imm" ist (486).

- Register auf Null prüfen:

Hier ist "TEST reg, reg" aus mehreren Gründen die beste Variante. Sie ist besser als "AND reg, reg" und "OR reg, reg" weil der Zieloperand bei "AND" und "OR" beschrieben wird (ist bei "TEST" nicht der Fall). Dieses Beschreiben könnte in der nachfolgenden Instruction zu einem Address Generation Interlock (AGI) führen (1 Clock Penalty).

Der Vorteil gegenüber "CMP reg, reg" ist, daß "TEST reg, reg" kürzer ist.

- LEA, das Allheilmittel... ;)

- Schnell und kurz bei Kettenoperationen, z.B. "LEA EDI, [EAX+EBX+8]".

- Quellregister (wie vorstehend EAX, EBX) bleiben erhalten und müssen nicht extra gesichert werden.

- LEA ist bei Shifts um 2, 4 und 8 Bits schneller als SHL/SHR (486+).

- Durch Verwendung von LEA, ADD, SUB und SHL/SHR Sequenzen lassen sich viele Konstantenmultiplikationen wesentlich schneller als mit MUL durchführen.

Beispiel: Grafikmodus 13H (320x200x256 bei a000:0H). Der Offset von Zeile EBX soll errechnet und in EAX abgelegt werden.

lea eax, [ebx*4+ebx] ; * 5 shl eax, 6 ; * 64 (= * 320)

- Bei all diesen Vorteilen darf natürlich nicht vergessen werden, daß bei Einsatz von LEA die Gefahr eines AGI (1 Clock Penalty) besteht, wenn die vorhergehende Instruction ungünstig gewählt wird. Bei ent- sprechendem Instruction Scheduling aber wohl kein Problem...

Joerg Kubitz 2:240/9301.12:

- Stacktransfer von Speichervariablen:

Auf 486ern ist ein "MOV reg, [mem] / PUSH reg" zwei Taktzyklen schnel- ler als ein "PUSH [mem]". Gleiches gilt natürlich auch für POP...

Thomas-Ivo Heinen 2:2449/533:

- Vorzeichenlose Erweiterung eines Word:

Schnellste Variante: LEA EAX,[SI]

Leider passen aber zwischen die Klammern nur wenige Register[kombina- tionen], nämlich: BX, BP, SI, DI oder BX/BP+SI/DI+Imm.


(Übersicht)

Unrolled Loops

Thorsten Jordan 2:2461/349.19:

Zunächst: Was versteht man unter dem Begriff "Unrolled Loops" und was bring- en sie?

"Unrolled Loops" werden eingesetzt, um eine Schleife (englisch: "loop") zu beschleunigen, indem die Zeit, die für die Veränderung und die Überprüfung des Schleifenzählers benötigt wird, reduziert wird oder im Extremfall ganz auf eine Überprüfung verzichtet wird. Letzteres klingt paradox, und auch das erste Ziel scheint schwer erreichbar. Betrachten wir uns nunmal eine normale Schleife (mit Taktzyklenangabe für 386 bis Pentium):

schleife: ; 386 486 Pentium mov [si],bx ; 2 1 1 add bx,ax ; 2 1 1 <---------\ add si,2 ; 2 1 0 <-Pairing-/ dec cx ; 2 1 1 jne schleife ; 7+2 3 1

-gesamt- 17 7 4

In einem Schleifendurchlauf geht also einige Rechenzeit auf das Verändern und Überprüfen des Schleifenzählers drauf, auf dem 386 und 486er sogar mehr als die eigentliche Schleife braucht (die 2 Extrazyklen fallen wegen einer Besonderheit des 386ers an, siehe dazu OPT0007)! Das sieht gar nicht optimal aus. Unser Ziel muß also sein, den Anteil der Rechenzeit für die eigentliche Schleife relativ zur Zählerüberprüfung zu erhöhen. Da Rechenzeit in etwa äq- uivalent zur Menge der Befehle ist, warum dann nicht den Anteil der Befehle für die eigentliche Schleife erhöhen?

Das klingt zunächst seltsam, da die Schleife ja schneller werden soll - wa- rum also die Anzahl der Befehle erhöhen? Ganz einfach: Wenn wir doppelt so viele Befehle nehmen, brauchen wir die Schleife nur halb so oft zu durchlau- fen:

schleife: ; 386 486 Pentium mov [si],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+2],bx ; 2 1 1 add bx,ax ; 2 1 1 <---------\ add si,4 ; 2 1 0 <-Pairing-/ dec cx ; 2 1 1 jne schleife ; 7+2 3 1

-gesamt- 21 9 6

-ursprüngliche Schleife mal 2- 34 14 8

-Gewinn- 13 5 2

Geschickterweise kann man beide anfallenden "add si,2" in ein "add si,4" zu- sammenführen und Zeit sparen. In einem Schleifendurchlauf arbeiten wir also doppelt so viel ab, aber wir brauchen keinesfalls die doppelte Zeit, sondern viel weniger! Hinzu kommen einige wenige Zyklen, die gebraucht werden, um das CX-Register vor Beginn der Schleife zu halbieren, was jedoch vernachläs- sigbar ist.

Das ganze hat zwei Nachteile:

Erstens ist die zweite Lösung länger, aber was sind schon ein paar Bytes ge- gen diesen Geschwindigkeitsgewinn?

Zweitens (und somit viel gravierender) ist, daß CX durch zwei teilbar sein muß, sonst wird nicht die ursprünglich gewünschte Zahl Schleifendurchläufe erreicht. Das Behandeln des Restes kann den Vorteil wieder wettmachen. Hier kommt es auf die Anzahl der Durchläufe an - bei mehreren tausend Durchläufen gewinnt man eine Menge Zeit, die für die Restbearbeitung locker ausreicht; bei wenigen Durchläufen könnte es umgedreht sein. Das muß der Programmierer abwägen.

Dieses Vervielfachen, quasi ein "ausrollen" der Schleife führt zum Begriff "unrolled loop" (ausgerollte Schleife).

Man kann das ganze natürlich noch weiter treiben. Hier ist der Code:

schleife: ; 386 486 Pentium mov [si],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+2],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+4],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+6],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+8],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+10],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+12],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+14],bx ; 2 1 1 add bx,ax ; 2 1 1 <---------\ add si,16 ; 2 1 0 <-Pairing-/ dec cx ; 2 1 1 jne schleife ; 7+2 3 1

-gesamt- 45 21 18

-ursprüngliche Schleife mal 8- 136 56 32

-Gewinn- 91 35 14

Der Gewinn erhöht sich zwar, aber der Code wird länger und die Zeit für die Abarbeitung des Restes auch. Was nun das beste Verfahren für die Optimierung ist, muß wieder der Programmierer abwägen.

Nun kann man es auch übertreiben... warum denn überhaupt noch eine Schleife machen? Man kann ganz auf die Veränderung und die Überprüfung des Schleifen- zählers verzichten.

Dazu muß man wissen, wie oft die Schleife höchstens durchlaufen werden soll. Dementsprechend schreibt man:

anfang: ; 386 486 Pentium mov [si],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+2],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+4],bx ; 2 1 1 add bx,ax ; 2 1 1 ... mov [si+2*(n-1)],bx ; 2 1 1 add bx,ax ; 2 1 1

-gesamt- 4n 2n 2n

Wobei "n" die Anzahl der Schleifendurchläufe angibt. Jetzt ist die Zahl der Durchläufe aber nicht mehr variabel? Doch, man muß nur Phantasie haben...

Zunächst wissen wir, wie oft die Schleife durchlaufen werden soll (nehmen wir dafür mal die Variable "x"), und wie oft sie maximal durchlaufen werden kann (n mal). Also springen wir an die Stelle im Code, ab der nur noch x mal diese Befehlsfolge aus der ursprünglichen Schleife steht. Wo ist nun diese Stelle? Wenn wir nur x mal die Befehlsfolge durchlaufen wollen, dann müssen wir also n-x ("n" minus "x") Befehlsfolgen übergehen. Woher wissen wir dann die Adresse, wo beginnt die "n-x"te Befehlsfolge?

Da die Länge einer Befehlsfolge konstant ist, multiplizieren wir diese Länge (die man sich anhand der Befehle ausrechnen kann und als Konstante in den Code einfügen muß) mit der Zahl n-x-1.

Dann haben wir die Adresse der Befehlsfolge relativ zum Label "anfang" (-1 deswegen, weil die erste Befehlsfolge logischerweise die Adresse 0 hat). Man muß natürlich darauf achten, daß der Ausdruck n-x größer Null ergibt! Sonst springt der PC irgendwo vor die Schleife und eventuell direkt ins Nirwana!

Ein letztes fehlt uns noch: Relative Sprungziele werden in Registerform (jmp reg) nicht unterstützt, also muß noch die Adresse von "anfang" addiert wer- den. Und noch was... wir wollen bei der Bearbeitung bei [si] anfangen, da wo wir hinspringen steht aber [si+irgendwas]. Also muß von si "irgendwas" abge- zogen werden, so daß insgesamt die korrekte Adresse verwendet wird. Dieses "irgendwas" ergibt sich aus: Anzahl übersprungener Befehle mal Größe bei der Verarbeitung. Ersteres ist n-x, letzteres logischerweise 2, da wir 2 Bytes (1 Word) bearbeiten (add si,2 pro Durchlauf). Hier der Code:

mov ax,Maximale_Durchläufe ; n laden sub ax,cx ; n-x errechnet mov dx,ax ; dx = n-x add dx,dx ; dx = dx*2 sub si,dx ; si korrigieren dec ax ; n-x-1 errechnet. mov cx,ax ; in cx mov ax,Länge_der_Befehlsfolge ; Konstante "Länge", hier = 4 Byte mul cx ; (n-x-1)*Länge errechnet add ax,offset anfang ; + offset (anfang) jmp ax ; und dorthin springen

anfang: ; 386 486 Pentium mov [si],bx ; 2 1 1 add bx,ax ; 2 1 1 mov [si+2],bx ; 2 1 1 add bx,ax ; 2 1 1 ... mov [si+2*(n-1)],bx ; 2 1 1 add bx,ax ; 2 1 1

Das ganze sieht arg kompliziert aus. Wir brauchen eine Menge Zyklen für die Berechnung am Anfang, diese sind bei einer großen Anzahl Durchläufe jedoch vernachlässigbar. Bei diesem Verfahren kommt noch ein großer Nachteil hinzu: bei mehreren tausend Durchläufen und längeren Befehlen reicht eventuell der L1-Cache nicht mehr aus!

Dies betrifft den 386 gar nicht (er hat keinen L1-Cache), den 486 am meisten (nur 4096 Byte L1-Code-Cache) und den Pentium (8192 Byte L1-Code-Cache) auch nicht viel weniger. Die Frage ist also, ob dieses Verfahren sinnvoll ist - die Antwort sei erneut dem Programmierer überlassen. Meiner Erfahrung nach wird dieses Verfahren selten angewendet, zumindest in der Zeit nach dem 386 kaum noch, es sei hier aber der Vollständigkeit wegen erwähnt. Die Nachteile (benötigt viel Platz und nutzt u.U. den ganzen L1-Cache) sind eben doch zie- mlich groß. Dagegen muß die Anzahl der Durchläufe nicht unbedingt durch 2 (8, usw.) teilbar sein, die Bearbeitung des Restes entfällt.

Als Hilfe für den Programmierer hier noch die Taktzyklenberechnung. Sie ist in diesem Fall von der Anzahl der Durchläufe abhängig:

386 486 Pentium

Vorbereitung 86 47 24

(Bei wenigen Durchläufen durchaus zu berücksichtigen. AGIs, Pairing, etc. wird mitberechnet, die Dauer ist unabhängig von der Anzahl der Durchläufe)

Zeit für 500 Durchläufe 2000 1000 1000

Gesamt 2086 1047 1024

Zeit für 500 Durchläufe 8500 3500 2000 der Originalschleife

Gewinn 6414 2453 976

( Gewinn bei 100 Durchl. 1214 453 176

Gewinn bei 20 Durchl. 174 53 16)

Man sieht also, es lohnt sich erst ab einer gewissen Anzahl Durchläufen. Der Preis ist die Blockade des L1-Caches, der von anderen Codeteilen vielleicht dringender benötigt wird.

Das Verhalten von "unrolled loops" ändert sich je nach Modus (RM, VM, PM) nicht. Im Protected Mode fallen für Konstanten ([exx+Konstante]) 4 statt 2 Byte an, also Vorsicht, der Cache kann schnell voll sein! ;)

Zum Abschluß noch eine Variante der "unrolled loops", die auf dem Pentium eine schnellere Alternative zum "rep movsd" ist. So was gibt's? Ja, ist aber wirklich nur auf dem Pentium vorteilhaft. Prozessoren der 586er und 686er- Reihe von AMD und Cyrix sind dafür ungeeignet ("rep movsd" ist die bessere Variante).

Diese Alternative basiert auf der FPU (Floating Point Unit) und kommt daher für manche 386er sowieso nicht in Frage, bei 386/486ern ist "rep movsd" um einiges schneller. Der Pentium dagegen ist beim Laden und Speichern der FPU- Register viel schneller als seine Vorgänger (und schneller als seine Konkur- renten von AMD u. Cyrix) und (im Gegensatz zu seinen Vorgängern) auch in der Lage, über einen 64bit-Bus auf den Speicher zuzugreifen. Es können also acht Byte auf einmal ("movsd" nur 4) bearbeitet werden.

Ok, los geht's (ausnahmsweise mal Protected-Mode-Code):

schleife: ; Pentium fld qword ptr [esi] ; 1 <---------\ fld qword ptr [esi+8] ; 0 <-Pairing-/ fld qword ptr [esi+16] ; 1 <---------\ fld qword ptr [esi+24] ; 0 <-Pairing-/ fld qword ptr [esi+32] ; 1 <---------\ fld qword ptr [esi+40] ; 0 <-Pairing-/ fld qword ptr [esi+48] ; 1 <---------\ fld qword ptr [esi+56] ; 0 <-Pairing-/ fstp qword ptr [edi+56] ; 2 <---------\ fstp qword ptr [edi+48] ; 0 <-Pairing-/ fstp qword ptr [edi+40] ; 2 <---------\ fstp qword ptr [edi+32] ; 0 <-Pairing-/ fstp qword ptr [edi+24] ; 2 <---------\ fstp qword ptr [edi+16] ; 0 <-Pairing-/ fstp qword ptr [edi+8] ; 2 <---------\ fstp qword ptr [edi] ; 0 <-Pairing-/ add esi,32 ; 1 <---------\ add edi,32 ; 0 <-Pairing-/ dec ecx ; 1 jne schleife ; 1

-gesamt- 15

Die Taktzyklen für "rep movsd" sind 13+n, also 13 in der Vorbereitung und je einer pro Durchlauf. Die "unrolled"-Alternative braucht um 64 Byte zu kopie- ren also 15 Takte - "rep movsd" benötigt da 16. Im RM/VM benötigt diese Va- riante ("es:"-Präfix!) 23, "rep movsd" 32 Takte (32bit-Präfix).

Soweit die theoretische Berechnung der Geschwindigkeit. Mehrere Pentium-Be- sitzer (ich gehöre nicht dazu ;) berichteten mir, daß die FPU-Variante sogar um den Faktor 1,5 bis 2 mal schneller als "rep movsd" läuft.

Diese Technik wird übrigens auch von einem bekannten u. indizierten 3D-Spiel verwendet, dessen Namen an ein Erdbeben erinnert ;)


(Übersicht)

Cache-Optimierung (alle CPUs)

Thomas-Ivo Heinen 2:2449/533:

Der Unterschied zwischen einem Cache-Hit und einem Cache-Miss besteht in et- lichen verlorenen Taktzyklen. So sieht die Cache-Grösse in etwa aus:

- 386 : 0 kB intern, 64kB-128kB extern - 486 : 4 kB intern, 64kB-512kB extern - P5 : 8kB Code/Data, 256kB- 1MB extern - P6 : 256kB-512kB L2, 32kB L1, 256kB- 1MB extern - Klamath : 256kB-512kB PB, 64kB L1, 256kB- 1MB extern

Jumps -----

Bei der Verwendung von Short Jumps ist die Chance, daß der komplette Code noch im Cache liegt, besonders hoch - die Geschwindigkeit ebenfalls...

Strip-Mining ------------

Falls man grosse Arrays bearbeitet, sollte man diese NICHT in mehreren Durchgängen komplett bearbeiten, sondern diese in kleineren "Portionen" durchgehen. Dadurch bleiben die Daten im Cache und können ohne jeden Cache-Miss abgearbeitet werden, dieses Prinzip heisst "STRIP-MINING". Um die optimale STRIP/STREIFEN-Grösse zu ermitteln, kann man am Start des Programms eine Routine einfügen, die die Geschwindigkeit von 32k, 64k, 128k, 256k und 512kB durchtestet. Auf einem Pentium sind 8kB gut, da damit der Data-Cache optimal genutzt wird (der interne Cache arbeitet immer mit der vollen inter- nen Taktrate, während der externe oft nur mit halber betrieben wird. Der Vorteil von Strip Mining besteht darin, daß die evtl. nötigen zusätzlichen Jumps/Loops für die Abarbeitung der Strips weniger Zeit benötigen, als auch nur ein Cache-Miss...

Juergen Thelen 2:2450/55.5:

- Prefetch Queue empty (486), Penalty bis zu 3 Clocks

Sobald im Prefetch Queue Raum und Zeit für eine weitere Cache Line (16 Bytes) ist, lädt die Prefetch Unit Daten nach. Allerdings räumt die Unit Speicherzugriffen immer höhere Priorität als Cachezugriffen ein. Blockt man nun den Cache mit dauernden Speicherzugriffen, hat die Prefetch Unit keine Möglichkeit zwischendurch eine Cache Line wieder aufzufüllen. Die Prefetch Unit muss dann den gesamten Prefetch Queue neu füllen und auf- bereiten, was natürlich länger dauert, als ein Cache Line Update.

Um diese Situation zu vermeiden, sollte man der Prefetch Unit spätestens drei Clocks vor der vollständigen Prefetch Queue Leerung die Möglichkeit geben, eine Cache Line nachzuladen. Dies kann mit jedem Nicht-Speicher- zugriff (also z.B. einem Registerzugriff) erreicht werden.


(Übersicht)

386er-Optimierung

Thomas-Ivo Heinen 2:2449/533:

Decode-After-Jump -----------------

Nach einem Sprung muß ein 386er-Prozessor einige Zeit mit dem Decodiern der folgenden Instruktion und dem Flushen der Pipeline verbringen. Dadurch benö- tigt der erste Befehl nach einem Sprung EINEN Tick für JEDE (!) KOMPONENTE, also je Präfix, Opcode, mod/rm, SIB, Offset und Konstante. Auch ein 8/32bit Displacement braucht jeweils einen Extra-Tick.

SCHNELL LAAAAHM

Loop: INC EDX Loop: MOV [EBX+1234h],EAX MOV [EBX+1234h],EAX INC EDX DEC ECX DEC ECX JNE SHORT Loop JNE SHORT Loop

Die zweite Variante ist im 32Bit-Modus (also ohne Prefixes) ZWEI Ticks lang- samer - verrückt, oder ? Also kann man auf diese Weise 386er-Code um einiges beschleunigen...

Befehlslänge ------------

Die Länge eines Befehls (in Bytes) spielt auf einem 386er eine gewichtigere Rolle als z.B. auf einem 486er, da ein 80386 KEINEN internen Cache besitzt und die Bandbreite beim Zugriff auf das RAM (naturgemäß) viel, viel geringer als bei seinen Nachfahren ist. Dementsprechend besonders beim 386 auf kurze Befehle achten, da diese schneller decodiert und ausgeführt werden.

Eine Ausnahme bilden hier aber die String-Befehle, die trotz ihrer Komplexi- tät schneller ausgeführt werden, insbesondere wenn sie als erste Befehle in einer Loop auftauchen (-> keine Prefixe -> 1 Byte -> schnell...).


(Übersicht)

Diverse Optimierungen - nocheinmal Quickies <g> ...

Thomas-Ivo Heinen 2:2449/533:

Akkumulator/DS -------------- Es empfiehlt sich, so oft möglich, den Akkumulator (AL, AH, AX oder EAX) zu verwenden, da etliche Befehle dafür einen eigenen Opcode haben, der Befehl also ein Byte weniger benötigt. Dazu kommt häufig noch, daß diese "speziali- sierten" Opcodes erheblich schneller sind. Aus demselben Grund ist auch bes- ser, möglichst häufig das DS-Segmentregister zu benutzen, da alle anderen Segmentregister einen Prefix erzeugen und die Befehle meistens deshalb auch langsamer werden.

CDQ-Instruktion --------------- CDQ wird häufig vor Divisionen verwendet, um das EDX-Register zu löschen. Es gibt jedoch eine Alternative, die zwar von der Ticksanzahl genauso schnell, jedoch auf einem P5+ pipeable ist, und zwar: MOV EDX,EAX; SAR EDX,31.

Falls bekannt ist, das die Zahl immer positiv ist, sollte man einfach ein XOR EDX,EDX verwenden (Mann, was ein alter Hut...).

JMP-Instruktion --------------- Short Jumps sind IMMER schneller als Long Jumps, jedoch erzeugen unglück- licherweise einige Compiler defaultmäßig einen Long Jump, wo er nicht nötig wäre. Also lieber immer JMP SHORT schreiben - ist zwar mehr Tipparbeit, holt aber ab und an vielleicht ein oder zwei Ticks raus <g>...

Komplexe Instruktionen ---------------------- Komplexe Instruktionen wie z.B. LEAVE, ENTER und LOOP verbrauchen unnötig viel Zeit. Es ist daher besser, sie durch Befehlsfolgen einfacherer Instruk- tionen zu umschreiben (siehe zu LOOP auch OPT0001). ENTER kann z.B. mit einer Befehlsfolge ähnlich "PUSH eBP; MOV eBP, eSP; SUB eSP,COUNT" besser ersetzt werden (siehe z.B. Source in LSG0004)...

Displacements ------------- Kurz und bündig: Arbeitet man häufig mit einer Variable und Displacement, so ist es besser dieses in ein Register zu laden - Konstante Displacements ver- brauchen immer etwas Zeit zum Decodieren.

REP MOVSD --------- Vergesst nicht diese Instruktion, wenn Ihr 32Bit-Blöcke verschieben wollt, denn diese Kombination ersetzt die Befehlsfolge

Rep_Loop: MOV EAX,[ESI] ADD ESI,4 MOV [EDI],EAX ADD DI,4 DEC ECX JNE Rep_Loop

Diese "superoptimierte" Befehlsfolge braucht auf einem 386 21n-4 Ticks und auf einem 486 8n-2 Ticks, während REP MOVSD nur 7n+2 Ticks braucht. Obige Routine benötigt 13 Bytes, ein REP MOVSD nur 2, das auch EAX unangetastet lässt und nicht den Branch Target Buffer des P5+ strapaziert.

MOV EAX und Konsorten --------------------- Hmm, nocheinmal LEA. Um einen Wert in EAX zu schreiben,gibt es eine grössen- mässig bessere Möglichkeit: LEA EAX,[1234h] ist nämlich äquivalent zu einem MOV EAX,1234h... Aber Achtung: Einige Editoren mögen LEA mit einer Konstan- ten nicht - d.h. man muss HARDCODEN und die entsprechenden Hexkombinationen eintippseln...

TASM: MOVS WORD PTR ------------------- Unter TASM gibt es ein paar lustige Makros, die es erlauben,eine Instruktion wie MOVS WORD PTR ES:[DI],ES:[SI] zu einem SEGES; MOVSW zu verkürzen. Derar- tige Makros existieren für alle Segmentpräfixe...


(Übersicht)

Pairing

Topic noch zu vergeben.








converted with af2html V 0.01d Win95/NT
a Green meadoW production MXMVIII
copyright © by Guido Wischrop