Jazyk D a radix sort

V poslední době jsem se začal učit jazyk D. Chtěl jsem poznat nějaký nový jazyk, nejlépe něco kompilovaného, co mi poskytne dobrou kontrolou nad layoutem paměti. Zkoušel jsem Rust, ale nějak moc mě nechytl, vždycky mi připadalo, že učící křivka začíná strašlivým hrbolem. Chtěl jsem začít tak, že napíšu nějaký jednoduchý program, ale v případě Rustu se musím prokousat přes reference, vypůjčování a systém vlastnictví objektů/paměti, než se do něčeho můžu pustit, a ani potom nemám dojem, že znám všechno potřebné. Chtěl bych začít stylem na hulváta: Něco o syntaxi, pár datových struktur a nějaké ty idiomy, pustit vim a začít. Ale v Rustu vždycky pochybuji: má to být objekt, reference na objekt, refcountovaná reference nebo atomicky refcountovaná reference. Co z toho mám použít a jak?

Pak jsem se pustil do D a neslo se to v duchu: Znáš C/C++? Jo? Tak je to podobné, jen tohle, tohle a tohle je jinak, má to v sobě CG, kontroluje rozsahy polí a o pointery se není třeba příliš starat (segfaultnul jsem jen jednou), takhle uděláš dynamické pole, takhle asociativní, přeji příjemné kódování. Hotovo.

D má tu příjemnou (a překvapivou) vlastnost, že všechno prostě funguje. Když nevím, jak něco udělat, něco zkusím a ejhle: Ono to je správné řešení. I když jazyk neznám, působí familiárním dojmem, má bohatou standardní knihovnu a proto je s ním jednoduché začít.

Jen typový systém mě trochu děsí. Ze Scaly jsem zvyklý na něco rigorózního a systematického. D nemá nic takového, jen nekonečné instanciace šablon. To je na jednu stranu fajn, protože můžu přesně řídit, jak a pro co se mi specializuje kód, ale na druhou stranu z toho mám pocit, jako kdybych proplouval mezihvězdným prostorem: Není tam nic stabilního, o co bych se mohl opřít.


V rámci studia jsem v D napsal radix sort (zdrojáky tady). Jde překvapivě pouze o 40 řádků kódu a i když to nezvládá znaménkové typy nebo floaty, jde o templatovaný kód pro všechny neznaménkové inty1. To není nijak zlé, není se třeba zdržovat žádnou manuální specializací, která by byla potřeba v Javě/Scale, abych pořádně rozpálil křemík.

Oproti minulé verzi, kterou jsem vyseknul ve Scale, je tohle provedení v jazyku, který poskytuje kontrolu nad layoutem paměti, zaručenou alokaci na zásobníku a možností obejít kontroly rozsahů polí, rychlejší. Ale hlavně je stabilně rychlejší a můžu se na to spolehnout. Nemusím se strachovat, aby JIT všechno devirtualizoval a inlinoval.

Čas na element vstupního pole je konstantní od maličkých polí kolem 64 elementů až po gigantické s délkou 256M. Když je délka vstupního intu konstantní, jde skutečně o lineární řazení.

Následující tabulka je pro pole 64M intů (256MB kus paměti). Porovnává radix sort s řadícím algo ze standardní knihovny D (mělo by jít o introsort nebo timsort).

typ radix sort std.algorithm­.sorting.sort
ubyte 1.5 ns/el 42 ns/el
ushort 3.7 ns/el 66 ns/el
uint 9.5 ns/el 89 ns/el
ulong 28.5 ns/el 91 ns/el

s.a.s.sort má O(n log n) složitost, je pomalejší a jeho čas na element roste s velikostí vstupu. Radix sort 256G intů se stále pohybuje pod 10ns/položku, U 1G intu to spadne na 15ns na položku. To se však dá čekat. Vstupní pole má 4GB (+ 4GB originál v testovacím kódu) a dočasný pracovní prostor zabírá další 4GB (tento radix sort není in-place2). Dohromady to zabírá většinu paměti na mém stroji, který mohl občas swapovat.

Z podrobnějšího zkoumání to vypadá, že algoritmus je limitován pamětí a/nebo cache. perf hlásí velké množství L1-dcache-load-misses a také LLC-load-misses a LLC-store-misses, ale skoro žádné dTLB-load-misses. Když program čte data lineárně, ale cache selhávají, může to znamenat, že prefetch nestíhá data sypat z paměti. LLC-*-misses skoro zmizí pro menší vstupní pole intů a čas spadne na 8.5 ns/el.

ulong je oproti uint verzi 3× pomalejší. To se dá vysvětlit tak, že jednak dělá 2× více iterací (jedna iterace pro každý byte) a navíc při každé iteraci přehazuje dvojnásobek dat a přitom dělá jen velice málo práce.

Hlavní smyčka vypadá takhle:

foreach(v; arr) {
  uint c = (v >> (b * 8)) & 0xff;
  tmparr.ptr[offsets[c]] = v;
  offsets[c] += 1;
}

Jen pár instrukcí, jedna potenciální datová závislost, dvakrát čtu z paměti, jednou do ní zapisuji, dělám 4 iterace + jednu pro spočítání globálního histogramu. Pro seřazení 4B intu musím pohnout 52B dat. A paralelizace nepřinesla vůbec žádné zrychlení. Na 4 vláknech běží pořád něco přes 10ns/el. Paralelizace přinesla určité zrychlení. Na 4 jádrech běží ~2× rychleji. Poloviční zrychlení oproti ideálu se dá čekat, protože program provede 2× tolik instrukcí (rozdělení práce a spojení výsledků není zadarmo). Tahle verze přehazuje data z/do paměti kolem tempem přes 10GB/s.

D mi připadá jako dobrý jazyk pro psaní těchto nízkoúrovňových věcí. Dovolí mi dostat z hardware maximum, ale nepůsobí neohrabaně jako C nebo vyloženě nepřátelsky jako C++.


Dále k tématu:


Pozn:

  1. D má tu příjemnou vlastnost, že jeho celočíselné typy mají stejné délky jako v Javě: byte (1B), short/ushort (2B), int/uint (4B) a long/ulong (8B)
  2. Na rozdíl od PARADISu

Flattr this!

This entry was posted in D, low level, řazení. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *