Deprecated: mysql_connect(): The mysql extension is deprecated and will be removed in the future: use mysqli or PDO instead in /home/www/novacisko.cz/subdomains/bredy/init.php on line 11

Warning: mysql_connect(): Headers and client library minor version mismatch. Headers:50562 Library:100020 in /home/www/novacisko.cz/subdomains/bredy/init.php on line 11

Warning: Cannot modify header information - headers already sent by (output started at /home/www/novacisko.cz/subdomains/bredy/init.php:11) in /home/www/novacisko.cz/subdomains/bredy/index.php on line 38
Efektivní alokátor malých objektů II - Bredyho blog - Ondřej Novák
Bredyho blog - Ondřej Novák

Efektivní alokátor malých objektů II

V minulém díle jsme si představili objěkt Chunk jako objekt, který provádí efektivní alokace malých objektů stejné velikosti. Řekli jsme si, že počet objektů v jednom chunku je limitován na maximální počet 255. (nikoliv 256).

V dnešním díle se pokusíme využít chunky k odstranění limitu.

ChunkMaster, správce chunků

Stále ještě předpokládejme, že budeme alokovat objekty stejné velikosti, tedy že požadavky na alokaci budou vždy mít stejnou požadovanou velikost. Co teď vadí víc je limit 255 alokací na chunk.

Ukázali jsme si důvody, jak tento limit vznikl a zjistili jsme, že není vhodné se snažit tento limit obcházet na úrovni chunku. Můžeme přeci použít víc chunků...

ChunkMaster je třída, která implementuje kontejner chunků a jejím úkolem je vhodně alokovat a spravovat alokované chunky. Podívejme se na vnitřní strukturu.

class ChunkMaster
{
typedef std::set<Chunk *> ChunkSet;
typedef std::set<Chunk *> FreeChunkSet;
typedef ChunkSet::iterator ChunkSetIter;
typedef FreeChunkSet::iterator FreeChunkSetIter;

///List of all allocated chunks
ChunkSet _chunks;
///Pointer to chunk that was recently used for allocating
Chunk *_lastAlloc;
///Pointer to chunk that is complette free and waiting for deleteing
Chunk *_wholeEmpty;
///Pointer to chunk that has been recently subject of deallocation
Chunk *_lastFree;
///List of chunks that contains some empty space
FreeChunkSet _freeChunks;

///count of slots in one chunk
unsigned char _maxSlots;
public:
...
}

Členění chunků

Chunky nalezneme

  • Plně obsazené (full)
  • Částečně obsazené (some empty)
  • Prázdné (empty)

ChunkMaster obsahuje

  • Množinu všech chunků, které spravuje.
  • Podmnožinu referencí na částečně obsazené chunky
  • Jednu pozici pro prázdný chunk.
  • Ukazatel na chunk ve kterém se naposledy alokovalo.
  • Ukazatel na chunk ze kterého se naposledy dealokovalo.

Jak ChunkMaster funguje a problémy s tím spjaté

Při návrhu třídy spravující chunky narazíme na několik zádrhelů. Alokace pomocí třídy je snadná a pochopitelná. Buď se využije některá množina poloprázdných nebo prázdných chunků, případně se zaalokuje nový chunk. S dealokací je to o mnoho horší. Operátor delete (pokud jej využijeme) neposkytuje příliš mnoho informací. K dispozici máme jen ukazatel na paměťový blok, který program chce uvolnit. Není vlastně ani praktické si s adresou bloku pamatovat adresu chunku, kterému blok patří. Je potřeba ten příslušný chunk nalézt jinak.

Možností je více. Například si při alokaci bloku rezervovat místo na zpětný ukazatel. Nicméně tím se vzdáme myšlenky "alokace malých bloků". Bude lepší se obejít bez ukazatele. Pak nám tedy zbývá použití mapy nebo množiny. V deklaraci ChunkMasteru najdeme set<Chunk *>. To už hodně napovídám. Stačí, když množina bude seřazená podle adresy ukazatele na chunk. Budeme-li v množině hledat adresu chunku podle adresy dealokovaného bloku, nejspíš nic nenajdeme, ale můžeme také hledat prvek, který je největší ale zároveň menší než adresa dealokovaného bloku. Pak pouze stačí ověřit, že adresa se skutečně nachází uvnitř chunku a spočítat index.

Je zřejmé, že toto hledání bude mít nejhorší složitost log N. Můžeme tedy konstatovat, že dealokace nebude v konstantním čase.

Avšak lze této složitosti pomoci a získat v průměru složitost lepší. Předpokládá se, že bloky alokované v jednom místě programu (pospolu) budou pravděpodobně dealokovány také pospolu. K tomu nám pomůže ukazatel na chunk, ze kterého se naposledy dealokovalo.

A nyní algoritmicky popsaná činnost ChunkMasteru.

alokace
  1. Pokud je obsazen ukazatel na chunk poslední alokace, zkus alokovat v něm -> při úspěchu konec, hotovo.
  2. Pokud je obsazen chunk poslední dealokace, zkus alokovat v něm ->při úspěchu konec, hotovo
  3. Pokud je podmnožina částečně obsazených chunků neprázdná, vyber jeden chunk a alokuj v něm. Pokud se stane chunk plným, odstraň ho z podmnožiny. Jinak jeho adresu ulož do ukazatele poslední alokace -> hotovo
  4. Ve všech ostatních případech alokuj nový chunk, alokuj v chunku a zařaď chunk do obou množin a obsaď ukazatel poslední alokace.
dealokace
  1. Patří adresa chunku, jenž je referencován ukazatelem chunku s poslední dealokací? Ano, dealokuj v něm. Je-li chunk prázdný, odstraň jej ze všech množina obsaď jeho pozici pro prázdný chunk. Je-li ale tato pozice obsazená, nejprve dealokuj předchozí chunk. -> hotovo
  2. Patří adresa chunku, jenž je referencován ukazateelm chunku s poslední alokaci? Ano, dealokuj v něm. Je-li chunk prázdný, odstraň jej ze všech množina obsaď jeho pozici pro prázdný chunk. Je-li ale tato pozice obsazená, nejprve dealokuj předchozí chunk. -> hotovo
  3. Najdi chunk v množině.
  4. Dealokuj v něm
  5. Byl-li chunk plný, vlož jej do množiny částečně obsazených chunků.
  6. Je-li chunk prázdný, odstraň jej ze všech množina obsaď jeho pozici pro prázdný chunk. Je-li ale tato pozice obsazená, nejprve dealokuj předchozí chunk.

Při každé alokaci a dealokaci se aktualizují ukazatelé poslední akce. Pouze v případě, že při alokaci se chunk naplní se pozice poslední alokace neobsazuje. Stejně tak pokud při dealokaci se chunk vyprázdní, neobsazuje se pozice poslední dealkoace. Při vyprázdnění chunku zůstává chunk stále ještě alokován. Dealokuje se až po vyprázdnění dalšího chunku. To proto, aby se eliminovaly situace střídavého alokování a dealokování, pokud dochází opakovaně k vyprázdňování jednoho chunku. Dealokace a alokace celého chunku by nás stálo zbytečnou režii.

V tomto místě se má implementace liší od implementace Anree Alexandresca, který pro podobný kontejner používá obyčejný seznam. Domnívám se, že efektivita hledání množině je vyšší, než hledání v seznamu. Na druhou stranu, správa množiny přináší nějakou režii,protože pro pomocní instance množinu se tyto alokátory nepoužijí (leda vylepšit množiny nějakým speciálním alokátorem).

Všimněte si
ChunkMaster vede informaci o velikosti chunku (je konstantní, uvádí se v počtu prvků na chunk). To proto, že co instance třídy, to možnost jiného počtu prvku na chunk. Stále však nevede velikost jednoho prvku. Protože i zde je pro ChunkMaster velikost konstantou, kterou obdrží při volání funkcí pro alokaci a dealokaci. Je úkolem objektu, který ChunkMastera ovládá, aby zajisti, že velikost je pro jednu instanci třídy ChunkMaster konstantní.

Závěr kapitoly

ChunkMaster řeší limit chunku na počet alokací pomocí kontejneru chunků v podobně množiny (set). Alokace pomocí ChunkMaster je v nejhorším případe stejná jako alokace pomocí standrdního new a to zejména díky potřeby alokovat chunky pomocí new. Avšak protože se počet alokací díky chunkům a jejich organizaci výrazně redukuje, je složitost o konstantu lepší, v dlouhodobém průměru se blíží až ke konstantní složitosti.

Dealokace má v nějhorším případě složitost standardní ho delete a to nutností chunk občas dealokovat. Opět množství dealokací se výrazně redukuje a v průměru dosahuje spíš složitosti log N, ovšem díky několika optimalizacím bude vždy rychlejší, než standardní delete. V určitých případech se průměrná složitost může blížit složitosti konstantní.

Příště si povíme o zatřešujícím objektu Allocator. Ten bude pomocí ChunkMasterů řešit alokace libovolné velikosti.

Efektivní alokátor malých objektů III

SmallAllocII_Listing.h Výpis programu. Obsahuje jak ChunkMaster tak Chunk z předchozí kapitoly. ChunkMaster lze použít jako plněhodnotný alokátor instancí jedné třídy.
vytvořeno: 23.1.2007 11:18:59, změněno: 23.1.2007 11:21:57
Jsou informace v článku pro Vás užitečné?
  • (1)
  • (0)
  • (0)
  • (0)
  • (0)

Podobné články

Efektivní alokátor malých objektů III

Třetí díl seriálu o alokaci paměti. Předchozí díl Efektivní alokátor malých objektů II

Efektivní alokátor malých objektů I

Traduje se, že používání new a delete v OOP může mít výkonostní dopady. Toto zjištění se skutečně opírá o reálný základ. Ale my si ukážeme, že new a delete mohou být mnohem efektivnější.

FastAllocPool - urychlení častých alokací a dealokací

Pokud v programu z nějakých důvodů potřebujeme často provádět new a delete nad některými třídami, můžeme zvýšit efektivitu těchto operací zavedením poolu předalokované paměti

Vracíme z funkce objekty

Podívejme se blížeji na to, jakým způsobem je implementováno vracení výsledku z volání funkcí. Zboříme při tom všelijaké mýty

Garbage collector v C++ - Popis API tříd kolekce LightSpeed::GC

V tomto článku si představíme rozhrani Garbage Collectoru v knihovně LightSpeed. Princip GC byl přidstaven v předchozím díle
Reklama: