funkcionálně.cz

Iterace křížem krážem

Tenhle článek bych klidně mohl začít clic­kbait ti­tul­kem: „Jeden ne­u­vě­ři­telný trik, který zrychlí vaše pro­gramy,“ a ani bych se za to ne­sty­děl. Asi takhle: Když zpra­co­vá­vám hro­madu dat v ně­ko­lika prů­cho­dech (které z ně­ja­kých důvodů není možné spojit do jed­noho), může nastat ná­sle­du­jící si­tu­ace:

for (x <- xs) f(x)
for (x <- xs) g(x)
for (x <- xs) h(x)

-> 1. iterace ->
|---------------------------|-cache na konci iterace-|
-> 2. iterace ->
|---------------------------|-cache na konci iterace-|
-> 3. iterace ->
|---------------------------|-cache na konci iterace-|

Jak ite­ruji ko­lekcí, CPU načítá data z paměti do cache a po­stupně vy­ha­zuje staré cache-line, na které dlouho ne­sáhlo, aby uvol­nil místo novým ob­jek­tům. Pro­tože ko­lekcí jen pro­lé­tá­vám, na každý objekt sáhnu jen jednou a musím něco starého vy­ho­dit. Když začnu další ite­raci, ob­jekty ze za­čátku ko­lekce jsou s nej­větší prav­dě­po­dob­ností už dávno vy­ho­zeny z cache a začnu tedy při­stu­po­vat ke stu­de­ným datům. V cache jsou jen data z konce před­chozí ite­race. Proto může dávat smysl ite­ro­vat ve stří­da­vých smě­rech.

for (x <- xs)         f(x)
for (x <- xs.reverse) g(x)
for (x <- xs)         h(x)

-> 1. iterace ->
|---------------------------|-cache na konci iterace-|
                                      <- 2. iterace <-
|-cache na konci iterace-|---------------------------|
-> 3. iterace ->
|---------------------------|-cache na konci iterace-|

Za­čá­tek ná­sle­du­jící ite­race vy­u­žije obsah cache, který tam zůstal po mi­nu­lém prů­chodu. Pří­stup do cache je rych­lejší než čtení z RAM i v těch nej­lep­ších pří­pa­dech, kdy jen stre­a­muji sou­vislý bok paměti.

Tohle jsem momo jiné apli­ko­val na radix sort (první ite­race, která jen sbírá sta­tis­tiky, běží po­zpátku) a když jsou data 2x větší než L3 cache, vede to ke ~10% zrych­lení. V ex­trémně spe­ci­fic­kých si­tu­a­cích to může na­kop­nout výkon až o 50%, Když jsou však data mnohem větší než cache, efekt je za­ne­dba­telný. Na druhou stranu je to jen malá změna, která ne­uškodí (hard­wa­rový pre­fetch umí pra­co­vat i po­zpátku).

Když je všechno ostatní op­ti­ma­li­zo­vané na kost, tohle může v ur­či­tých pří­pa­dech při­nést nějaké zrych­lení. Ale jako v pří­padě každé mikro-op­ti­ma­li­zace je třeba měřit a pro­fi­lo­vat.

Dále k tématu:

• In­klu­zivní cache, mnoho vláken a pro­blémy