funkcionálně.cz

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

Lokalita v grafech a negrafech

19. 2. 2017 — k47

Dneska jen krátce a stručně.

po­sled­ních dnech jsem hodně četl o gar­bage collec­to­rech. Byla to za­jí­mavá ex­kurze do pul­zu­jí­cích střev vir­tu­ál­ních strojů, ale o tom teď nechci psát. Chci se zmínit o něčem mnohem menším a skrom­něj­ším, co mě nej­spíš na­padlo po masáži GC al­go­ritmy, kdy se mi začaly zdát sny o ne­ko­neč­ných mark and sweep cyk­lech.

Si­tu­ace je ná­sle­du­jící: Zpra­co­vá­vám nějaká data, která mají po­ten­ci­álně pře­krý­va­jící se okolí. Každá po­ložka má re­fe­rence na ob­jekty, které můžou být sdí­lené jinými po­lož­kami. Při zpra­co­vání dané po­ložky musím načíst všechny tyhle re­fe­ro­vané in­for­mace. Sché­ma­ticky to může vy­pa­dat nějak takhle:

Černé fleky jsou moje po­ložky, kruh zná­zor­ňuje okolí a ko­so­čtverce jsou dílčí ob­jekty. Jak je vidět ně­které jsou sdí­lené, jiné jsou ex­klu­zivní. Když je zpra­co­vá­vám v daném ex­ter­ním pořadí, lo­ka­lita je mizivá. V di­a­gramu sou­sední po­ložky ne­sdílí nic ze svého okolí a při­stu­puji k nim v pod­statě v ná­hod­ném pořadí. To ve větším mě­řítku, může vést ke špat­ném vy­u­žití CPU cache nebo opa­ko­va­ným IO ope­ra­cím (pokud se všechno ne­ve­jde do paměti) a to může věci značně zpo­ma­lit.

Kla­sic­kým ře­še­ním je za­tnout zuby a lif­ro­vat víc peněz Ama­zonu. To může fun­go­vat, ale není to vůbec in­te­lek­tu­álně uspo­ko­jivé.

Právě ve spo­jení s GC al­go­ritmy, které musí projít graf ob­jektů na haldě, aby ozna­čily/zko­pí­ro­valy živé ob­jekty, mě na­padlo si to před­sta­vit jako graf a začít to pro­chá­zet jako graf.

Nemusí jít o přesné pro­hle­dá­vání do šířky nebo do hloubky, stačí li­bo­volná heu­ris­tika, která skáče z jed­noho uzlu na druhý a zaručí, že pro­leze všechno (graf nemusí být spo­jitý). Pokud platí, že uzly často sdílí pod­stat­nou část svého okolí, může to zvýšit lo­ka­litu a to povede ke zrych­lení.

Přesně tohle jsem použil v knihovně sket­ches jako stra­te­gii hro­mad­ného vy­hod­no­co­vání (sek­venční a do­konce i pa­ra­lelní) a vedlo to ke zrych­lení o 25%. Jedna čtvr­tina není zas tak moc, ale v tomto pří­padě to byla čtvr­tina skoro za­darmo.

Jako v pří­padě každé (mikro)op­ti­ma­li­zace i tady platí: pro­fi­lo­vat, pro­fi­lo­vat, pro­fi­lo­vat.


K tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články