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

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á1) v ideálním případě2 vytvoří iluzi, že paměť je nejenom velká ale také rychlá.3

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é4.

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) – maličkého kusu hardwaru, který pro aktuálně bežící proces cachuje mapování virtuálních stránek na fyzické.

Vždycky 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á.5,6

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, 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 čekat7.

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.


  1. 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ě.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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á.
  7. 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:

Flattr this!

Posted in CPU, Paměť, PHP, VM | Leave a comment

Za jak dlouho procesor vynásobí tisíc čísel

Jednoduchá otázka: Jak rychle dokáže počítač vynásobit tisíc celých čísel? Odpověď, která přijde na mysl jako první: jde o tisíc instrukcí a tedy o tisíc taktů, není tak úplně správná.

Tak předně instrukce celočíselného násobení na x86 procesorech (které nepatří mezi single cycle procesory) trvá 3 takty.

Dohromady to tedy musí trvat 3000 taktů.

Ne tak docela. Moderní procesory jsou pipelinované a i když instrukce trvá 3 takty procesor umí začít s jednou novou operaci každý takt. V každém taktu se tedy můžou překrývat tři fáze třech různých mul instrukcí.

Ok, takže to znamená 1002 taktů. Tisíc instrukcí započatých v tisíci taktech a pak počkat dva takty než doběhne ta úplně poslední.

Ono je to o něco málo složitější. Takhle jednoduše to funguje, pouze když na sobě nejsou jednotlivé instrukce závislé. Pokud nastane situace, že každá instrukce závisí na výsledku té předchozí, musí je procesor vykonávat jednu po druhé. Existují různé hardwarové triky, které v téhle situaci pomůžou jako třeba operand forwarding, kdy se výsledek nezapisuje do registru, ale rovnou se přesměruje do následující instrukce, ale ty pomůžou jen částečně a neodstraní hlavní problém, kterým je závislost operací.

I když v určitých případech nemusí závislost mezi instrukcemi představovat nutně velkou překážku. Pokud na výsledku jedné instrukce nezávisí tři následující, ale až ta za nimi, není nic ztraceno, jak ukazuje následující schéma (čas je na vodorovné ose).

nezávislé operace

+--------+
| 1      |
+--+-----+--+
   | 2      |
   +--+-----+--+
      | 3      |
      +--+-----+--+
         | 4      |
         +--+-----+--+
            | 5      |
            +--+-----+--+
               | 6      |
               +--------+



operace v řádcích na sobě závisí

+--------+  +--------+
| 1      |  | 5      |
+--+-----+-----+-----+--+
   | 2      |  | 6      |
   +--+-----+-----+-----+--+
      | 3      |  | 7      |
      +--+-----+-----+-----+--+
         | 4      |  | 8      |
         +--------+  +--------+


oprace závisí na výsledku předchozí

+--------+--------+--------+--------+--------+
| 1      | 2      | 3      | 4      | 5      |
+--------+--------+--------+--------+--------+

Takže to bude něco v rozmezí 1002–3000 taktů.

Ani tohle není úplná pravda. Mainstreamové procesory od doby Pentia Pro jsou out-of-order superskalární CPU. Dokáží tedy vykonat několik instrukcí najednou a OOO jádro dynamicky vybírá ty nezávislé, které na nic nečekají a ty provede. Současná generace procesorů má 4 ALU a dokáže tedy provést 4 mul instrukce každý takt (pokud na sobě nejsou závislé a nic jiného nestojí v cestě).

To tedy znamená, že tisíc čísel se dá vynásobit v 252 až 3000 taktech.

Skoro. Problém je v tom, že předchozí kalkulace počítají s tím, že operandy instrukcí jsou okamžitě k dispozici. Ale to není pravda. Data, která jsou násobena, se nachází někde v paměti a před použitím musí být natažena do procesoru a cesta z RAM do CPU je zatraceně dlouhá. Může trvat i něco kolem 100ns, což může pro změnu odpovídat 300 taktům procesoru. CPU se snaží, co může, aby tyto prodlevy a latence eliminovalo – má hlubokou cache hierarchii, data načítá ve větších blocích (cache line), data přednačítá a může provádět několik load operací paralelně (tedy spíš na ně čekat). Přesto v nejhorším případě může utrpět prodlevu 300 taktů na každé slovo paměti. V nejlepším případě procesor rozjede svojí magii a latence nebude vůbec patrná.

Takže když budeme předpokládat, že každá instrukce násobení načte jedno slovo z RAM1, může jich tisíc trvat od 252 taktů do 300000.

Skoro, ale může to být ještě lepší. Pokud kód násobí data, která jsou extrémně regulární – například násobí mezi sebou odpovídající elementy dvou polí – může kompilátor použít SIMD instrukce, které provádějí stejnou operaci mezi několika různými položkami vektoru nejednou (SIMD znamená Single Instruction Multiple Data).2 Poslední generace x86 procesorů přidávají do instrukční sady rozšíření AVX2, které pracuje s vektorovými registry délky 256 bitů a umí provádět většinu operací i s celými čísly (původní SIMD rozšíření SSE umělo pracovat jen s floaty). Jedna SIMD instrukce dokáže vynásobit dva registry ve kterých je 8 čtyřbajtových integerů – tedy provést 8 násobení najednou. I když latence těchto operací je 10 taktů, CPU dokáže začít jednu takovou operaci každý takt3.

To tedy znamená, že to v nejlepším případě bude trvat 129 taktů a v nejhorším pak 300 tisíc.

Takové rozmezí vypadá že je skoro správné. Zanedbává ostatní operace, které budou s největší pravděpodobností v takovém kódu přítomné jako třeba mov instrukce nebo instrukce smyček, ale když nejde o užitečný odhad, je aspoň reálný. Všechno záleží na detailech. Nebo jak řekl Linus Torvalds: Talk is cheap. Show me the code.


  1. A to je možné, protože x86 je register-memory architektura a instrukce můžou pracovat jak s registry tak i přímo s pamětí.
  2. Pro detailní rozbor SIMD, array/vector procesorů doporučuji tuto přednášku kurzu Computer Architecture
  3. Jde o instrukci VPMULLD. V případě floatů je situace ještě lepší: Procesor může začít dvě VFMADD (která toho dělá trochu víc, ale dá se použít jako jednoduché násobení) v každém taktu a trvají 5 taktů (viz. instruction tables),

Dále k tématu:

Flattr this!

Posted in CPU | 3 Comments

Bez typů se obejdeme, ale…

Však to znáte, něco tweetnete a jedna odpověď vás donutí napsat celý článek jako vysvětlení, co je tím vlastně myšleno.

Dneska to byla tato perla nevšední krásy (odsud):

Without soundness, types can merely be used as optimisation hints, but the generated code would still need to be able to back out.

Na první pohled tato věta může vypadat jen jako další nevýznamný příspěvek do debaty mezi příznivci staticky a dynamicky typovaných jazyků (které jsou téměř výhradně vedeny diletanty, mě nevyjímaje). Ve skutečnosti jde o hluboký princip. Když má jazyk nekorektní typový systém, typy představují jen nástin toho, co se bude s největší pravděpodobností dít, ale virtuální stroj musí být připraven na eventualitu, že věci nepůjdou podle plánu.

Jako příklad uvedu legendární vadu typového systému javy, ve kterém jsou pole kovariantní. Kovariance znamená, že jestliže B je potomek A, tak B[] je potomek A[].

class Animal {}
class Pony extends Animal {}

Pony[] ponies = { new Pony() };
Animal[] animals = ponies; // kovariance zafunguje zde

animals[0] = new Animal(); // tohle skončí výjimkou ArrayStoreException

O co jde. Na začátku jsem vytvořil pole poníků a pak ho přiřadil do proměnné typu pole zvířat a kovariance polí to povolila. Teď, když se do pole, na které ukazuje proměnná typu Animal[], snažím přiřadit objekt typu Animal (což je naprosto korektní operace), vyskočí na mě výjimka ArrayStoreException. Za běhu. A kompilátor neřekl ani popel, protože kovariance polí není korektní.

A co je na celé věci nejhorší: Za ta tuhle podivnost z dávnověku, kdy java neměla ani generika 1, všichni do dneška platíme. Protože tohle může nastat, virtuální stroj musí při každém vložení do pole provádět typecheck jestli typ elementu je podtypem přípustné třídy. Kdyby typový sytém neobsahoval tuto úchylku a pole by byla invariantní, runtime by měl naprostou jistotu a nemusel byl pokaždé dělat zbytečný typecheck3.

Virtuální stroj může v některých situacích nutnost této kontroly odstranit. Například pokud jde o pole objektů nějaké finální třídy nebo objektů třídy (nebo interface), která nemá potomky nebo je má, ale zatím nejsou natažené do JVM, někdy může být typecheck vytažen před smyčku a tak dále.

Jazyk s nekorektním typovým systémem může běžet rychle, jak je například vidět na všech moderních implementacích JavaScriptu. Toho je však dosaženo divokými a agresivními spekulacemi, které virtuální stroj provádí. Sází na to, že všechno poběží jako minule, že se typy stabilizují a specializuje kód pro to, co vypozoroval. Ale stále musí počítat s tím, že jeho předpoklady byly špatné nebo že se situace najednou změní. Typický guard, který hlídá předpoklady, je tvořen pár instrukcemi – kontrola typu a jeden podmíněný skok na místo, které si s problémem poradí, deoptimalizuje kód, přepne se do interpretru a začne znova.

Jestliže typový systém je korektní dá mi naprostou a nevyvratitelnou garanci toho, že určité stavy za žádných okolností nemůžou nastat a virtuální stroj a JIT s nimi nemusí vůbec ztrácet čas. To může vést k jednoduššímu VM, rychlejšímu kódu nebo rychlejší kompilaci, která je pro jazyky jako JavaScript velice důležitá, protože compile-time je run-time.

To však neznamená, že VM nebude spekulovat. Například takové JVM ve fázi profilování sleduje všechny callsite a když zjistí, že se z jednoho místa volají jen metody jedné třídy, místo zcela validního virtuálního volání metody optimisticky inlinuje tělo metody (pokud je malá) a před ní vloží guard, který se postará o situaci, kdy se na daný callsite dostane objekt jiné třídy.


Další věc, která internetem zní jako ozvěna, je tvrzení, že typy nejsou potřeba k rychlému programu, že je to jen a pouze dokumentace pro programátora. S druhou polovinou souhlasím, typy jsou formalizací myšlenek a předpokladů toho, co kód má dělat a na jakých datech. Ale s první částí tvrzení naprosto nesouhlasím a dolovím si tvrdit, že pravý opak je pravdou: Typy jsou zcela nepostradatelné pro rychlý běh programu. Háček je jenom v tom jaké typy. Protože, když říkám, že typy jsou nutné, nemyslím tím ty viditelné v kódu, ani ty, které odvodí Hindley–Milner, ale ty se kterými bude runtime pracovat.

Co dělá každý JavaScriptový virtuální stroj? Snaží se za běhu objevit takzvané skryté třídy (hidden class), které mají nějaký tvar, počet atributů nějakého druhu – tedy typy. Když jsou tyto typy známé, JIT může generovat mnohem rychlejší kód, protože nepracuje s horou hash tabulek, ale s bloky paměti, které mají jasně danou strukturu2.

Tohle předpokládá, že nějakou strukturu je možné objevit. Naštěstí to většinou platí, protože i když kód neobsahuje typové anotace a kompilátor nevynucuje korektnost, programy mají určitou implicitní strukturu – objekty předané jako argumenty nějaké funkci skoro vždycky vypadají velice podobně atd.

Pro rychlý běh tedy není tolik důležité jestli je jazyk staticky nebo dynamicky typovaný, ale jestli má statickou nebo dynamickou strukturu.


Pozn:

  1. Právě chybějící generika v prvních verzích javy mohou za toto kriminální chování. Stejnou vadou trpí i C#.
  2. Například: Když první verze virtuální stroje HHVM, vykonávaly kód napsaný v Hacku, což je ve své podstatě PHP s korektním(!) typovým systémem, tak všechny staticky známé typy zahodily a začaly dynamicky typy objevovat a specializovat kód.
  3. Další poněkud více esoterický příklad: Java kontroluje, jestli se index ke kterému přistupuji, nachází v poli a když je mimo, vyhodí ArrayIndexOutOfBoundsException. V dependetly typed jazycích může být délka pole obsažena v typu pole a v takovém případě je možné se zbavit těchto kontrol, protože typový systém garantuje, že nedojde ke čtení mimo pole.

Dále k tématu:

Flattr this!

Posted in JVM, Typy, VM | Leave a comment

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.

Dále k tématu:

Flattr this!

Posted in CPU, PHP | 1 Comment

Hyper-threading aneb “Jak sakra může běžet víc vláken na jednom jádře?”

Nedávno jsem narazil na článek, který testoval, jak se pod zátěží chová procesor se zapnutým hyper-threadingem. Autor onoho textu na základě měření a vlastních předpokladů vyslovoval divoké domněnky a spekulace, které bohužel neměly příliš mnoho společného s chladnou realitou křemíku.

Otázka tedy zní: Jak je to vlastně s hyper-threadingem a simultaneous multithreading (SMT) obecně? Jak můžou běžet dvě vlákna na jednom procesorovém jádře zároveň?

Odpověď je jednoduchá: SMT se stará jenom o to, aby procesor měl stálý přísun nezávislých instrukcí k vykonání na out-of-order jádru.

Téměř všechna moderní CPU jsou pipelinované out-of-order superskalární procesory1, které dokážou dělat mnoho věcí najednou. Nejde jen o souběžná vlákna běžící na různých jádrech multiprocesoru, ale také o schopnost naráz vykonávat několik instrukcí jednovláknového programu (jde o takzvaný instuction level parallelism, zkráceně ILP). Tohle je možné právě proto, že i když se současné procesory navenek tváří, jako kdyby plně respektovaly Von Neumannovu architekturu, jejich vnitřní fungování v mnohém připomíná data-flow model. Tento způsob práce se označuje jako out-of-order execution (OOO). CPU nezpracovává jednu instrukci za druhou, ale načítá a dekóduje2 jich několik v každém taktu. Tyto instrukce jsou poté umístěny do re-order bufferu (ROB), což je ve své podstatě fronta dekódovaných mikrooperací3, které čekají na vykonání. Out-of-order jádro se poté snaží dynamicky tyto instrukce provést na dostupných funkčních jednotkách procesoru (nejnovější Intely, které je označují jako porty, jich mají osm) a zkouší vybrat co nejvíce instrukcí, které mohou běžet najednou. Když jsou operace nezávislé (tj. nezávisí na žádných předchozích) mohou být vykonány paralelně na různých portech. To je obzvláště výhodné, když jde o load4 instrukce načítající data z paměti. Než blok dat dorazí z RAM do cache CPU, může to trvat až několik stovek taktů. Pokud OOO engine dokáže zařídit, aby nezávislé load operace běžely paralelně, může tak dramaticky zrychlit program5. Pokud ale instrukce A závisí na B, A musí počkat ve frontě re-order bufferu dokud B není plně uskutečněna a teprve poté dostane svojí nanosekundu slávy. Moderní procesory vynakládají velké úsilí, plochu a energii na to, aby zaručily, že ve frontě jsou pořád nějaké nezávislé instrukce připravené k vykonání – prefetchují data, odhadují podmíněné skoky a divoce spekulují, jen aby objevily tu další load instrukci a narazily na ten další cache-miss.

Bohužel ILP má své limity a v běžných programech je jen omezené množství nezávislých instrukcí. Ivan Godard z Mill Computing říká „Tajemství out-of-order procesorů je, jak málo out-of-order vlastně jsou“6". Každé jádro Haswellu je schopné načíst, dekódovat a vykonat 4 instrukce v každém taktu8, mají re-order buffer délky 19212 a krotí smečku 168 virtuálních general purpose registrů7, ale jen zřídka dokáže tyto prostředky naplno využít. Běžný kód zkrátka neobsahuje dost ILP na to, aby byl procesor plně vytížený. Některé zdroje uvádějí, že běžné maximum ILP je někde kolem 2.5.

Právě v tomto místě přichází ke slovu hyper-threading. Když máme velice paralelní procesory, které většinu času nejsou schopny zcela využít svůj potenciál, je jenom logické před jádro přidat druhý frontend, který načítá a dekóduje instrukce jiného vlákna a který zásobí out-of-order strojovnu novým proudem instrukcí, v němž je s trochou štěstí možné najít dostatečné množství nezávislých operací, které zužitkují kapacitu dostupného hardwaru.

Taková je podstata hyper-threadingu a SMT9. Nejde o hardwarové context-switche10, nejde o to, že se Von Neumannovský procesor maskuje za dva (jako je tomu v případě barell temporal multithreading nebo super-threading), jde jen o to využít všechny možnosti procesoru, které by jinak ležely ladem.11

Nevýhodou hyper-threadingu je skutečnost, že najednou běží víc nezávislých vláken, které sdílejí dostupnou cache. Každé hyper-vlákno má tedy k dispozici efektivně poloviční množství cache, než kdyby procesor neměl povolený HT. To může v některých případech mít značný vliv na rychlost programu. I tady platí staré rčení: „Když jsi s rozumem v koncích, použij perf“.


Dále k tématu:


  • 1) Prvním komerčně úspěšným OOO procesorem bylo Pentium Pro. Průkopníky v této oblasti však byli gangsteři v kravatách z IBM, kteří navrhli první OOO procesor už v šedesátých letech.
  • 2) To že dekódování x86 instrukcí je problém se můžete přesvědčit tady a tady. Současné generace CPU mají kromě instrukční level 1 cache, také μops cache a loop buffer proto, aby eliminovaly režii dekódování instrukcí, které mají prefixy, escape-sekvence a proměnnou délku.
  • 3) Instrukce jsou dekódovány na mikrooperace (μops), které jsou pak vykonány procesorem. Proto i CISC architektury jako x86 se uvnitř chovají jako RISC.
  • 4) Na x86 jde o mov instrukci, která má jako zdroj adresu paměti.
  • 5) Zrychlení je tak dramatické, že všechny optimalizace v procesoru směřují jen a pouze k tomuto cíli – víc souběžných cache-miss (viz).
  • 6) Zdroj se mi nepodařilo vypátrat, ale je to zmíněno někde v sérii přednášek pořádaných Mill Computing. Godard dost možná cituje někoho jiného, pravděpodobně z týmu vyvíjejícího Itanium.
  • 7) A stejný počet floating point virtuálních registrů. Virtuální registry určují jak dalece může jádro spekulovat.
  • 8) Technicky je možné až 6 instrukcí, když program má to štěstí, že procesor dokáže sloučit několik párů operací (macro-op fusion). Čistě teoreticky by mohlo jít až o 8 operací vykonaných na všech osmi portech. Poslední generace procesorů Itanium (Poulson) stabilně zvládá 12 instrukcí za takt (ale v tomto případě nejde o OOO, ale o open pipeline a static scheduling).
  • 9) SMT bývá mnohem divočejší v ne-x86 procesorech. Například Power8 nebo Sparc M7 dokáže provádět osm vláken najednou, nikoli pouhé dvě, jak je běžné ve světě Intelu a AMD. Jde o kompromis mezi agresivitou a paralelismem procesoru. x86 se očividně snaží optimalizovat jednovláknový výkon, kdežto Power a Sparc se svými osmi souběžnými vlákny míří na propustnost a throughput.
  • 10) Hardwarové context-switche a hardwarový scheduling jsou však běžné ve světě GPGPU.
  • 11) Některý, zvláště numerický kód dokáže z procesoru vymáčknout 4 instrukce za takt (IPC). V takovém případě HT nebo SMT nemá žádný pozitivní dopad na výkon.
  • 12) Velikost ROB ve své podstatě udává jak daleko do budoucnosti procesor vidí. Čím dál vidí, tím víc ILP může z kódu získat. Někdy však může nastat divoká souhra okolností, která má překvapivě negativní dopad na výkon, jak je demonstrováno v tomto videu.

Flattr this!

Posted in CPU, Paměť | 1 Comment