funkcionálně.cz

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

Jak rychle řadit a šetřit čas

29. 5. 2016

Když už tu mluvím o ř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-3x 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-4x 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 Podobné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ž 100x 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.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články