0xDEADBEEF

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.