Ú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ídatel­ně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í:

* MASK MOD
time 1.2 s 4.5 s
cycles 4103.9M 15655.8M
instructions 11745.5M 13426.9M
IPC 2.86 0.85
cache-references 104.0M 10.1M
cache-misses 43.1M 7.9M
cache-misses 41.4% 78.7%
branches 1677.9M 1678.6M
branch-misses 0.0M 0.0M
branch-misses 0.0% 0.0%

Jak se ukazuje modulo je v tomto případě skoro 4× pomalejší než odmaskování pár bitů. Proč? Celočíselné dělení2/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í3 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.1

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 hyperthreadova­ných/SMT vláknech. Když nemá po ruce dostatečné množství práce, které by nasytilo OOO bestii, CPU musí čekat.4

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:

* závislý load nezávislý load
time 2.61 s 1.23 s
cycles 8978.9M 4139.9M
instructions 8396.2M 11751.5M
IPC 0.93 2.83
cache-references 23.4M 104.9M
cache-misses 12.4M 43.2M
cache-misses 53.0% 41.2%
branches 1679.0M 1679.0M
branch-misses 0.0M 0.0M
branch-misses 0.0% 0.0%

Jak je vidět, i když nezávislá verze potřebuje více instrukcí, běží 2× 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).5

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 264 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.6

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á.

* mask mod
time 3.15 s 21.32 s
cycles 10805.6M 74504.3M
instructions 10076.0M 11768.4M
IPC 0.93 0.15
cache-references 15.1M 7.8M
cache-misses 7.4M 6.8M
cache-misses 49.1% 87.0%
branches 1679.4M 1681.8M
branch-misses 0.0M 0.0M
branch-misses 0.0% 0.0%

Najednou je závislé modulo 7× pomalejší než závislé maskování a 21× 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.

* SEQ RAND
time 2.45 s 130.98 s
cycles 8650.7M 445541.6M
instructions 8391.4M 8643.6M
IPC 0.97 0.02
cache-references 21.1M 1698.0M
cache-misses 10.1M 1662.8M
cache-misses 48.1% 97.9%
branches 1678.2M 1722.0M
branch-misses 3592 0.4M
branch-misses 0.0% 0.026%

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 53× 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 StringIntDicti­onary – mapu specializovanou pro stringové klíče a primitivní hodnoty, která je až 3× 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.7

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–8× 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.

* SEQ RAND
time 1.22 s 25.55 s
cycles 4073.1M 86769.1M
instructions 13431.2M 13718.2M
IPC 3.29 0.15
cache-references 91.8M 2895.3M
cache-misses 36.4M 1835.3M
cache-misses 39.7% 63.3%
branches 1679.3M 1727.9M
branch-misses 22135 386246
branch-misses 0.0% 0.022%

Rozdíl v rychlosti je tentokrát pouze 21× 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:

test čas 1 iterace 1 iterace IPC
SEQ INDEP L1 0.95 1.8 taktu 0.6 ns 4.45
SEQ INDEP 1.22 2.4 taktů 0.8 ns 3.29
SEQ DEP 2.45 4.9 taktů 1.5 ns 0.97
RAND INDEP 25.55 51.1 taktů 16.0 ns 0.15
RAND REP 130.98 262.0 taktů 81.6 ns 0.02

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ěží 140× 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:

* x > 0 x != 0
time 8.05s 1.98s
cycles 25693M 6308M
instructions 19304M 23491M
IPC 0.75 3.72
cache-references 19M 35M
cache-misses 15M 12M
cache-misses 79% 34%
branches 3357M 3355M
branch-misses 838M 0M
branch-misses 25% 0%

Jak je vidět, tak verze, která dělá dvakrát víc práce, je 4× 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 2× 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ídatel­ný 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ů.

Flattr this!

This entry was posted in CPU, Paměť. Bookmark the permalink.

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

  1. Lukyer says:

    Díky za zajímavé čtení.
    Btw v druhém příkladu je prohozený komentář co je MOD a co MASK :)

Leave a Reply

Your email address will not be published. Required fields are marked *