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
FastAllocPool - urychlení častých alokací a dealokací - Bredyho blog - Ondřej Novák
Bredyho blog - Ondřej Novák

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


Občas nastane situace, kdy je třeba pracovat s objekty s krátkou dobou života tak, že standardní zásobník nestačí. Například při vracení instancí z funkcí, u kterých nelze aplikovat postupy popsané v články Vracíme z funkce objekty, dále pak různé dynamické objekty, které vznikají a zanikají nezávisle na provádění programu, například vnitřní reprezentace iterátorů.

Pro tyhle objekty lze použít Efektivní alokátor malých objektů ale jak záhy zjistíme, i přesto že tento alokátor má někdy složitost blízkou 1, i tak může být pomalejší, než by jsme si přáli a navíc je navržen pro alokaci malých objektů, takže časté alokace objektů větších se stejně neurychlí. Navíc použití tohoto alokátoru v programu je kanón na vrabce, protože implementace samotného alokátoru není jednoduchá. Přichází v úvahu pouze tam, kde se alokátor již používá na vícero místech.

Opravdu malý a efektní alokátor pro časté alokace a dealokace je alokátor s předalokovaným poolem, nebo řekněme alokátor s cache. Princip alokátoru je jednoduchý, jakmile zanikne nějaký objekt voláním delete, uvolněná paměť se zachytí do speciálního poolu, ze kterého je možné ji vyzvednout a to skutečně se složitostí 1. Pool je totiž origanizován jako spojový seznam (zásobník).

Pojdme se podívat na nějaké řešení poolu.

Prvně začneme tím, že si navrneme nějakého správce poolu, třídu která bude tím poolem. Zatím nebudeme řešit to, jak bude zaintegrovaná do systému a jak či zda bude volána pomocí new a delete. Prozatím tedy pouze základ.

template<size_t sz>
class AllocPool {
};

Všimněte si, že je to šablona s parametrem velikost. Nebude se tedy jednat o jeden pool, ale poolu budeme mít v aplikaci tolik, kolik máme různých objektů. Také je dobré povšimnout si, že používám velikost a nikoliv T jako typ objektu, který k alokaci využívá pool. To mi umožňuje vytvářet sdílené pooly, kdy dva objekty, které zabírají stejné množství paměti využijí stejný pool. Sdílení je v celku důležitá vlastnost, protože příliš mnoho poolů může vést k vyčerpání volné paměti i přesto, že v paměti nemusí být jediný alokovaný objekt (vyčerpá ji cache).

Nyní si nadefinujeme jak bude vypadat jedna položka poolu, jinými slovy, přímo onen blok rezervované paměti. Napíšeme to čistě v C++, byť se nabízí sáhnout do low-level programování

struct AllocItem {
AllocItem *nextItem;
char padding[sz - sizeof(AllocItem_t *)];
};

Jedná se o spojový seznam, kde prvním prvkem struktury je ukazatel na další prvek. Zbytek struktury je padding, neboli pro účely cache nevyužitá paměť, avšak důležitá pro umístění nového objektu při alokaci. Všimněte si, že padding je velký jako sz ovšem po odečtení ukazatele. Jakmile je totiž blok alokován, není ukazatel již potřebný a tak je zbytečné, aby byl jaksi navíc. Také je zřejmé, že bloky menší než velikost ukazatele nelze tímto systémem spravovat. Následně si stejně ukážeme, že toto omezení můžeme díky zarovnání (align) zanedbat.

Do AllocPool třídy si dopíšeme ještě tyto členské proměnné

   size_t count;
AllocItem *list;

Je dobré vědět velikost poolu bez počítání délky řetězu. A také zde máme ukazatel na první prvek v řetězu. A můžeme začít psát metody.

Nejprve si ujasníme výčet operací

  • alokace
  • dealokace
  • odstranění cache (někdy se to hodí)
  • statistické funkce (například zjištění vělikosti cache)

Protože pravděpodobně budeme pracovat se singletonem, musíme si přidat funkci

  • získání singletonu.
void *alloc();
void dealloc(void *ptr);
void freeCache();
size_t getSize();
static AllocPool *getPool();

Dosud jsem nemluvil o tom, že naše cache by měla mít nějaký limit na velikost. Co se stane, když naše aplikace znenadání uvolní 1.5GB objektů jedné velikosti a namísto toho alokuje 1.5GB objektů jiné velikosti? Na 32-bitovém stroji zcela určitě výjimku nebo pád. Nastavení limitu cache můžeme udělat třeba pomocí členské proměnné. Jenže kdo bude ten limit konfigurovat? A co když pro různé třídy chci definovat různé limity? Navzdory tomu, že se budou sdílet...

Já volil metodu určení limitu parametrem funkce dealloc. Limit se převezme z parametru šablny patřící pak konkrétní třídě. Není to úplně ideální varianta, ale umožňuje mi to různým třídám věnovat různé limity podle předem známého vzorce chování alokací a dealokací. Takže upravme

void dealloc(void *ptr, size_t limit);

Nyní metody implementujme.

void *alloc() {
if (list) {
void *ret = list;
list = list->nextItem;
count--;
return ret;
} else {
return operator new(sz);
}
}

Na funkci alloc není nic zvláštního. Pokud existuje nějaká položka v seznamu list, vyzvedne se, a seznam se o tuto položku zkrátí. Vyzvednutý blok se vrací jako výsledek. Operace má složitost 1. Pokud máme seznam prázdný, funkce pouze zavolá původní new. Povšimněte si, jak je new voláno, mimochodem jediný legální způsob, jak alokovat paměťový blok, který není spojen s vytvářením instance objektů. (oblíbené 'new char[...]' totiž volá jiný operátor a to nemusí být totéž).

void dealloc( void *item, int limit) {
if (count>=limit) {
operator delete (item);
} else {
AllocItem *itm = reinterpret_cast<AllocItem *>(item);
itm->nextItem = list;
list = itm;
count++;
}
}

operace dealloc kontroluje, zda velikost seznamu je větší nebo stejný než nastavený limit. Pakliže ano, provede se obyčejné delete. Jinak alokovaný blok je uložen do cache jako položka AllocItem vložením do spojového seznamu držený v proměnné list. V tomhle případě má dealloc složitost 1.

void freeCache() {
while (list) {
AllocItem *k = list;
list = k->nextItem;
operator delete(k);
}
}

Funkce odstraní všechny bloky seznamu list tak že postupně vyzvedává jeden po druhém a volá na ně operátor delete. Tím se paměť uvolní.

size_t getSize() const {return count;}
static AllocPool *getPool() {
static AllocPool pool;
return &pool;
}

AllocPool(): list(0) {}
~AllocPool() {freeExtra();count=~0;}

Povšimněte si získání singletonu. Tato metoda je celkem nejpoužívanější, ale přesto není bez problémů. Jednak operace není MT safe, pokud se singleton zrovna vytváří. Zatímco ostatní operace lze obalit do zámků, získání singletonu zpravidla ne, protože v době prvního zavolání ještě zámky neexistují. Druhým problémem může být ukončování programu. Pokud první objekt instancujeme v prostřed aplikace a pak v destruktorech provádíme vyčistění, můžeme na konci programu obdržet hlášení o existenci leaku.

Proto destruktor nastavuje count na maximum (~0 = 0xFFFFFFFF...). I přesto, že se předpokládá, že objekt je po návratu z destruktoru zničen, nastavení count na maximum zabrání používání zničeného objektu k dealokaci. To nastává zejména při ukončování aplikace, kdy se stane, že destrukce poolu se provede dřív, než destrukce objektů alokovaných přes pool. Jakmile někdo zavolá dealloc(), podmínka na limit způsobí, že dealokace se provede zapomocí standardního delete, což v tuto chvíli postačuje.

Podívejme se nyní na zapojení třídy do implementace globálních new a delete. Je zřejmé, že používat tento pool se superglobálními operátory alokací a dealokací nelze. Z výhodou využijeme přetěžování operátorů v třídě a dědění.

Namísto abysme museli new a delete deklarovat v každé třídě, která má k alokaci použít pool, napíšeme si šablonu.

template <class T, int limit = 256>
class FastAllocPool {
static const size_t typeSize = sizeof(T);
static const size_t alignSize = sizeof(void *);
static const size_t alignedBlock = ((typeSize + alignSize - 1)/alignSize)
*alignSize;
public:
void *operator new (size_t asz) {
if (asz != typeSize)
throw std::invalid_argument("cannot allocate such a block");
return AllocPool<alignedBlock>::getPool()->alloc();
}
void operator delete(void *ptr, size_t asz) {
if (asz != typeSize)
throw std::invalid_argument("inconsistent delete called");
return AllocPool<alignedBlock>::getPool()->dealloc(ptr,limit);
}
};

K tomu pár postřehu:

  • Alokátory alokují v pool odpovídající velikosti třídy, kterou alokují, avšak zaokrouhlují velikost na nejbližší zarovnání. Jednak to může pomoci řešit problémy se zarovnáním a jednak se tak redukuje množství instancí poolů. Šablonu lze v případě upravit i tak, aby granualita byla větší a tím ještě více redukovat množství poolů, na druhou stranu se tím zvyšuje paměťová náročnost, pokud granualita je výrazně vyšší než alokované velikost
  • Alokátory očekávají, že se bude alokovat právě třída, která byla deklarovaná v šabloně. Nelze ověřit, že to je skutečně tatáž třída, ale lze ověřit, že požadovaná velikost odpovídá deklarované velikost. Pokud se liší, tato implementace vyhazuje výjimku. Situace nastává, pokud například dědíme třídu a zapomeneme předefinovat alokační operátory. Nicméně lze implementovat méně drastické řešení, které namísto výjimky provede alokaci nebo dealokaci standardním operátorem.

Použití této šablony je jednoduché. Stačí ji podědit.

class MojeRychleAlokovanaTrida: public FastAllocPool<MojeRychleAlokovanaTrida, 1000> {
....
};

Tím deklarujeme třídu, která používá alokátor pomocí poolu/cache a nastavuje limit cache na 1000 instancí. Pokud již třída dědí, není problém použít vícenásobnou dědičnost.

class MojeRychleAlokovanaTrida: public Rodic,
public FastAllocPool<MojeRychleAlokovanaTrida, 1000> {
....
};

Pokud dědíme třídu MojeRychleAlokovanaTrida, záleží opět na implementaci šablony. Výše uvedená šablona může vyhodit výjimku, nezbývá nám tedy redefinovat new a delete ve všech potomcích. Pokud místo výjimky provedeme standardní alokaci, lze dědění provést libovolně avšak instance potomka alokaci pomocí poolu nebude pravděpodobně používat.

NEZAPOMEŇTE DEKLAROVAT VIRTUÁLNÍ DESTRUKTOR
Tím si zaručíme, že i delete na předka proběhne přes pool.

Závěr

Když se podíváte na celý zdrojový kód, zjistíte, že je to velice krátký kód. Přesto velice užitečný, protože může často urychlit operace o několik desítek procent v závislosti na četnosti provádění alokací a dealokací. Proto si mýslím, že by tento alokátor měl být standardní výbavou standardní knihovny každého programátora.

Listing

template<size_t sz>
class AllocPool {
struct AllocItem {
AllocItem *nextItem;
char padding[sz - sizeof(AllocItem *)];
};
size_t count;
AllocItem *list;

public:

AllocPool(): list(0) {}
~AllocPool() {freeExtra();count=~0;}

void freeExtra() {
while (list) {
AllocItem_t *k = list;
list = k->nextItem;
operator delete(k);
}
}

void *alloc() {
if (list) {
void *ret = list;
list = list->nextItem;
count--;
return ret;
} else {
count = 0;
return operator new(sz);
}
}

void dealloc( void *item, size_t limit) {
if (count>=limit) {
operator delete (item);
} else {
AllocItem *itm = reinterpret_cast<AllocItem *>(item);
itm->nextItem = list;
list = itm;
count++;
}
}

static AllocPool *getPool() {
static AllocPool pool;
return &pool;
}
};

template <class T, int limit = 256>
class FastAllocPool {
static const size_t typeSize = sizeof(T);
static const size_t alignSize = sizeof(void *);
static const size_t alignedBlock = ((typeSize + alignSize - 1)/alignSize)
*alignSize;
public:
void *operator new (size_t asz) {
if (asz != typeSize)
return operator new(asz);
return AllocPool<alignedBlock>::getPool()->alloc();
}
void operator delete(void *ptr, size_t asz) {
if (asz != typeSize)
return operator delete(ptr,asz);
return AllocPool<alignedBlock>::getPool()->dealloc(ptr,limit);
}
};

Dodatek k Visual Studiu

Visual Studio výše uvedený zdroják nepřeloží, pokud jako parametr FastAllocPool<> uvedeme třídu, která tento pool dědí (což je běžná praxe). Oznámí nám na řádce, kde je deklarace FastAllocPool::typeSize, že pracujeme s nekompletní třídou. To je zřejmé, Visual Studio instanciuje konstanty při vytváření třídy, takže nemůže instanciovat konstantu typeSize, protože ještě neví, jak velika třída T bude. Kupodivu lze Visual Studio (VC8) obalamutit zabalením konstant do struktury a poupravit implementaci operátorů. Pak se překlad podaří, protože konstanty ve struktuře se instanciují až při použitá a to už je třída známá.

v GCCčku se i konstanty na hlavní úrovni instanciují až při použití, proto tam překlad proběhne bez problémů

template<class T, int limit = 256>
class FastAllocPool_t {
struct H {
static const size_t typeSize = sizeof(T);
static const size_t alignSize = sizeof(void *);
static const size_t alignedBlock = ((typeSize + alignSize - 1)/alignSize)
*alignSize;
};
public:
...
...
};
vytvořeno: 8.4.2008 19:40:59, změněno: 11.4.2008 01:22:02
Jsou informace v článku pro Vás užitečné?
  • (7)
  • (1)
  • (0)
  • (0)
  • (0)
Nick nebo OpenID
Vzkaz
 
5.2.2010 19:48:56

Ondra openid

Ano, zrovna konstrukce zde getPool() řešená přes static není bezpečná ani v MS ani v GCC. Já mám na to třidu Singleton, která vzniká před tím, než program zavola main(). Pak lze konstrukci zapsat

static AllocPool *getPool() {
return Singleton<AllocPool>::getInstance()
}

Třída Singleton<T> se opírá o staticky alokovaný objekt a může provádět inicializaci v kritické sekci, ve které lze vytvářet zámky bezpečně.
3.2.2010 08:59:36

marian

S tymi zamkami na singletone je to osemetne, aspon co som videl v clanku od Alexandrescu & Meyers, kde sa zo singletonu stalo same 'volatile' konstrukcie, kde problem je s vytvorenim singletonu a odporucanie je, vytvorit vsetky singletony v hlavnom vlakne.
5.1.2010 15:30:21

Ondra openid

PS: Ještě mě napadá, singleton je použitelný i v MT prostředí a je žádoucí, aby se cache sdílela (pokud tedy k není důvod proč by sdílení vadilo). Ale bude tam potřeba minimálně globální kritická sekce, spin-lock (jedna obyčejná proměnná) by také stačil, protože většina operací je velice rychlá.
5.1.2010 15:27:07

Ondra openid

1) Díky za reakci. Vícevláknově jsem to neřešil, předpokládal jsem to formou buď nějakého zámku na singletonu, nebo použít interlocked operace nad seznamem, což by asi zvedlo výkon, ale asi by to nebylo tak hezký na pohled.

2) To se dá řešit, musí se to znova podědit a protože překladač zahlásí ambignuitu, tak je potřeba předefinovat new a delete ručně. Já sám jsem nepředpokládal, že se to bude používat uvnitř hierarchie, ale že se to použije až na finálním objektu před jeho alokací, třeba jako vnitřní třída dedící originální

void foo() {
class MyClassFastAlloc: public MyClass, public FastAllocPool_t.... {
//nejaky konstruktor;
};

MyClass *inst = new MyClassFastAlloc(...);
//work with MyClass
}

Teoreticky by se na to dala vymyslet i nějaká šablona, která by takovou třídu vytvořila.

MyClass *inst = new MakeFastAlloc<MyClass>(...) {};

To už nechám na čtenářovi fantasii :-)
4.1.2010 14:18:18

marian

1. Pekny clanok, trochu mi chyba dotiahnutie vo viacvlaknovom prostredi. V tom pripade by sa ale nemohol pouzit v clanku uvedeny singleton; mohol by sa pouzit "double-check locking" a vymysliet destruovanie.
2. Nutnost redefinovania new/delete ak sa bude odvodzovat nova trieda XX od MojeRychleAlokovanaTrida definuje asi pravidlo, ze odvodzovat od FastAllocPool je vyhodne az na konci dedicskej hierarchie.

Podobné články

Efektivní alokátor malých objektů II

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

Multithreading v C++ (ve Win32) III - OOP a vlákna

Pokračování dokumentace k Multithreading v C++ (ve Win32) - Tentokrát si povíme něco o tom jak začlenit vlákna do OOP

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

Funkce s volitelným počtem argumentů v C++

Leckterý programátor v C jistě zná syntaxtický zápis funkce s volitelným počtem argumentů. V následujícím článku se podíváme na nevýhody tohoto nástroje a způsoby jak to implementovat jinak

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ší.
Reklama: