Mýtus o O(1) paměti

Vzpomínám si, jak se mě po jedné z přednášek, kde jsem dlouze mluvil o tom, jak drastický má hardware efekt na naše křehké algoritmy a příčetnost, někdo zeptal, jestli to není jen honba po artefaktech a podivnostech současného hardwaru, a tedy v dlouhodobém měřítku zbytečná práce. Odpověděl jsem něco v tom duchu, že uvažování o několikaúrovňové cache a RAM je užitečné, protože všechny současné procesory – počínaje těmi v mobilech až po ty v obrovských serverech – jsou od sebe skoro k nerozeznání. Možná jsem do plénu hodil zkazku o rychlosti světla a limitaci třírozměrným prostorem, ale nebyl jsem se svojí odpovědí spokojený. Tahle otázka mě donutila provést exkurzi do historie architektury procesorů, ale ani poté jsem neměl skutečnou odpověď.

Tu jsem dostal až teď, když jsem přes Martina Thompsona narazil na čtyřdílný seriál blogpostů The Myth of RAM (2, 3, 4). Jejich autor empiricky i teoreticky ukazuje, že čtení a zápis do paměti – ať už to je cache, RAM, SSD nebo HDD – je O(√N) operace, nikoli O(1). N je v tomto případě velikost paměti, ke které je přistupováno v náhodném a nepředvídatelném pořadí. Nejde nutně o celý dataset, ale jen tu nepředvídatel­nou část.

Tento model je (aspoň podle mého skromného názoru) velký skok kupředu, protože popisuje reálné efekty, která má hardware na chování programů. Ty se s narůstající velikostí dat zpomalují rychleji, než by odpovídalo samotným asymptotám právě proto, že v nich někde figuruje zbloudilá odmocnina N. Například průchod spojovým seznamem není O(N), ale O(N√N). Čtení z hashtabulky není O(1) ale O(√N). Binární hledání není O(log(N)) ale O(log(N)√N). Najednou všechny ad-hoc konstrukce vysvětlující efekty cache v tom kterém případě dostávají uniformitu a řád.

Model rozeznává dva případy: nepředvídatelné a předvídatelné čtení z paměti. Když chci přečíst pole objektů, které leží v paměti jeden vedle druhého, platím √N jen jednou, prefetcher se postará, aby každá další položka dorazila ve skutečném O(1) čase. Prefetcher tedy amortizuje počáteční √N cenu v mnoha následujících předvídatelných operacích.

Články však nezmiňují rozdíl mezi závislými a nezávislými operacemi a vůbec neuvažují paralelní přístup k paměti, MLP a out-of-order superskalární procesory, které zvládají dělat víc věcí najednou včetně několika paralelních dotazů do paměti. Procházení spojovým seznamem je příklad závislých operací. Čtení z hashmapy zase těch nezávislých. Když jsou operace nezávislé, hardware jich může provést několik najednou. Na druhou stranu závislost implikuje sekvenční zpracování (o důsledcích víc tady). O těchto záležitostech se dá uvažovat jako o konfliktu mezi paralelismem a √N cenou paměti. OOO hardware spekuluje hlavně proto, aby mohl začít co nejvíc paměťových transakcí najednou a platit několik √N souběžně.

Celá tahle věc mě nadchla, protože do věci vnáší systém a řád vysvětlující, co se skutečně děje. Není to model, který věci zjednodušuje, ale který je zpřesňuje s ohledem na velikost dat od kilobajtů po petabajty.

Teď mě jen napadá, jestli tento √N faktor nemá nějakou spojitost s cache-oblivious algoritmy, v jichž složitostech skoro vždy figurují právě odmocniny N. To si ale nejspíš nechám jako materiál k přemýšlení pro dlouhé zimní noci v baru HG.

Flattr this!

This entry was posted in CPU, Paměť. Bookmark the permalink.

Leave a Reply

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