Strategie alokování paměti v C++

Strategie alokování paměti v C++
« kdy: 25. 03. 2011, 11:59:23 »
V C++ se nějakou dobu zabývám nejvhodnější alokační strategií pro různé situace. V diskuzích o Javě a GC jsem psal o alokacích do clusterů a dočasných alokátorech a podobně, v zásadě z toho vyplynulo, že pro každý algoritmus je vhodná jiná alokační strategie.

Nicméně, při vyvoji jsem  objevil alokační strategii, která (zatím jen teoreticky) vykazuje alokační složitost O(1) a dealokační složitost O(log N), kde N je počet dealokovaných bloků s možností provádět dealokaci na pozadí.

Hledal jsem na internetu nějaké zdroje zabývající se alokačními strategiemi, ale moc hledat neumím. Nevíte někdo o nějakém uceleném seznamu teoretických pracech, článcích, kteří se tématem zabývají? Jde mi o analýzu problémů a srovnání výhod a nevýhod různých metod, abych případně mohl následně mou strategii naimplementovat a vyzkoušet, nebo poslat k ledu.

Případně je možné rozvinout diskuzi zde.
« Poslední změna: 25. 03. 2011, 12:39:37 od Petr Krčmář »


František

Re: Strategie alokování paměti v C++
« Odpověď #1 kdy: 25. 03. 2011, 18:41:39 »
Mimochodem co je to alokační složitost? Měříte složitost časem (počet operací při alokaci/dealokaci), pamětí (paměť vyžadovaná samotným alokátorem k provedení alokace/dealokace), počtem nutných synchronizačních zámků při (de)alokaci při sdílení paměti vlákny/procesy...

Re: Strategie alokování paměti v C++
« Odpověď #2 kdy: 25. 03. 2011, 19:56:56 »
Jde o casovou slozitost. Pametova slozitost je konstantni, stejne tak synchronizacni. Pokud jde o dealokaci na pozadi, je-li provadena v jednom vlakne oddeleneho od uzivatelskych vlaken, ma synchronizace konstantni slozitost a pocas provadeni operace neni allokator blokovan.

(kontantni slozitost znamena konstantni pocet synchronizacnich operaci na jednu operaci alokace/dealokace. zpravidle dve - zamknout a odemknout)

__dark__

Re: Strategie alokování paměti v C++
« Odpověď #3 kdy: 26. 03. 2011, 00:21:08 »
Ahoj,

jak píšeš, jde zejména o oblast použití. Při vývoji AsmJit jsem se setkal s jedním typem alokace paměti - tzv. ZoneAllocator. Jde o alokátor malých objektů, které většinou reprezentují AST. Alokace probíhá podobně jak v JVM, tedy pouhé přičtení offsetu v alokovaném bloku, v případě nedostatku paměti se alokuje další blok, atd. Dealokace se provede jednoduše tak, že se uvolní všechny alokované bloky (které byly alokované pomocí malloc() nebo jiného systémového alokátoru) - to způsobí zánik všech alokovaných dat/objektů/...

Další typ alokace, který jsem napsal a použil v knihovně Fog-Framework jsem nazval BlockAllocator. Je to alokátor, který se používá ve vícevláknovém prostředí - hlavní vlákno alokuje data pro objekty, které budou uvolněné v hlavním nebo jiném vlákně. Protože vím, že objekty budou rychle vznikat i zanikat, zvolil jsem velice jednoduchý způsob alokace/dealokace. Alokace je podobná ZoneAllocatoru z předchozího odstavce, jen se navíc eviduje u každého bloku velikost použité paměti, nikde se ale nezaznamenávají ukazatele. Pokud chci uvolnit alokovanou pamět, jen se z odkazu na blok odečte, kolik paměti vracím - pokud se toto číslo sníží na nulu, je blok volný a může se použít v další alokaci.

U obou alokátorů jsem dosáhl velmi dobrých výsledků. Alokace je v obou případech O(1), uvolnění je v případě ZoneAllocatoru okamžité a v případě BlockAllocatoru zase O(1).

Re: Strategie alokování paměti v C++
« Odpověď #4 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.


Re: Strategie alokování paměti v C++
« Odpověď #5 kdy: 26. 03. 2011, 12:56:50 »
Kdysi jsem řešil něco podobného, bo původní alokátory byly přinejmenším v multi-thread naprosto příšerné.

Optimalizoval jsem jen malé bloky, velké příliš používané nejsou. Strategie je celkem triviální, ale účinná (O(1)). Do nějaké velikosti byl seznam 8-byte, 16-byte, 24-byte, 32-byte atd., od větších velikostí vždy po 1.5 násobku. Alokoval se vždycky velký blok a ten se rozsekal na menší a strčil se vždy celý řetězec do toho seznamu. Výhodou byl výskyt bloků pro stejné účely v rámci stejného kusu paměti, což je dobré pro cache (na druhé straně dvojice node-objekt byla v různých částech, ale snad to procesor zvládal :) ). Při dealokaci se jen zkontrolovala velikost a strčila se do správného seznamu - základní úvaha je, že když byl daný blok jednou třeba, bude někdy v budoucnu opět využit. Spojování děr apod. jsem tedy vůbec neřešil, stejně by to jen nadělalo zmatek pro cache.

Samozřejmě, pro hodně-multi-thread vytížené serverové věci je dobré mít ještě per-thread cache, buď s explicitním nebo implicitním uvolňováním po nějakém počtu alokací. To hromadné uvolnění je velice levné - jen O(1) pro celý řetěz bloků stejné velikosti.

Re: Strategie alokování paměti v C++
« Odpověď #6 kdy: 26. 03. 2011, 13:26:45 »
Specialoziovane alokatory jsou rozhodne lepsi pro urcitou tridu uloh. Ja treba pouzivam specializovane alokatory, kde jsou jeji instance "per container" a pokud je kontejner pouzit v ramci jednoho vlakna, neni treba je zamykat. A v pripade, ze se kontejner sdili, resi si zamykani sam, takze i tady to odpada. Pro alokaci uzlu ve strome, spojovych seznamu a podobne mam CLusterAllocator, ktery vytvari clustery pro objekty stejne velikost a tam je alokace konstantni a dealokace (v dusledku nutnosti podle adresy vyhledat patricny cluster) asymtoticky log N.

Vsechny tyhle alokatory maji dve nevyhody. Samy nejsou efektivni (jak velke clustery pro mapu?) s tim souvisejici hodne mista, ktere lezi ladem a ceka ze mozna nekdy v budoucnu bude potreba.

Dalsi nevyhodou je to, ze kdyz dojde vyhrazene misto, nastupuje opet malloc, jehoz casova a pametova slozitost, rezie a MT propustnost je neznama a casto velice neoptimalni.

Ale jiste, je urcite dobre alokaci rozdelit vhodnou formou rozdel a panuj a pak to ma lepsi zejmena casove slozitosti