Stejná data, patnáctkrát pomaleji

Sečti 2^26 celých čísel popořadě. Pak sečti ta samá čísla v náhodném pořadí. Druhá varianta poběží dvanáctkrát pomaleji. A když víš, proč je náhodný přístup pomalý, dokážeš zkonstruovat pořadí, které je pomalejší ještě o polovinu — patnáctkrát pomalejší než sekvenční průchod.

Stejný počet sčítání, stejná data v paměti. Rozdíl nedělá procesor. Dělá ho to, jak k paměti přistupuješ.

Paměť není plochá

Mentální model „RAM je pole, ke kterému mám konstantní přístup" je pohodlný a špatný. Procesor nenačítá jednotlivé bajty. Načítá celé cache line po 64 bajtech jako nedělitelné bloky a spoléhá na dvě věci: že brzy sáhneš i vedle (prostorová lokalita) a že se ke stejnému místu brzy vrátíš (časová lokalita).

Sekvenční součet obě splňuje dokonale. Jeden fetch cache line obslouží šestnáct čtyřbajtových intů a hardwarový prefetcher navíc dopředu natáhne další. Náhodný přístup obě lokality zabíjí — každé čtení je nový fetch, který se skoro nevyužije.

Pět vrstev, kde se lokalita láme

Zajímavé je, že náhodnost není nejhorší možnost. Cílené ničení lokality na každé úrovni hierarchie je horší:

• Cache line reuse. Skákání po krocích přesně jedné cache line znamená, že se blok načte a stihne se vyhodit dřív, než ho využiješ.
• Set-associativita. Krok po celé stránce (4096 B) mapuje všechny přístupy do jedné cache sady místo rozprostření do všech. Efektivní kapacita L1 spadne z desítek kilobajtů na stovky bajtů.
• Hranice stránky. Prefetcher nespekuluje přes hranici 4 KB, protože překlad virtuální adresy vnáší nejistotu. Za hranicí tě žádné dopředné načítání nezachrání.
• Page table entries. Dostatečně velký krok rozbije i cache samotného překladu adres — platíš miss navíc jen za to, zjistit, kde data leží.
• DRAM row buffer. Střídání řádků v téže bance nutí paměť pořád dokola „precharge a activate", což je jedna z nejdražších operací vůbec.

Každá vrstva se násobí s předchozí. Proto z dvanáctinásobku snadno uděláš patnáctinásobek.

Rozumět selhání znamená umět optimalizovat

Autor postavil nejhorší možný přístup tak, že vzal každý mechanismus, který dělá paměť rychlou, a záměrně ho obrátil. To je poučné víc než samotné číslo. Výkon paměti není jedna veličina, je to vrstvený systém — a optimalizovat ho znamená respektovat lokalitu na všech vrstvách naráz, ne jen se vejít do cache.

Mechanical sympathy není o tom umět zpaměti latence. Je to o tom vědět, že datová struktura, která se v paměti prochází skokově — linked list, strom ukazatelů, hashmapa s rozházenými bucket — platí tuhle daň, i když má „konstantní" složitost na papíře.

Co si z toho odnést

Když měříš horký kód a čísla nedávají smysl, podívej se dřív na přístupový vzor než na počet operací. Souvislé pole, které projdeš popořadě, porazí chytřejší strukturu s horší lokalitou i o řád.

Big-O ti řekne, jak škáluje počet kroků. Neřekne nic o tom, kolik každý krok stojí — a ta cena se u paměti liší patnáctkrát. Uspořádání dat v paměti je návrhové rozhodnutí, ne implementační detail.