Von Neumannovy lži

Asi takhle: Existují dvě široké rodiny procesorů. Na jedné straně Von Neumannovy stroje a na druhé data-flow mašiny. První jmenovaná zpracovává jednu instrukci za druhou, druhá k programu přistupuje jako ke grafu závislostí, kdy každá operace je závislá na některých předcházejících a jakmile jsou všechny závislosti splněny, může být operace provedena.

Von Neumannova architektura je na papíře horší a mnohem méně ambiciózní než data-flow, protože je z povahy sekvenční, kdežto data-flow architektury jsou přirozeně paralelní. Jak dokládá historie, nakonec jsme skončili ve spárech Von Neumanna i přesto, že data-flow nebyl jen divoký sen poblázněných akademiků a tyto stroje se skutečně vyráběly. Na první pohled to může vypadat jako další triumf worse is better a vítězství průměrnosti. Pravda je však komplikovanější a má v sobě něco málo dramatické ironie.

To by jako úvod stačilo, teď je čas se po hlavě vrhnout do zákopů.

Budu uvažovat, že jsem napsal následující funkci (jde o kus kódu z mých experimentů s řazením):

def packedTerminatedByteSlice(arr: Array[Byte], from: Int, to: Int): Long = {
  var i = from
  var j = 0
  val end = math.min(arr.length, to)
  var res = 0L

  while (i < end) {
    res |= ((1 << 8) | arr(i)) << j
    i += 1
    j += 9
  }

  res
}

Jak by tato funkce byla vykonána na hypotetické data-flow mašině? Zajímá mě jen smyčka na konci funkce.

Je vidět, že v těle smyčky existují tři nezávislé cesty, které může data-flow stroj provádět najednou. Zatímco dělá logické ORy a SHIFTy, aby aktualizoval proměnnou res, může paralelně inkrementovat i a j. Napříč iteracemi se otevírají další možnosti: Podmínka smyčky i < end závisí jen na proměnné i, je možné ji tedy testovat, zatímco stroj provádí operace minulé iterace. Ze schématu je vidět, že jeden běh smyčky zabere tolik času, kolik potřebuje nejdelší cesta v grafu (modulo implementační detaily).

Von Neumannova architektura je proti tomu mnohem jednodušší. Program je přeložen na lineární sekvenci instrukcí, které jsou prováděny v řadě jedna za druhou.

Moje funkce by se mohla přeložit například na následující pseudo-assembly:

cond = cmp i end
jump_if_less_then cond
tmp1 = mov arr(i)
tmp2 = or 256 tmp1
tmp3 = shift tmp2 j
res  = or res tmp3
i    = add i 1
j    = add j 9
jump back

Kanonický Von Neumann načte jednu instrukci, provede ji a přesune se na další. Tělo smyčky obsahuje 9 instrukcí a to by mělo určit dobu jejího běhu1.

Návrháři architektur jsou však vynalézaví lidé, věčně nespokojení s tím, co současný hardware dokáže, a neustále přemýšlejí, jak starého Von Neumanna vylepšit. Došlo ke zvyšování taktů, což vedlo nejdříve k několika-taktovým instrukcím a pak k pipelinování. Ale stále šlo o stejnou architekturu – jedna instrukce v jeden čas, i když se různé fáze různých instrukcí překrývaly. Změnila se jediná věc: Nejednou bylo třeba sledovat závislosti pipelinovaných instrukcí. Pokud operace hned požadovala výsledek té předchozí, musela čekat, než ta předchozí dokončí svojí práci a zapíše výsledek do registru2. Kdyby nečekala, přečetla by nevalidní data. Hardware musel na pár taktů zastavit práci a v pipeline se vyskytla bublina (pipeline bubble).

a = x + 1
b = a + 1 // závisí na a

a: [ fetch | decode | read operands | execute | write result ]
b:         [ fetch  | decode        | ------- | ------------ | read operands | execute | write result ]

Pozorný čtenář si jistě všiml, že poslední dva součty ve výpisu instrukcí ukázkové funkce jsou na sobě zcela nezávislé. Je tedy možné je odpálit najednou bez komplikované data-flow mašinérie, která sleduje závislosti celého programu. Stačí jen trochu křemíku, který analyzuje vztahy sousedících operací. Tohle zjištění vedlo ke vzestupu superskalárních/wi­de-issue strojů – stále Von Neumannovských architektur, jen rozšířených o schopnost najednou odbavit nezávislé sousedící instrukce, pokud hardware má dostatek prostředků (v mém případě dvě ALU). Může jít o dynamickou vlastnost, kdy třeba X86 procesor analyzuje proud instrukcí za běhu a nebo statickou jako v případě VLIW nebo Itania.

Wide-issue jak jsem ho popsal využívá paralelismu jen v omezených případech. Nemůže paralelně provádět nezávislé instrukce mimo pořadí programu. Například tento kousek kódu

tmp1 = add input 1
x    = add tmp1 1
y    = add input 2

má vzájemně nezávislé operace na prvním a třetím řádku, ale druhý řádek závisí na výsledku toho prvního. Aby hardware mohl paralelně provést nezávislé instrukce, musí dělat věci mimo pořadí programu, tedy out-of-order (OOO). Tímto směrem směřovala evoluce ctihodného Von Neumannova stroje. OOO hardware sleduje vzájemné závislosti poměrně velkého okna instrukcí3 a snaží se naplno vytížit všechny dostupné funkční jednotky pomocí spekulativní exekuce. Udržuje si při tom dostatečné množství stavových informací, aby se dokázal vrátit zpátky do konzistentního stavu, kdyby se spekulace ukázaly jako příliš optimistické (např. kvůli špatné branch prediction).4

Všimli jste si toho taky? Out-of-order procesor vypadá skoro jako data-flow stroj.

Ironií osudu je, že postupnou evolucí se Von Neumann postupně přibližoval data-flow architekturám a došlo to tak daleko, že interní chování OOO stroje je téměř k nerozeznání od jeho data-flow bratrance. Rozdíl je jen v tom, že OOO stroj vytváří graf závislostí za běhu na poměrně omezeném okně instrukcí, zatímco data-flow to dělá na celém programu v době kompilace.

OOO stroje do segmentu osobních počítačů vpadly spolu s Pentiem Pro v roce 1995. Von Neumanovu architekturu tedy téměř nikdo z nás nepoužívá už dvacet let.


Dále k tématu:

  1. Pokud tedy budu uvažovat jednoduchý model, kdy každá instrukce trvá stejně dlouho a odmyslím si všechny nežádoucí efekty jako jsou rozdíly mezi rychlostí cache a RAM.
  2. Tyto případy částečně řeší tzv. Operand forwarding, který kromě zápisu do příslušného registru, data přesměruje přímo do následující instrukce.
  3. Například na Haswelech je to 192. Skylake generace Intelích CPU to rozšířila na 224. Nejde o x86 instrukce, ale o dekódované mikro-operace.
  4. Způsoby zotavení ze špatných spekulací jsou popsány například ve Fast Branch Misprediction Recovery in Out-of-order Superscalar Processors

Pozn:

Flattr this!

Posted in CPU | 3 Comments

Radix merge sort

Nedávno jsem tu psal o divoké hybridizaci řadících algoritmů, která mě dovedla k mergeselectu. Teď bych chtěl v této cestě pokračovat.

Metodou sledování os a hledání průsečíků jsem našel jedno nepokryté místo: Radixovou obdobu merge sortu. Quicksort má radixovou verzi (radixsort) a proto by mělo být možné zkřížit merge sort s radixovým způsobem života a vyprodukovat řadídí algoritmus, který stejně jako radixsort postrádá jeden logaritmus z asymptotické složitosti. Výsledek se v retrospektivě zdá natolik očividný, že se mi o něm skoro ani nechce psát. Wikipedie ho přímo nezmiňuje, ale chybí ji k tomu jen malý krůček.

Začnu však popořadě:

  • quicksort je založen na diskriminaci na základě porovnávání s pivotem a běží v průměrném čase O(n log(n))
  • radix sort je založen na diskriminaci podle radixu (jedna cifra/bajt/bit) a běží v čase O(bn), kde b je počet bitů klíče, podle něhož se řadí.
  • merge sort je založen na slučování na základě porovnávání čelních prvků dvou seřazených polí a v nejhorším případě běží v čase O(n log(n))
  • hypotetický radix merge sort by měl být také založen na slučování. To by však nemělo být hnané porovnáním s jinými prvky, ale jen inspekcí prefixů řadícího klíče. Výsledek by měl běžet v čase O(bn).

Merge sort za běhu vypadá nějak takhle:

Jde o strom slučování seřazených polí do větších seřazených polí. Logaritmus je ve složitosti proto, že hloubka stromu je logaritmická vzhledem k počtu slučovaných polí (které budu označovat jako m na rozdíl od celkového počtu řazených prvků, který dostane klasické jméno n).

Klasický merge sort materializuje všechna dočasná pole. To však není nutné. Strom slučovacích operátorů můžu nahradit stromem operátorů, které extrahují minimum ze svých podstromů, jak ukazuje další obrázek.

Výsledkem je líná verze merge sortu, která v čase O(m) sestaví strom MIN operátorů a potom v čase O(log(m)) extrahuje nejmenší element a to bez jakékoli materializace mezikroků. Líný merge sort není soubor míst do kterých se zapisuje, ale série trubek, kterými data protékají.

Ve funkcionálních jazycích s líným vyhodnocováním se takto chová merge sort napsaný tradičním stylem. Vstupem jsou líné spojové seznamy, které jsou vyhodnocovány jen tak daleko, jak je nutné. Ze slučovacích mezikroků se stane thunk / suspended computation (jako vždycky nemám ponětí o české terminologii) a jen jedna cesta stromem je přinucena k vyhodnocení s každým extrahovaným elementem. Mám za to, že řazení v Haskellu standardně používá verzi merge sortu právě proto, jak dobře spolupracuje s líným vyhodnocováním.2

Asymptotické časy líné verze vypadají velice povědomě, skoro jako kdyby šlo o haldu. Tu je taky možné vybudovat v lineárním čase a pak extrahovat minimum (a následně ji rebalancovat) v čase logaritmickém.

Min-heap je struktura, která dělá přesně to, co v tomto případě potřebuji. V klasickém merge sortu vezmu dvě pole a porovnám jejich čela, abych zjistil, které z nich je menší. Když slučuji víc polí, musím také najít nejmenší čelo mezi několika kandidáty – tedy to, co umí min-heap.

Když to dotáhnu do krajnosti a zvolím že m = n (všechna vstupní pole jsou singulární) podpůrná datová struktuta úplně převezme otěže a dostanu heapsort. To ale odbočuji.

Min-heap nebo línou konstrukci je možné nahradit binárním vyhledávacím stromem, i když asymptotická analýza ukazuje, že výsledek je morálně sporný. Konstrukce BST trvá O(mlog(m)) a extrakce minima O(log(m)).

V tomto okamžiku už všem musí být jasné, jak vypadá hledaný radix merge sort, žeano? Když vyměním min-heap za trie (neboli prefixový strom) dostanu kýžený algoritmus.

Pro klíče konstantní délky b má trie hloubku O(1). Přesné detaily záleží, na jaké kusy klíče nasekám: zdali na bajty, bity nebo jiné fragmenty.

Algoritmus pracuje tak, že vezme čela seřazených polí a vloží je do trie. Pak ji začne sekvenčně procházet. První prvek, na který narazí, je ten nejmenší. Zapíše ho do výstupu, nové čelo pole, ze kterého prvek pochází, zas vloží do trie a celý postup opakuje. Na diagramu je hledání nejbližšího prvku vyznačeno tečkovaně.

Když mám klíče délky b bitů a rozdělím je na úseky po f bitech, musím v nejhorším případě iterovat 2^f * (2b/f – 1) pozic stromu, než objevím následující nejmenší prvek. 2^f je velikost uzlu a 2b/f-1 představuje cestu z aktuálního listu ke kořeni a pak k dalšímu listu. Dá se předpokládat, že často bude nejbližší větší element relativně blízko, možná i ve stejném listu.

Teoreticky na přesném vzorci nezáleží. bf jsou konstanty, singulární operace má tedy složitost O(1) a celé řazení pracuje v lineárním čase.

Když začnu přemýšlet o praxi, existuje několik optimalizací, které můžou všechno značně urychlit. Jedna z nich vychází z poznatku, že iteruji jen vpřed a nikdy se nevracím. V momentě, kdy opustím jeden uzel, už ho nikdy nepoužiji, můžu ho tedy zrecyklovat a uštřit nějaké alokace. Trie může mít v nejhorším případě něco pod b/f * m uzlů (m je počet slučovaných polí).

Další zlepšovák spočívá v použití bitmapy, která označuje neprázdné pozice.

struct node {
        void* children[256];
        uint64_t bitmap[4];
}

Nejbližší obsazený slot pak najdu několika LZCNT instrukcemi (number of leading zeros) zcela bez podmíněných skoků (po odrolování).

min = 256;
for (i = 0; i < 4; i++) {
        m = _lzcnt_u64(bitmap[i]);
        min = MIN(min, m < 64 ? m + i*64 : 256);
}

Masochisté, kteří si libují v instrinsics, můžou udělat to samé pomocí AVX2:

zeros      = _mm256_broadcastb_epi8(0);
emptyBytes = _mm256_cmpeq_epi8(bitmap, zeros);
mask       = _mm256_movemask_epi8(emptyBytes);
pos        = _lzcnt_u32(~mask);
i          = _lzcnt_u32(((uint8_t*)&bitmap)[pos]);
return pos * 8 + i;

(Případné chyby jsem v kódu nechal jako cvičení pro čtenáře.)

Bitmapy mají příjemnou synergii s recyklací uzlů, protože nemusím vynulovat celý uzel, ale jen příslušnou bitmapu. Situaci o něco málo komplikují možné duplikáty, ale to není nic, co by se nedalo vyřešit.

To všechno je moc pěkné, ale k čemu je radix merge sort vlastně užitečný? Rozhodně ne pro sortování neseřazeného pole. Kdybych ho použil tak jak je, algoritmus by zdegeneroval na obyčejnou trie, která, tak jak jsem ji tu prezentoval, není příliš paměťově úsporná. Na druhou stranu mi přijde jako celkem užitečný nástroj pro velice široké slučování mnoha seřazených polí1, protože složitost nenarůstá s jejich počtem.

Na druhou stranu je třeba stále mít na paměti ošklivé tajemství všech radix-sortů: Pro reprezentaci každé z n rozdílných hodnot potřebuji log2(n) bitů. Radixová složitost n*b tedy není nic víc než n * log(n), kde jsme si řekli, že n neporoste nad praktické meze.

  1. Ta mohla vzniknout obyčejným radix sortem a jsou dostatečně malá, že se vešla do CPU cache pro maximální efektivitu
  2. Na líné řazení se spoléhali autoři Haskellové knihovny pro hledání nejbližších sousedů využívající cover tree.

Flattr this!

Posted in Algo, řazení | Leave a comment

Kompaktní stringy

S tímhle blogem možná skončím. Možná. Rozhodně sem vysypu všechny rozepsané články z bufferu a pak se uvidí.

Četl jsem Java 9: Compact Strings Vojtěcha Růžičky o kompaktní reprezentaci řetězců. Stringy, jejichž znaky spadají do ASCII, jsou reprezentovány kompaktně jako byte[]. V článku jsem narazil na:

Java 9 brings a new improved string, which in most cases, will reduce String memory consumption to half.

To není tak úplně pravda. Platí to asymptoticky pro nekonečně dlouhé stringy, ale pro ty kratší to nebude tak slavné. String má konstantní režii, která není úplně zanedbatelná. Javě je String tvořen dvěma objekty. String objekt obsahuje ukazatel na pole charů (v Javě 9 pole bytů). V paměti to vypadá takhle (na 64 bitovém stroji s komprimovanými pointery):

Oba objekty začínají 12B hlavičkami. Pole obsahuje 4B s informací o délce. String objekt obsahuje 4B komprimovaný pointer, 4B kešovaný hashCode a nevyužité 4B ztracené kvůli zarovnání objektů na 8B hranice.

Prázdný string tedy zabere 40 bajtů, krátké stringy budou tuhle cenu platit a relativní úspora kompaktních stringů bude o něco méně výrazná. Bude záležet jaké délky řetězců budou v aplikaci převládat.


K tématu:

Flattr this!

Posted in Java, JVM | 5 Comments

Iterace křížem krážem

Tenhle článek bych klidně mohl začít clickbait titulkem: „Jeden neuvěřitelný trik, který zrychlí vaše programy,“ a ani bych se za to nestyděl. Asi takhle: Když zpracovávám hromadu dat v několika průchodech (které z nějakých důvodů není možné spojit do jednoho), může nastat následující situace:

for (x <- xs) f(x)
for (x <- xs) g(x)
for (x <- xs) h(x)
-> 1. iterace ->
|---------------------------|-cache na konci iterace-|
-> 2. iterace ->
|---------------------------|-cache na konci iterace-|
-> 3. iterace ->
|---------------------------|-cache na konci iterace-|

Jak iteruji kolekcí, CPU načítá data z paměti do cache a postupně vyhazuje staré cache-line, na které dlouho nesáhlo, aby uvolnil místo novým objektům. Protože kolekcí jen prolétávám, na každý objekt sáhnu jen jednou a musím něco starého vyhodit. Když začnu další iteraci, objekty ze začátku kolekce jsou s největší pravděpodobností už dávno vyhozeny z cache a začnu tedy přistupovat ke studeným datům. V cache jsou jen data z konce předchozí iterace. Proto může dávat smysl iterovat ve střídavých směrech.

for (x <- xs)         f(x)
for (x <- xs.reverse) g(x)
for (x <- xs)         h(x)
-> 1. iterace ->
|---------------------------|-cache na konci iterace-|
                                      <- 2. iterace <-
|-cache na konci iterace-|---------------------------|
-> 3. iterace ->
|---------------------------|-cache na konci iterace-|

Začátek následující iterace využije obsah cache, který tam zůstal po minulém průchodu. Přístup do cache je rychlejší než čtení z RAM i v těch nejlepších případech, kdy jen streamuji souvislý bok paměti.

Tohle jsem momo jiné aplikoval na radix sort (první iterace, která jen sbírá statistiky, běží pozpátku) a když jsou data 2× větší než L3 cache, vede to ke ~10% zrychlení. V extrémně specifických situacích to může nakopnout výkon až o 50%, Když jsou však data mnohem větší než cache, efekt je zanedbatelný. Na druhou stranu je to jen malá změna, která neuškodí (hardwarový prefetch umí pracovat i pozpátku).

Když je všechno ostatní optimalizované na kost, tohle může v určitých případech přinést nějaké zrychlení. Ale jako v případě každé mikro-optimalizace je třeba měřit a profilovat.


Dále k tématu:

Flattr this!

Posted in Algo, CPU, low level | Leave a comment

Mikrobenchmarky jsou těžké

Na Twitteru jsem zaznamenal vtipnou etudu. Stalo se to už před nějakou dobou, ale tenhle článek mi nedokončený ležel na disku. Nicméně začalo to tímhle tweetem.

Podle všeho je v Javascriptu

if (obj !== undefined) { return obj.x }

v průměru o 15% rychlejší než stručné

if (obj) { return obj.x }

Je to proto, že ke kontrole proti undefined jsou potřeba jen 2 x86 instrukce (cmp a jz). Naproti tomu kontrola pravdivosti obnáší kontrolu jestli to není undefined, null, nula, prázdný string a nejspíš ještě něco dalšího.

To ale není zajímavé. Sranda začala v okamžiku kdy DHH napsal mikrobenchmark, který podle něj prokázal, že zrychlení není patrné. Velice rychle mu někdo začal důrazně vysvětlovat, že jeho benchmark je k ničemu a nic nedokazuje.

Zmíněný benchmark vypadal následovně. Já jen přidal třetí test nihilist-friendly.

const Benchmark = require('benchmark')
const suite = new Benchmark.Suite

let a = undefined

suite
  .add('human-friendly',    function () { if (a) true })
  .add('machine-friendly',  function () { if (a !== undefined) true })
  .add('nihilist-friendly', function () {})
  .on('complete', function () { console.log('Fastest is ' + this.filter('fastest').map('name')) })
  .on('cycle', function(event) { console.log(String(event.target)) })
  .run()

Výsledky jsou takovéto:

human-friendly    x 103,629,158 ops/sec ±0.79% (93 runs sampled)
machine-friendly  x 105,345,660 ops/sec ±1.00% (90 runs sampled)
nihilist-friendly x 110,587,292 ops/sec ±1.07% (92 runs sampled)

Z čísel je vidět, že benchmark benchmarkuje hlavně sám sebe a neměří nic užitečného. Rozdíl mezi noop funkcí a dvěma ostatními je jen minimální. To znamená, že se v nich něco děje, ale režie benchmarkovacího nástroje je veliká a všechno utopí.

Mikrobenchmarkování je zrádné, zvlášť v prostředí s agresivním JITem, jako jsou všechny Javovské nebo JS virtuální stroje stojící za pozornost. Jediným posláním JITu je optimalizovat a on je v tom zatraceně dobrý. Když si člověk nedá pozor, JIT může kompletně odstranit testovaný kód, protože ten například nemá žádné vedlejší efekty nebo nic nevrací. V testu můžu volat nějaké funkce, JIT je spekulativně inlinuje, zjistí, že kód je zbytečný, protože nedělá nic viditelného zvenčí a odstraní ho, tělo smyčky najednou můře být prázdné, tak ji také odstraní a takto může pokračovat dál, dokud kompletně nevyhlodá měřený kód a nezůstanou jen chapadla benchmarkovacího nástroje, který měří svou vlastní režii.

Když člověk chce měřit výkon takhle šíleně maličkého kusu kódu – jde doslova jen o hrstku instrukcí – musí si dávat zatraceně velký pozor a i přesto je třeba se podívat na dekompilovaný assembler, protože jinak si nikdy nemůže být jistý.

Pokud bych se cítil odvážně, mohl bych z oněch tří čísel vydedukovat, že cena noop funkce je 29 ns, cena rychlé funkce je 30.5 ns a pomalé 31.1 ns. Když odečtu těch 29 ns, je to 2.1 ns proti 1.5 ns, to je zrychlení o 30%, přesně podle výchozí teze. Ale jak říkám: Bůh ví, co se vlastně měří. Mikrobenchmarkování je zrádné a člověk nesmí mít slepou důvěru v použité nástroje a musí jim dobře rozumět, aby výsledná čísla byla k něčemu.


Dále k tématu:

Flattr this!

Posted in VM | Leave a comment