Iterace křížem krážem

Tenhle článek bych klidně mohl začít clickbait titulkem: „Jeden neuvěřitelný trik, který zrychlí vaše programy,“ a ani bych se za to nestyděl. Asi takhle: Když zpracovávám hromadu dat v několika průchodech (které z nějakých důvodů není možné spojit do jednoho), může nastat následující situace:

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 iteruji kolekcí, CPU načítá data z paměti do cache a postupně vyhazuje staré cache-line, na které dlouho nesáhlo, aby uvolnil místo novým objektům. Protože kolekcí jen prolétávám, na každý objekt sáhnu jen jednou a musím něco starého vyhodit. Když začnu další iteraci, objekty ze začátku kolekce jsou s největší pravděpodobností už dávno vyhozeny z cache a začnu tedy přistupovat ke studeným datům. V cache jsou jen data z konce předchozí iterace. Proto může dávat smysl iterovat ve střídavý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ásledující iterace využije obsah cache, který tam zůstal po minulém průchodu. Přístup do cache je rychlejší než čtení z RAM i v těch nejlepších případech, kdy jen streamuji souvislý bok paměti.

Tohle jsem momo jiné aplikoval na radix sort (první iterace, která jen sbírá statistiky, běží pozpátku) a když jsou data 2× větší než L3 cache, vede to ke ~10% zrychlení. V extrémně specifických situacích to může nakopnout výkon až o 50%, Když jsou však data mnohem větší než cache, efekt je zanedbatelný. Na druhou stranu je to jen malá změna, která neuškodí (hardwarový prefetch umí pracovat i pozpátku).

Když je všechno ostatní optimalizované na kost, tohle může v určitých případech přinést nějaké zrychlení. Ale jako v případě každé mikro-optimalizace je třeba měřit a profilovat.


Dále k tématu:

Flattr this!

This entry was posted in Algo, CPU, low level. Bookmark the permalink.

Leave a Reply

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