mikro-neefektivity
Vrtám se teď v C++ zdrojácích VCMI – reimplementace klasické tahovky Heroes of Might and Magic 3 – ve snaze to trochu zrychlit. Když jsem hrál na svém starém laptopu, na gigantické mapě tahy 7 počítačových oponentů trvaly 2 minuty. To bylo dost času na to, abych nastaroval perf, jeden tah sbíral data a potom, co jsem odehrál svůj tah, jsem další dvě minuty zkoumal, kde jsou slabá místa.
Je jich nepřeberně.
Neefektivní datové struktury, O(n) kód, kde by měl být O(1), třídy a structy jsou příliš velké, používající neefektivní reprezentaci dat. A pak tisíc dalších maličkých mikro-neefktivit.
Jako příklad si vezměte funkci, co kontroluje, jestli se daná souřadnice nachází v mapě.
bool CMap::isInTheMap(const int3 & pos) const { return pos.x >= 0 && pos.y >= 0 && pos.z >= 0 && pos.x < width && pos.y < height && pos.z <= (twoLevel ? 1 : 0); }
Je to maličká věc, která se přeloží na 19 instrukcí. Co na ní může být špatného? Jen v ní se stráví 1.3% času a tak je to kandidát na optimalizaci.
Můžu ji přepsat do následující podoby:
bool CMap::isInTheMap(const int3 & pos) const { return (uint32_t)pos.x < width && (uint32_t)pos.y < height && (uint32_t)pos.z <= (twoLevel ? 1 : 0); }
Tuhle techniku jsem poprvé viděl ve zdrojácích PHP. Pokud je pozice negativní, při konverzi na int bez znaménka se z ní stane velká pozitivní hodnota, vždy větší než všechny znaménkové inty. Ušetříme si tak 3 porovnání s nulou. Kompilátor tuhle transformaci nemůže udělat sám, protože neví, že velikost mapy je vždy pozitivní.
Výsledná binárka je pak tohle:
mov 0x44(%rdi),%edx xor %eax,%eax cmp %edx,(%rsi) jae exit mov 0x40(%rdi),%ecx cmp %ecx,0x4(%rsi) jae exit movzbl 0x48(%rdi),%eax cmp 0x8(%rsi),%eax setae %al .exit ret
Jen 11 instrukcí a to ušetří asi 0.5% času.
Dál: int3 argument se předává jako reference, tedy jako pointer,
takže když volající má x, y, z souřadnice v registrech, musí je zkopírovat na
zásobník, jen aby je funkce isInTheMap o pár instrukcí dál z paměti zase
vytáhla. Nepřestavuje to velké zpomalení, L1 cache má latenci obvykle 3-5
taktů, ale čtení z registru je zadarmo.
Protože jde o struct, podle System V ABI by se tři inty poslaly ve dvou registrech a funkce by musela udělat nějaké shifty, ale to je teď vedlejší.
Dál: protože jádro VCMI se kompiluje jako knihovna, která se dynamicky linkuje jak ze serveru, tak i z klienta, volání probíhá přes plt.
call CMap::isInTheMap@plt
V plt stubu je pak něco jako
jmp *0x79845a(%rip)
Další úroveň indirekce, další zpomalení. Podle perfu se jen v plt pahýlech strávilo 0.2% času.
Ale hlavní je, že i takto jednoduchá funkce nebude inlinována. A konvence volání říká, že některé registry nemusí přežít a tak je volající buď nemůže použít a alokátor registrů má svázané ruce, nebo si je musí uložit na zásobník. Zase je to další malá komplikace a další malá neefektivita.
Když se podívám na binárku, je vidět, že jen 6 instrukcí dělá užitečnou práci. Tolik by jich v ideálním případě zůstalo po inlinování.
mov 0x44(%rdi),%edx // argument xor %eax,%eax // návratová hodnota cmp %edx,(%rsi) // užitečná práce jae exit // užitečná práce mov 0x40(%rdi),%ecx // argument cmp %ecx,0x4(%rsi) // užitečná práce jae exit // užitečná práce movzbl 0x48(%rdi),%eax // argument cmp 0x8(%rsi),%eax // užitečná práce setae %al // užitečná práce, jmp po inlinování .exit ret // návratová hodnota
Navíc kompilátor může provádět kontextovou optimalizaci. Pokud je po inlinování
vidět, že se souřadnice z nemění (např. dívám se na sousední políčka v jedné
úrovni, kompilátor z zkontroluje jen jednou a pak dvě instrukce zcela vynechá.
To je jeden případ mikro-neefektivity na kterou jsem narazil. Teď si
představte, že jich je tam tisíc, ale přesto jsou zcela zastíněné čtením z paměti, protože data jsou zkrátka prostě příliš velká a nevejdou se rozumně do
cache. V jedné funkci, hned po volání isInTheMap, následuje mov co poprvé
sáhne na dané struct TerrainTile a jen na tomhle jednom movu se stráví
0.56% celkového času.