funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

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

25. 5. 2015 — k47

Před ně­ko­lika dny Jan Smitka na twit­ter post­nul vý­sledky ben­chmarků PHP7 a HHVM. Vý­sle­dek uka­zuje, že PHP7 se rych­lostí blíží HHVM a někdy ho i pře­ko­nává. To je po­ně­kud ne­če­kané, pro­tože, i když bylo PHP7 značně vy­lep­šené a zrych­lené, HHVM má pl­no­hod­notný JIT kom­pi­lá­tor, který by měl vyhrát na celé čáře.

V ben­chmar­cích byly také vý­sledky perfu a po chvíli zírání do stěny čísel jsem našel to, co by mohlo vy­svět­lo­vat, proč je HHVM po­ma­lejší, než by člověk oče­ká­val: L1-icache-load-missesiTLB-load-misses.

Abych vy­svět­lil proč jsou tyto dva čítače tak dů­le­žité, musím to vzít okli­kou přes nej­dů­le­ži­tější část pro­ce­sorů: cache.


Jak všichni jistě vědí, cache je malá a rychlá paměť, která se na­chází na kře­mí­kové placce pro­ce­soru a ca­chuje ak­tivní data. L1 cache může mít pro před­stavu 32KB a la­tenci 3 takty. RAM na­proti tomu může mít něco kolem te­ra­bajtu, ale data z ní putují se zpož­dě­ním až ٍٍ±300 taktů. Právě cache tvo­řící hi­e­rar­chii o ně­ko­lika úrov­ních (L1 – prťavá & rychlá, L3 velká & pomalá1) v ide­ál­ním pří­padě2 vy­tvoří iluzi, že paměť je neje­nom velká ale také rychlá.3

Cache je zcela zá­sadní, pro­tože rozdíl mezi čtením z re­gis­tru a RAM je ob­rov­ský. Kdyby paměť do­ká­zala dodat data v jednom taktu, ca­cho­vání by nebylo třeba. V prehis­to­ric­kých dobách tomu tak bylo, ale rych­lost CPU rostla rych­leji než rych­lost pamětí a to vedlo k uve­dení cache – nej­prve in­strukční cache, pak datové, pak dal­ších úrovní a pre­fetch apa­rátu a dy­na­mic­kých spe­ku­lací. V tomto ohledu se ne­za­svě­ce­ným může zdát, že se pro­ce­sory cho­vají po­divně, ale není to proto, že to někomu při­pa­dalo jako dobrý nápad, ale proto, že to bylo ne­zbytné4.

A teď, co se stane, když data nejsou v L1 cache? Pro­ce­sor zkon­t­ro­luje L2, pak L3 a když ne­u­spěje ani tam, jde rovnou do paměti a za­platí za to pár de­sít­kami na­no­sekund. Na­štěstí mo­derní CPU jsou out-of-order su­per­ska­lární bestie s SMT/Hy­perthrea­din­gem při ruce, takže i když musí čekat na jeden load, v pi­pe­line má při­pra­vené další in­strukce, které můžou běžet ne­zá­visle na pro­bí­ha­jí­cím čtení z paměti. Když bude mít veliké štěstí, podaří se mu vy­pl­nit celou pro­dlevu uži­teč­nou prací, nebo aspoň narazí na pár dal­ších load ope­rací, které můžou čekat pa­ra­lelně.

To není zas tak strašné.

Si­tu­ace však může být o něco horší, když se do věci začne míchat vir­tu­ální paměť a ma­po­vání strá­nek. Pro­gram běží v pro­cesu, který ne­při­stu­puje k fy­zické paměti (tu vidí je kernel ope­rač­ního systém), ale k pouhé abs­trakci – vir­tu­ální paměti. Ta po­sky­tuje iluzi, že proces má pro sebe celý 32bitový nebo 64bitový ad­resní pro­stor, který je zcela od­dě­lený od paměti jiných pro­cesů. Aby to fun­go­valo svižně je po­třeba adresy pře­klá­dat za pomoci TLB (translation loo­kaside buffer) – ma­lič­kého kusu hard­waru, který pro ak­tu­álně bežící proces ca­chuje ma­po­vání vir­tu­ál­ních strá­nek na fy­zické.

Vždycky když chci načíst nějaký kus dat z paměti nebo cache, musím nej­prve nechat TLB pře­lo­žit vir­tu­ální adresu na fy­zic­kou a pak teprve najít, kde daný kus dat sídlí. V dů­sledku toho musí být TLB velice rychlá, což zna­mená, že žere hodně proudu a nemůže být moc velká.5,6

Co na­stane, když kus paměti, který chci číst, leží ve stránce, jejíž ma­po­vání není v TLB? Nejen že musím čekat na sa­motná data než dorazí z RAM, ale před­tím musím čekat než přečtu ta­bulku strá­nek (page table) a najdu v ní ma­po­vání po­ža­do­vané vir­tu­ální adresy. Ta­bulka strá­nek se na­chází v paměti a má ně­ko­lik úrovní. Počet cest do paměti na­jed­nou ne­pří­jemně roste a s nimi i la­tence. Avšak pořád je možné dělat ně­ko­lik ta­ko­vých čtení na­jed­nou.

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

První cache byly in­strukční, teprve po nich při­byly datové cache, pak další sdí­lené úrovně a pak ještě rych­lejší in­strukční cache. Jme­no­vitě L0 cache, která ob­sa­huje in­strukce de­kó­do­vané na mi­k­ro­o­pe­race (šetří se tak práce de­ko­déru) a loop buffer (také μop queue nebo podle Intelu loop stream de­tec­tor), který ob­sa­huje ně­ko­lik málo de­kó­do­va­ných in­strukcí horké smyčky.

Jak je vidět, in­strukční cache má mnohem víc úrovní a to má velice dobrý důvod: Když data nejsou v cache, pro­ce­sor může dělat něco jiného, může vy­ko­ná­vat jiné ne­zá­vislé ope­race, ale když nemá k dis­po­zici ná­sle­du­jící in­strukce, nemůže dělat vůbec nic, jen čekat7.

Teď si k tomu při­počtěte si­tu­aci, kdy ná­sle­du­jící in­strukce nejen že nejsou v cache, ale na­chází se na stránce paměti, která není v TLB. Pro­ce­sor musí nejdříve na­pl­nit TLB a pak teprve hráb­nout do paměti. Po celou tuhle dobu nemůže dělat vůbec nic.

A právě tuto si­tu­aci po­pi­sují udá­losti L1-icache-load-missesiTLB-load-misses – L1 in­strukční cache ne­ob­sa­huje po­třebný kus bi­nárky a po­ža­do­vaná stránka s bi­nár­kou není v in­strukční TLB – jde o ty nej­horší možné si­tu­ace, které můžou nastat. Čekáme, než nám šéf zavolá, co máme dělat.

perf uka­zuje, že HHVM vy­vo­lává nad­měrně mnoho těchto dvou udá­lostí a já se do­mní­vám, že tohle má značný vliv na srov­nání s PHP7.

Otázka zní: Proč?

Podle mých in­for­mací HHVM po­u­žívá tra­cing JIT na úrovni zá­klad­ních bloků:

HHVM’s JIT uses a trace-based form of com­pi­lation that limits each trace to a single basic block where the input types are known at translation time (the „tra­ce­let“ ap­pro­ach).

Basic block je kus kódu, který má jeden entry point a jeden exit point. Pokud HHVM spe­ci­a­li­zuje a kom­pi­luje každý blok zvlášť, vy­tváří velké množ­ství malých seg­mentů in­strukcí, které se ne­na­chází nutně v pořadí od­po­ví­da­jí­címu zdro­jo­vému kódu. Mezi seg­menty (které za­čí­nají gu­ar­dem kon­t­ro­lu­jí­cím jesti pre­con­di­tion platí), se kon­t­rola pře­dává skoky. Není těžké si před­sta­vit, že to povede k si­tu­aci, kdy CPU skáče na mnoho růz­ných míst v paměti, které se ne­ve­jdou do L1I cache a jejich stránky nejsou v iTLB a to se pro­jeví jako pomalý pro­gram a nad­míra L1-icache-load-missesiTLB-load-misses.

Avšak bez po­drob­ného zkou­mání vy­ge­ne­ro­va­ných bi­ná­rek jde jen o odhady a spe­ku­lace.


  1. L3 často není vý­razně rych­lejší než RAM, ale šetří pře­no­so­vou ka­pa­citu a proud. Když pro­ce­sor nemusí pro data do RAM, ale je ob­slou­žen z L3, ne­vy­tě­žuje sys­té­mový ban­dwi­dth a DRAM kon­t­ro­lér nemusí být pár na­no­sekund na­pá­jen, což má dopad na te­pelné vlast­nosti čipu. Cen­taur čip na Power8 pro­ce­so­rech od IBM, který se dá po­va­žo­vat za L4 cache nebo DRAM buffer, fun­guje po­dobně.
  2. Cache sází na tři aspekty: spa­tial lo­ca­lity, tem­po­ral lo­ca­lity a sek­venční povahu dat – tedy: když budu po­tře­bo­vat nějaká data s nej­větší prav­dě­po­dob­ností mě budou za­jí­mat i ta, která se na­chází v nej­bliž­ším okolí (data se na­čí­tají po vět­ších blo­cích cache-line), když jsem nějaká data po­tře­bo­val teď, s nej­větší prav­dě­po­dob­ností je budu po­tře­bo­vat i za chvíli (data zů­sta­nou v cache do té doby dokud je jiná po­třebná ne­vy­tlačí) a když pro­chá­zím data sek­venčně s nej­větší prav­dě­po­dob­ností budu po­tře­bo­vat i ta ná­sle­du­jící a CPU je pre­fetchne. Když při­stu­puji k datům na ne­před­ví­da­tel­ných ad­re­sách v ne­před­ví­da­tel­ném pořadí, cache nemá žádný vliv. Na­štěstí se to ne­stává často, pro­tože pro­gramy mají ob­vykle velice před­ví­da­telný a pra­vi­delný průběh.
  3. Na mnoha pro­ce­so­rech je možné zcela za­ká­zat po­u­žití cache a vý­sledný stroj běží až ko­micky pomalu. Viz tato pre­zen­tace froze cache útoku.
  4. Ně­které věci nejsou ne­zbytné, ale jde o hříchy našich otců, kte­rých se ne­mů­žeme zbavit, jako na­pří­klad ba­rokní schéma kó­do­vání x86 in­strukcí se všemi escape sek­ven­cemi a pre­fixy.
  5. Ně­které pro­ce­sory pro ad­re­so­vání dat v L1 cache po­u­ží­vají vir­tu­ální adresu, kdy pa­ra­lelně načtou data z L1 cache a zá­ro­veň v TLB vy­hle­dají od­po­ví­da­jící fy­zic­kou adresu a tu pak po­u­žijí k ově­ření, že je to správná cache line. Viz Adress translation.
  6. Bylo na­vr­ženo ně­ko­lik pří­stupů, jak od­stra­nit tuto ne­e­fek­ti­vitu. Jeden z nich je zavést ja­kousi super-stránku, která po­krývá vět­šinu paměti, je alo­ko­vána při startu sys­tému. Pro pře­lo­žení adresy v této stránce stačí zjisti, jestli adresa spadá do daného roz­sahu a pak k ní při­číst offset, což je tri­vi­ální a velice rychlá ope­race. Tento pří­stup se hodí pro ser­ve­rové apli­kace, jako na­pří­klad mem­cache, kdy na ser­veru běží jedna apli­kace – jme­no­vitě mem­ca­ched, která vy­u­žívá na­pros­tou vět­šinu paměti ser­veru. Další pří­stup, jaký zvo­lili vý­vo­jáři ar­chi­tek­tury Mill, je použít jeden 64 bitový pa­mě­ťový pro­stor, který je sdílen všemi pro­cesy, ale stále po­sky­tuje ochranu paměti. Proto, že jde o jeden pro­stor ve kterém různé apli­kace ne­mů­žou mít stejné adresy, ali­a­sing ne­před­sta­vuje pro­blém a v dů­sledku toho je možné ad­re­so­vat data v cache pomocí vir­tu­ální adresy. TLB je po­tř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 (re­la­tivně) pomalá.
  7. Hy­perthrea­ding tech­nicky může mírně pomoci, pro­tože za­tímco jedno vlákno čeká, druhé má všechny pro­středky jádra pro sebe a může v klidu po­kra­čo­vat v práci.

Dále k tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články