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

XPath – co, proč a hlavně jak?

Potom, co jsem na nedávné Poslední Sobotě mluvilMatcheru, se zájem o tento nástroj znatelně zvýšil. Lidé začali posílat pull-requesty, bugreporty a maily s otázkami jak se dá udělat to či ono. Na všechny jsem rád odpověděl, protože dotazy byly buď triviální a tudíž jednoduché na vytřešení nebo zajímavé oříšky, které musely být vyřešeny. Jedno měly však společné: V naprosté většině řešení nemělo nic společného s Matcherem, ale ve správném použití XPath, na němž je nástroj založený. Právě z toho důvodu jsem napsal následující letmý úvod do XPath, který ukáže vlastnosti nejčastěji používané při extrakci dat z HTML.

XPath plní stejný účel jako CSS selektory: Z HTML stromu vybere uzly, které mě zajímají a se kterými bych chtěl dál pracovat – ostylovat v případě CSS nebo z nich extrahovat data v případě Matcheru. Ve srovnání se současnou verzí CSS selektorů je však XPath expresivnější a místy má odlišnou sémantiku.

Všechno bude nejlépe patrné z ukázek.

/html – Vybere element html, který je kořenovým elementem stromu.

/html/body – Odpovídá všem elementům body, které jsou přímými potomky kořenového elementu html.

//h2 – Všechny elementy h2, které se v dokumentu vyskytují, včetně vlastních podstromů. Pokud jeden h2 kdekoli v sobě obsahuje jiný element h2, výsledkem budou všechny tyto elementy.

//div/span//a – Selektory je možno libovolně řetězit a tento najde všechny a jako potomky span, které jsou přímými potomky libovolného divu.

./div nebo div – Vybere všechny elementy div které jsou přímými potomky právě aktivního elementu. Jde o relativní polohu a ne o polohu fixovanou ke kořenu dokumentu.

.//div – To samé jako předchozí výraz, ale připouští i nepřímé potomky.

div[@class="asdf"] – div, jehož atribut class je „asdf“. XPath nepodporuje CSS třídy a k obsahu atributů přistupuje jako ke stringům a proto, tento výraz není stejný jako css selektor div.asdf. XPath podmínce @class="asdf" vyhoví jen ty elementy jejichž atribut class je jen a pouze string „asdf“. Na toto je si třeba dávat pozor, protože jde o největší odchylku od chování, které by čekal člověk odkojený CSS selektory.

div[@class != "asdf"] nebo div[not(@class = "asdf")] – Odpovídá divům jejichž třída není „asdf“.

div[contains(@class, "asdf")] – divy jejichž atribut class obsahuje string „asdf“. Například: Třída „xasdfy“ také vyhovuje tomuto predikátu.

div[starts-with(@class, "asdf")] – divy jejichž atribut class začíná na „asdf“.

div[contains(concat(" ", normalize-space(@class), " "), " asdf ")] – Tento výraz má stejný význam jako CSS selektor div.asdf (tedy kromě toho, že CSS nepřihlíží v velikosti písmen a XPath ano). Naštěstí takové konstrukce nejsou skoro nikdy potřeba, protože většinou stačí jednoduché @class="asdf" nebo funkce contains().

div[@class] – divy, které mají nějaký atribut class

div[span] – divy, které mají jako přímého potomka span

div[.//span] – divy, které obsahují span

div[span[@class]] – divy, které mají přímého potomka span, který má nastavenou libovolnou třídu

div[@class and span] – divy, které mají nastaven atribut class a zároveň obsahují span jako potomka. Stejně jako and se dá použít i logické or nebo funkce not().

div[1] – První div v pořadí v jakém se vyskytuje v dokumentu.

div[last()] – Poslední div.

div[position() mod 2 = 0] – Každý sudý div.

Na pořadí predikátů v hranatých závorkách záleží:

div[@class="asdf"][1] – Vybere všechny divy s třídou „asdf“ a z nich pak vybere ten první. Pokud existují nějaké divy s touto třídou, výsledkem bude vždycky první z nich.

div[1][@class="asdf"] – Vybere první div a ten ve výsledné množině ponechá jen pokud má třídu „asdf“. Když existují divy s touto třídou, ale první ji nemá, výsledkem je prázdná množina.

div/text()[1] – Z divu vybere první kus textu, který není obsažen v žádném jiném elementu.

preceding-sibling::h2 – Vybere elementy h2, které předcházejí aktivnímu elementu a zároveň jsou jeho sourozenci (tj. jsou přímými potomky stejného elementu jako aktivní element).

a[@class="active"]/following-sibling::a[1] – Vybere první odkaz, který následuje (a je sourozenec) po odkazu s třídou „active“.


Dále k tématu:

PHP DOM, SimpleXML a Matcher

flattr this!

Posted in PHP | 5 Comments

Branch prediction moderních procesorů

Před nějakou dobou jsem narazil na článek z roku 2010, který testoval, jak si branch prediction procesorů té doby poradí s různými opakujícími se vzory skoků v programu. Došel k závěru, že když procesor nedokáže skoky předvídat, může být výsledný program až 6× pomalejší, než když předvídá perfektně. Rozhodl jsem se test zopakovat a zjistit, jak je na tom současný hardware.

Rychlost branch instrukce (neboli podmíněného skoku) závisí na tom, jestli je její podmínka předvídatelná. Pokud procesor dokáže správně uhodnout, zdali má skočit na jiné místo programu nebo pokračovat s následující instrukcí, je skok skoro zadarmo. Ale pokud procesor neví nebo uhodne špatně, následuje takzvaný pipeline stall, kdy CPU zahodí všechnu rozdělanou práci a začne číst, dekódovat a vykonávat instrukce ze správného místa.

Toto chování souvisí s faktem, že všechny současné procesory jsou pipelinované. Každá instrukce vyžaduje několik nezávislých kroků, typicky to jsou fetch, decode, execute a write-back, kdy je instrukce načtena z paměti, dekódována, vykonána a výsledky zapsány zpátky do paměti. Kdysi dávno procesory vzaly jednu instrukci, vykonaly sekvenčně všechny čtyři fáze a teprve potom se posunuly na další. V honbě za vyšším výkonem CPU začala provádět všechny fáze najednou pro různé instrukce. Zatímco jedna instrukce zapisuje do paměti, následující se vykonává, následující je dekódována a následující je načítaná z paměti. Najednou se v procesoru nachází několik instrukcí za letu. Současné procesory mají pipeline s více kroky než jsou ony čtyři a navíc jsou superskalární, což znamená, že v každém taktu dokážou zpracovat několik instrukcí. Z těchto důvodů je počet instrukcí „za letu“ je mnohem vyšší. Délka pipeline souvisí s navyšováním taktu: Čím vyšší frekvence, tím méně času má signál dostat se skrz jednu fázi pipeline, když se zvýší počet kroků, každý může být o něco kratší. Současné x86 mají něco mezi 12–15 fázemi a když je hezky zvládnout zpracovat 4 instrukce za takt, Itanium zvládne stabilně 12 a chystaný Mill až 33.

Teď si představte, že se v tomto perfektním soustrojí vyskytne podmíněný skok. Část CPU, která načítá instrukce na začátku pipeline, se musí rozhodnout, jestli načte následující instrukci, nebo tu na kterou branch může skočit. Podmínka, která to určuje, není zatím vykonána a ještě několik taktů nebude, dokud se neprobojuje na druhý konec pipeline. To je však příliš dlouhá doba a procesor si nemůže dovolit čekat. V ten okamžik na scénu nastoupí branch predictor a pokusí se to uhodnout. Když se trefí, všechno jede jako na drátkách, když se zmýlí, nastane pipeline stall, procesor musí zahodit všechnu práci do které se spekulativně pustil a začít načítat instrukce ze správného místa a prohnat je skrz celou pipeline a tedy ztratit množství času odpovídající délce pipeline.

Naštěstí je většina skoků v programu velice dobře předvídatelná. Například smyčky, které projedou mnoho iterací a během každé z nich branch instrukce skočí na začátek, kromě té poslední, kdy propadne. Procesory používají mnoho různých variant branch predictorů, které zaznamenávají minulé chování podmíněných skoků a předpokládají, že se stejné nebo podobné chování bude opakovat i v budoucnu. Někdy mají několik různých predictorů a jeden meta-predictor, který učiní finální rozhodnutí. Tímto způsobem dosahují impresivních výsledků, kdy mají skoro vždycky pravdu.

Branch predictor je velice důležitá část CPU, protože v typických programech představují skoky každou šestou až osmou instrukci a pipeline stall znamená obrovské zdržení. Například Pentium-Pro, Pentium 2 a Pentium 3 měly pipeline s více jak 12 fázemi, mispredict stál něco mezi 10 a 15 takty a i když měly pokročilý dynamický branch predictor, který fungoval s 90% přesností, ztrácely 30% výkonu kvůli těm 10 zmýleným procentům. Pentium 4 měl pipeline dlouhou 31 taktů a to pravděpodobně způsobovalo jeho nepřesvědčivé výkony.

V současných velkých procesorech jen přibližně 6 až 8 procent plochy čipu skutečně provádí výpočty, zbytek se stará, aby tento zlomek křemíku měl stále co na práci. Jde o branch predition jednotky, několik úrovní cache, out-of-order engine, virtuální registry, spekulace, prefetching a další hardware, který bojuje proti latenci a zrychluje běžný kód, který je typický tím, že obsahuje hodně skoků.


Zpátky ke zmíněnému článku. Ten testoval rychlost skoků na kódu, který vypadal nějak takto:

for (int i = 0; i < max; i++) if (<condition>) sum++;

Podmínka měla tvar (i & constant) == 0. Volbou různé konstanty se dá snadno vytvořit krátký opakující se vzor. Původní výsledky zkombinované s těmi mými vypadají následovně:

|-------------------------------------------------------------------------------------
| Condition              | Pattern     |   2010  |  Intel Atom      | Intel Haswell i5
|                                      |         |     -O0 |    -O3 |    -O0 |   -O3
|-------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  | TTTTTTTT    |  322 ms |  388 ms | 374 ms | 211 ms | 86 ms
| (i & 0xffffffff) == 0  | FFFFFFFF    |  276 ms |  334 ms | 374 ms | 218 ms | 86 ms
| (i & 1) == 0           | TFTFTFTF    |  760 ms |  602 ms | 371 ms | 216 ms | 86 ms
| (i & 3) == 0           | TFFFTFFF    |  513 ms |  427 ms | 378 ms | 219 ms | 86 ms
| (i & 2) == 0           | TTFFTTFF    | 1675 ms |  441 ms | 373 ms | 213 ms | 85 ms
| (i & 4) == 0           | TTTTFFFF    | 1275 ms |  642 ms | 378 ms | 214 ms | 85 ms
| (i & 8) == 0           | 8T 8F ...   |  752 ms |  546 ms | 370 ms | 214 ms | 85 ms
| (i & 16) == 0          | 16T 16F ... |  490 ms |  446 ms | 377 ms | 214 ms | 85 ms
|-------------------------------------------------------------------------------------
| xorshift rand len 8    | random      |  ---    | 1212 ms | 680 ms | 234 ms | 86 ms
| xorshift rand len 16   | random      |  ---    | 1284 ms | 676 ms | 230 ms | 86 ms
| xorshift rand len 32   | random      |  ---    | 1328 ms | 679 ms | 228 ms | 86 ms
| xorshift rand len 64   | random      |  ---    | 1428 ms | 676 ms | 227 ms | 86 ms
| xorshift rand len 128  | random      |  ---    | 1475 ms | 676 ms | 227 ms | 86 ms
| xorshift rand len 256  | random      |  ---    | 1560 ms | 679 ms | 229 ms | 85 ms

Sloupec 2010 ukazuje časy naměřené v onom článku na neznámém procesoru a s neznámým počtem iterací. Z toho důvodu nevěnujte žádnou pozornost rozdílu v absolutních číslech mezi těmito a mými časy. V následujících sloupcích jsou časy na Atomu reprezentující low-end všech low-endů a na desktopovém i5 Haswellu, reprezentujícím rozumný křemík. V obou případech byl testovací kód kompilovaný gcc s příznaky -O0 (bez optimalizací) a -O3 (maximální optimalizace). K tomu jsem přidal pár pseudo-náhodných testů, ve kterých se opakoval náhodný vzor určité délky (vygenerovaný přes xorshift RNG).

Jak je z výsledků vidět, tak i prachobyčejný levný Atom určený do netbooků v nejhorším případě běží 2× pomaleji a současné rozumné procesory v žádném z testů nepocítí žádné zpomalení. Branch prediction jednotky doznaly znatelného zlepšení a dokáží perfektně detekovat dlouhé opakující se vzory, pokud jsou přítomny. Když má skok skutečně náhodný charakter, nepomůže ani svěcená voda.

Zajímavé jsou také výsledky -O3 optimalizace. Na Haswellu kód s -03 je jenom rychlejší, ale na Atomu smaže rozdíly mezi ideálními a neideálními případy a všechno najednou běží tak, jako kdyby branch predictor vždycky uhodl správně. Kouzlo spočívá v tom, že GCC se rozhodlo if (<condition>) sum++ nekompilovat jako podmíněný skok, ale jako instrukci CMOV neboli conditional move. Ta funguje tak, že přesune data mezi dvěma místy, ale jen pokud je splněná určitá podmínka. CMOV je vykonána v každém případě, ale může nebo nemusí mít svůj efekt. Protože nejde o podmíněný skok, procesoru nehrozí pipeline stall a kód běží stabilní rychlostí. Pokud je skok nepředvídatelný, zrychlení může být znatelné (jak je vidět tak pro náhodné vzory je to až 2.5×), ale to není zas tak běžný případ.

Pro úplnost: -O0 vygeneruje následující instrukce:

test   %eax,%eax        ; kontrola podmínky
jne    40065a           ; skočí za následující instrukci, pokud podmínka neplatí
addl   $0x1,-0x8(%rbp)  ; inkrementuje sum

-O3 vygeneruje něco na způsob tohoto:

test   %edx,%eax        ; kontrola podmínky
cmove  %ecx,%ebx        ; pokud podmínka platí, přesune ecx do ebx
lea    0x1(%ebx),%ecx   ; ecx ← ebx + 1

CMOV je jediná podmíněná x86 instrukce, ale například 32bitový ARM nebo Itanium má podmíněné skoro všechno a může tedy dělat například podmíněné aritmetiku. ARM to má kvůli chybějícím/slabým branch predictorům, Itanium proto, že bylo navrženo pro masivní ILP a software pipelining (z toho důvodu má 64 1-bitových predikátových registrů a rotující registry).


Když se podívám na podrobné informace vygenerované programem perf, který poskytuje přístup k interním čítačům CPU, dostanu velice podrobný pohled, co se děje pod kapotou.

|------------------------------------------------------------------------------------------------------
| Condition              | Intel Atom
|                        | -O0                                  | -O3
|                        |    time | branch-miss | instr |  IPC |   time | branch-miss | instr |  IPC
|------------------------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  |  388 ms |       0,01% |   893 | 1,41 | 374 ms |       0.02% |   600 | 0,98
| (i & 0xffffffff) == 0  |  334 ms |       0,01% |   799 | 1,48 | 374 ms |       0.02% |   599 | 0,99
| (i & 1) == 0           |  602 ms |       0,02% |   851 | 0,86 | 371 ms |       0.02% |   600 | 0,99
| (i & 3) == 0           |  427 ms |       0,01% |   823 | 1,18 | 378 ms |       0.02% |   600 | 0,97
| (i & 2) == 0           |  441 ms |       0,01% |   850 | 1,18 | 373 ms |       0.02% |   599 | 0,98
| (i & 4) == 0           |  642 ms |       0,02% |   849 | 0,81 | 378 ms |       0.02% |   598 | 0,97
| (i & 8) == 0           |  546 ms |       6,27% |   850 | 0,95 | 370 ms |       0.02% |   600 | 0,99
| (i & 16) == 0          |  446 ms |       3,15% |   846 | 1,16 | 377 ms |       0.02% |   599 | 0,98
|------------------------------------------------------------------------------------------------------
| xorshift rand len 8    | 1212 ms |       0,04% |  1625 | 0,82 | 680 ms |       0,03% |   901 | 0.81
| xorshift rand len 16   | 1284 ms |       4,15% |  1637 | 0,78 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 32   | 1328 ms |       7,53% |  1645 | 0,75 | 679 ms |       0,03% |   901 | 0.81
| xorshift rand len 64   | 1428 ms |      12,87% |  1653 | 0,70 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 128  | 1475 ms |      15,43% |  1658 | 0,68 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 256  | 1560 ms |      20,32% |  1650 | 0,64 | 679 ms |       0,03% |   900 | 0.81

|------------------------------------------------------------------------------------------------------
| Condition              | Intel Haswell i5
|                        | -O0                                  | -O3
|                        |    time | branch-miss | instr |  IPC |  time  | branch-miss | instr |  IPC
|------------------------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  |  211 ms |       0.00% |   800 | 1,07 |  86 ms |       0.00% |   600 | 1.99
| (i & 0xffffffff) == 0  |  218 ms |       0.00% |   701 | 0,91 |  86 ms |       0.00% |   600 | 1.99
| (i & 1) == 0           |  216 ms |       0.00% |   751 | 0,99 |  86 ms |       0.00% |   600 | 1.99
| (i & 3) == 0           |  219 ms |       0.00% |   725 | 0,94 |  86 ms |       0.00% |   600 | 1.99
| (i & 2) == 0           |  213 ms |       0.00% |   750 | 1,00 |  85 ms |       0.00% |   600 | 1.99
| (i & 4) == 0           |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
| (i & 8) == 0           |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
| (i & 16) == 0          |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
|------------------------------------------------------------------------------------------------------
| xorshift rand len 8    |  234 ms |       0.00% |  1625 | 1,96 |  86 ms |       0.01% |   900 | 2.98
| xorshift rand len 16   |  230 ms |       0.00% |  1638 | 2,01 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 32   |  228 ms |       0.00% |  1644 | 2,04 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 64   |  227 ms |       0.00% |  1652 | 2,06 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 128  |  227 ms |       0.06% |  1657 | 2,06 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 256  |  229 ms |       0.01% |  1649 | 2,05 |  85 ms |       0.01% |   900 | 2.99

Sloupec branch-miss ukazuje kolik podmíněných skoků bylo špatně předpovězeno, instr počet vykonaných instrukcí a IPC počet instrukcí vykonaných v jednom taktu. Jak je vidět úplně napravo, v tomto testu rozumný procesor dneška zvládá vykonat dvě až tři instrukce každý takt a téměř žádný skok není chybně předpovězen.


Dále k tématu:

flattr this!

Posted in CPU | 2 Comments

Procesory a jejich architektura (sebrané spisy)

Moderní procesory jsou velice komplikované křemíkové bestie a mnoho lidí neví, nebo má jen mlhavou představu, co se děje uvnitř a co způsobuje, že některé programy běží neuvěřitelně rychle a jiné tak pomalu, že si člověk stihne uvařit kafe a udělat něco k jídlu.

Pokud se chcete dozvědět, jak CPU fungují, připravil jsem pro vás seznam článků, videí, paperů a knih, které vám na této cestě za poznáním pomůžou a do nejmenších detailů osvětlí fantastická soukolí Stroje.

Obecné

Detaily procesorů a architektur

Algoritmy a datové struktury využívající vlastnosti CPU ve svůj prospěch

Mill CPU

Názorná série videí, která představuje chystanou architekturu Mill a během toho ukáže, jak fungují současné procesory a jak se od nich Mill liší.

Concurrency

Java, JVM

flattr this!

Posted in CPU, Paměť | Leave a comment

Types will carry you over the Monads

Teď nechci zabřednout do bažin internetu a napsat další monádový tutoriál, ale jen zveřejnit jeden postřeh, díky kterému jsem pochopil sílu Applicatives:

Vždycky, když jsi v úzkých, následuj typy a ty tě dovedou do cíle.


Funkce bind definovaná na monádě má typ:

bind :: M a -> (a -> M b) -> M b

Ten říká, že mám nějaké M a a pak funkci z a do M b a když je nějak zkombinuji, dostanu M b. Z typu je vidět, že do funkce a -> M b musím dodat a, které je uvězněno v M a a jinak není možné pokračovat. Monády tedy popisují operace, které jsou sekvenční a jeden krok závisí na výsledku toho předchozího.

Pokud tedy například M a reprezentuje asynchronní operaci, která eventuálně vyprodukuje hodnotu typu a, argument a -> M b představuje další async akci, která k tomu, aby vůbec začala, potřebuje znát a – tedy předchozí výsledek. Jde tedy o řetězení async operací, které je jasně patrné z typu funkce.


Applicative definuje jednu funkci, které tady budu říkat apply 1 a která má typ:

apply :: M a -> M (a -> b) -> M b

Ten říká, že mám nějaké M a a nějaké M (a -> b) (tedy funkci a -> b uvnitř M) a když je nějak zkombinuji, dostanu M b. Ale na rozdíl od předchozího případu, M (a -> b) nepotřebuje a k tomu aby začal pracovat.

Pokud je M opět asynchronní operace, pak druhý argument představuje jinou asynchronní operaci, která nezávisle na prvním argumentu vyprodukuje funkci a -> b. Když jsou oba dva argumenty připraveny, je možné zavolat funkci z druhého argumentu s výsledkem toho prvního a dostat tak výsledek reprezentovaný async operací M b.

Opět: I tohle je patrné z typu funkce a není možné to udělat jinak a stále vyhovovat typové signatuře.


Pro úplnost ještě uvedu funktor, jehož funkce fmap má typ:

fmap :: M a -> (a -> b) -> M b

Když by M byla zase async operace, pak argument a -> b představuje pure transformaci výsledku této operace, který sám nedělá žádná async kouzla.

To všechno je zas patrné z pouhého typu.

Ještě se sluší dodat, že každá monáda je applicative a každá applicative je funktor.

Doufám, že jsem tedy nakonec nenapsal další monádový tutoriál, ale něco, co bude aspoň trochu užitečné, A mimochodem: Titulek je variace na jméno alba We will carry you over the mountains od Magyar Posse.


Dále k tématu:


  1. V Haskellu tahle funkce má jiné pořadí argumentů a nese jméno (<*>), které může být podobně jako axaxaxas mlö vysloveno jen jako posměšný a krutý smích autorů Haskellu.

flattr this!

Posted in Funkcionální programování, Typy | 2 Comments