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 2x 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: