Optimalizace assembleru: jak jedno písmeno zrychluje kód 3násobně

# Jak změna jedné písmene v assembleru ztrojnásobí rychlost dělení: technický rozbor

Jedna změněná značka v instrukci assembleru zkrátí čas provádění operace dělení o 66 %. Experiment s reálnými měřeními na moderních CPU ukazuje, jak falešné závislosti mezi registry proměňují potenciál out-of-order provádění v úzké místo. Rozkládáme architektonické nuance x86-64 ovlivňující výkon.

Architektonické vlastnosti registrů x86-64

Moderní procesory x86-64 využívají hierarchii registrů s dědičnou strukturou. Registr rax (64 bitů) zahrnuje:

┌───────────────────────────────────────────────────────────────┐
│                           rax (64 bitů)                      │
├───────────────────────────────┬───────────────────────────────┤
│          (horních 32)         │           eax (32 bitů)       │
│                               ├───────────────┬───────────────┤
│                               │               │   ax (16 bitů)│
│                               │               ├───────┬───────┤
│                               │               │ah (8) │al (8) │
└───────────────────────────────┴───────────────┴───────┴───────┘

Klíčový moment: zápis do nižších částí registru (ax, al) neovlivňuje vyšší bity, zatímco operace s 32bitovými registry (eax) úplně přepíšou horních 32 bitů. Tato vlastnost vytváří skryté závislosti, které jsou kritické pro pipeline.

Instrukce dělení div/idiv využívají pár registrů:

┌──────────┬────────────────┬──────────────┬─────────────────────┐
│ Velikost │ Dělenec        │ Podíl v      │ Zbytek v            │
├──────────┼────────────────┼──────────────┼─────────────────────┤
│ 16-bit   │ dx:ax          │ ax           │ dx                  │
├──────────┼────────────────┼──────────────┼─────────────────────┤
│ 32-bit   │ edx:eax        │ eax          │ edx                 │
├──────────┼────────────────┼──────────────┼─────────────────────┤
│ 64-bit   │ rdx:rax        │ rax          │ rdx                 │
└──────────┴────────────────┴──────────────┴─────────────────────┘

Před provedením dělení je nutné vynulovat vyšší část páru. Standardní vzor:

mov edx, 0
mov eax, 536700
div dword [denominator]

Experimentální data: rozdíl 3,7×

Testovací smyčka zpracovávala 2 073 600 iterací (1920×1080), simulující vykreslování pixelů. Výsledky v taktech na iteraci (po odečtení režijních nákladů smyčky):

┌────────┬──────────────┬──────────────┐
│        │ idiv (čist.) │ div (čist.)  │
├────────┼──────────────┼──────────────┤
│ 16-bit │ 22.2         │ 22.2         │
├────────┼──────────────┼──────────────┤
│ 32-bit │  6.0         │  6.0         │
├────────┼──────────────┼──────────────┤
│ 64-bit │ 26.2         │ 24.1         │
└────────┴──────────────┴──────────────┘

Překvapení: 32bitové operace probíhají 3,7krát rychleji než 16bitové při stejných vstupních datech. Důvod nespočívá v složitosti algoritmu dělení, ale ve vlastnostech provádění na úrovni mikroarchitektury.

Mechanismus falešných závislostí

Procesory využívají Register Alias Table (RAT) pro mapování logických registrů na fyzické. Při tom:

• Zápis do 32bitového registru (mov edx, ...) úplně přepíše hodnotu a přeruší závislosti na předchozích operacích
• Zápis do 16bitového registru (mov dx, ...) vyžaduje spojení nových dat s vyššími bity, což vytváří falešnou závislost

V 16bitové variantě řetězec závislostí vypadá takto:

div word → merge → mov dx → merge → div word → ...

Každá iterace musí čekat na dokončení předchozí kvůli nutnosti spojování registrů. V 32bitové variantě se tento řetězec přeruší, což umožňuje procesoru pipeline provádění.

Klíčové metriky výkonu

• Latency: 21–22 takTů pro 16bitové div (čas do připravenosti výsledku)
• Throughput: 6 takTů pro 16bitové div (interval mezi spuštěním operací)

Když jsou operace závislé, limitujícím faktorem je latency. U nezávislých operací je to throughput. Poměr 22/6 ≈ 3,7 vysvětluje pozorované zrychlení.

Ověření hypotézy: změna jedné písmene

Experiment potvrdil teorii. Nahrazení 16bitových instrukcí 32bitovými v 16bitovém kontextu:

; Bylo
mov dx, 0x0008
mov ax, 0x2B7C

; Stalo se
mov edx, 8
mov eax, 0x2B7C

Vedlo k radikální změně výsledků:

┌───────────────────────┬──────────────┬──────────────┐
│                       │ idiv (čist.) │ div (čist.)  │
├───────────────────────┼──────────────┼──────────────┤
│ 16-bit (mov dx)       │ 22.2         │ 22.2         │
├───────────────────────┼──────────────┼──────────────┤
│ 16-bit (mov edx)      │  7.0         │  7.0         │
└───────────────────────┴──────────────┴──────────────┘

Jedno písmeno e v instrukci odstranilo falešnou závislost a zkrátilo čas provádění z 22,2 na 7,0 takTů – přesně na úroveň throughput děliče.

Co je důležité

• Výběr velikosti registru je kritický: Použití 32bitových operací pro přípravu 16bitového dělení odstraní zbytečné závislosti
• Latency vs Throughput: Při přítomnosti závislostí výkon určuje latency, ne throughput
• Architektonické nuance: Porozumění RAT a partial register merging je nutné pro nízkourovňovou optimalizaci
• Děliče vrací zbytek rychleji: V x86 je implementováno paralelní výpočet podílu a zbytku, což umožňuje použít edx dříve než rax
• Testování je nezbytné: Teoretické odhady často nesouhlasí s reálnými měřeními kvůli mikroarchitektonickým vlastnostem

Praktické doporučení pro vývojáře

• Při práci s dělením vždy používejte 32bitové operace pro vynulování vyšších částí registrů, i když pracujete se 16bitovými daty
• Vyhněte se míchání operací s různými velikostmi registrů ve smyčkách
• Pro výkonově kritické části kódu kontrolujte assemblerový výstup kompilátoru
• Berte v úvahu, že throughput děliče je vyšší než jeho latency, ale pouze při absenci závislostí
• Na moderních CPU (Ice Lake a novější) kontrolujte specifikace uops.info pro aktuální metriky

Experiment ukazuje, jak hluboké porozumění mikroarchitektuře umožňuje nalézt neobvyklé body optimalizace. Změna jedné písmene v instrukci, která na první pohled vypadá nesmyslně, přináší trojnásobné zrychlení díky odstranění umělých omezení pipeline. Pro vývojáře systémového softwaru je to připomínka: i v tak nízkourovňových konstrukcích jako assemblerové instrukce se skrývají možnosti optimalizace, dostupné pouze při porozumění „železu“ pod kapotou.

— Editorial Team