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 — k47

Když už tu mluvímřazení a řadící ma­ši­ne­rii, tak bych taky mohl stručně a sro­zu­mi­telně shr­nout co, jak a proč dělat a čemu se vy­hnout.

Asi takhle: Obecné řadící al­go­ritmy jako quicksort, mer­gesort nebo he­ap­sort jsou super. Sami o sobě nejsou nej­rych­lejší, ale nej­lepší hlavy strá­vily po­sled­ních pa­de­sát let jejich op­ti­ma­li­zací a zlep­šo­vá­ním a proto dá se na ně spo­leh­nout a vý­ko­nem nikoho ne­za­hanbí.

Vý­sled­kem oněch pěti dekád je na­pří­klad ra­fi­no­vaný three-way quicksort, který je odolný proti zá­keř­ným vstu­pům4 nebo celá paleta hyb­ridů jako je sta­bilní Tim­sort (který se snaží využít se­řa­zené běhy dat, které se při­ro­zeně vy­sky­tují ve vstupní ko­lekci, začíná práci in­ser­tion sortem a pak na­star­tuje merge sort) nebo ne­sta­bilní1 in­tro­sort (začne rych­lým quicksor­tem, který v pa­to­lo­gic­kých pří­pa­dech pře­padne do he­ap­sortu a krátké sek­vence řadí in­ser­tion sortem, který je sice asympto­ticky pomalý, ale pro malé n je rych­lejší než chytré al­go­ritmy).

Sa­mo­statný k-ary he­ap­sort také může být efek­tivní a rych­lostí může kon­ku­ro­vat quicksortu, pokud je po­rov­nání levné (třeba prosté po­rov­nání intů) a pří­stup do paměti re­la­tivně drahý.


Pokud ale řadím krátké stringy pevné délky (jako třeba 32/64bit inty nebo floaty) a mám k dis­po­zici velkou pro­pust­nost paměti least sig­ni­fi­cant digit (LSD) radix sort je ne­po­ra­zi­telný.

Kla­sická im­ple­men­tace řadící osm bitů v jedné ite­raci po­tře­buje 5 ite­rací pro 32bit klíče (první spo­čítá frek­vence jed­not­li­vých bajtů, po které ná­sle­dují čtyři řadící ite­race) a musí pře­nést všechna data tři­náct­krát (čtyři prů­chody po­tře­bují data načíst a pak je zapsat na jiné místo, za­pi­so­vání nejdřív na­táhne z RAM stará data do cache, tam je pře­píše a pak je poz­ději zapíše zpátky do RAM)2 .

LSD radix sort data vždycky stre­a­muje, vůbec ne­vy­u­žívá cache a za všechno platí pro­pust­ností pamětí. Quicksort nebo most sig­ni­fi­cant digit (MSD) radix sort re­kur­zivně dělí vstup na menší a menší sek­vence. Ty se even­tu­álně vejdou do cache a od toho oka­mžiku jsou všechny ite­race li­mi­to­vané pro­pust­ností cache, která bývá mnohem větší než pro­pust­nost RAM a je lo­kální kaž­dému jádru. Pokud je pro­pust­nosti málo, je možné nejdřív udělat quicksort, MSD radix sort nebo jinou dis­kri­mi­naci do částí, které se vejdou do nějaké úrovně cache a na nich rozjet rychlý LSD radix sort. Vznikne tak ně­ko­li­ka­úrov­ňový hybrid, na který se dá na­ra­zit v li­te­ra­tuře.


Když mě zajímá řazení dlou­hých stringů po­ten­ci­álně pro­měnné délky, na sou­čas­ných cache CPU ar­chi­tek­tu­rách je nej­e­fek­tiv­něj­ším al­go­rit­mem burst­sort. Ten je za­lo­žený na před­po­kladu, že nej­větší dopad na rych­lost řazení mají opa­ko­vané cache-miss, kdy data nejsou při­pra­vena v cache, ale musí se pro ně do RAM. Quicksort nebo jiný dis­kri­mi­nační al­go­rit­mus musí na každé úrovni ite­race projít všechny po­ložky a pokud jich je hodně3 , pří­stup ke každé z nich vyvolá jeden pomalý cache-miss5 . A pro­tože se dělá O(log n) ite­rací, bude třeba i tolik po­ma­lých cache-miss na každý ele­ment vstupní sek­vence. Jak re­kurze po­stu­puje, even­tu­álně se všechny po­ložky jedné sub­sek­vence vejdou do cache a od té doby jsou ite­race rychlé a bez cache-miss. Pokud jsou ele­menty velké, ná­hodně roz­ho­zené nebo kom­po­zitní, tak každý z nich může zabrat ně­ko­lik cache-line a vy­u­žití cache pak není nijak efek­tivní. Burst­sort se snaží snížit počet cache-miss a zrych­lit tak řazení. Ne­pra­cuje re­kur­zivně, jen jednou pro­jede vstupní data a na zá­kladě pre­fixu strin­go­vého klíče je přidá do čás­tečné trie. Ne­snaží se umís­tit ele­ment na pozici určené plnou cestu, ale jen její částí, která vede k listu trie ob­sa­hu­jí­címu ko­lekci ne­se­řa­ze­ných po­lo­žek sdí­le­jí­cích daný prefix. Když algo dorazí k listu, vloží do něj nový ele­ment, v pří­padě po­třeby zvětší list, a když pře­sáhne ur­či­tou mez, ko­lekce v listu praskne (odtud burst) a vy­tvoří se další úroveň trie. V jedné ite­raci je tedy vy­tvo­řena trie, kterou pak projdu v in-order pořadí, jiným al­go­rit­mem řadím ko­lekce, na které na­ra­zím, a získám tak se­řa­zený vý­sle­dek. V ide­ál­ním pří­padě jsou po­třeba jen 2 cache-miss na po­ložku: Jeden při vklá­dání do trie a jeden při zá­vě­reč­ném řazení9 . Oproti dis­kri­mi­nač­ním al­go­ritmům má burst­sort tu výhodu, že se do cache nemusí vejít ko­lekce ele­mentů, ale jen mnohem kom­pakt­nější kostra trie stromu. Ta ne­ob­sa­huje žádná data sa­mot­ných ele­mentů a navíc po­tře­buje jen jeden a něco poin­ter na každou ne­se­řa­ze­nou ko­lekci v listu, která může ob­sa­ho­vat něco mezi 100 a 1000 ele­menty.

Ja­vov­ská verze7 burst­sortu po­u­ží­va­jící Tim­sort (kterou jsem opilý napsal ve tři ráno a zkom­pi­lo­val jsem ji až druhý den) je 2.5-3x rych­lejší než Tim­sort ze stan­dardní knihovny Javy. Je stejně rychlá jako three-way radix quicksort z má za­hrádky (který se vý­borně hodí pro řazení stringů se spo­leč­ným pre­fi­xem). Hybrid burst­sort + three-way radix quicksort je v mých tes­tech 3-4x rych­lejší než sa­motný Tim­sort. To podle mě není vůbec špatný vý­sle­dek pár hodin pro­gra­mo­vání.

Dva dny po před­nášce mě napadl způsob, jak vy­lep­šit burst­sort pomocí sch­war­t­zian trans­form a v ide­ál­ním pří­padě snížit počet cache-miss na po­lo­vinu. O tom se však ro­ze­píšu až někdy příště.


Pro pro­blémy, kdy je počet mož­ných hodnot srov­na­telný nebo menší než ve­li­kost vstupní ko­lekce, dá se řadit v li­ne­ár­ním čase pomocí coun­ting sortu nebo pi­ge­onhole sortu. A když do­předu znám roz­lo­žení vstup­ních dat, můžu řadit v oče­ká­va­ném li­ne­ár­ním čase pomocí bucket sortu nebo pro­x­map sortu.

Ale to není všechno. Co když chci řadit líně? Heap sort je kla­sická volba, ale líně se dá řadit i pomocí quicksortu, radix sortu nebo quicksortu re­i­fi­ko­va­ného do podoby stromu (na tohle jsem nikde v li­te­ra­tuře ne­na­ra­zil a tak jsem to skromně po­jme­no­val YOLO tree, re­le­vantní in­for­mace v Im­ple­men­ting sets ef­fi­ci­ently in a functi­o­nal lan­gu­age).

Když mě za­jí­mají per­cen­tily, kla­sic­kou cestou je quick­se­lect. Ten se dá také na­rou­bo­vat na ra­di­x­sort nebo jiný dis­kri­mi­nační al­go­rit­mus. Median of me­di­ans zaručí li­ne­ární čas, ale kon­stantní fak­tory nejsou nijak pří­z­nivé.6 Po­dob­ného vý­sledku se dá do­sáh­nout adap­tací merge sortu a trochu prav­dě­po­dob­nostní magie. Tento al­go­rit­mus jsem také nikde ne­na­šel a proto jsem mu promptně dal do­časné jméno mer­ge­se­lect. Po­ku­sím se o něm v bu­doucnu něco napsat.

A co pa­ra­lelní řazení? Quicksort se dá tri­vi­álně pa­ra­le­li­zo­vat pomocí součtů pre­fixu (prefix sum) jak je po­psáno v Pro­gra­m­ming on Pa­ral­lel Ma­chi­nes, stejně tak radix sorty nebo merge sort. Určité verze Ra­di­x­sortu můžou být nejen pa­ra­lelní, ale také in-place.

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

Kla­sický pří­stup k řazení quicksort and chill fun­guje, rych­lost nikoho neu­razí a vět­ši­nou při­pra­ven k oka­mži­tému po­u­žití ve stan­dard­ních knihov­nách vět­šiny jazyků. Tohle fun­guje, ale vždycky se spo­k­jit jen s tím, co pouze fun­guje, může být rychlé a po­ho­dlné řešení, ale jen stěží je in­te­lek­tu­álně uspo­ko­jivé. Pokud na něčem záleží, mohli bychom se po­o­hléd­nou po způ­so­bech, jak to udělat co nej­lépe.

Já v sou­časné době pře­mýš­lím, jak vzít Hen­glei­novy nápady, z kom­bi­ná­torů po­pi­su­jí­cích řazení makry vy­ge­ne­ro­vat kom­paktní a efek­tivní kód, který ne­a­lo­kuje do­časné datové struk­tury, a za­po­jit to do vy­lep­še­ného burst­sortu. Vý­sled­kem by mohla být knihovna, která je nejen ge­ne­rická, ale také rych­lejší než všechno ostatní. To je podle mě plán do­sta­tečně od­vážný na to, aby se do něj někdo pustil.


Dále k tématu:


Pozn:

  1. Z kaž­dého ne­sta­bil­ního sortu se dá snadno udělat sta­bilní, když se neřadí podle klíče, ale podle dvo­jice [klíč, po­řa­dové číslo ele­mentu].
  2. Si­tu­ace se dá v tomto pří­padě vy­lep­šit po­u­ži­tím tzv. non-tem­po­ral store in­strukcí, které ne­způ­sobí na­ta­žení cache-line do cache, ale rovnou data za­pí­šou do RAM. Non-tem­po­ral in­strukce jsou vý­hodné, když vím, že data po zápisu nebudu dlouho po­tře­bo­vat a nechci jimi špinit cache a tahat je do věcí cache co­he­rence pro­to­kolu.
  3. A jsou to poin­tery na dy­na­micky alo­ko­vané ob­jekty a ne pole structů, se kte­rými pomůže pre­fet­cher, viz Intel op­ti­mi­zation manual, který po­sky­tuje před­stavu o tom, co pre­fetch dokáže.
  4. Pro­ble­ma­tický vstup je na­pří­klad se­stupně nebo vze­stupně se­řa­zená sek­vence. Kla­sický Hoarův quicksort, který jako pivot vybírá první ele­ment 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 pa­to­lo­gický případ dá eli­mi­no­vat. Ale změna pivotu ne­po­může se vstu­pem ob­sa­hu­jí­cím všechny stejné hod­noty. Na ty je třeba po­změ­nit al­go­rit­mus, aby dělil po­ložky do tří skupin: menší než pivot, rovné pivotu a menší než pivot. S touto změnou quicksort pole iden­tic­kých po­lo­žek trvá li­ne­ární čas místo ka­ta­stro­fic­kého kva­d­ra­tic­kého času.
  5. Mo­derní OOO hard­ware dokáže spe­ku­lo­vat do­předu a za­tímco čeká na data z RAM, spe­ku­la­tivně vykoná kód ná­sle­du­jí­cích ite­rací, které můžou ob­sa­ho­vat další load in­strukce, které skončí jako cache-miss. Takto může na­pří­klad na­čí­tat čtyři věci na­jed­nou a efek­tivně taz zre­du­ko­vat la­tenci na čtvr­tinu. I když je to značné zrych­lení, může to být až 100x po­ma­lejší než sek­venční čtení z paměti nebo pří­stup do cache. (viz MLP)
  6. Když jsem při­pra­vo­val výše zmí­ně­nou před­nášku, na mysl se mi stále vra­cela slova z knihy/filmu No Coun­try For Old Men, která řekl Anton Chi­gurh lovci odměn Car­so­novi chvíli před tím, než ho zabil: „If the rule you followed brou­ght you to this, of what use was the rule?“ K čemu jsou nám záruky dobré asympto­tické kom­ple­xity, když vý­sle­dek bude pomalý. Stejně tak není žádná hanba použít te­o­re­ticky ne­e­fek­tivní algo, který je ale v praxi na re­ál­ných datech rychlý.
  7. Ně­kteří jistě budou na­mí­tat, že JVM je špatná volba pro kód, pro který je kri­tický výkon. Těm lidem vzka­zuji, aby si šli hrát na pís­ko­viště. JVM má jen pro­blém v tom, že není možné ovliv­nit roz­lo­žení paměti – buď mám ob­jekty nebo pole pri­mi­tiv­ních typů/re­fe­rencí a to je všechno. To člo­věku sva­zuje ruce v návrhu da­to­vých struk­tur, pro­tože nemůže požít na­pří­klad objekt, který má na konci in­li­no­vané pole nebo struct tam, kde by se při­ro­zeně hodily. Na­pří­klad burst­sort řazení Java string ob­jektů je o 50% po­ma­lejší než řazení nahých polí charů/bajtů, pro­tože string objekt ob­sa­huje poin­ter na pole znaků, který je třeba de­re­fe­ren­co­vat, což vede k da­to­vým zá­vis­los­tem a (po­ten­ci­álně8 ) dalším zby­teč­ným cache-miss. Kdyby string objekt ob­sa­ho­val pole znaků na konci, bylo by to mnohem lepší.
  8. Tady si­tu­aci značně kom­pli­kuje fakt, že JVM je dy­na­mické pro­středí s gar­bage collec­to­rem, který pře­souvá data z místa na místo a může (ale tady nemusí) data, která jsou po­u­žita spolu (např. ob­sa­hují datově zá­vislé poin­tery), skončí vedle sebe. Někdy se může stát, že vý­sle­dek ben­chmarku bude zá­vi­set jestli pro­běhl GC, v jakém mo­mentu pro­běhl a v jakém pořadí zpra­co­vává ko­ře­nové re­fe­rence. Když je kód velice těsný a jde o na­no­sekundy, ta­ko­váto šaráda může mít dopad v řádech de­sí­tek pro­cent.
  9. Toto platí pokud se celý obsah listu vejde do cache, což není pro­blém, když listy mají ma­xi­lální ve­li­kost v roz­mezí od 1k do 8k. Dále bude pár cache-miss po­třeba během pras­kání listů, ale to se děje jen zřídka. Když se kostra stromu ne­ve­jde do cache, budou třeba další cache miss. Na­štěstí se burst trie široce větví (v li­te­ra­tuře se uvádí prak­tická hod­nota 256) a proto, když se do cache vejde burst trie např. pro 1M po­lo­žek, jeden extra cache-miss je třeba pro vstupní ko­lekci do 256M po­lo­žek.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články