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ů III - Bredyho blog - Ondřej Novák
Bredyho blog - Ondřej Novák

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


V předchozích dvou dílech jsme si ukázali nástroje na alokaci bloků stejné velikosti. Nyní tedy není problém alokovat libovolné množství bloků fixní velikosti. Nastává tedy okamžik, kdy tyto nástroje použít k alokaci libovolně velikého bloku.

Třída Alokátor

Všechny nástroje máme připravené. Umíme pomocí třídy ChunkMaster alokovat libovolné množství bloků stejné velikost. Jak tedy využít tuto třídu k alokaci bloků různých velikostí?

Řešení je celkem jednoduché. Vytvoříme kontejner objektů vycházející ze třídy ChunkMaster, každý pro jinou alokovatelnou velikost. Podle požadavku na velikost bloku pak vybereme příslušný objekt a v něm provedeme alokaci.

Tohle se zdá jednoduché, teď musíme vybrat vhodný kontejner. Pravděpodobně vás napadla mapa nebo množina. Podle velikosti vyhledáme v mapě objekt, a zavoláme funkci Alloc. Na začátku nemusíme vytvářet všechny ty objekty, můžeme je vytvářet až v okamžiku prvního požadavku na alokaci dané velikosti. Prostě, není-li objekt typu ChunkMaster v kontejneru nalezen, založí se nový.

Nevýhodou použití mapy je její složitost, která se v nejlepším případě pohybuje okolo log n. Je pravdou, že alokace v ChunkMasteru má také občas složitost log n, takže složitost hledání v mapě by nás nemusela tolik bolet. Prakticky je alokace v ChunkMasteru rychlejší, zejména kvůli různým optimalizacím, jenž redukují počet případů, kdy je pro alokaci skutečně třeba prohledávat mapu. Při úspěchu optimalizací jsme schopni dosáhnout konstantní složitosti. Zavedením mapy v tříde Alokátor by jsme prakticky degradovali všechny optimalizace v ChunkMasteru

Proto třída Alokátor použije jednoduché pole, kde pro každou velikost, kterou je možné alokovat bude existovat položka. Použijeme pole ukazatelů. V poli se tak mohou vyskytovat i položky s NULL. Výběr vhodného objektu pro alokaci pak má složitost konstantní.

Na první pohled je zřejmé, že pole velikostí bude konečné. Musíme si stanovit limit velikost alokace. Všechny alokace nad limit pak budeme přímo předávat mallocu. Tohle řešení je efektivní. Alokátor tak může být použit pro alokaci libovolné velikost. Sám je však efektivní pouze pro alokaci malých bloků. U velkých bloků ta efektivita není oproti použití mallocu výrazná, troufnu si říct, že malloc může být v některých případech efektivnější.

Vnitřnosti alokátoru

Začátek třídy Allocator vypadá následovně:

class Allocator
{
///list of chunk masters
ChunkMaster **_list;
///list size
size_t _listSize;
///chunk size limit
size_t _maxChunkSize;
public:
_list
Pole objektů typu ChunkMaster je zde implementováno dynamicky, jako pole ukazatelů. Má to svůj důvod. Dokud nepoužijeme jedinou "malou" alokaci, nedojde k alokaci žádné pomocné paměti. První "malá" alokace alokuje pole a v něm alokuje jednu instanci ChunkMasteru. Takto ušetříme nějakou paměť.
_listSize
Bude udávat velikost seznamu, čili počet prvků ChunkMaster.
_maxChunkSize
Udává maximální velikost celého chunku. Třída přepočítá tento údaj a vypočte maximální počet položek uložitlných do jednoho chunku.

Problém: zarovnání

Řekli jsme si, že se jedná o alokátor malých objektů. Alokátor umí pro nás alokovat objekt velikost od 1 bajtu výše. Nemůžeme však alokovat libovolnou velikost. Pro efektivní běh programu je potřeba, aby veškeré alokace začínali na adrese dělitelné 4 (resp. 8 na 64bitové architektuře). Pouze alokace bloku o velikosti 2 bajty musí začínat na adrese dělitelné dvěmi a alokace bloku o velikosti 1 bajt může začínat kdekoliv. Z toho také vyplývá, že alokace 3 bajtů ve skutečnost znamená alokaci 4 bajtů. Všechny další možné velikosti pak jsou zarovnány nahoru na číslo dělitelné 4 (resp. 8).

V kapitole výše jsme si vyhradili pole pro každou alokovatelnou velikost. Je tedy zřejmé, že na položkách které nejsou dělitelné 4 bude za každých okolností NULL. Je otázkou, jak moc to vadí. Pro ušetření paměti můžeme provést následující úpravu:

int index; //index v kontejneru
size_t finsize;//upravena velikost
if (size>2) //size je velikost, nulu neuvažujeme
{
index = (size+3)>>2; //(index + 3) / 4 vypocet indexu v tabulce
finsize = index<<2; //vypocet nove velikosti
index += 1; //prvni dva indexy jsou vyhrazeny na 1,2 ... <3,4> -> 2, <5,8> -> 3, atd
}
else
{
finsize = size; //konecna velikost je rovna puvodni
index = size - 1; //1 -> 0, 2 -> 1
}

Výpočet ušetří nějakou paměť za cenu delšího zpracování.

Dealokace

Řekli jsme si, že alokátor se při výběru podřízeného objektu typu ChunkMaster rozhoduje podle velikosti. Jak to je ale s dealokací? Jak zjistíme, v jakém dealokovat?

Standardní delete nám dodá pouze ukazatel. Z ukazatele ovšem velikost nezjistíme. Mohli by jsme si ji poznamenat do každého bloku, ovšem tím by se ztratila efektivita alokátoru malých bloků.

Je zřejmé, že pro dealokaci musíme velikost získat jinudy. Naštěští, C++ definuje variantu delete která kromě ukazatele dodá velikost bloku v parametru. Má následující prototyp

void operator delete(void *ptr, size_t sz);

Pokud zadefinujeme tento operátor, a vyzkoušíme alokace a dealokace, zjistíme, že to opravdu funguje. Přitom se můžeme přesvědčit, že velikost bloku se skutečně nikam nepoznamenává. Jak je to možné?

Velikost paměti, kterou objekt obsazuje, lze totiž spočítat. Přesněji, je známa již během překladu. V případě, že likvidujeme jakýkoliv jednoduchý objekt, je velikost přímo spočítatelná ze sizeof. A překladač toto číslo použije. Horší situace nastane, pokud likvidujeme objekt potomka za pomocí ukazatele předka. V takovém případě se pro destrukci používá virtuální destruktor, který zajistí zničení celého objektu. Překladač tedy nemůže použít sizeof na typ ukazatele (jenž je použit na referenci likvidovaného objektu). Povědomí o celkové velikosti objektu má destruktor potomka, který si při destrukci umí udělat sizeof.

Když nahlédneme do přeloženého kódu programu, zjistíme, že každý destruktor se chová jako funkce, jenž vrací celé číslo. A právě toto vrácené číslo představuje velikost celého objektu, s nímž lze posléze zavolat operátor delete.

Listing

Dnes si ukážeme pouze vlastní alokátor. V příštím díle bude k dispozici celý funkční zdrojový kód.

class Allocator
{
///list of chunk masters
ChunkMaster **_list;
///list size
size_t _listSize;
///chunk size limit
size_t _maxChunkSize;
public:
Allocator(size_t maxSmallBlock, size_t maxChunkSize):_list(0),_listSize(maxSmallBlock),_maxChunkSize(maxChunkSize) {}
~Allocator()
{
if (_list)
{
for (unsigned int i=0;i<_listSize;i++) ::delete _list[i];
::delete [] _list;
}
}

void *Alloc(size_t sz)
{
if (sz==0) sz=1;
if (sz>_listSize) return new char[sz];
if (_list==0)
{
_list=new ChunkMaster *[_listSize];
for (unsigned int i=0;i<_listSize;i++) _list[i]=0;
}
if (_list[sz-1]==0)
{
size_t slots=_maxChunkSize/sz;
if (slots<0) slots=1;
if (slots>255) slots=255;
_list[sz-1]=new ChunkMaster((unsigned char)slots);
}
return _list[sz-1]->Alloc(sz);
}
void Free(void *p, size_t sz)
{
if (p==0) return ;
if (sz==0) sz=1;
if (sz>_listSize)
{
delete [] (char *)p;
return;
}
assert(_list[sz-1]!=0);
_list[sz-1]->Free(p,sz);
}
void ReportUsedBlocks(const IChunkReport &report)
{
if (_list==0) return;
for (unsigned int i=0;i<_listSize;i++)
if (_list[i])
_list[i]->ReportUsedBlocks(report,i+1);
}
};

Závěr

Seriál se blíží k závěru. V posledním díle dokončíme Alokátor a zabalíme ho do nějaké úhledné třídy, která bude řešit alokace obecně, a bude řešit alokaci ve více vláknech. Ukážeme si i jak zapojit alokátor do aplikace a nakonec bude přiložen zdrojový kód celé knihovny.

vytvořeno: 8.3.2007 09:22:52, změněno: 8.3.2007 09:22:52
Jsou informace v článku pro Vás užitečné?
  • (0)
  • (0)
  • (0)
  • (0)
  • (1)
Nick nebo OpenID
Vzkaz
 
25.7.2016 18:25:41

RunVwU5W

Dat wist ik niet. Ik heb er ook nog niet echt in verdiept. Toch ook &#8216;de Zilveren lepel&#8217; maar aanschaffen. Het is wel een lekker recept dit. Misschien een nieuwe titel verannnei?Vzn Maaike op 11.10.07 9:24 am

Podobné články

Efektivní alokátor malých objektů II

Pokračování seriálu Efektivní alokátor malých objektů I

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: