funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Mýtus o O(1) paměti

9. 9. 2016 — k47

Vzpo­mí­nám si, jak se mě po jedné z před­ná­šek, kde jsem dlouze mluvil o tom, jak dras­tický má hard­ware efekt na naše křehké al­go­ritmy a pří­čet­nost, někdo zeptal, jestli to není jen honba po ar­te­fak­tech a po­div­nos­tech sou­čas­ného hard­waru, a tedy v dlou­ho­do­bém mě­řítku zby­tečná práce. Od­po­vě­děl jsem něco v tom duchu, že uva­žo­vání o ně­ko­li­ka­úrov­ňové cache a RAM je uži­tečné, pro­tože všechny sou­časné pro­ce­sory – po­čí­naje těmi v mo­bi­lech až po ty v ob­rov­ských ser­ve­rech – jsou od sebe skoro k ne­ro­ze­znání. Možná jsem do plénu hodil zkazku o rych­losti světla a li­mi­taci tří­roz­měr­ným pro­sto­rem, ale nebyl jsem se svojí od­po­vědí spo­ko­jený. Tahle otázka mě do­nu­tila pro­vést ex­kurzi do his­to­rie ar­chi­tek­tury pro­ce­sorů, ale ani poté jsem neměl sku­teč­nou od­po­věď.

Tu jsem dostal až teď, když jsem přes Mar­tina Thomp­sona na­ra­zil na čtyř­dílný seriál blo­gpo­stů The Myth of RAM (2, 3, 4). Jejich autor em­pi­ricky i te­o­re­ticky uka­zuje, že čtení a zápis do paměti – ať už to je cache, RAM, SSD nebo HDD – je O(√N) ope­race, nikoli O(1). N je v tomto pří­padě ve­li­kost paměti, ke které je při­stu­po­váno v ná­hod­ném a ne­před­ví­da­tel­ném pořadí. Nejde nutně o celý da­ta­set, ale jen tu ne­před­ví­da­tel­nou část.

Tento model je (aspoň podle mého skrom­ného názoru) velký skok kupředu, pro­tože po­pi­suje reálné efekty, která má hard­ware na cho­vání pro­gramů. Ty se s na­růs­ta­jící ve­li­kostí dat zpo­ma­lují rych­leji, než by od­po­ví­dalo sa­mot­ným asympto­tám právě proto, že v nich někde fi­gu­ruje zblou­dilá od­moc­nina N. Na­pří­klad prů­chod spo­jo­vým se­zna­mem není O(N), ale O(N√N). Čtení z ha­sh­ta­bulky není O(1) ale O(√N). Bi­nární hle­dání není O(log(N)) ale O(log(N)√N). Na­jed­nou všechny ad-hoc kon­strukce vy­svět­lu­jící efekty cache v tom kterém pří­padě do­stá­vají uni­for­mitu a řád.

Model ro­ze­znává dva pří­pady: ne­před­ví­da­telné a před­ví­da­telné čtení z paměti. Když chci pře­číst pole ob­jektů, které leží v paměti jeden vedle dru­hého, platím √N jen jednou, pre­fet­cher se po­stará, aby každá další po­ložka do­ra­zila ve sku­teč­ném O(1) čase. Pre­fet­cher tedy amor­ti­zuje po­čá­teční √N cenu v mnoha ná­sle­du­jí­cích před­ví­da­tel­ných ope­ra­cích.

Články však ne­zmi­ňují rozdíl mezi zá­vis­lými a ne­zá­vis­lými ope­ra­cemi a vůbec ne­u­va­žují pa­ra­lelní pří­stup k paměti, MLPout-of-order su­per­ska­lární pro­ce­sory, které zvlá­dají dělat víc věcí na­jed­nou včetně ně­ko­lika pa­ra­lel­ních dotazů do paměti. Pro­chá­zení spo­jo­vým se­zna­mem je pří­klad zá­vis­lých ope­rací. Čtení z ha­shmapy zase těch ne­zá­vis­lých. Když jsou ope­race ne­zá­vislé, hard­ware jich může pro­vést ně­ko­lik na­jed­nou. Na druhou stranu zá­vis­lost im­pli­kuje sek­venční zpra­co­vání (o dů­sled­cích víc tady). O těchto zá­le­ži­tos­tech se dá uva­žo­vat jako o kon­fliktu mezi pa­ra­le­lis­mem a √N cenou paměti. OOO hard­ware spe­ku­luje hlavně proto, aby mohl začít co nejvíc pa­mě­ťo­vých trans­akcí na­jed­nou a platit ně­ko­lik √N sou­běžně.

Celá tahle věc mě nadchla, pro­tože do věci vnáší systém a řád vy­svět­lu­jící, co se sku­tečně děje. Není to model, který věci zjed­no­du­šuje, ale který je zpřes­ňuje s ohle­dem na ve­li­kost dat od ki­lo­bajtů po pe­ta­bajty.

Teď mě jen napadá, jestli tento √N faktor nemá ně­ja­kou spo­ji­tost s cache-ob­li­vi­ous al­go­ritmy, v jichž slo­ži­tos­tech skoro vždy fi­gu­rují právě od­moc­niny N. To si ale nej­spíš nechám jako ma­te­riál k pře­mýš­lení pro dlouhé zimní noci v barz HG.

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články