funkcionálně.cz

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

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

26. 7. 2016 — k47

Ne­za­svě­ce­ným se může cho­vání hard­ware a pro­ce­sorů zvlášť zdát zcela bi­zarní a ne­po­cho­pi­telné, plné ne­smy­sl­ných vý­ji­mek a ná­strah če­ka­jí­cích na ne­po­zorné, které můžou způ­so­bit ne­vy­svět­li­telný propad výkonu. Op­ti­ma­li­zace pak vypadá jako jakási pra­stará forma okultní magie, sro­zu­mi­telná jen kruhu za­svě­ce­ných.

Prav­dou je však na­prostý opak. CPU jsou vý­ji­mečná sou­strojí, kde má všechno do po­sled­ního de­tailu svůj důvod, a které ne­ob­sa­hují nic zby­teč­ného. Všechny kom­po­nenty jsou vzá­jemně pro­po­jené a in­ter­a­gují spolu v de­li­kátní souhře.

Ně­které z těchto důvodů se nám nemusí líbit. Na­pří­klad in­strukční sada x86 i přes to, jak je ba­rokní, re­dun­dantní a bi­zarní, má svůj důvod – zpět­nou kom­pa­ti­bi­litu. A Intel to ví nej­lépe. V prů­běhu his­to­rie se snažil x86 zabít a na­hra­dit něčím lepším čty­ři­krát (iAPX 4328, i960, i860 a na­po­sledy v tan­demu s HP velice am­bi­ci­óz­ním Ita­niem). Všechny tyto snahy ale se­lhaly, když AMD roz­ší­řilo x86 o pod­poru 64 bitů. In­strukční sada už tak po­strá­dala ele­ganci a roz­ší­ření bylo ještě méně ele­gantní, ale ujalo se.


V tomto článku ukážu a vzá­pětí vy­svět­lím ně­které z těchto po­div­ností na sérii testů a ben­chmarků na­psa­ných v jazyce C. Proč zrovna v céčku? Proč ne ne třeba v Javě, když i v ní je možné do­sáh­nout low-level výkonu. To je pravda, ale když se chci bavit s hard­warem, vyberu si jazyk, který přede mě klade mi­ni­mum pře­ká­žek a je co nej­před­ví­da­tel­nější.

Všechny testy zkom­pi­luji přes gcc -O3 a pro­ženu perfem a budu měřit takové věci jako počet taktů pro­ce­soru, in­strukcí, IPC (in­structi­ons-per-cycle/in­strukce 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 vy­ge­ne­ruje pole, kde platí, že na pozici n je hod­nota (n+1) % len. Jde tedy o offset o jednu pozici vpravo. Dá se o tom taky uva­žo­vat jako o poin­teru, který uka­zuje na ve­d­lejší pozici.

Funkce random_order vy­ge­ne­ruje po­dobné pole off­setů/skoro-poin­terů, které však mají ná­hodné pořadí. Když budu opa­ko­vaně ná­sle­do­vat tyto poin­tery, v obou pří­pa­dech projdu všechny po­ložky daných polí.

mod vs mask

Není in­strukce jako in­strukce a v pří­padě su­per­ska­lár­ních out-of-order pro­ce­sorů to platí ob­zvlášť silně. Každá ope­race má různou la­tenci, která může být někdy za­mas­ko­vána in­strukční pi­pe­line, a různou pro­pust­nost, kdy CPU dokáže vy­pra­vit ně­ko­lik in­strukcí v jednom taktu.

Abych si tohle ověřil, budu tes­to­vat staré známé modulo a mas­ko­vání. Jde o jed­no­du­chý způsob jak za­jis­tit, že hod­nota i zů­stane v ur­či­tém roz­sahu len. Buď můžu spo­čí­tat i % len nebo, pokud je len moc­nina dvou, můžu to samé napsat jako i & (len - 1). Část len - 1 vyrobí masku, která ob­sa­huje samé jed­ničky na nej­niž­ších po­zi­cích a & vy­fil­truje nej­nižší bity čísla i.

Jaký je tedy v rozdíl v rych­losti těchto dvou frag­mentů 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á­sle­du­jící:

* MASK MOD
time 1.2 s 4.5 s
cycles 4103.9M 15655.8M
in­structi­ons 11745.5M 13426.9M
IPC 2.86 0.85
cache-re­fe­ren­ces 104.0M 10.1M
cache-misses 43.1M 7.9M
cache-misses 41.4% 78.7%
bran­ches 1677.9M 1678.6M
branch-misses 0.0M 0.0M
branch-misses 0.0% 0.0%

Jak se uka­zuje modulo je v tomto pří­padě skoro 4x po­ma­lejší než od­mas­ko­vání pár bitů. Proč? Ce­lo­čí­selné dělení2/modulo je pomalé, pro­tože ho nikdo ne­po­u­žívá a pro­tože ho nikdo ne­po­u­žívá, tak tyto ope­race není nutno op­ti­ma­li­zo­vat (stejně jako např. in­strukce INDEX na sta­rých VAXech).

Tento fakt může mít vliv na návrh ha­sho­va­cích ta­bu­lek a jiných da­to­vých struk­tur. Když po­u­žiji ve­li­kost, která je moc­ni­nou dvou, vyhnu se modulu/dělení3 a ope­race s ta­bul­kou můžou být o něco rych­lejší. Na druhou stranu to může mít ne­blahý dopad, pokud jsou (na­pří­klad) klíče ta­bulky ná­sobky osmi nebo jiné malé moc­niny dvou, hash funkce tyto ko­re­lace za­chová, v dů­sledku toho bude ob­sa­zena jen 1/8 slotů ta­bulky, to povede k vel­kému počtu kolizí a to věci značně zpo­malí. V tomto pří­padě je třeba si na tohle dát pozor a po­u­ží­vat dobrou ha­sho­vací funkci.

Pozn: Kom­pi­lá­tor dokáže tri­vi­ální pří­pady jako x % 64 op­ti­ma­li­zo­vat na x & 63. Někdy si dokáže po­ra­dit i s mnohem zá­lud­něj­šími pří­pady, kdy to vypadá, že se nedělí/ne­mo­du­luje kon­stan­tou. V ur­či­tých pří­pa­dech může být modulo eli­mi­no­váno nebo vy­ta­ženo před smyčku.1

Pozn 2: Větší počet cache-miss v pří­padě mas­ku­jící va­ri­anty může být způ­so­bený tím, že kód je tak rychlý, že pre­fetch ne­stíhá data do­dá­vat z paměti.

Zá­vislé a ne­zá­vislé ope­race

Su­per­ska­lární CPU mají pod ka­po­tou kaž­dého vlákna značné množ­ství pa­ra­le­lismu – v každém taktu do­ká­žou načíst, de­kó­do­vat, na­plá­no­vat, vy­ko­nat ně­ko­lik in­strukcí. Tato dech be­roucí ma­ši­né­rie může však fun­go­vat jedině, když má k dis­po­zici do­sta­tečné množ­ství ne­zá­vis­lých ope­rací v jednom nebo v ně­ko­lika hy­perthrea­do­va­ných/SMT vlák­nech. Když nemá po ruce do­sta­tečné množ­ství práce, které by na­sy­tilo OOO bestii, CPU musí čekat.4

Ná­sle­du­jící test tes­tuje právě tohle. V prvním pří­padě pro­gram ite­ruje polem sek­venč­ních off­setů. V druhém ne­po­u­žívá k na­vi­gaci off­sety, ale čte hod­noty přímo. Oba pro­gramy pro­chází polem na­prosto shodně a udě­lají stejné množ­ství práce. Na konci má pro­měnná sum v obou pří­pa­dech stej­nou hod­notu.

//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 ne­zá­vislý load
time 2.61 s 1.23 s
cycles 8978.9M 4139.9M
in­structi­ons 8396.2M 11751.5M
IPC 0.93 2.83
cache-re­fe­ren­ces 23.4M 104.9M
cache-misses 12.4M 43.2M
cache-misses 53.0% 41.2%
bran­ches 1679.0M 1679.0M
branch-misses 0.0M 0.0M
branch-misses 0.0% 0.0%

Jak je vidět, i když ne­zá­vislá verze po­tře­buje více in­strukcí, běží 2x rych­leji.

V prvním pří­padě jedna ite­race plně závisí na té před­chozí. Při­řa­zení x = arr[x] tvoří da­to­vou zá­vis­lost. Ná­sle­du­jící ite­race nemůže po­kra­čo­vat, pokud ještě ne­skon­čilo na­čí­tání arr[x], pro­tože pro­ce­sor neví, která hod­nota bude na­čtena a tedy neví, na jakou adresu skočit. V tomto pří­padě to bude x+1, ale to pro­ce­sor nemůže vědět, ten vidí jen bajty na­há­zené v paměti, a proto musí čekat, dokud na­čí­tání ne­skončí, než bude po­kra­čo­vat.

Druhý kus kódu také ob­sa­huje zá­vis­lost, ale v tomto pří­padě nejde o zá­vis­lost da­to­vou, ale o zá­vis­lost řídící struk­tury (con­t­rol flow). Pro­ce­sor se musí jen roz­hod­nout, jestli i < iter bude vy­hod­no­cena jako pravda nebo ne­pravda a podle toho skočit na další ite­raci nebo smyčku za­říz­nout. Jde o jed­no­du­chou bi­nární volbu, kterou dokáže branch pre­dic­tor od­had­nout přesně i v kom­pli­ko­va­ných pří­pa­dech. Tady jde o tri­vi­ální smyčku, kterou pro­ce­sor od­hadne vždy, roz­jede OOO ma­ši­né­rii, začne spe­ku­lo­vat napříč ite­ra­cemi a na­je­dou má k mání moře ne­zá­vis­lých ope­rací (i za cenu, že se občas zmýlí ve spe­ku­la­cích a bude muset za­ho­dit ně­které vý­sledky).5

I když tech­nicky vzato, pro­ce­sor může od­had­nout hod­notu před tím, než je na­čtena z paměti a na zá­kladě toho rozjet spe­ku­la­tivní exe­kuci. Pokud mají data jed­no­duše před­ví­da­telný vzor jako v mém pří­padě výše, pro­ce­sor ho může velice snadno za­chy­tit a využít. Obecně je to však pro­blém, pro­tože je třeba trefit správ­nou hod­notu z 2^64 mož­ností (a navíc to má dopad na im­ple­men­taci pa­mě­ťo­vého modelu). V pří­padě con­t­rol flow de­pen­dency se stačí roz­hod­nout mezi pou­hýma dvěma mož­nostmi.6

Oba pro­gramy pro­chá­zejí pamětí li­ne­árně a proto pre­fet­cher dodává všechna data s před­sti­hem. Avšak stejně jako v mi­nu­lém testu, se i tady uka­zuje určitý počet cache miss. To může sig­na­li­zo­vat, že RAM ne­stíhá do­dá­vat data. Kdy­bych měl ve svém stroji rych­lejší paměti, pro­gram by běžel o něco rych­leji bez těchto cache-miss.

Rozdíl mezi zá­vis­lými a ne­zá­vis­lými ope­ra­cemi má pře­kva­pivě dopad úplně na všechno. Datové struk­tury za­lo­žená na poin­te­rech, jako jsou spo­jové se­znamy nebo stromy, ne­dě­lají nic jiného než zá­vislé ope­race – musím na­čí­tat jeden poin­ter za druhým než se pro­koušu k listům stromu. Tohle platí pro všechny druhy stromů nebo hi­e­rar­chic­kých struk­tur, můžou být široké nebo mělké, ale v cestě za cílem vždycky stojí zá­vislé ope­race. A shodou náhod všechny funk­ci­o­nální per­si­s­tentní datové struk­tury jsou im­ple­men­to­vány právě jako stromy.


Pokud upra­vím před­mi­nulý mod/mask test tak, aby na sobě byly jed­not­livé ite­race zá­vislé, si­tu­ace je na­jed­nou hro­zivě chmurná.

* mask mod
time 3.15 s 21.32 s
cycles 10805.6M 74504.3M
in­structi­ons 10076.0M 11768.4M
IPC 0.93 0.15
cache-re­fe­ren­ces 15.1M 7.8M
cache-misses 7.4M 6.8M
cache-misses 49.1% 87.0%
bran­ches 1679.4M 1681.8M
branch-misses 0.0M 0.0M
branch-misses 0.0% 0.0%

Na­jed­nou je zá­vislé modulo 7x po­ma­lejší než zá­vislé mas­ko­vání a 21x po­ma­lejší než ne­zá­vislé plně pi­pe­li­no­vané mas­ko­vání. To (kromě jiného) není vůbec dobrá zpráva pro RRB stromy. IPC 0.15 mluví za své.

Zá­vislé sek­venční čtení a zá­vislé ná­hodné čtení

Je čas při­tla­čit na pilu. Co se stane, když po­rov­nám zá­vislé sek­venční čtení jako minule a zá­vislé čtení z ná­hod­ných míst v paměti, tedy něčeho, co při­po­míná divoký hon na poin­tery 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 pro­chází. V jenom pří­padě polem li­ne­árně ros­tou­cích off­setů, v druhém pří­padě off­setů roz­há­ze­ných bez ladu a skladu.

* SEQ RAND
time 2.45 s 130.98 s
cycles 8650.7M 445541.6M
in­structi­ons 8391.4M 8643.6M
IPC 0.97 0.02
cache-re­fe­ren­ces 21.1M 1698.0M
cache-misses 10.1M 1662.8M
cache-misses 48.1% 97.9%
bran­ches 1678.2M 1722.0M
branch-misses 3592 0.4M
branch-misses 0.0% 0.026%

Jestliže všechny ostatní testy před­sta­vo­valy jen drobné ne­pří­jem­nosti, tohle roz­hodne o všem. Když můj pro­gram pro­chází data sek­venčně, pre­fet­cher to pozná a po­stará se, že všechno po­třebné bude včas k dis­po­zici v rychlé cache, při­pra­vené ke čtení. Na­proti tomu, když chci v každé ite­raci číst z ne­před­ví­da­telné lokace v paměti, pre­fet­cher nemůže pomoct, cache jsou k ničemu a vý­sle­dek je 53x po­ma­lejší. Pokud jsou data větší než pár me­ga­bajtů, které má L3 cache, každý load jde přímo do RAM a RAM je za­tra­ceně pomalá. Hlavní paměť má uchá­ze­jící pro­pust­nost a proto ne­před­sta­vuje zas takový pro­blém, když je pro­gram li­mi­to­vaný právě prů­to­kem bitů. Když však záleží na la­tenci každé ope­race, všechno jde do kytek, pro­tože zá­vis­losti vy­tvoří kauzální ře­tě­zec.

Datové struk­tury, které jsou pro­chá­zeny v před­ví­da­tel­ném li­ne­ár­ním pořadí nebo ty, je­jichž horká část se vejde do ně­které úrovně cache pro­ce­soru budou rychlé. Ty, které tyto pod­mínky ne­spl­ňují, můžou trpět.

Na­pří­klad java.util.Ha­shMap je im­ple­men­to­vaná tak, že po­tře­buje 3 zá­vislé load ope­race. Když je ha­shmapa velká a ne­ve­jde se do cache, každý pří­stup do ní, může stát ně­ko­lik cache-miss. Ne­dávno jsem napsal Strin­gIn­t­Dicti­o­nary – mapu spe­ci­a­li­zo­va­nou pro strin­gové klíče a pri­mi­tivní hod­noty, která je až 3x rych­lejší než j.u.HashMap[String, Int] právě proto, že po­tře­buje načíst data jen z jed­noho 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 im­ple­men­to­ván velice ši­ro­kým stro­mem a v zá­vis­losti na ve­li­kosti po­tře­buje něco mezi 1 a 7 zá­vis­lými load ope­ra­cemi. Na druhou stranu, když k danému vek­toru při­stu­puji často, prv­ních pár úrovní bude v cache a cena pří­stupu tak nemusí být pře­hnaná. V ben­chmar­cích jsem zjis­til, že Vector je 4-8x po­ma­lejší než oby­čejný plochý Arra­y­Bu­f­fer.

Za zmínku může stát také tento test spe­ci­a­li­zo­va­ných map, který uka­zuje, že ty mapy které po­tře­bují při­stou­pit jen k jed­nomu místu v paměti, jsou rych­lejší než ty které po­tře­bují při­stou­pit ke dvěma nebo třemi.

Ne­zá­vislé sek­venční čtení a ne­zá­vislé ná­hodné čtení

Další test: Jak je na tom ne­zá­vislé sek­venční čtení v po­rov­nání s ne­zá­vis­lým ná­hod­ný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 stej­nému vý­sledku, liší se však jen po­řa­dím v jakém při­stu­puje k ele­men­tům pole – jednou sek­venč­ním a po­druhé ná­hod­ném.

* SEQ RAND
time 1.22 s 25.55 s
cycles 4073.1M 86769.1M
in­structi­ons 13431.2M 13718.2M
IPC 3.29 0.15
cache-re­fe­ren­ces 91.8M 2895.3M
cache-misses 36.4M 1835.3M
cache-misses 39.7% 63.3%
bran­ches 1679.3M 1727.9M
branch-misses 22135 386246
branch-misses 0.0% 0.022%

Rozdíl v rych­losti je ten­to­krát pouze 21x v ne­pro­spěch ná­hod­ného čtení. Jak je vidět z těchto vý­sledků, i když se čte z ná­hod­ných míst v DRAM, pro­ce­sor dokáže spe­ku­lo­vat a začít pár čtení na­jed­nou a za­mas­ko­vat tak la­tence. Ne­zá­vislé sek­venční čtení je ještě o něco rych­lejší než zá­vislé sek­venční i když po­tře­buje o 50% více in­strukcí.

Když po­rov­nám všechny pří­pady, začne se mi rý­so­vat ná­sle­du­jící obraz:

test čas 1 ite­race 1 ite­race 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 re­pre­zen­tuje případ, kdy se všechna data vejdou do L1 cache a pro­gram ne­po­tře­buje číst a být li­mi­to­ván rych­lostmi DRAM. Jak je vidět, v tomto pří­padě pro­ce­sor našel dost pa­ra­le­lismu, na to aby stihl vy­ko­ná­vat 4.45 in­strukce každý takt.

Dů­le­žitý je rozdíl mezi nej­rych­lej­ším a nej­po­ma­lejší verzí – i když dělají to samé, jedna běží 140x po­ma­leji než ta druhá. To zhruba od­po­vídá roz­dílu v rych­losti mezi dneš­ními po­čí­tači a těmi z roku 2003. Jde sice o vy­kon­stru­o­vaný případ, ale přesto uka­zuje rozpětí, do kte­rého budou reálné pro­gramy spadat.

branch pre­diction

Na závěr ukážu ne­in­tu­i­tivní cho­vání pod­mí­nek.

Funkce generate_truly_random_array vy­ge­ne­ruje pole ná­hod­ných čísel z roz­sahu INT_MIN až INT_MAX. Chci spo­čí­tat ně­ja­kou agre­gaci těchto hodnot, ale ně­které ne­vy­ho­vu­jící bych chtěl ig­no­ro­vat. V prvním pří­padě za­po­čí­tám jen hod­noty větší než 0 a v druhém všechny kromě nuly. Dva kusy kódu na rozdíl od před­cho­zích po­ve­dou 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
in­structi­ons 19304M 23491M
IPC 0.75 3.72
cache-re­fe­ren­ces 19M 35M
cache-misses 15M 12M
cache-misses 79% 34%
bran­ches 3357M 3355M
branch-misses 838M 0M
branch-misses 25% 0%

Jak je vidět, tak verze, která dělá dva­krát víc práce, je 4x rych­lejší. Pro­blém ten­to­krát spo­čívá v před­ví­da­tel­nosti pod­mí­nek. Pokud je pod­mínka dobře před­ví­da­telná, branch pre­dic­tor ji uhodne, začne číst a de­kó­do­vat in­strukce správné sek­vence ná­sle­du­jí­cích in­strukcí a všechno jede, jako kdyby se v kódu žádný skok ne­vy­sky­to­val. Když však uhodne špatně a bude muset všechnu spe­ku­la­tivní práci za­ho­dit a začít od správ­ného konce. Na­stane tak­zvaný pi­pe­line stall nebo pi­pe­line bubble. Množ­ství ztra­cené práce od­po­vídá hloubce pi­pe­line, která na mém Haswellu má délku 14-19 taktů. V ben­chmarku pomalá verze po­tře­buje 11.5 taktu na každou ite­raci, což při­bližně od­po­vídá ta­bul­ko­vým hod­no­tám a faktu, že rychlá verze musí pořád udělat 2x víc uži­tečné práce.

Dále je vidět, že jen 25% in­strukcí vedlo k branch-miss. Po­lo­vina pod­mí­ně­ných skoků tvoří smyčku, kterou hard­ware uhodl na­prosto do­ko­nale. Ve zbý­va­jící po­lo­vině se trefil na 50% – měl tedy stej­nou úspěš­nost, jako kdyby házel mincí.

K tomuto pří­padu se sluší dodat, že kdyby bylo tělo smyčky o něco jed­no­dušší (to dělení pro­měn­nou d tam nebylo jen tak pro nic za nic), kom­pi­lá­tor by ji mohl pře­lo­žit na sérii cmov in­strukcí. cmov neboli con­di­ti­o­nal move ne­před­sta­vuje vět­vení toku pro­gramu, ale ope­raci, která je vy­ko­nána tak jako tak, pod­mínka určí jestli má nějaký efekt. Kdyby se tak stalo, běžely by obě verze stejně rychle, pro­tože by ne­ob­sa­ho­valy žádný ne­před­ví­da­telný skok.

x86 má jed­ni­nou ta­ko­vou in­strukci – cmov, mnoho in­strukcí na 32bi­to­vých ARMech je pre­di­ko­va­tel­ných a celé ne­slavné Ita­nium bylo na tomto prin­cipu po­sta­veno.

Takže co?

Doufám, že jsem ukázal, jaký může být rozdíl v rych­losti pro­gramů, když pra­cují s hard­warem a když pra­cují proti němu. Když jsou al­go­ritmy a datové struk­tury malé, lo­kální, sek­venční a před­ví­da­telné, na mo­der­ním hard­waru do­slova poletí, pokud tyto vlast­nosti chybí, s rych­lostí to může drh­nout.

To je všechno, jděte domů a po­u­žijte, co jste se do­zvě­děli.


Pozn:

  1. S modulo je samá zábava. Modulo ne­ga­tiv­ního čísla vrátí zá­porný vý­sle­dek a ani funkce Math.abs nemusí pomoci, pokud není po­u­žita správně.
  2. Dělení v plo­voucí čárce je o něco rych­lejší, ale přesto po­ma­lejší, než ná­so­bení pře­vrá­ce­nou hod­no­tou.
  3. Dělení a modulo je (aspoň na x86) jedna a ta samá ope­race. DIV/IDIV vrátí jak vý­sle­dek dělení, tak i zbytek po dělení.
  4. V tomto kon­textu stojí za zmínku Cray XMT/Thread­Storm, který dotáhl hy­perthrea­ding/SMT do ex­trému. Thread­Storm je pro­ce­sor, určený pro úlohy, které vy­ka­zují jen mi­zi­vou lo­ka­litu dat a kde cache ne­po­mů­žou (jako např. zpra­co­vání gi­gan­tic­kých grafů). Za­tímco běžné x86 pro­ce­sory si poradí s 2 vlánky na­jed­nou, Xeon Phy, Power8 a nej­no­vější Sparcy od Oraclu zvlá­dají 8 vláken, Thread­Storm dokáže zpra­co­vat 64 vláken na­jed­nou. por­ce­sor ob­ra­huje všechny hard­wa­rové pro­středy všech 64 vláken (soubor re­gis­trů 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 ope­rač­ního sys­tému. Jde tedy o hard­wa­ro­vou im­ple­men­taci pře­pí­nání pro­cesů, když je ak­tivně běžící vlákno blo­kuje. Viz: Over­view of the Next Ge­ne­ration Cray XMT.
  5. A že může spe­ku­lo­vat za­tra­ceně hlu­boko. Nový Sky­lake od Intelu ob­sa­huje bu­f­fery pro 224 in­strukcí za letu, 72 pa­ra­lel­ních load in­strukcí a 180 in­te­ger a 168 flo­a­ting-point re­gis­trů, které spe­ku­lace po­tře­bují k pře­jme­no­vá­vání.
  6. Navíc i když pro­ce­sor nemá plnou pod­poru pro pre­dikci hodnot, může ob­sa­ho­vat tak­zvaný branch target pre­dic­tor, který se snaží od­had­nout cíle ne­sta­tic­kých skoků (jump re­gis­ter). Tohle může zrych­lit volání vir­tu­ál­ních metod v C++ a po­dob­ných ja­zy­cích, které se ne­mů­žou spo­leh­nout na JIT a inline cacheopor­tu­nis­tic­kou op­ti­ma­li­zaci. 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é al­fa­nu­me­rické klíče ne­u­klá­dám jako String ob­jekty, ale jako spe­ci­álně za­kó­do­va­ných do 54 bitů nebo offset/délku od sou­vis­lého pole znaků.
  8. Tady nešlo o snahu zabít x86, pro­tože iAPX a x86 mají po­čátky ve stejné době.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články