Lokalita v grafech a negrafech
Dneska jen krátce a stručně.
V posledních dnech jsem hodně četl o garbage collectorech. Byla to zajímavá exkurze do pulzujících střev virtuálních strojů, ale o tom teď nechci psát. Chci se zmínit o něčem mnohem menším a skromnějším, co mě nejspíš napadlo po masáži GC algoritmy, kdy se mi začaly zdát sny o nekonečných mark and sweep cyklech.
Situace je následující: Zpracovávám nějaká data, která mají potenciálně překrývající se okolí. Každá položka má reference na objekty, které můžou být sdílené jinými položkami. Při zpracování dané položky musím načíst všechny tyhle referované informace. Schématicky to může vypadat nějak takhle:
Černé fleky jsou moje položky, kruh znázorňuje okolí a kosočtverce jsou dílčí objekty. Jak je vidět některé jsou sdílené, jiné jsou exkluzivní. Když je zpracovávám v daném externím pořadí, lokalita je mizivá. V diagramu sousední položky nesdílí nic ze svého okolí a přistupuji k nim v podstatě v náhodném pořadí. To ve větším měřítku, může vést ke špatném využití CPU cache nebo opakovaným IO operacím (pokud se všechno nevejde do paměti) a to může věci značně zpomalit.
Klasickým řešením je zatnout zuby a lifrovat víc peněz Amazonu. To může fungovat, ale není to vůbec intelektuálně uspokojivé.
Právě ve spojení s GC algoritmy, které musí projít graf objektů na haldě, aby označily/zkopírovaly živé objekty, mě napadlo si to představit jako graf a začít to procházet jako graf.
Nemusí jít o přesné prohledávání do šířky nebo do hloubky, stačí libovolná heuristika, která skáče z jednoho uzlu na druhý a zaručí, že proleze všechno (graf nemusí být spojitý). Pokud platí, že uzly často sdílí podstatnou část svého okolí, může to zvýšit lokalitu a to povede ke zrychlení.
Přesně tohle jsem použil v knihovně sketches jako strategii hromadného vyhodnocování (sekvenční a dokonce i paralelní) a vedlo to ke zrychlení o 25%. Jedna čtvrtina není zas tak moc, ale v tomto případě to byla čtvrtina skoro zadarmo.
Jako v případě každé (mikro)optimalizace i tady platí: profilovat, profilovat, profilovat.
K tématu:
- Sorting out graph processing - lokalita grafů se dá také zlepšit řazením.