Cache: proč je pole rychlejší, než složitost slibuje
Projít pole o milionu prvků je O(n). Projít spojový seznam o milionu prvků je taky O(n). Ve skutečnosti je to první několikanásobně rychlejší, a v té notaci není nic, co by to naznačovalo.
Paměť se nečte po prvcích, ale po řádkách
Procesor si z hlavní paměti nikdy nebere jeden bajt. Bere celou řádku cache — typicky 64 bajtů. Když se čte prvek, přijde s ním i těch 56 bajtů okolo, ať jsou potřeba nebo ne.
Pro pole je to dar zdarma: prvky jsou vedle sebe, takže jedno sáhnutí do paměti přinese osm z nich. Pro spojový seznam je to k ničemu: další prvek je někde jinde, takže těch 56 bajtů, co přišly s ním, jsou cizí data.
A ten rozdíl není osminásobný, ale větší, protože sáhnutí do hlavní paměti stojí kolem stovky taktů, kdežto čtení z cache jednotky. Osmkrát méně sáhnutí tedy znamená mnohem víc než osmkrát rychleji — a přesně proto se v praxi spojový seznam skoro nepoužívá, ačkoli v učebnici vypadá stejně dobře.
Důsledky, které z toho plynou
- Procházet paměť po pořádku je mnohem rychlejší než skákat. Proto je průchod maticí po řádcích rychlejší než po sloupcích, i když je to týž počet operací.
- Menší prvek je rychlejší prvek. Když se položka zmenší z 32 na 8 bajtů, vejde se jich do řádky čtyřikrát víc — a průchod je čtyřikrát levnější, aniž se změnil jediný řádek algoritmu.
- Rozdělit data podle toho, co se čte spolu. Když se ve smyčce čte jen jedna položka ze struktury, je lepší mít pole těch položek než pole struktur.
Proč se to tady modeluje, a neměří
Skutečné výpadky cache se změřit dají, ale výsledek závisí na procesoru, na velikosti jeho cache, na prefetcheru a na tom, co běží vedle — tedy na všem tom, kvůli čemu se v kapitole 1 zavrhly stopky. Model s jednou řádkou o 64 bajtech je hrubý a přiznává to, ale ten osminásobek vysvětlí a spočítat se dá pokaždé stejně.