Jak optimalizovat deoptimalizací
Když jsem si připravoval dnešní přednášku na Poslední Sobotu, ve které jsem plánoval odhalit všechny podivnosti v chování a výkonu PHP polí, a hrabal se v céčkovských zdrojácích Zend enginu, omylem se mi povedlo napsat rychlejší verzi funkce, kterou PHP používá k hashování stringů. Zajímavé na celé věci byl hlavně fakt, že zrychlení jsem dosáhl tím, že jsem se zbavil low-level optimalizací a napsal funkci mnohem hloupěji, hůře a méně rafinovaně.
Někdy méně je zkrátka více, worse is better a kompilátor se v kombinaci s moderním hardware postará o zbytek.
Jak už jsem dříve psal, PHP používá hashovací funkci DJBX33A, která není příliš dobrá, protože útočník může snadno uhodnout klíče s kolidujícími hashi. Při práci s takovými klíči se konstantní časová složitost, pro kterou hash tabulky uctíváme a milujeme, změní na složitost lineární. Hash-flood útok na sebe pak nenechá dlouho čekat. Jak se říká: tvoje hash tabulka je jenom tak dobrá, jak dobrá je tvoje hash funkce. Ale na druhou stranu je DJBX33A aspoň rychlá.
V podstatě vypadá následovně:
long DJBX33A(const unsigned char *key) { unsigned long hash = 5381; while(*key) hash = 33 * hash + *key++; return hash; }
Potřebuje provést jen pár instrukcí na každý znak hashovaného stringu.
V PHP má pak následující znatelně méně elegantní podobu:
unsigned long zend_inline_hash_func(const char *str, int len) { unsigned long hash = 5381UL; /* variant with the hash unrolled eight times */ for (; len >= 8; len -= 8) { hash = ((hash << 5) + hash) + *str++; hash = ((hash << 5) + hash) + *str++; hash = ((hash << 5) + hash) + *str++; hash = ((hash << 5) + hash) + *str++; hash = ((hash << 5) + hash) + *str++; hash = ((hash << 5) + hash) + *str++; hash = ((hash << 5) + hash) + *str++; hash = ((hash << 5) + hash) + *str++; } switch (len) { case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ case 1: hash = ((hash << 5) + hash) + *str++; break; case 0: break; } return hash; }
Smyčka je osmkrát odrolovaná a místo násobení provádí jeden shift a jeden součet (odrolování má překvapivě velký dopad na rychlost).
To dává smysl, protože sčítání, bitové operace a bitové posuny jsou rychlé operace a násobení patří mezi ty pomalé. Některé prastaré RISC procesory dokonce ani násobit neuměly a místo toho musel program provést několik součtů. (Teď pominu například fakt, že P4 měly pomalé shift instrukce, protože to už je dávná historie.)
Na současných procesorech má násobení (imul) latenci tři takty; shift a
součet pak jeden takt, ale každý takt jich může být vykonáno několik
(viz). Ve světle těchto skutečností to vypadá, že se manuální
optimalizace vyplatí a kód je ideální.
Až na to, že všechny operace jsou závislé jedna na druhé.
To mi nedalo a po chvíli pokusů a omylů jsem vyprodukoval následující verzi hashe, který si se svým PHP předkem v ošklivost v ničem nezadá.
#define M1 (33UL) #define M2 (33UL*33) #define M3 (33UL*33*33) #define M4 (33UL*33*33*33) #define M5 (33UL*33*33*33*33) #define M6 (33UL*33*33*33*33*33) #define M7 (33UL*33*33*33*33*33*33) #define M8 (33UL*33*33*33*33*33*33*33) unsigned long MS[8] = { 1, M1, M2, M3, M4, M5, M6, M7 }; unsigned long ilp_hash(const char *str, int len) { unsigned long hash = 5381UL; for (; len >= 8; len -= 8) { hash *= M8; hash += M7 * str[0]; hash += M6 * str[1]; hash += M5 * str[2]; hash += M4 * str[3]; hash += M3 * str[4]; hash += M2 * str[5]; hash += M1 * str[6]; hash += str[7]; str += 8; } hash *= MS[len]; switch (len) { case 7: hash += M6 * str[len-7]; /* fallthrough... */ case 6: hash += M5 * str[len-6]; /* fallthrough... */ case 5: hash += M4 * str[len-5]; /* fallthrough... */ case 4: hash += M3 * str[len-4]; /* fallthrough... */ case 3: hash += M2 * str[len-3]; /* fallthrough... */ case 2: hash += M1 * str[len-2]; /* fallthrough... */ case 1: hash += str[len-1]; break; case 0: break; } return hash; }
A výsledek je na mém Haswellu překvapivě rychlejší. Na dlouhých klíčích dokonce výrazně rychlejší. Spočítání 100 milionu hashů trvá takhle dlouho:
| délka klíče | zend_inline_hash_func | ILP_hash | rozdíl |
|---|---|---|---|
| 4 | 280 ms | 253 ms | -10% |
| 6 | 337 ms | 280 ms | -16% |
| 10 | 504 ms | 440 ms | -12% |
| 20 | 949 ms | 755 ms | -20% |
| 50 | 2824 ms | 1764 ms | -37% |
| 100 | 6028 ms | 3667 ms | -39% |
Nová verze nepoužívá iterativní verzi hashe, ale ekvivalentní formu
hash * 33n-1 + Σ(ki * 33n-i-1).
)
Ta má tu výhodu, že jedna iterace není závislá na té předchozí, což je hlavní
problém původní implementace: Jednu iteraci hashe může vypočítat až potom, co
je předchozí iterace dokončená. Stejně tak z pointeru str může číst až po
tom, co byl inkrementován. Není možné využít příliš mnoho ILP (instruction level
parallelism). Moderní hardware může částečně pomoci, když se pustí do divokého
přejmenovávání registrů, ale kde nic není, ani out-of-order jádro nebere.
ILP verze může všechny movy provádět najednou, každý takt začít s jedním
násobením a o tři takty později ho přičíst k proměnné hash. Chytrý kompilátor
(v tomto případě GCC) přeloží násobení 33 na rychlejší operace a překvapivě to
udělá i v případě násobení (n * 33 * 33), které mohou být provedeny také paralelně
s násobením předchozích iterací.
Výsledkem tohoto aplikovaného diletantství je funkce, která potřebuje méně
instrukcí, méně taktů procesoru a má vyšší ILP (v exrémních případech perf
hlásí rekordních 4.18 instrukce za takt) a to jenom proto, že její jednotlivé
kroky jsou na sobě nezávislé a hardware je tedy může vykonat paralelně.
A pointa: PHP hashe nepočítá zas tak často a (stejně jako Java) ve string objektu ukládá už jednou spočítaný hash. Navíc hashování už tak potřebuje jen pár taktů na každý znak řetězce. Takže i když je moje funkce o něco rychlejší, akcelerace nemá ve výsledku skoro žádný dopad.
No jo, co nadělám.