Wie das Ersetzen eines Buchstabens im Assembler die Division um das Dreifache beschleunigt: Eine technische Analyse
Moderne x86-64-Prozessoren verwenden eine Registerhierarchie mit einer vererbten Struktur. Das rax-Register (64 Bit) umfasst:
┌───────────────────────────────────────────────────────────────┐
│ rax (64 Bit) │
├───────────────────────────────┬───────────────────────────────┤
│ (obere 32) │ eax (32 Bit) │
│ ├───────────────┬───────────────┤
│ │ │ ax (16 Bit) │
│ │ ├───────┬───────┤
│ │ │ah (8) │al (8) │
└───────────────────────────────┴───────────────┴───────┴───────┘Wichtiger Punkt: Das Schreiben in die unteren Teile des Registers (ax, al) beeinflusst die oberen Bits nicht, während Operationen mit 32-Bit-Registern (eax) die oberen 32 Bits vollständig überschreiben. Dies erzeugt versteckte Abhängigkeiten, die für das Pipelining entscheidend sind.
Die Divisionsanweisungen div/idiv verwenden ein Registerpaar:
┌──────────┬────────────────┬──────────────┬─────────────────────┐
│ Größe │ Dividende │ Quotient in │ Rest in │
├──────────┼────────────────┼──────────────┼─────────────────────┤
│ 16-Bit │ dx:ax │ ax │ dx │
├──────────┼────────────────┼──────────────┼─────────────────────┤
│ 32-Bit │ edx:eax │ eax │ edx │
├──────────┼────────────────┼──────────────┼─────────────────────┤
│ 64-Bit │ rdx:rax │ rax │ rdx │
└──────────┴────────────────┴──────────────┴─────────────────────┘Vor der Division muss der obere Teil des Paares auf Null gesetzt werden. Standardmuster:
mod edx, 0
mov eax, 536700
div dword [denominator]Experimentelle Daten: 3,7-facher Unterschied
Die Testschleife verarbeitete 2.073.600 Iterationen (1920×1080) und simulierte Pixel-Rendering. Ergebnisse in Zyklen pro Iteration (nach Abzug des Schleifenoverheads):
┌────────┬──────────────┬──────────────┐
│ │ idiv (rein) │ div (rein) │
├────────┼──────────────┼──────────────┤
│ 16-Bit │ 22,2 │ 22,2 │
├────────┼──────────────┼──────────────┤
│ 32-Bit │ 6,0 │ 6,0 │
├────────┼──────────────┼──────────────┤
│ 64-Bit │ 26,2 │ 24,1 │
└────────┴──────────────┴──────────────┘Überraschung: 32-Bit-Operationen laufen 3,7-mal schneller als 16-Bit-Operationen bei identischen Eingabedaten. Der Grund liegt nicht in der Komplexität des Divisionsalgorithmus, sondern in mikroarchitektonischen Ausführungsdetails.
Mechanismus falscher Abhängigkeiten
Prozessoren verwenden die Register Alias Table (RAT), um logische Register auf physische zu mappen. Bemerkenswert:
- Das Schreiben in ein 32-Bit-Register (
mov edx, ...) überschreibt vollständig den Wert und bricht Abhängigkeiten zu vorherigen Operationen - Das Schreiben in ein 16-Bit-Register (
mov dx, ...) erfordert Zusammenführen neuer Daten mit oberen Bits und erzeugt eine falsche Abhängigkeit
In der 16-Bit-Variante sieht die Abhängigkeitskette so aus:
div word → merge → mov dx → merge → div word → ...Jede Iteration muss auf die vorherige warten wegen der Registerzusammenführungsanforderungen. In der 32-Bit-Variante bricht diese Kette, was dem Prozessor ermöglicht, die Ausführung zu pipelinen.
Wichtige Leistungsmetriken
- Latenz: 21–22 Zyklen für 16-Bit-
div(Zeit bis Ergebnis bereit) - Throughput: 6 Zyklen für 16-Bit-
div(Ausgabungsintervall zwischen Operationen)
Wenn Operationen voneinander abhängen, ist die Latenz der Engpass. Bei unabhängigen Operationen – das Throughput. Das Verhältnis 22/6 ≈ 3,7 erklärt die Beschleunigung.
Hypothesenprüfung: Ersetzen eines Buchstabens
Das Experiment bestätigte die Theorie. Ersetzen von 16-Bit-Anweisungen durch 32-Bit-Anweisungen im 16-Bit-Kontext:
; Before
mov dx, 0x0008
mov ax, 0x2B7C
; After
mov edx, 8
mov eax, 0x2B7CFührte zu dramatischen Ergebnissen:
┌───────────────────────┬──────────────┬──────────────┐
│ │ idiv (rein) │ div (rein) │
├───────────────────────┼──────────────┼──────────────┤
│ 16-Bit (mov dx) │ 22,2 │ 22,2 │
├───────────────────────┼──────────────┼──────────────┤
│ 16-Bit (mov edx) │ 7,0 │ 7,0 │
└───────────────────────┴──────────────┴──────────────┘Ein Buchstabe e in der Anweisung eliminierte die falsche Abhängigkeit und reduzierte die Ausführungszeit von 22,2 auf 7,0 Zyklen – genau auf das Throughput-Niveau des Dividers.
Was wichtig ist
- Auswahl der Registergröße ist entscheidend: 32-Bit-Operationen zum Vorbereiten einer 16-Bit-Division eliminieren unnötige Abhängigkeiten
- Latenz vs. Throughput: Abhängigkeiten machen die Leistung latenzbegrenzt, nicht throughputbegrenzt
- Architektonische Feinheiten: Verständnis von RAT und partieller Registerzusammenführung ist essenziell für Low-Level-Optimierungen
- Divider erzeugt Rest schneller: x86 berechnet Quotient und Rest parallel und erlaubt frühere Nutzung von edx vor rax
- Testen ist obligatorisch: Theoretische Schätzungen weichen oft von realen Messungen ab wegen mikroarchitektonischer Eigenarten
Praktische Empfehlungen für Entwickler
- Für Division immer 32-Bit-Operationen verwenden, um obere Registerteile zu nullen, auch bei 16-Bit-Daten
- Vermischen von Registergrößen in Schleifen vermeiden
- Bei leistungs-kritischem Code die Assembler-Ausgabe des Compilers prüfen
- Beachten: Divider-Throughput übersteigt Latenz, aber nur ohne Abhängigkeiten
- Auf modernen CPUs (Ice Lake und neuer) uops.info-Spezifikationen für aktuelle Metriken prüfen
Dieses Experiment zeigt, wie tiefes Mikroarchitekturwissen nicht-offensichtliche Optimierungen aufdeckt. Das Tauschen eines scheinbar sinnlosen Buchstabens in einer Anweisung liefert eine dreifache Beschleunigung, indem künstliche Pipeline-Grenzen entfernt werden. Für Systemsprogrammierer ist es eine Erinnerung: Selbst im Low-Level-Assembly verstecken sich Optimierungschancen im Hardwareverständnis.
— Editorial Team
Noch keine Kommentare.