funkcionálně.cz

Úvod do podivností moderního hardwaru, které vás budou budit ze spaní

Nezasvěceným se může chování hardware a procesorů zvlášť zdát zcela bizarní a nepochopitelné, plné nesmyslných výjimek a nástrah čekajících na nepozorné, které můžou způsobit nevysvětlitelný propad výkonu. Optimalizace pak vypadá jako jakási prastará forma okultní magie, srozumitelná jen kruhu zasvěcených.

Pravdou je však naprostý opak. CPU jsou výjimečná soustrojí, kde má všechno do posledního detailu svůj důvod, a které neobsahují nic zbytečného. Všechny komponenty jsou vzájemně propojené a interagují spolu v delikátní souhře.

Některé z těchto důvodů se nám nemusí líbit. Například instrukční sada x86 i přes to, jak je barokní, redundantní a bizarní, má svůj důvod - zpětnou kompatibilitu. A Intel to ví nejlépe. V průběhu historie se snažil x86 zabít a nahradit něčím lepším čtyřikrát (iAPX 432⁸ , i960, i860 a naposledy v tandemu s HP velice ambiciózním Itaniem). Všechny tyto snahy ale selhaly, když AMD rozšířilo x86 o podporu 64 bitů. Instrukční sada už tak postrádala eleganci a rozšíření bylo ještě méně elegantní, ale ujalo se.

V tomto článku ukážu a vzápětí vysvětlím některé z těchto podivností na sérii testů a benchmarků napsaných v jazyce C. Proč zrovna v céčku? Proč ne ne třeba v Javě, když i v ní je možné dosáhnout low-level výkonu. To je pravda, ale když se chci bavit s hardwarem, vyberu si jazyk, který přede mě klade minimum překážek a je co nejpředvídatelnější.

Všechny testy zkompiluji přes gcc -O3 a proženu perfem a budu měřit takové věci jako počet taktů procesoru, instrukcí, IPC (instructions-per-cycle/instrukce za takt), podíl branch-miss a podíl cache-miss. Každý z nich začíná tímto kusem kódu, který není měřený:

// argv[1] musí být mocnina dvou, ve všech testech používám hodnotu 16
const int len  = atoi(argv[1]) * 1024 * 1024;
const int iter = 100 * len;

long *seqarr  = sequential_order(len);
long *randarr = random_order(len);

Funkce sequential_order vygeneruje pole, kde platí, že na pozici n je hodnota (n+1) % len. Jde tedy o offset o jednu pozici vpravo. Dá se o tom taky uvažovat jako o pointeru, který ukazuje na vedlejší pozici.

Funkce random_order vygeneruje podobné pole offsetů/skoro-pointerů, které však mají náhodné pořadí. Když budu opakovaně následovat tyto pointery, v obou případech projdu všechny položky daných polí.

mod vs mask

Není instrukce jako instrukce a v případě superskalárních out-of-order procesorů to platí obzvlášť silně. Každá operace má různou latenci, která může být někdy zamaskována instrukční pipeline, a různou propustnost, kdy CPU dokáže vypravit několik instrukcí v jednom taktu.

Abych si tohle ověřil, budu testovat staré známé modulo a maskování. Jde o jednoduchý způsob jak zajistit, že hodnota i zůstane v určitém rozsahu len. Buď můžu spočítat i % len nebo, pokud je len mocnina dvou, můžu to samé napsat jako i & (len - 1). Část len - 1 vyrobí masku, která obsahuje samé jedničky na nejnižších pozicích a & vyfiltruje nejnižší bity čísla i.

Jaký je tedy v rozdíl v rychlosti těchto dvou fragmentů kódu:

// MOD
long sum = 0;
for (int i = 0; i < iter; i ++) {
  sum += seqarr[i % len];
}

// MASK
long sum = 0;
for (int i = 0; i < iter; i ++) {
  sum += seqarr[i & (len - 1)];
}

Výsledky jsou následující:

Jak se ukazuje modulo je v tomto případě skoro 4x pomalejší než odmaskování pár bitů. Proč? Celočíselné dělení² /modulo je pomalé, protože ho nikdo nepoužívá a protože ho nikdo nepoužívá, tak tyto operace není nutno optimalizovat (stejně jako např. instrukce INDEX na starých VAXech).

Tento fakt může mít vliv na návrh hashovacích tabulek a jiných datových struktur. Když použiji velikost, která je mocninou dvou, vyhnu se modulu/dělení³ a operace s tabulkou můžou být o něco rychlejší. Na druhou stranu to může mít neblahý dopad, pokud jsou (například) klíče tabulky násobky osmi nebo jiné malé mocniny dvou, hash funkce tyto korelace zachová, v důsledku toho bude obsazena jen 1/8 slotů tabulky, to povede k velkému počtu kolizí a to věci značně zpomalí. V tomto případě je třeba si na tohle dát pozor a používat dobrou hashovací funkci.

Pozn: Kompilátor dokáže triviální případy jako x % 64 optimalizovat na x & 63. Někdy si dokáže poradit i s mnohem záludnějšími případy, kdy to vypadá, že se nedělí/nemoduluje konstantou. V určitých případech může být modulo eliminováno nebo vytaženo před smyčku.¹

Pozn 2: Větší počet cache-miss v případě maskující varianty může být způsobený tím, že kód je tak rychlý, že prefetch nestíhá data dodávat z paměti.

Závislé a nezávislé operace

Superskalární CPU mají pod kapotou každého vlákna značné množství paralelismu - v každém taktu dokážou načíst, dekódovat, naplánovat, vykonat několik instrukcí. Tato dech beroucí mašinérie může však fungovat jedině, když má k dispozici dostatečné množství nezávislých operací v jednom nebo v několika hyperthreadovaných/SMT vláknech. Když nemá po ruce dostatečné množství práce, které by nasytilo OOO bestii, CPU musí čekat.⁴

Následující test testuje právě tohle. V prvním případě program iteruje polem sekvenčních offsetů. V druhém nepoužívá k navigaci offsety, ale čte hodnoty přímo. Oba programy prochází polem naprosto shodně a udělají stejné množství práce. Na konci má proměnná sum v obou případech stejnou hodnotu.

//závislý load

long sum = 0;
int x = arr[0];
for (int i = 0; i < iter; i ++) {
  sum += x;
  x = arr[x];
}

//nezávislý load

long sum = 0;
for (int i = 0; i < iter; i ++) {
  sum += arr[i & (len - 1)];
}

Výsledky:

Jak je vidět, i když nezávislá verze potřebuje více instrukcí, běží 2x rychleji.

V prvním případě jedna iterace plně závisí na té předchozí. Přiřazení x = arr[x] tvoří datovou závislost. Následující iterace nemůže pokračovat, pokud ještě neskončilo načítání arr[x], protože procesor neví, která hodnota bude načtena a tedy neví, na jakou adresu skočit. V tomto případě to bude x+1, ale to procesor nemůže vědět, ten vidí jen bajty naházené v paměti, a proto musí čekat, dokud načítání neskončí, než bude pokračovat.

Druhý kus kódu také obsahuje závislost, ale v tomto případě nejde o závislost datovou, ale o závislost řídící struktury (control flow). Procesor se musí jen rozhodnout, jestli i < iter bude vyhodnocena jako pravda nebo nepravda a podle toho skočit na další iteraci nebo smyčku zaříznout. Jde o jednoduchou binární volbu, kterou dokáže branch predictor odhadnout přesně i v komplikovaných případech. Tady jde o triviální smyčku, kterou procesor odhadne vždy, rozjede OOO mašinérii, začne spekulovat napříč iteracemi a najedou má k mání moře nezávislých operací (i za cenu, že se občas zmýlí ve spekulacích a bude muset zahodit některé výsledky).⁵

I když technicky vzato, procesor může odhadnout hodnotu před tím, než je načtena z paměti a na základě toho rozjet spekulativní exekuci. Pokud mají data jednoduše předvídatelný vzor jako v mém případě výše, procesor ho může velice snadno zachytit a využít. Obecně je to však problém, protože je třeba trefit správnou hodnotu z 2⁶⁴ možností (a navíc to má dopad na implementaci paměťového modelu). V případě control flow dependency se stačí rozhodnout mezi pouhýma dvěma možnostmi.⁶

Oba programy procházejí pamětí lineárně a proto prefetcher dodává všechna data s předstihem. Avšak stejně jako v minulém testu, se i tady ukazuje určitý počet cache miss. To může signalizovat, že RAM nestíhá dodávat data. Kdybych měl ve svém stroji rychlejší paměti, program by běžel o něco rychleji bez těchto cache-miss.

Rozdíl mezi závislými a nezávislými operacemi má překvapivě dopad úplně na všechno. Datové struktury založená na pointerech, jako jsou spojové seznamy nebo stromy, nedělají nic jiného než závislé operace - musím načítat jeden pointer za druhým než se prokoušu k listům stromu. Tohle platí pro všechny druhy stromů nebo hierarchických struktur, můžou být široké nebo mělké, ale v cestě za cílem vždycky stojí závislé operace. A shodou náhod všechny funkcionální persistentní datové struktury jsou implementovány právě jako stromy.

Pokud upravím předminulý mod/mask test tak, aby na sobě byly jednotlivé iterace závislé, situace je najednou hrozivě chmurná.

Najednou je závislé modulo 7x pomalejší než závislé maskování a 21x pomalejší než nezávislé plně pipelinované maskování. To (kromě jiného) není vůbec dobrá zpráva pro RRB stromy. IPC 0.15 mluví za své.

Závislé sekvenční čtení a závislé náhodné čtení

Je čas přitlačit na pilu. Co se stane, když porovnám závislé sekvenční čtení jako minule a závislé čtení z náhodných míst v paměti, tedy něčeho, co připomíná divoký hon na pointery napříč celou haldou.

// SEQ
long sum = 0, x = seqarr[0];
for (int i = 0; i < iter; i ++) {
  sum += x;
  x = seqarr[x];
}

// RAND
long sum = 0, x = randarr[0];
for (int i = 0; i < iter; i ++) {
  sum += x;
  x = randarr[x];
}

Jde o shodný kód, který se liší jen v tom, jakým polem prochází. V jenom případě polem lineárně rostoucích offsetů, v druhém případě offsetů rozházených bez ladu a skladu.

Jestliže všechny ostatní testy představovaly jen drobné nepříjemnosti, tohle rozhodne o všem. Když můj program prochází data sekvenčně, prefetcher to pozná a postará se, že všechno potřebné bude včas k dispozici v rychlé cache, připravené ke čtení. Naproti tomu, když chci v každé iteraci číst z nepředvídatelné lokace v paměti, prefetcher nemůže pomoct, cache jsou k ničemu a výsledek je 53x pomalejší. Pokud jsou data větší než pár megabajtů, které má L3 cache, každý load jde přímo do RAM a RAM je zatraceně pomalá. Hlavní paměť má ucházející propustnost a proto nepředstavuje zas takový problém, když je program limitovaný právě průtokem bitů. Když však záleží na latenci každé operace, všechno jde do kytek, protože závislosti vytvoří kauzální řetězec.

Datové struktury, které jsou procházeny v předvídatelném lineárním pořadí nebo ty, jejichž horká část se vejde do některé úrovně cache procesoru budou rychlé. Ty, které tyto podmínky nesplňují, můžou trpět.

Například java.util.HashMap je implementovaná tak, že potřebuje 3 závislé load operace. Když je hashmapa velká a nevejde se do cache, každý přístup do ní, může stát několik cache-miss. Nedávno jsem napsal StringIntDictionary - mapu specializovanou pro stringové klíče a primitivní hodnoty, která je až 3x rychlejší než j.u.HashMap[String, Int] právě proto, že potřebuje načíst data jen z jednoho místa v paměti a proto vyvolá jen jeden cache-miss.⁷

Jako další příklad může sloužit scala.collection.immutable.Vector. Ten je implementován velice širokým stromem a v závislosti na velikosti potřebuje něco mezi 1 a 7 závislými load operacemi. Na druhou stranu, když k danému vektoru přistupuji často, prvních pár úrovní bude v cache a cena přístupu tak nemusí být přehnaná. V benchmarcích jsem zjistil, že Vector je 4-8x pomalejší než obyčejný plochý ArrayBuffer.

Za zmínku může stát také tento test specializovaných map, který ukazuje, že ty mapy které potřebují přistoupit jen k jednomu místu v paměti, jsou rychlejší než ty které potřebují přistoupit ke dvěma nebo třemi.

Nezávislé sekvenční čtení a nezávislé náhodné čtení

Další test: Jak je na tom nezávislé sekvenční čtení v porovnání s nezávislým náhodným čtením.

// SEQ
long sum = 0;
for (int i = 0; i < iter; i ++) {
  sum += seqarr[seqarr[i & (len - 1)]];
}

// RAND
long sum = 0;
for (int i = 0; i < iter; i ++) {
  sum += rndarr[rndarr[i & (len - 1)]];
}

Zase jde o stejný kód, který vede ke stejnému výsledku, liší se však jen pořadím v jakém přistupuje k elementům pole - jednou sekvenčním a podruhé náhodném.

Rozdíl v rychlosti je tentokrát pouze 21x v neprospěch náhodného čtení. Jak je vidět z těchto výsledků, i když se čte z náhodných míst v DRAM, procesor dokáže spekulovat a začít pár čtení najednou a zamaskovat tak latence. Nezávislé sekvenční čtení je ještě o něco rychlejší než závislé sekvenční i když potřebuje o 50% více instrukcí.

Když porovnám všechny případy, začne se mi rýsovat následující obraz:

První řádek reprezentuje případ, kdy se všechna data vejdou do L1 cache a program nepotřebuje číst a být limitován rychlostmi DRAM. Jak je vidět, v tomto případě procesor našel dost paralelismu, na to aby stihl vykonávat 4.45 instrukce každý takt.

Důležitý je rozdíl mezi nejrychlejším a nejpomalejší verzí - i když dělají to samé, jedna běží 140x pomaleji než ta druhá. To zhruba odpovídá rozdílu v rychlosti mezi dnešními počítači a těmi z roku 2003. Jde sice o vykonstruovaný případ, ale přesto ukazuje rozpětí, do kterého budou reálné programy spadat.

branch prediction

Na závěr ukážu neintuitivní chování podmínek.

Funkce generate_truly_random_array vygeneruje pole náhodných čísel z rozsahu INT_MIN až INT_MAX. Chci spočítat nějakou agregaci těchto hodnot, ale některé nevyhovující bych chtěl ignorovat. V prvním případě započítám jen hodnoty větší než 0 a v druhém všechny kromě nuly. Dva kusy kódu na rozdíl od předchozích povedou k různým součtům.

long* rndarr = generate_truly_random_array(len);

double d = 0.5;
long count = 0;
double sum = 0.0;
for (int i = 0; i < iter; i++) {
  if (rndarr[i & (len - 1)] > 0) { // tady se to liší
    sum += rndarr[i & (len - 1)] / d;
    count += 1;
  }
}

long* rndarr = generate_truly_random_array(len);

double d = 0.5;
long count = 0;
double sum = 0.0;
for (int i = 0; i < iter; i++) {
  if (rndarr[i & (len - 1)] != 0) { // tady se to liší
    sum += rndarr[i & (len - 1)] / d;
    count += 1;
  }
}

Výsledky:

Jak je vidět, tak verze, která dělá dvakrát víc práce, je 4x rychlejší. Problém tentokrát spočívá v předvídatelnosti podmínek. Pokud je podmínka dobře předvídatelná, branch predictor ji uhodne, začne číst a dekódovat instrukce správné sekvence následujících instrukcí a všechno jede, jako kdyby se v kódu žádný skok nevyskytoval. Když však uhodne špatně a bude muset všechnu spekulativní práci zahodit a začít od správného konce. Nastane takzvaný pipeline stall nebo pipeline bubble. Množství ztracené práce odpovídá hloubce pipeline, která na mém Haswellu má délku 14-19 taktů. V benchmarku pomalá verze potřebuje 11.5 taktu na každou iteraci, což přibližně odpovídá tabulkovým hodnotám a faktu, že rychlá verze musí pořád udělat 2x víc užitečné práce.

Dále je vidět, že jen 25% instrukcí vedlo k branch-miss. Polovina podmíněných skoků tvoří smyčku, kterou hardware uhodl naprosto dokonale. Ve zbývající polovině se trefil na 50% - měl tedy stejnou úspěšnost, jako kdyby házel mincí.

K tomuto případu se sluší dodat, že kdyby bylo tělo smyčky o něco jednodušší (to dělení proměnnou d tam nebylo jen tak pro nic za nic), kompilátor by ji mohl přeložit na sérii cmov instrukcí. cmov neboli conditional move nepředstavuje větvení toku programu, ale operaci, která je vykonána tak jako tak, podmínka určí jestli má nějaký efekt. Kdyby se tak stalo, běžely by obě verze stejně rychle, protože by neobsahovaly žádný nepředvídatelný skok.

x86 má jedninou takovou instrukci - cmov, mnoho instrukcí na 32bitových ARMech je predikovatelných a celé neslavné Itanium bylo na tomto principu postaveno.

Takže co?

Doufám, že jsem ukázal, jaký může být rozdíl v rychlosti programů, když pracují s hardwarem a když pracují proti němu. Když jsou algoritmy a datové struktury malé, lokální, sekvenční a předvídatelné, na moderním hardwaru doslova poletí, pokud tyto vlastnosti chybí, s rychlostí to může drhnout.

To je všechno, jděte domů a použijte, co jste se dozvěděli.

Pozn:

1. S modulo je samá zábava. Modulo negativního čísla vrátí záporný výsledek a ani funkce Math.abs nemusí pomoci, pokud není použita správně.
2. Dělení v plovoucí čárce je o něco rychlejší, ale přesto pomalejší, než násobení převrácenou hodnotou.
3. Dělení a modulo je (aspoň na x86) jedna a ta samá operace. DIV/IDIV vrátí jak výsledek dělení, tak i zbytek po dělení.
4. V tomto kontextu stojí za zmínku Cray XMT/ThreadStorm, který dotáhl hyperthreading/SMT do extrému. ThreadStorm je procesor, určený pro úlohy, které vykazují jen mizivou lokalitu dat a kde cache nepomůžou (jako např. zpracování gigantických grafů). Zatímco běžné x86 procesory si poradí s 2 vlánky najednou, Xeon Phy, Power8 a nejnovější Sparcy od Oraclu zvládají 8 vláken, ThreadStorm dokáže zpracovat 64 vláken najednou. porcesor obrahuje všechny hardwarové prostředy všech 64 vláken (soubor registrů atd.) a v každém taktu najde jedno vlákno, které na nic nečeká a může běžet a spustí ho a to všechno bez zásahu operačního systému. Jde tedy o hardwarovou implementaci přepínání procesů, když je aktivně běžící vlákno blokuje. Viz: Overview of the Next Generation Cray XMT.
5. A že může spekulovat zatraceně hluboko. Nový Skylake od Intelu obsahuje buffery pro 224 instrukcí za letu, 72 paralelních load instrukcí a 180 integer a 168 floating-point registrů, které spekulace potřebují k přejmenovávání.
6. Navíc i když procesor nemá plnou podporu pro predikci hodnot, může obsahovat takzvaný branch target predictor, který se snaží odhadnout cíle nestatických skoků (jump register). Tohle může zrychlit volání virtuálních metod v C++ a podobných jazycích, které se nemůžou spolehnout na JIT a inline cache a oportunistickou optimalizaci. Ale i v tomto případě je počet možných cílů mnohem menší než počet možných hodnot.
7. Tohoto jsem dosáhl tak, že krátké alfanumerické klíče neukládám jako String objekty, ale jako speciálně zakódovaných do 54 bitů nebo offset/délku od souvislého pole znaků.
8. Tady nešlo o snahu zabít x86, protože iAPX a x86 mají počátky ve stejné době.