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í:

*MASKMOD
time1.2 s4.5 s
cycles4103.9M15655.8M
in­structi­ons11745.5M13426.9M
IPC2.860.85
cache-re­fe­ren­ces104.0M10.1M
cache-misses43.1M7.9M
cache-misses41.4%78.7%
bran­ches1677.9M1678.6M
branch-misses0.0M0.0M
branch-misses0.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ý loadne­zá­vislý load
time2.61 s1.23 s
cycles8978.9M4139.9M
in­structi­ons8396.2M11751.5M
IPC0.932.83
cache-re­fe­ren­ces23.4M104.9M
cache-misses12.4M43.2M
cache-misses53.0%41.2%
bran­ches1679.0M1679.0M
branch-misses0.0M0.0M
branch-misses0.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 264 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á.

*maskmod
time3.15 s21.32 s
cycles10805.6M74504.3M
in­structi­ons10076.0M11768.4M
IPC0.930.15
cache-re­fe­ren­ces15.1M7.8M
cache-misses7.4M6.8M
cache-misses49.1%87.0%
bran­ches1679.4M1681.8M
branch-misses0.0M0.0M
branch-misses0.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.

*SEQRAND
time2.45 s130.98 s
cycles8650.7M445541.6M
in­structi­ons8391.4M8643.6M
IPC0.970.02
cache-re­fe­ren­ces21.1M1698.0M
cache-misses10.1M1662.8M
cache-misses48.1%97.9%
bran­ches1678.2M1722.0M
branch-misses35920.4M
branch-misses0.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.

*SEQRAND
time1.22 s25.55 s
cycles4073.1M86769.1M
in­structi­ons13431.2M13718.2M
IPC3.290.15
cache-re­fe­ren­ces91.8M2895.3M
cache-misses36.4M1835.3M
cache-misses39.7%63.3%
bran­ches1679.3M1727.9M
branch-misses22135386246
branch-misses0.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čas1 ite­race1 ite­raceIPC
SEQ INDEP L10.951.8 taktu0.6 ns4.45
SEQ INDEP1.222.4 taktů0.8 ns3.29
SEQ DEP2.454.9 taktů1.5 ns0.97
RAND INDEP25.5551.1 taktů16.0 ns0.15
RAND REP130.98262.0 taktů81.6 ns0.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 > 0x != 0
time8.05s1.98s
cycles25693M6308M
in­structi­ons19304M23491M
IPC0.753.72
cache-re­fe­ren­ces19M35M
cache-misses15M12M
cache-misses79%34%
bran­ches3357M3355M
branch-misses838M0M
branch-misses25%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