L1I cache a iTLB - když ani spekulace nepomůžou

25. 5. 2015

Před několika dny Jan Smitka na twitter postnul výsledky benchmarků PHP7 a HHVM. Výsledek ukazuje, že PHP7 se rychlostí blíží HHVM a někdy ho i překonává. To je poněkud nečekané, protože, i když bylo PHP7 značně vylepšené a zrychlené, HHVM má plnohodnotný JIT kompilátor, který by měl vyhrát na celé čáře.

V benchmarcích byly také výsledky perfu a po chvíli zírání do stěny čísel jsem našel to, co by mohlo vysvětlovat, proč je HHVM pomalejší, než by člověk očekával: L1-icache-load-misses a iTLB-load-misses.

Abych vysvětlil proč jsou tyto dva čítače tak důležité, musím to vzít oklikou přes nejdůležitější část procesorů: cache.

Jak všichni jistě vědí, cache je malá a rychlá paměť, která se nachází na křemíkové placce procesoru a cachuje aktivní data. L1 cache může mít pro představu 32KB a latenci 3 takty. RAM naproti tomu může mít něco kolem terabajtu, ale data z ní putují se zpožděním až ٍٍ±300 taktů. Právě cache tvořící hierarchii o několika úrovních (L1 - prťavá & rychlá, L3 velká & pomalá¹ ) v ideálním případě² vytvoří iluzi, že paměť je nejenom velká ale také rychlá.³

Cache je zcela zásadní, protože rozdíl mezi čtením z registru a RAM je obrovský. Kdyby paměť dokázala dodat data v jednom taktu, cachování by nebylo třeba. V prehistorických dobách tomu tak bylo, ale rychlost CPU rostla rychleji než rychlost pamětí a to vedlo k uvedení cache - nejprve instrukční cache, pak datové, pak dalších úrovní a prefetch aparátu a dynamických spekulací. V tomto ohledu se nezasvěceným může zdát, že se procesory chovají podivně, ale není to proto, že to někomu připadalo jako dobrý nápad, ale proto, že to bylo nezbytné⁴ .

A teď, co se stane, když data nejsou v L1 cache? Procesor zkontroluje L2, pak L3 a když neuspěje ani tam, jde rovnou do paměti a zaplatí za to pár desítkami nanosekund. Naštěstí moderní CPU jsou out-of-order superskalární bestie s SMT/Hyperthreadingem při ruce, takže i když musí čekat na jeden load, v pipeline má připravené další instrukce, které můžou běžet nezávisle na probíhajícím čtení z paměti. Když bude mít veliké štěstí, podaří se mu vyplnit celou prodlevu užitečnou prací, nebo aspoň narazí na pár dalších load operací, které můžou čekat paralelně.

To není zas tak strašné.

Situace však může být o něco horší, když se do věci začne míchat virtuální paměť a mapování stránek. Program běží v procesu, který nepřistupuje k fyzické paměti (tu vidí je kernel operačního systém), ale k pouhé abstrakci - virtuální paměti. Ta poskytuje iluzi, že proces má pro sebe celý 32bitový nebo 64bitový adresní prostor, který je zcela oddělený od paměti jiných procesů. Aby to fungovalo svižně je potřeba adresy překládat za pomoci TLB (translation lookaside buffer) - malého kusu hardwaru, který pro aktuálně bežící proces cachuje mapování virtuálních stránek na fyzické.

Vždy když chci načíst nějaký kus dat z paměti nebo cache, musím nejprve nechat TLB přeložit virtuální adresu na fyzickou a pak teprve najít, kde daný kus dat sídlí. V důsledku toho musí být TLB velice rychlá, což znamená, že žere hodně proudu a nemůže být moc velká.⁵ ⁶

Co nastane, když kus paměti, který chci číst, leží ve stránce, jejíž mapování není v TLB? Nejen že musím čekat na samotná data než dorazí z RAM, ale předtím musím čekat než přečtu tabulku stránek (page table) a najdu v ní mapování požadované virtuální adresy. Tabulka stránek se nachází v paměti a má několik úrovní. Počet cest do paměti najednou nepříjemně roste a s nimi i latence. Avšak pořád je možné dělat několik takových čtení najednou.

Ale může být ještě hůř.

První cache byly instrukční, teprve po nich přibyly datové cache, pak další sdílené úrovně a pak ještě rychlejší instrukční cache. Jmenovitě L0 cache, která obsahuje instrukce dekódované na mikrooperace (šetří se tak práce dekodéru) a loop buffer (také μop queue nebo podle Intelu loop stream detector), který obsahuje několik málo dekódovaných instrukcí horké smyčky.

Jak je vidět, instrukční cache má mnohem víc úrovní a to má velice dobrý důvod: Když data nejsou v cache, procesor může dělat něco jiného, může vykonávat jiné nezávislé operace, ale když nemá k dispozici následující instrukce, nemůže dělat vůbec nic, jen čekat⁷ .

Teď si k tomu připočtěte situaci, kdy následující instrukce nejen že nejsou v cache, ale nachází se na stránce paměti, která není v TLB. Procesor musí nejdříve naplnit TLB a pak teprve hrábnout do paměti. Po celou tuhle dobu nemůže dělat vůbec nic.

A právě tuto situaci popisují události L1-icache-load-misses a iTLB-load-misses - L1 instrukční cache neobsahuje potřebný kus binárky a požadovaná stránka s binárkou není v instrukční TLB - jde o ty nejhorší možné situace, které můžou nastat. Čekáme, než nám šéf zavolá, co máme dělat.

perf ukazuje, že HHVM vyvolává nadměrně mnoho těchto dvou událostí a já se domnívám, že tohle má značný vliv na srovnání s PHP7.

Otázka zní: Proč?

Podle mých informací HHVM používá tracing JIT na úrovni základních bloků:

HHVM’s JIT uses a trace-based form of compilation that limits each trace to a single basic block where the input types are known at translation time (the "tracelet" approach).

Basic block je kus kódu, který má jeden entry point a jeden exit point. Pokud HHVM specializuje a kompiluje každý blok zvlášť, vytváří velké množství malých segmentů instrukcí, které se nenachází nutně v pořadí odpovídajícímu zdrojovému kódu. Mezi segmenty (které začínají guardem kontrolujícím jesti precondition platí), se kontrola předává skoky. Není těžké si představit, že to povede k situaci, kdy CPU skáče na mnoho různých míst v paměti, které se nevejdou do L1I cache a jejich stránky nejsou v iTLB a to se projeví jako pomalý program a nadmíra L1-icache-load-misses a iTLB-load-misses.

Avšak bez podrobného zkoumání vygenerovaných binárek jde jen o odhady a spekulace.

L3 často není výrazně rychlejší než RAM, ale šetří přenosovou kapacitu a proud. Když procesor nemusí pro data do RAM, ale je obsloužen z L3, nevytěžuje systémový bandwidth a DRAM kontrolér nemusí být pár nanosekund napájen, což má dopad na tepelné vlastnosti čipu. Centaur čip na Power8 procesorech od IBM, který se dá považovat za L4 cache nebo DRAM buffer, funguje podobně.
Cache sází na tři aspekty: spatial locality, temporal locality a sekvenční povahu dat - tedy: když budu potřebovat nějaká data s největší pravděpodobností mě budou zajímat i ta, která se nachází v nejbližším okolí (data se načítají po větších blocích cache-line), když jsem nějaká data potřeboval teď, s největší pravděpodobností je budu potřebovat i za chvíli (data zůstanou v cache do té doby dokud je jiná potřebná nevytlačí) a když procházím data sekvenčně s největší pravděpodobností budu potřebovat i ta následující a CPU je prefetchne. Když přistupuji k datům na nepředvídatelných adresách v nepředvídatelném pořadí, cache nemá žádný vliv. Naštěstí se to nestává často, protože programy mají obvykle velice předvídatelný a pravidelný průběh.
Na mnoha procesorech je možné zcela zakázat použití cache a výsledný stroj běží až komicky pomalu. Viz tato prezentace froze cache útoku.
Některé věci nejsou nezbytné, ale jde o hříchy našich otců, kterých se nemůžeme zbavit, jako například barokní schéma kódování x86 instrukcí se všemi escape sekvencemi a prefixy.
Některé procesory pro adresování dat v L1 cache používají virtuální adresu, kdy paralelně načtou data z L1 cache a zároveň v TLB vyhledají odpovídající fyzickou adresu a tu pak použijí k ověření, že je to správná cache line. Viz Adress translation.
Bylo navrženo několik přístupů, jak odstranit tuto neefektivitu. Jeden z nich je zavést jakousi super-stránku, která pokrývá většinu paměti, je alokována při startu systému. Pro přeložení adresy v této stránce stačí zjisti, jestli adresa spadá do daného rozsahu a pak k ní přičíst offset, což je triviální a velice rychlá operace. Tento přístup se hodí pro serverové aplikace, jako například memcache, kdy na serveru běží jedna aplikace - jmenovitě memcached, která využívá naprostou většinu paměti serveru. Další přístup, jaký zvolili vývojáři architektury Mill, je použít jeden 64 bitový paměťový prostor, který je sdílen všemi procesy, ale stále poskytuje ochranu paměti. Proto, že jde o jeden prostor ve kterém různé aplikace nemůžou mít stejné adresy, aliasing nepředstavuje problém a v důsledku toho je možné adresovat data v cache pomocí virtuální adresy. TLB je potřeba jen, když data nejsou v cache a musí se pro ně do paměti. To ale bude samo o sobě trvat pár stovek taktů a tak nevadí, když je TLB velká a (relativně) pomalá.
Hyperthreading technicky může mírně pomoci, protože zatímco jedno vlákno čeká, druhé má všechny prostředky jádra pro sebe a může v klidu pokračovat v práci.

Dále k tématu: