563
« kdy: 26. 03. 2011, 11:22:33 »
V zásadě ano, inkrementální alokátor má konstantní složitost a to je i základ mého návrhu. Pokud alokované bloky dealokujeme dekrementálně (v opačném pořadí), tak naprosto postačuje, takhle vlastně funguje zásobník. Horší je to s dírami.
Potřeboval jsem alokátor v mapované paměti. Mám datové struktur pro vytváření stromů v mapovaném souboru a potřeboval jsem nějakým způsobem spravovat přidělenou paměť, aby bylo možné prvky ze stromu i mazat a přidávat nové. Celý zádrhel je v tom, že v mapovaném souboru se může vyskytnout více druhů uzlů, různě veliké a je zde prostor i pro alokaci řetězců, které nechci držet mimo.
Snahou bylo přesunout správu volného místa (děr) až na proces dealokace, aby operace "alloc()" měla vše již připravené a nemusela nic hledat. Při dealokaci mimo pořadí, tzn jinde než na konec, se díra jen zaznamená, ale není ji možné zatím používat pro alokace. Dál se tedy alokuje inkrementálně na konci. Jednou za čas, na základě analýzy stavu haldy a na základě její "děravosti" (dejme tomu, jakmile díry obsadí víc, než 20% místa), se spustí dávka, ideálně na pozadí a všechny díry posbírá, seřadí podle adresy, sloučí ty, co leží vedle sebe a následně seřadí od největší po nejmenší. To lze dělat bez synchronizace, protože volné místo by už nikdo neměl používat. Evidence děr se provádí přímo v uvolněném prostoru, takže defacto nezabírá žádnou paměť. Paměťová složitost pro dávku je O(N), potřebuj pole o 2*N prvcích, kde N je počet děr, proto na jednu díru to vychází 2 (konstantní paměťová složitost na dealokaci). K řazení používám HeapSort a to průběžně, nejprve tam díry nasypu a pak je vybírám seřazeně a slučuju a sypu to do další heapy, kde se to řadí podle velikosti. HeapSort má složitost NlogN.
Alokátor pak dává přednost seznamu děr tak, že alokuje inkrementálně v té největší. Pokud nelze alokaci uspokojit v té největší díře (protože už byla předtím obsazena jinými alokacemi), zbývající nevyužité místo se nechá zatím ležet ladem a sáhne se pro další volnou díru v seznamu. Pokud se ale požadavek nevejde ani tam, rovnou se přistoupí ke klasické inkrementální alokaci na konci. To že je seznam seřazen má výhodu v tom, že nemusím procházet žádný seznam a že hned vidím, zda najdu dostatečnou díru na alokaci nebo ne. Proto konstantní složitost alokace.
Nevýhodu bych viděl v nižší efektivitě čelit fragmentaci. Protože se nepoužívá strategie best-fit, ale spíš first-fit (přesnějí largest-fit), nemusí na malé bloky vůbec vyjít řada protože jak se zmenšuje largest, přechází se postupně na klasickou inkrementální alokaci a roste i množství děr dočasně ležících ladem. Takže dřív nebo později se zase spustí dávka, posbírá je a seřadí. Malé díry se takto protočí i několikrát, než v nich někdo alokuje, větší šanci mají, když se je podaří poslučovat do většího souvislého bloku.
To všechno je podřízeno rychlosti. Nevýhodou také v jednovláknovém prostředí je, že dealokace nemá vždy stejnou složitost, protože většinu času je 1, ale když alokátor rozhodne spustit dávku, může to celé vlákno nachvíli pozastavit. Pustit to v separátním vlákně je tedy lepší.
Chtěl jsem původně porovnat různé strategie a podívat se, zda už tohle někdo neimplementovat. Nikdy nevěřím na možnost, že bych vymyslel něco, co už někdo nezkusil předemnou, abych se případně vyhnul opakování stejných chyb.
Zobrazit příspěvky
se mi nelíbí, staví na begin() a end() což nepovažuji za šťasné.