funkcionálně.cz

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

Jazyk D a radix sort

1. 6. 2017 — k47

V po­slední době jsem se začal učit jazyk D. Chtěl jsem poznat nějaký nový jazyk, nej­lépe něco kom­pi­lo­va­ného, co mi po­skytne dobrou kon­t­ro­lou nad la­y­ou­tem paměti. Zkou­šel jsem Rust, ale nějak moc mě ne­chytl, vždycky mi při­pa­dalo, že učící křivka začíná straš­li­vým hr­bo­lem. Chtěl jsem začít tak, že napíšu nějaký jed­no­du­chý pro­gram, ale v pří­padě Rustu se musím pro­kou­sat přes re­fe­rence, vy­půj­čo­vání a systém vlast­nic­tví ob­jektů/paměti, než se do něčeho můžu pustit, a ani potom nemám dojem, že znám všechno po­třebné. Chtěl bych začít stylem na hul­váta: Něco o syn­taxi, pár da­to­vých struk­tur a nějaké ty idiomy, pustit vim a začít. Ale v Rustu vždycky po­chy­buji: má to být objekt, re­fe­rence na objekt, re­f­coun­to­vaná re­fe­rence nebo ato­micky re­f­coun­to­vaná re­fe­rence. 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 po­dobné, jen tohle, tohle a tohle je jinak, má to v sobě CG, kon­t­ro­luje roz­sahy polí a o poin­tery se není třeba příliš starat (se­g­fault­nul jsem jen jednou), takhle uděláš dy­na­mické pole, takhle aso­ci­a­tivní, přeji pří­jemné kó­do­vání. Hotovo.

D má tu pří­jem­nou (a pře­kva­pi­vou) vlast­nost, že všechno prostě fun­guje. 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í fa­mi­li­ár­ním dojmem, má bo­ha­tou stan­dardní kni­hovnu a proto je s ním jed­no­du­ché začít.

Jen typový systém mě trochu děsí. Ze Scaly jsem zvyklý na něco ri­goróz­ního a sys­te­ma­tic­kého. D nemá nic ta­ko­vého, jen ne­ko­nečné in­stan­ci­ace šablon. To je na jednu stranu fajn, pro­tože můžu přesně řídit, jak a pro co se mi spe­ci­a­li­zuje kód, ale na druhou stranu z toho mám pocit, jako kdy­bych pro­plou­val me­zihvězd­ným pro­sto­rem: Není tam nic sta­bil­ního, o co bych se mohl opřít.


V rámci studia jsem v D napsal radix sort (zdro­jáky tady). Jde pře­kva­pivě pouze o 40 řádků kódu a i když to ne­zvládá zna­mén­kové typy nebo floaty, jde o tem­pla­to­vaný kód pro všechny ne­zna­mén­kové inty1 . To není nijak zlé, není se třeba zdr­žo­vat žádnou ma­nu­ální spe­ci­a­li­zací, která by byla po­třeba v Javě/Scale, abych po­řádně roz­pá­lil křemík.

Oproti minulé verzi, kterou jsem vy­sek­nul ve Scale, je tohle pro­ve­dení v jazyku, který po­sky­tuje kon­t­rolu nad la­y­ou­tem paměti, za­ru­če­nou alo­kaci na zá­sob­níku a mož­ností obejít kon­t­roly roz­sahů polí, rych­lejší. Ale hlavně je sta­bilně rych­lejší a můžu se na to spo­leh­nout. Ne­mu­sím se stra­cho­vat, aby JIT všechno de­vir­tu­a­li­zo­val a in­li­no­val.

Čas na ele­ment vstup­ního pole je kon­stantní od ma­lič­kých polí kolem 64 ele­mentů až po gi­gan­tické s délkou 256M. Když je délka vstup­ního intu kon­stantní, jde sku­tečně o li­ne­ární řazení.

Ná­sle­du­jící ta­bulka je pro pole 64M intů (256MB kus paměti). Po­rov­nává radix sort s řa­dí­cím algo ze stan­dardní knihovny D (mělo by jít o in­tro­sort nebo tim­sort).

typ radix sort std.al­go­ri­thm.sor­ting.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­ži­tost, je po­ma­lejší a jeho čas na ele­ment roste s ve­li­kostí vstupu. Radix sort 256G intů se stále po­hy­buje pod 10ns/po­ložku, U 1G intu to spadne na 15ns na po­ložku. To se však dá čekat. Vstupní pole má 4GB (+ 4GB ori­gi­nál v tes­to­va­cím kódu) a do­časný pra­covní pro­stor zabírá další 4GB (tento radix sort není in-place2 ). Do­hro­mady to zabírá vět­šinu paměti na mém stroji, který mohl občas swa­po­vat.

Z po­drob­něj­šího zkou­mání to vypadá, že al­go­rit­mus je li­mi­to­ván pamětí a/nebo cache. perf hlásí velké množ­ství L1-dcache-load-misses a také LLC-load-missesLLC-store-misses, ale skoro žádné dTLB-load-misses. Když pro­gram čte data li­ne­árně, ale cache se­lhá­vají, může to zna­me­nat, že pre­fetch ne­stí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 3x po­ma­lejší. To se dá vy­svět­lit tak, že jednak dělá 2x více ite­rací (jedna ite­race pro každý byte) a navíc při každé ite­raci pře­ha­zuje dvoj­ná­so­bek 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 in­strukcí, jedna po­ten­ci­ální datová zá­vis­lost, dva­krát čtu z paměti, jednou do ní za­pi­suji, dělám 4 ite­race + jednu pro spo­čí­tání glo­bál­ního his­to­gramu. Pro se­řa­zení 4B intu musím po­hnout 52B dat. A pa­ra­le­li­zace ne­při­nesla vůbec žádné zrych­lení. Na 4 vlák­nech běží pořád něco přes 10ns/el. Pa­ra­le­li­zace při­nesla určité zrych­lení. Na 4 já­drech běží ~2x rych­leji. Po­lo­viční zrych­lení oproti ideálu se dá čekat, pro­tože pro­gram pro­vede 2x tolik in­strukcí (roz­dě­lení práce a spo­jení vý­sledků není za­darmo). Tahle verze pře­ha­zuje data z/do paměti kolem tempem přes 10GB/s.

D mi při­padá jako dobrý jazyk pro psaní těchto níz­ko­úrov­ňo­vých věcí. Dovolí mi dostat z hard­ware ma­xi­mum, ale ne­pů­sobí ne­o­hra­baně jako C nebo vy­lo­ženě ne­přá­tel­sky jako C++.


Dále k tématu:


Pozn:

  1. D má tu pří­jem­nou vlast­nost, že jeho ce­lo­čí­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 PA­RA­DISu
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články