Escape analysis

Dneska jenom krátce: Nedávno jsem zakopl o paper popisující partial escape analysis a napadlo mě, že bych tu mohl napsat pár slov o tom, co je escape analysis vlastně zač (termín s dovolením nebudu překládat a vystačím si s kurzívovou metodou).

Escape analysis je optimalizační technika používaná v kompilátorech, JITech a virtuálních strojích k eliminaci určitých alokací, která povede ke zrychlení programu. Jde v podstatě o to, že pokud objekt neunikne z metody (odtud to escape), není ho třeba alokovat na haldě, ale postačí alokace na zásobníku. Když metoda skončí, její rámec je zahozen a s ním jsou automaticky dealokovány i všechny objekty na zásobníku. Díky tomu není třeba ztrácet čas alokací1, ulehčí se práce garbage collectoru a protože zásobník je skoro vždy horký v cache, je práce s ním velice rychlá. Kompilátor může jít ještě o krok dál a provést scalar replacement, kdy objekt není alokován ani na zásobníku, ale jeho členské proměnné skončí v registrech CPU.

Objekt/pole unikne pokud:

  • je návratovou hodnotou metody
  • je přiřazen do statické proměnné
  • je přiřazen do členské proměnné jiného objektu, který uniká
  • je předán jako argument metody (včetně implicitního argumentu this)

Jde o tranzitivní vlastnost. Kompilátor může alokovat na zásobníku jen pokud dokázal, že objekt za žádných okolností nemůže uniknout a z toho důvodu musí být konzervativní.

Jako v případě každé jiné optimalizace, je nutné k dobré funkci escape analysis inlinovat. Inlinování rozšíří kontext, na kterém JIT provádí analýzu a to vede k lepším výsledkům.

class X {
  // metoda `doSomething` vrací Int, neuniká z ní `this`
  // pointer a je dost malá na to, aby byla inlinována
  def doSomething(): Int = ???
}

def f(): Int = {
  // objekt `x` neuniká z metody a může být alokován
  // na zásobníku
  val x = new X
  x.doSomething()
}

Efekt inlinování je vidět na následujícím kusu kódu.

// objekt x uniká z této metody
def f(): X = new X

def g(): Int = {
  // pokud je metoda `f` inlinována, JIT zjistí, že
  // objekt x neuniká z metody `g` a tedy může být
  // alokován na zásobníku pokud však `f` není
  // inlinována, alokuje objekt, vrátí ho a `g` se
  // s ním musí vypořádat
  val x = f()
  x.doSomething()
}

Přímočará escape analysis uspěje jen když si je jistá, že objekt nemůže uniknout nehledě na řídící struktury, podmínky a cykly. Pokud se však kód metody větví a v jedné větvi smyčky nic neuniká, ale v jiné, která se provede jen zřídka, uniká, JIT to vzdá a prohlásí, že objekt uniká.

Triviální příklad:

def f(): X = {
  val x = new X

  if (x.doSomething() != 0) {
    // v téhle větvi `x` neuniká
    null
  } else {
    // v téhle ano
    x
  }
}

Tohle je právě téma na začátku zmíněného paperu popisující partial escape analysis v GraalVM, která si dokáže poradit s podmínkami a control flow. Kompilátor generuje kód, který provádí alokaci na haldě až na poslední chvíli, kdy je jasné, že osud objektu je zpečetěn a nemůže se stát nic jiného, než že unikne z metody. Ale než tento okamžik nastane, objekt žije na haldě nebo v registrech.

Výsledek může odpovídat tomuto pseudokódu:

def f(): X = {
  val x1, x2, x3 = scalarReplacedFieldsOfX

  if (x.doSomething() != 0) {
    // nic se nealokuje
    null
  } else {
    // tady proběhne alokace, objekt je
    // rematerializován na haldě
    val x = new X
    setFields(x, x1, x2, x3)
    s
  }
}

V určitých benchmarcích použití partial escape analysis vede k redukci alokací o 58% a zrychlení programu o 33%.

Zmíněný GraalVM je projekt poskytující API, kterým je možné řídit chování JVM JITu. S touto kontrolou nad kompilátorem je možné na JVM jednoduše naroubovat podporu jazyků, které se chovají jinak než Java a které tedy standardní JIT nekompiluje ideálním způsobem. S GraalVM není třeba při implementaci nového jazyka začínat od nuly, protože má k dispozici všechny prostředky JVM jako je GC a efektivní JIT, který dokáže kód optimalizovat a (hlavně) deoptimalizovat.

O JRuby backendu založeném na Truffle a GraalVM píše Chris Seaton na svém blogu. Jeden z nejzajímavějších článků je ten, kde popisuje, jak překonali MRI Ruby s rozšířeními napsanými v céčku tím, že interpretovali C kód spolu Ruby kódem pomocí GraalVM.

Další přístup k eliminaci alokací je escape detection (letmo zmíněná Cliff Clickem), kterou používal Azul na jejich JVM běžící na jejich hardware.

Escape detection je optimistický přístup – všechny objekty jsou alokovány na zásobníku s tím, že hardware detekuje, jestli neunikl pointer na zásobník. Když unikl, procesor vyvolá výjimku, jejíž handler přesune objekt na haldu a přepíše pointer. Tento postup údajně vede k velice efektivní redukci alokací, protože je agresivní, nemusí mít 100% důkaz a sám o sobě dělá to, co partial escape analysis.


Dále k tématu:

Poznámky:

  1. Za alokaci se platí dvakrát v propustnosti paměti. Poprvé, když vytvářím objekt, musím jeho blok paměti načíst z RAM do cache, vynulovat (aspoň v případě JVM), přepsat užitečnými daty. Podruhé, když už není třeba, je vyhozen z cache a musí být zapsán zpátky do RAM na místo, kam patří na haldě. Tohle zabolí zvláště v případě objektů, které žijí jen deset nanosekund – po velice krátké době k nim už nikdy nepřistoupím, ale stále je třeba dodržet cache coherence protokol a zapsat je zpátky do RAM. I když propustnost pamětí je typicky velká, není nekonečná a obrovské tempo alokací na mnohajádrovém procesoru může trubky pořádně přiškrtit. Proto je alokace na zásobníku tak efektivní – opakovaně používá stejný blok paměti který je stále v cache a do RAM skoro vůbec nepřistupuje.

Flattr this!

Posted in Algo, JVM, VM | 4 Comments

Jak rychle řadit a šetřit čas

Když už tu mluvímřazení a řadící mašinerii, tak bych taky mohl stručně a srozumitelně shrnout co, jak a proč dělat a čemu se vyhnout.

Asi takhle: Obecné řadící algoritmy jako quicksort, mergesort nebo heapsort jsou super. Sami o sobě nejsou nejrychlejší, ale nejlepší hlavy strávily posledních padesát let jejich optimalizací a zlepšováním a proto dá se na ně spolehnout a výkonem nikoho nezahanbí.

Výsledkem oněch pěti dekád je například rafinovaný three-way quicksort, který je odolný proti zákeřným vstupům4 nebo celá paleta hybridů jako je stabilní Timsort (který se snaží využít seřazené běhy dat, které se přirozeně vyskytují ve vstupní kolekci, začíná práci insertion sortem a pak nastartuje merge sort) nebo nestabilní1 introsort (začne rychlým quicksortem, který v patologických případech přepadne do heapsortu a krátké sekvence řadí insertion sortem, který je sice asymptoticky pomalý, ale pro malé n je rychlejší než chytré algoritmy).

Samostatný k-ary heapsort také může být efektivní a rychlostí může konkurovat quicksortu, pokud je porovnání levné (třeba prosté porovnání intů) a přístup do paměti relativně drahý.


Pokud ale řadím krátké stringy pevné délky (jako třeba 32/64bit inty nebo floaty) a mám k dispozici velkou propustnost paměti least significant digit (LSD) radix sort je neporazitelný.

Klasická implementace řadící osm bitů v jedné iteraci potřebuje 5 iterací pro 32bit klíče (první spočítá frekvence jednotlivých bajtů, po které následují čtyři řadící iterace) a musí přenést všechna data třináctkrát (čtyři průchody potřebují data načíst a pak je zapsat na jiné místo, zapisování nejdřív natáhne z RAM stará data do cache, tam je přepíše a pak je později zapíše zpátky do RAM)2.

LSD radix sort data vždycky streamuje, vůbec nevyužívá cache a za všechno platí propustností pamětí. Quicksort nebo most significant digit (MSD) radix sort rekurzivně dělí vstup na menší a menší sekvence. Ty se eventuálně vejdou do cache a od toho okamžiku jsou všechny iterace limitované propustností cache, která bývá mnohem větší než propustnost RAM a je lokální každému jádru. Pokud je propustnosti málo, je možné nejdřív udělat quicksort, MSD radix sort nebo jinou diskriminaci do částí, které se vejdou do nějaké úrovně cache a na nich rozjet rychlý LSD radix sort. Vznikne tak několikaúrovňový hybrid, na který se dá narazit v literatuře.


Když mě zajímá řazení dlouhých stringů potenciálně proměnné délky, na současných cache CPU architekturách je nejefektivnějším algoritmem burstsort. Ten je založený na předpokladu, že největší dopad na rychlost řazení mají opakované cache-miss, kdy data nejsou připravena v cache, ale musí se pro ně do RAM. Quicksort nebo jiný diskriminační algoritmus musí na každé úrovni iterace projít všechny položky a pokud jich je hodně3, přístup ke každé z nich vyvolá jeden pomalý cache-miss5. A protože se dělá O(log n) iterací, bude třeba i tolik pomalých cache-miss na každý element vstupní sekvence. Jak rekurze postupuje, eventuálně se všechny položky jedné subsekvence vejdou do cache a od té doby jsou iterace rychlé a bez cache-miss. Pokud jsou elementy velké, náhodně rozhozené nebo kompozitní, tak každý z nich může zabrat několik cache-line a využití cache pak není nijak efektivní. Burstsort se snaží snížit počet cache-miss a zrychlit tak řazení. Nepracuje rekurzivně, jen jednou projede vstupní data a na základě prefixu stringového klíče je přidá do částečné trie. Nesnaží se umístit element na pozici určené plnou cestu, ale jen její částí, která vede k listu trie obsahujícímu kolekci neseřazených položek sdílejících daný prefix. Když algo dorazí k listu, vloží do něj nový element, v případě potřeby zvětší list, a když přesáhne určitou mez, kolekce v listu praskne (odtud burst) a vytvoří se další úroveň trie. V jedné iteraci je tedy vytvořena trie, kterou pak projdu v in-order pořadí, jiným algoritmem řadím kolekce, na které narazím, a získám tak seřazený výsledek. V ideálním případě jsou potřeba jen 2 cache-miss na položku: Jeden při vkládání do trie a jeden při závěrečném řazení9. Oproti diskriminačním algoritmům má burstsort tu výhodu, že se do cache nemusí vejít kolekce elementů, ale jen mnohem kompaktnější kostra trie stromu. Ta neobsahuje žádná data samotných elementů a navíc potřebuje jen jeden a něco pointer na každou neseřazenou kolekci v listu, která může obsahovat něco mezi 100 a 1000 elementy.

Javovská verze7 burstsortu používající Timsort (kterou jsem opilý napsal ve tři ráno a zkompiloval jsem ji až druhý den) je 2.5–3× rychlejší než Timsort ze standardní knihovny Javy. Je stejně rychlá jako three-way radix quicksort* z má zahrádky (který se výborně hodí pro řazení stringů se společným prefixem). Hybrid burstsort + *three-way radix quicksort je v mých testech 3–4× rychlejší než samotný Timsort. To podle mě není vůbec špatný výsledek pár hodin programování.

Dva dny po přednášce mě napadl způsob, jak vylepšit burstsort pomocí schwartzian transform a v ideálním případě snížit počet cache-miss na polovinu. O tom se však rozepíšu až někdy příště.


Pro problémy, kdy je počet možných hodnot srovnatelný nebo menší než velikost vstupní kolekce, dá se řadit v lineárním čase pomocí counting sortu nebo pigeonhole sortu. A když dopředu znám rozložení vstupních dat, můžu řadit v očekávaném lineárním čase pomocí bucket sortu nebo proxmap sortu.

Ale to není všechno. Co když chci řadit líně? Heap sort je klasická volba, ale líně se dá řadit i pomocí quicksortu, radix sortu nebo quicksortu reifikovaného do podoby stromu (na tohle jsem nikde v literatuře nenarazil a tak jsem to skromně pojmenoval YOLO tree, relevantní informace v Implementing sets efficiently in a functional language).

Když mě zajímají percentily, klasickou cestou je quickselect. Ten se dá také naroubovat na radixsort nebo jiný diskriminační algoritmus. *Median of medians* zaručí lineární čas, ale konstantní faktory nejsou nijak příznivé.6 Po­dobného výsledku se dá dosáhnout adaptací merge sortu a trochu pravděpodobnostní magie. Tento algoritmus jsem také nikde nenašel a proto jsem mu promptně dal dočasné jméno mergeselect. Pokusím se o něm v budoucnu něco napsat.

A co paralelní řazení? Quicksort se dá triviálně paralelizovat pomocí součtů prefixu (prefix sum) jak je popsáno v Programming on Parallel Machines, stejně tak radix sorty nebo merge sort. Určité verze Radixsortu můžou být nejen paralelní, ale také in-place.

If a thing like this is worth doing at all, it’s worth doing right

Klasický přístup k řazení quicksort and chill funguje, rychlost nikoho neurazí a většinou připraven k okamžitému použití ve standardních knihovnách většiny jazyků. Tohle funguje, ale vždycky se spokjit jen s tím, co pouze funguje, může být rychlé a pohodlné řešení, ale jen stěží je intelektuálně uspokojivé. Pokud na něčem záleží, mohli bychom se poohlédnou po způsobech, jak to udělat co nejlépe.

Já v současné době přemýšlím, jak vzít Hengleinovy nápady, z kombinátorů popisujících řazení makry vygenerovat kompaktní a efektivní kód, který nealokuje dočasné datové struktury, a zapojit to do vylepšeného burstsortu. Výsledkem by mohla být knihovna, která je nejen generická, ale také rychlejší než všechno ostatní. To je podle mě plán dostatečně odvážný na to, aby se do něj někdo pustil.


Dále k tématu:


Pozn:

  1. Z každého nestabilního sortu se dá snadno udělat stabilní, když se neřadí podle klíče, ale podle dvojice [klíč, pořadové číslo elementu].
  2. Situace se dá v tomto případě vylepšit použitím tzv. non-temporal store instrukcí, které nezpůsobí natažení cache-line do cache, ale rovnou data zapíšou do RAM. Non-temporal instrukce jsou výhodné, když vím, že data po zápisu nebudu dlouho potřebovat a nechci jimi špinit cache a tahat je do věcí cache coherence protokolu.
  3. A jsou to pointery na dynamicky alokované objekty a ne pole structů, se kterými pomůže prefetcher, viz Intel optimization manual, který poskytuje představu o tom, co prefetch dokáže.
  4. Problematický vstup je například sestupně nebo vzestupně seřazená sekvence. Klasický Hoarův quicksort, který jako pivot vybírá první element si na ní vyláme zuby. Změnou volby pivotu na best-of-3, quasi-best-of-9 nebo náhodný výběr se tento patologický případ dá eliminovat. Ale změna pivotu nepomůže se vstupem obsahujícím všechny stejné hodnoty. Na ty je třeba pozměnit algoritmus, aby dělil položky do tří skupin: menší než pivot, rovné pivotu a menší než pivot. S touto změnou quicksort pole identických položek trvá lineární čas místo katastrofického kvadratického času.
  5. Moderní OOO hardware dokáže spekulovat dopředu a zatímco čeká na data z RAM, spekulativně vykoná kód následujících iterací, které můžou obsahovat další load instrukce, které skončí jako cache-miss. Takto může například načítat čtyři věci najednou a efektivně taz zredukovat latenci na čtvrtinu. I když je to značné zrychlení, může to být až 100× pomalejší než sekvenční čtení z paměti nebo přístup do cache. (viz MLP)
  6. Když jsem připravoval výše zmíněnou přednášku, na mysl se mi stále vracela slova z knihy/filmu No Country For Old Men, která řekl Anton Chigurh lovci odměn Carsonovi chvíli před tím, než ho zabil: „If the rule you followed brought you to this, of what use was the rule?“ K čemu jsou nám záruky dobré asymptotické komplexity, když výsledek bude pomalý. Stejně tak není žádná hanba použít teoreticky neefektivní algo, který je ale v praxi na reálných datech rychlý.
  7. Někteří jistě budou namítat, že JVM je špatná volba pro kód, pro který je kritický výkon. Těm lidem vzkazuji, aby si šli hrát na pískoviště. JVM má jen problém v tom, že není možné ovlivnit rozložení paměti – buď mám objekty nebo pole primitivních typů/referencí a to je všechno. To člověku svazuje ruce v návrhu datových struktur, protože nemůže požít například objekt, který má na konci inlinované pole nebo struct tam, kde by se přirozeně hodily. Například burstsort řazení Java string objektů je o 50% pomalejší než řazení nahých polí charů/bajtů, protože string objekt obsahuje pointer na pole znaků, který je třeba dereferencovat, což vede k datovým závislostem a (potenciálně8) dalším zbytečným cache-miss. Kdyby string objekt obsahoval pole znaků na konci, bylo by to mnohem lepší.
  8. Tady situaci značně komplikuje fakt, že JVM je dynamické prostředí s garbage collectorem, který přesouvá data z místa na místo a může (ale tady nemusí) data, která jsou použita spolu (např. obsahují datově závislé pointery), skončí vedle sebe. Někdy se může stát, že výsledek benchmarku bude záviset jestli proběhl GC, v jakém momentu proběhl a v jakém pořadí zpracovává kořenové reference. Když je kód velice těsný a jde o nanosekundy, takováto šaráda může mít dopad v řádech desítek procent.
  9. Toto platí pokud se celý obsah listu vejde do cache, což není problém, když listy mají maxilální velikost v rozmezí od 1k do 8k. Dále bude pár cache-miss potřeba během praskání listů, ale to se děje jen zřídka. Když se kostra stromu nevejde do cache, budou třeba další cache miss. Naštěstí se burst trie široce větví (v literatuře se uvádí praktická hodnota 256) a proto, když se do cache vejde burst trie např. pro 1M položek, jeden extra cache-miss je třeba pro vstupní kolekci do 256M položek.

Flattr this!

Posted in Algo, CPU, Paměť, řazení, Uncategorized | Leave a comment

Čím více se věci mění, tím více zůstávají stejné

Evgeny Morozov v knize To Save Everything Click Here mluvil o epochalismu a ahistorickém myšlení. Epochalismus říká, že žijeme ve výjimečných časech a současná doba je diametrálně odlišná od všech minulých a nic staré už neplatí. Ahistorické myšlení s epochalismem velice úzce souvisí – v podstatě jde o systematické ignorování historie a všeho, co jsme se z ní mohli naučit.

Přestože Morozov psal o „Internetu“ a digitální debatě obecně, stejný trend lze vycítit v IT komunitě. Zdá se, že dominantní myšlenkový proud tvrdí, že se všechno neustále mění a vyvíjí, že co jsme se naučili včera bude zítra zastaralé, že co jsme věděli přestane platit a všechno se musí co nevidět od základů změnit. Cynik by ukázal na seznam Javascriptovch frameworků a namítl, že nic jako pokrok neexistuje a že jen opakujeme stejné chyby a občasný skok vpřed nastane, když znovuobjevíme zapadlou akademickou práci ze sedmdesátých let.

Já tak daleko nechci zajít, protože popírat samotnou myšlenku pokroku je šílené. Zdá se však, že iluze totální disrupce je v oboru, o kterém by cynik prohlásil, že je poháněn vpřed výhradně nesmysly, marketingem a popíráním minulosti, nevyhnutelná.

S tímhle na mysli jsem se začal zajímat, kdy a kde byly vynalezeny všechny techniky organizace a architektury používané v současných procesorech. Kdyby ahistorická hypotéza platila, všechno na čem jsou soudobá CPU postavená, se diametrálně liší od všeho minulého a jde jen o dočasnou bublinu, která co nevidět splaskne. Pokud je to pravda, nemá valný smysl současný hardware sledovat.


Všechno začalo dvěma systémy: ILLIAC II (1962) a IBM Stretch (1956–1961), jejichž tvůrci přišli s naprostou většinu architekturálních technik a způsobů organizace procesorů.

Tyto dva stroje uvedly cache, instrukční pipeline, multitasking, virtuální paměť, ochranu paměti, osmibitový bajt, prefetch a prokládání paměti (který je bohatě používán např. v GPU).

Po těchto naprosto zásadních strojích následoval systém CDC 6600 (1965) a výzkumný projekt IBM ACS-1 (později přejmenovaný na ACS-360, 1961–1969). Ty uvedly všechno ostatní. Jmenovitě: dekódování a vykonání několika instrukcí v jednom taktu (superskalární CPU), branch target buffer, multithreading implementovaný v hardware, out-of-order execution, přejmenovávání registrů, predication.

Současné procesory obsahují tohle všechno a nic víc. Poslední generace hardware jsou jen sny designérů šedesátých let dovedené k dokonalosti.

Je však třeba dodat, že i když byla nějaká technika přivedena k životu před padesáti lety, neznamená to, že byla celou dobu aktivně využívána. Velká část postupů byla na dlouhá léta opuštěna, protože se dařilo výkon dostatečně zvyšovat prostým nárůstem frekvence. Nebylo třeba dělat nic chytrého, stačilo se nechat unášet vlnami Moorova zákonu a stále pokročilejší litografií. Až s postupem času (ale stále dlouho před zastavením růstu frekvence1) začali návrháři čipů využívat rostoucí množství tranzistorů k agresivním implementacím chytrých a pokročilých technik.

Ve zbývajících odstavcích projdu jednotlivé architektonické vzory a jejich stručnou historii.

Instrukční pipeline

Instrukční pipeline byla použita už ve strojích ILLIAC II a IBM Stretch. První nasazení je však o mnoho let starší a sahá až k mechanickým a elektromechanickým počítačům Z1 (1939) a Z3 (1941). Pipeline poté začala být používána v superpočítačích sedmdesátých let a je spjata s přechodem od jedntaktových instrukcí k mnohataktovým instrukcím.

Cache

Už ILLIAC II měl rychlou a pomalou paměť. Pomalá paměť měla přístupovou dobu 2 µs, rychlá, které by se dnes říkalo cache, 0.25 µs.

Rozdíl mezi rychlostí procesorů a pamětí začal narůstat v osmdesátých letech. Paměť, která byla předtím dostupná v jednom taktu, přestávala stíhat CPU a čtení a zapis začal trvat víc jak jeden takt.

První cache byly TLB, které se objevily krátce po příchodu virtuální paměti ve strojích GE 645 (1968) a IBM 360/67 (1967).

Datová cache jako taková se poprvé objevila ve stroji IBM S/360 M85 v roce 1968.

Dedikovaná instrukční cache měla premiéru v Motorole 68010 (1982), do které byl přidán „loop mode“ pro 2 instrukce těsné smyčky. Pozdější Motorola 68020 (1984) přidala 256 bajtovou I-cache, Motorola 68030 (1987) přidala stejně velkou D-cache. První x86 procesor s instrukční cache bylo dvacetimegahertzové 386 (1987).

Superskalární CPU

Už CDC 6600 z roku 1965 byl superskalární stroj. Prvními komerčními jednočipovými superskalárními procesory byly až Motorola MC88100 (1988), Intel i960 (1989) a AMD 29000 (1990, viz). Pentium se v roce 1993 stalo prvním superskalárním x86 procesorem. Více méně všechny procesory vyrobené přibližně po roce 1998 jsou superskalární.

Nx586, Pentium Pro a AMD K5 byly první x86 superskalární procesory, které překládaly složité CISC instrukce na jednodušší RISC operace, kterých pak mohly vykonat víc najednou.

Out-of-order

Prvním OOO strojem byl CDC 6600 z roku 1965. Avšak podle dnešních standardů nešlo o plnohodnotné OOO, protože používal scoreboarding, který dovoloval pouze dokončení (retire) instrukcí out-of-order, začínat musely stále v pořadí programu. To umožňovalo začít rychlé a pomalé operace najednou s tím, že ty pomalé nevytvořily bublinu v pipeline, ale hardware je prováděl souběžně a potom přerovnal jejich výsledky tak, aby odpovídaly sekvenčnímu programu.

Skutečný OOO stroj uvedl až big blue a byl jím IBM 390/91 z roku 1966 implementující Tomasulo algoritmus, který sleduje závislosti mezi instrukcemi a dynamicky je plánuje mimo pořadí. Ale i tady to mělo jeden háček: OOO logika byla použita jen pro floating point část procesoru. To bylo nejspíš proto, že FP operace byly drahé a FP logika zabírala velkou část čipu a bylo třeba zařídit, aby byla za každou cenu efektivně využita.

Pak se třicet let nic nedělo a prvním moderním OOO mikroprocesorem se stal až POWER1 (1990), který také OOO aplikoval jen na floating point operace. O tři roky později IBM uvedl PowerPC (1993), který už uměl plné OOO. To rozpoutalo bouři a mnoho architektur začalo přecházet: Sparc (1995), Pentium Pro (1995), R10000 od MIPS/SGI (1996) PA-RISCový PA-8000 od HP (1996), AMD K5 (1996) a nakonec Alpha (1998).

Branch prediction

Už IBM Stretch měl jednoduchý statický branch predictor, který vždycky předpokládal, že podmíněný skok nebude použit a kód propadne (predict untaken)2. Po tomto experimentu IBM nepoužívala branch predictor ve velkých systémech až do roku 1985. Pravděpodobně to nebylo třeba, protože cena špatného odhadu byla s krátkou pipeline malá nebo byly k dispozici predikované instrukce, případě delay sloty

Branch prediction se objevuje v systémech jiných společností: Burroughs B4900 (1982) nebo VAX 9000 (1989). První komerční RISCy (1986) po vzoru Stretche a měly statický prediktor predict untaken. Branch prediktor začal být velice důležitý po roce 1993 pro superskalární procesory s hlubokou pipeline, kde cena špatného rozhodnutí začínala narůstat. Pentium, Alpha 21064, R8000 a POWER také začaly nasazovat branch predictior.

Multicore

Překvapivé je, že i několikajádrové procesory nejsou tak nové, jak by se zdálo. První kousek vyrobil v polovině osmdesátých let Rockwell, když zkombinoval dva 6502 čipy do jednoho pouzdra. Po roce 2000 se staly mnohojádrové procesory běžnými artikly.

SMT/HyperThreading

Hardwarový multi-threading (SMT) byl poprvé implementován v prototypu ACS-360 (1968), který nebyl nikdy dokončen.

Procesor Alpha 21464 (ohlášený 1999, plánovaný na 2003, nakonec zrušen), měl být prvním SMT mikroprocesorem, měl zvládat 8-wide issue (8 instrukcí v jednom taktu) a 4 souběžná vlákna v každém jádře. Pentium 4 (2002) se stalo prvním moderním desktopovým CPU s podporou SMT. SMT v podání Intelu (překřtěné na HyperThreading) zvládá jen dvě vlákna na jednom jádře. Další na řadě byl POWER5 (2004) od IBM.

SIMD

Vývoj vektorových procesorů, které spadají do kategorie SIMD, začal v šedesátých letech (např. ILLIAC IV). Konkrétní stroje se začaly objevovat v letech sedmdesátých a šlo především o různé architektury Cray (viz).


Jak je vidět, všechny techniky organizace a architektury procesorů jsou velice staré. Naprostá většina zažila debut na přelomu padesátých a šedesátých let. Cynik by mohl namítat, že se v tomto oboru od osmdesátých let nestalo nic skutečně nového a nebyl by daleko od pravdy. Dalo by se říct, že v procesorech je za posledních padesát let to samé, jen je tam toho víc.6 Protože jsou tyto principy s námi od samého počátku, dá se předpokládat, že na nich něco bude a budou mít určitou univerzální platnost. Jinými slovy: když budeme optimalizovat pro současný hardware, neznamená to nutně, že podléháme diktátu podivností poslední várky křemíku z továren Intelu, ale široké množině procesorů, které mají velkou cache, hlubokou pipeline, chytrý branch predictor, agresivní OOO engine a neuvěřitelně pomalou DRAM. Do této kategorie spadá skoro všechno od největších serverových bestií až po mobilní procesory. Ona poslední generace mobilních procesorů se skoro vůbec neliší od těch desktopových a třeba papírová specifikace Apple Cyclone se až nepříjemně podobá číslům Haswellu.3

Některé z těchto principů nejsou jen výsledky snah hardwarových designérů napravit hříchy našich otců4, ale důsledky fyzikálních principů. Cache je například důsledkem toho, že v prostoru může být jen omezené množství věcí blízko procesoru (rychlá cache) a obrovské množství daleko (pomalá DRAM). Datová závislost je potom manifestací kauzality, kdy pointer neukazuje jen na místo v paměti, ale zároveň udává pořadí operací.

What's the score here? What's next?

Co by se muselo změnit, aby staré pořádky přestaly platit?

Na paměti s malou latencí nejspíš můžeme zapomenout. Tahle bitva je už dávno prohraná. Místo toho se můžeme dočkat strojů s velikou paměťovou propustností. Každý jeden přenos zabere dlouhou dobu, ale hardware jich může provádět hodně najednou, podobně jako to dělají grafické karty nebo ThreadStorm architektura. Tenhle datově paralelní model funguje nejlépe, když jsou operace relativně přímočaré a vzájemně nezávislé. To ale není pravda o obecném kódu, který je plný podmíněných skoků, polymorfismu a často vyžaduje jemnou synchronizaci a koordinaci. GPU mají problém s podmíněnými skoky, alokacemi a rekurzí, tedy s tím, čeho je general purpose kód plný. Realita bude tedy nejspíš taková, že obecné procesory budou mít u sebe paměť s velkou propustností, ale jednotlivá jádra budou celkem obyčejná jádra podobná těm, jaké máme v současnosti, jen možná o něco jednodušší, možná s širším SMT nebo hardwarovým přepínáním vláken.

Pokrok můžou přinést levné nevolatilní paměti (NVRAM), které fungují jako RAM, ale data přežijí výpadek napájení a restart systému (jako 3D XPoint od Micronu/Intelu nebo memristorová paměť od HP5). Mnoho lidí je z nich nadšených, protože NVRAM můžou změnit úplně všechno (co se týká RAM). Na druhou stranu také nemusí změnit vůbec nic. To, že data přežijí pád sytému, znamená také, že porušená data přežijí restart a chyby můžou přetrvat. Někdo může jásat nad tím, že nebude třeba dělat nic speciálního pro uložení souboru, protože data jsou v paměti a paměť je persistentní. Pokud tohle přijmu, musím uvažovat, co se stane, když systém spadne v průběhu jedné operace. Najednou můžou být data zapsána částečně a kdo ví, co to bude dělat, až systém znovu naběhne. V tomto případě je třeba mít transakční protokol úplně všude a ne jen v místech, které se starají o ukládání dat. Z tohoto důvodu možná nějaká paměť nebude tolik persistentní jako jiná. Když přihlédnu k prezentovaným číslům, která naznačují, že NVRAM může být rychlá asi jako DRAM, ale přesto o něco pomalejší, některé systémy budou mít na palubě jak NVRAM tak i DRAM. Nakonec to nemusí být technologie, která nás všechny spasí, ale jen jeden druh z celého spektra pamětí: páska, HDD, SDD, NVRAM, DRAM, SRAM.

Když zajdu do jiného oboru a podívám se na řadící algoritmy je situace až nepříjemně podobná: Všichni stále používáme quicksort, na který v roce 1959 přišel Tony Hoare (publikováno v roce 1961 jako Algorithm 64: Quicksort), merge sort, jehož autorem byl sám John von Neumann (1945), nebo Radix sort, jehož kořeny sahají až do roku 1897. Kromě nich nepoužíváme skoro nic jiného. To ale neznamená, že se nic neděje. Všechny zmíněná algoritmy jsou postupně vylepšovány, vylaďovány a přizpůsobovány hardwarové realitě doby, jako využití SIMD bitonických sítí pro merge sort, skosený quicksort nebo různá schémata paralelizace všech sortů. Ale pořád platí, že znalost základních verzí těchto algoritmů nikdy nezastarala.

Naproti tomu svět databází se otřásá v základech. Tedy to tak aspoň vypadá na první pohled. Současné RDMS v některých případech přestávají stačit požadavkům na ně kladeným a proto se začaly ozývat hlasy k zapovězení relačních databází a přechodu na něco drasticky jiného a lepšího. Dokonce i Stonebraker tvrdí, že doba jedné databáze pro všechno je u konce a je efektivnější přejít na in-memory databázi na OLTP, sloupcovou na OLTP a něco jako Hadoop/Spark na ostatní věci. V tomto kontextu není těžké pochopit hlasy, které tvrdí, že relační databáze jsou zastaralé a morálně špatné. To ale nic nemění na tom, že byly více než dostačující posledních 40 let, od doby, kdy Codd publikoval seminální paper o relační algebře. Navíc techniky použité pod kapotou se příliš neliší mezi (některými) relačními dinosaury a (některými) moderními key-value NoSQL datastory. Konec konců chci někam uložit hromadu bitů a chci ji taky dostat rychle zpátky.

V dlouhodobém měřítku všechno jednou zastará a jediné, co můžeme chtít, je pár let jízdy plnou rychlostí, než to strhneme do škarpy a zmizíme v explozi slávy. Proto ale nemá smysl tvrdit, že dočasná znalost nemá žádnou hodnotu. Jestliže to, co se dneska naučíme o hardware, bude platit následující dekádu, bude to víc než bychom si mohli přát. Onen pomyslný cynik by jistě ukázal na hořící hromadu Javascriptových frameworků a dodal by, že je to víc než bychom si zasloužili.


Dále k tématu:

Pozn:

  1. viz známý článek The Free Lunch Is Over.
  2. Z toho se dá usoudit, že předpokládal, že smyčky budou začínat skokem ven a na konci bude nepodmíněný skok na začátek smyčky. Kdyby předpokládal opak (predict taken), znamenalo by to, že smyčce bude končit podmíněným skokem na začátek.
  3. O tom také svědčí fakt, že mnoho firem plánuje uvést vlastní ARM serverové čipy. Jsou to třeba AMD, Qualcomm, Tilera, EZchip, Cavium, Aplied Micro nebo Broadcom.
  4. viz bizarní kódování x86, které vede k masivním CISC → RICS dekodérům, L0 cache, LSB a dalším snahám jak rozlámat instruction stream a nakrmit hladové funkční jednotky.
  5. Pro úplnost se sluší dodat, že NVRAM je dostupná už teď, jen není vůbec levná (MRAM, FRAM). Příslib NVRAM je v tom, že bude jak nevolatilní, tak i velká.
  6. Podle přednášky The Chip Design Game at the End of Moore's Law se mezi roky 1980 a 2010 zvýšil takt procesorů 3500× a změny v architektuře a mikro-architektuře mohly přidat další padesátinásobné zvýšení rychlosti. Z toho plyne, že se skutečně něco děje a všechny ty staré principy se skutečně vylepšují a vylaďují k dokonalosti.

Flattr this!

Posted in CPU, DB | Leave a comment

How to sort out your life in O(n) time

slides

Flattr this!

Posted in řazení, Uncategorized | Leave a comment

Jak řadit v lineárním čase, křísit mrtvé a dosáhnout osvícení

Když se řekne řazení, většina lidí, kteří napsali víc než jednu smyčku a dva ify se zeptá: „A je to nutné?“ Řazení nemá pověst nejrychlejší operace pod sluncem a je preferováno, když se tomu dá vyhnout např. hashováním. Někdy je to ale nutné a v tom případ je třeba zatnout zuby a připravit se na nějaký ten rozpálený křemík.

Jedinci, kterým na zdi visí portrét Donalda Knutha si okamžitě vybaví, že řazení má v nejlepším případě časovou složitost O(n log(n)) a vzpomenou si na všechny ty quicksorty, merge sorty, heap sorty a různé monstrózní hybridy.

Pravda je ale o něco komplikovanější: Řadící algoritmy založené na porovnání potřebují provést řádově n * log(n) porovnání. Existují však i jiné způsoby řazení, které jsou založené na frekvenci, rozložení a histogramech, a ty nepotřebují porovnávat nic s ničím. Stačí jim lineární čas, a co víc: Jsou zatraceně rychlé.

Jedním z nejjednodušších je counting sort, který funguje tak, že vstupní pole jednou projdu, zaznamenávám kolikrát jsem na který element narazil a na konci položky vyplivnu ve požadovaném pořadí.

Může to vypadat například takhle (psáno v jazyce fast-and-loose Scala):

def countingSort(arrayToBeSorted: Array[Int]): Array[Int] = {
  val buckets = new ArrayBuffer[Int]()

  for (el <- arrayToBeSorted) {
    buckets(el) += 1 // increment counter
  }

  val result = new ArrayBuffer[Int]()

  for {
    i <- 0 until buckets.size // element
    _ <- 0 until buckets(i)   // count
  } result += i // append element

  result.toArray
}

Bystří si jistě už všimli, že slibovaná lineární složitost má pár nedostatků. Jak je vidět, je třeba mít po ruce pole, které je velké jako největší element ve vstupní kolekci. Co se stane, když bych se pokusil seřadit čísla 1 a 1844674407370­9551616? Musel bych přikoupit hodně paměti.

Counting sort má lineární časovou složitost, ale potřebuje prostor přímo úměrný rozpětí možných hodnot. To je ideální, když řadím například pole bajtů, ale v ostatních případech to má k ideálu velice daleko.

Řešením je radix sort. Ten funguje velice podobně, ale k řazení nepoužívá celou hodnotu najednou (tj. všechny dostupné bity), ale vždy jen její část. Tak například, když bych chtěl seřadit pole čtyřbajtových intů, radix sort může v první iteraci data rozdělit podle nejdůležitějšího bajtu. Vznikne tak 256 skupin (partition), kdy každá z nich obsahuje jen elementy shodující se v nejvyšším bajtu. V další iteraci provedu stejný krok pro každou skupinu zvlášť s druhým nejdůležitějším bajtem. Vznikne tak 256×256 podskupin, z nichž každá sdílí horních 16 bitů. Když udělám 4 rekurzivní iterace a spojím vzniklé podoblasti, dostanu seřazenou sekvenci. Stačí mi k tomu jen 4 iterace vstupním polem a pokud se nepletu, 4 lze považovat za konstantu.

Časová složitost radix sortu je O(kn), kde n je délka vstupu a k je velikost jedné položky. Když řadím pole primitivních typů nebo malých structů, k je malé a všechno běží velice rychle. Když se však rozhodnu radixovat dlouhé stringy nebo velké a komplikované (nedej bože nekonečné) objekty, k začne dominovat a situace je o poznaní méně růžová. Zvlášť s přihlédnutím k faktu, že log2(232), což je maximální rozsah 32 bitového intu, je jen 32, k tedy nemá moc místa pro manévrování. Stačí když radixovaný objekt trochu nakyne a najednou n log(n) představuje správnou cestu vpřed.


Majíce tohle všechno na paměti jsem napsal vlastní implementaci radix sortu ve Scale, abych na vlastní oči viděl jak rychlé je rychlé řazení. Můj kód je založený na moudrosti tohoto článku a jde o LSD radix sort. Neřadí tedy od nejvýznamnějšího bajtu, ale od toho nejméně významného. To se může zdát neintuitivní, ale funguje to, protože radix sort je stabilní algoritmus – více detailů ve zmiňovaném článku. Pro čtyřbajtové inty potřebuje provést 5 iterací nad daty – v jedné spočítá histogram frekvencí jednotlivých bajtů a ve čtyřech zbývajících přesouvá položky podle histogramů.

To však není jediný způsob. Existuje spousta dalších odrůd radix sortu: je možné řadit od nejdůležitějších bitů, od těch nejméně důležitých, může být in-place, může potřebovat extra O(n) místa, může být hybridní (použije se jiný algoritmus, když je jasné, že se nevyplatí radixovat), může být paralelní, může brát v potaz cache, může používat software managed buffers, atd. atd.

Výsledek? Jak řekl klasik: ho-ly-shit. Přesvědčte se sami:

Graf ukazuje rychlost řazení polí obsahujících náhodné inty mým radix sortem a funkcí java.util.Arra­ys.sort, což je hybrid mezi dual-pivot quicksortem, mergesortem a insertion sortem. Jak je vidět, radix sort běží v lineárním čase a navíc je velice rychlý. A to jde o neaktuální graf, který měří rychlost verze bez několika optimalizací3, a navíc do průměru započítává i počáteční pomalé běhy, kdy JVM nebyla zahřátá. Malé zpomalení s rostoucí velikostí dat není způsobeno asymptotami algoritmu, ale hardwarovými efekty. Všechny operace jsou rychlé, čtení je vždycky sekvenční, zápis je skoro sekvenční do 256 míst v paměti, které se pohodlně vejdou do cache5, neobsahuje žádné nepředvídatelné skoky, které by vedly k brach-miss – situace je zcela odlišná od quicksortu, který neobsahuje nic jiného než nepředvídatelné skoky.1

1GB dat (250M zcela náhodných intů) je na mém stroji možné seřadit za 4 vteřiny, a 1GB floatů za 2.9 vteřiny2. To odpovídá 14.9 ns, resp 10.8 ns na každý element pole. Když se celé pole vejde do cache, řazení je o něco rychlejší. Každému intu i floatu stačí 9.7 ns, což odpovídá rychlosti řazení přes 100M/s v jednom vlákně. Radix sort navíc umí poznat, když není třeba řadit podle určitého bajtu a přeskočí celý jeden řadící krok, což vede ke značnému zrychlení. Například když řadím pole obsahující jen čísla mezi 0 a 64k, dvě iterace z pěti jsou přeskočeny a je třeba jen 8 ns místo 14.9 ns na element.

Řazení floatů radix sortem je poměrně delikátní záležitost, která se spoléhá na to, že čísla mají bitovou reprezentaci podle specifikace IEEE754. Nejjednodušší možností je data seřadit jako integery a pak opravit pořadí záporných hodnot. O něco rafinovanější je floaty na vstupu transformovat, tak aby by je bylo možné řadit jako 32-bitová čísla bez znaménka a na konci je změnit zpátky na float. Nejlepší řešení je však tomu předejít a upravit offsety záporných radixů.


Ok, takže když je radix sort tak rychlý, k čemu se dá použít? K řazení, pochopitelně. Ale najde i uplatnění tam, kde se řazení zdá, jako jít s kanónem na vrabce.

Jedno takové místo je seskupování.

Když bych chtěl seskupit moře hodnot podle jejich klíče z páru klíč-hodnota (kde klíč i hodnota jsou čtyřbajtové inty zabalené do osmibajtového longu), mohl bych to s do očí bijící neefektivitou napsat v jednom řádku Scaly.

keyvals.groupBy(getKey).map { case (k, vs) => vs.map(getKey) }

To je pěkné, ale nešlo by to rychleji, nejlépe s minimem alokací? Šlo. S pomocí mapy, která obsahuje měnitelné buffery.

val buffers = mutable.Map[Int, mutable.ArrayBuilder.ofInt]()

for (kv <- keyvals) {
  val k = getKey(kv)
  val v = getVal(kv)
  buffers.getOrElseUpdate(k, new mutable.ArrayBuilder.ofInt) += v
}

buffers.toSeq.sortBy(_._1).values

Když zanedbám režii mapy (která může být zanedbatelná, ale také nemusí), za pozornost stojí poslední řádek: sortBy. Najednou jsem tam, kde jsem začal. Když je velikost každé skupiny malá, je jejich počet úměrný velikosti vstupních dat a konečné řazení bude velice drané.

Když vím, že klíče náleží do určitého rozpětí, můžou použít pole bufferů.

val buffers = new Array[mutable.ArrayBuilder.ofInt](length)

for (kv <- keyvals) {
  val k = getKey(kv)
  val v = getVal(kv)
  if (buffers(k) == null) {
    buffers(k) = new mutable.ArrayBuilder.ofInt
  }

  buffers(k) += v
}

buffers.filter(_ != null).map(_.result)

Jak je vidět, na konci není třeba nic řadit, protože výsledek je přirozeně seřazen podle klíče ve stylu counting sortu. Pokud mě trápí opakované alokace a kopírování dat v rostoucích bufferech a můžu si dovolit dva průchody daty, je možné v jenom průchodu spočítat velikosti jednotlivých skupin, alokovat pro ně pole velká tak jak je potřeba, a v druhém průchodu je naplnit. To může být v některých případech rychlejší a v jiných, kdy nechci přijít s OutOfMemoryError po funuse, nezbytné.

Tohle je lepší, ale nešlo by to… však víte… rychleji?

Tady do hry vstupuje radix sort. Co kdybych pole seřadil podle prvních 4 bajtů (tj. té části, která obsahuje klíč) a pak výsledek v jedné iteraci rozřezal na kousíčky. Nějak takhle:

val scratch = new Array[Long](keyvals.length)
val (sorted, _) = RadixSort.sort(keyvals, scratch, 0, keyvals.length, 4, 8, false)

var i = 0
(0 until numberOfKeys iterator) map { key =>
  var start = i

  // find end of the current group
  while (i < keyvals.length && getKey(sorted(i)) == key) { i += 1 }
  val end = i

  // empty group
  if (start == end) {
    null

  // copy values  into a separate array
  } else {
    val res = new Array[Int](end - start)
    var j = 0
    while (start < end) {
      res(j) = getVal(sorted(start))
      start += 1
      j += 1
    }

    (key, res)
  }
} filter (_ != null )

Na rozdíl od předchozích případů je kód o něco složitější, na druhou stranu nejde o pseudokód, ale skutečně fungující fragment. A co víc: Je skutečně rychlejší než všechny předchozí ukázky.

Proč?

Jedno vysvětlení je nasnadě: Pokud je skupin hodně a data jsou více méně náhodná, v předchozím případě každý nový klíč může vést ke několika drahým cache-miss. Jeden načte více méně náhodný pointer na buffer a druhý načte objekt bufferu a třetí konec pole v bufferu na které se bude vkládat. A už jsem zmiňoval, že jít do DRAM je drahé? Myslím, že ano. Radix sort tyhle problémy nemá, párkrát projede data, seřadí je a výsledek se nakonec ještě jednou proletí a rozseká na kousíčky. A všechno udělá velice rychle.


Dále k tématu:


  1. Špatně odhadnuté skoky představují tak velký problém, že někdy je quicksort rychlejší, pokud je záměrně zvolen špatný pivot. Když pivot data rozdělí fifty-fifty, je skok nepředvídatelný. Když je ale rozdělí třeba 25–75, procesor bude odhadovat, že skok půjde doprava a většinou se trefí. viz: An Experimental Study of Sorting and Branch Prediction. V tomto kontextu za pozornost také stojí: Branch Prediction and the Performance of Interpreters – Don't Trust Folklore a Branchless code sequences.
  2. Předpokládám, že v případě floatů JVM JIT zkompiluje kód s využitím SIMD instrukcí a proto je výsledek rychlejší. Nebo také může jít o korelace mezi bitovými vzory v reprezentaci floatů. Podrobnosti jsem nezkoumal.
  3. Jedna z optimalizací, která může za velice specifických situací vést k dvojnásobnému zrychlení je zpětná iterace jedné smyčky. V běžných situacích, kdy jsou vstupní data větší než cache přidá k dobru ~10%. Když je vstupní pole velké, nemá žádný vliv. Další optimalizaci, kterou jsem zkoušel, byly software managed buffers zmiňované zde a zde. Ty fungují tak, že data nezapisuji přímo do paměti, ale do malého bufferu, který se vejde do cache a do paměti ho zkopíruji jen, když se naplní. Tohle přidalo pár procent výkonu pro řazení intů, ale vedlo to k drastickému zpomalení v případě floatů. Výsledek nebyl nijak přesvědčivý a proto jsem tuhle optimalizaci nakonec nepoužil.
  4. To s přihládnutím k tomu, že radix sort musí udělat 5 průchodů celým polem znamená 2.2ns/7taktů CPU na element v každé iteraci. Z paměti je přitom třeba číst/zapisovat 4.8 GB/s (vysvětlení v tomto paperu, který hlásí, že jeden průchod jejich radix sortu, který dává 240M/s na čtyřech jádrech, trvá 13.2 taktu na element – pozor jejich čísla nesedí).
  5. V literatuře se uvádí, že radix sort nedělá sekvenční zápis v tom smyslu, že nezapisuje do jednoho místa, ale do mnoha, v tomto případě 256. To vede k neoptimálnímu využití propustnosti pamětí a může vést k neustálým výpadkům TLB. Moje experimenty na moderním hardwaru však nejsou přesvědčivé aspoň, co se týká TLB. Perf hlásí skoro nulu dTLB-load-misses a dTLB-store-misses, ale na druhou stranu cache miss se stále nějaké vyskytují (jako load-miss tak i store-miss).
  6. Se složitostí radix sortu je to o něco komplikovanější. Je pravda, že běží v čase O(kn), ale povaha onoho k je trochu matoucí. Když bych měl n různých čísel, nejmenší počet bitů potřebných k reprezentaci každého z nich je log<sub>2</sub>(n). Ono O(kn) je tedy vlastně jen O(n log(n)) v přestrojení.

Flattr this!

Posted in Algo, CPU, Paměť | 3 Comments