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

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


Knihovnu, kterou nyní budu popisovat vychází z myšlenek programátora a publicisty Anrei Alexandrescu, který podobnou knihovnu představil ve své knize Modern C++ Design (u nás pod názvem Moderní programování v C++ - Šablony, generické komponenty a návrhové vzory).

A nebyl bych to já, abych knihovnu trošku nepřepracoval. Nejprve se ale podívejme na klasické implementace new a delete

Pod lupou: new a delete

Když se podíváme blíže na implementaci new a delete, zjistíme, že se nejedná o nic komplikovaného. Operátor new je implementován funkcí malloc a operátor delete se implementuje přes funkci free. V různých platformách mohou být odlišnosti.

V zásadě ale bývají alokační operátory implementovány službami operačního systému, které nejsou zrovna efektivní, pokud jde o malé bloky dat. Bohužel právě v C++ často alokujeme instance tříd, které v průměru nejsou velké. Konečně podívejte se do svých programů a zkuste odhadnout paměťovou náročnost vašich tříd. Přitom neuvažujte paměť dodatečně alokovanou za života instance (ukazatel má 4 bajty).

Funkce přidělující paměť mohou efektivně alokovat paměť pro bloky velikosti řádově kilobajty. Bloky menší než cca 30bajtů pak mají mnohem větší režii, kterou si vyhrazuje vlastní alokátor na správu takové paměti. Navíc vyhledání vhodného volného bloku je méně efektivní, pokud je blok malý, než při alokaci velkého bloku. Alokační funkce vedou seznamy volných bloků ve vyhledávacích stromech, kde volné místo pro velké bloky je nalezeno díky tomu, že větve s malými fragmenty jsou vynechány prakticky ihned na začátku.

Dalším argumentem proti standardním alokátorům je fragmentace paměti. Je nanejvíš jasné, že uvolnění instance velikosti několika desítek bajtů způsobí vznik díry, kterou nelze přidělit prakticky nikomu (jen opět té samé třídě).

Motivace

Motivací je nalézt takový systém který by umožňoval

  • Převést problém malých bloků na problém velkých bloků (a využít efektivitu standardních alokátorů)
  • Alokovat a dealokovat v co nejkratším čase (ideálně v konstantním čase)
  • Redukovat fragmentaci.
  • Redukovat režii

V zásadě spolu tyto body úzce souvisí. Alokací větších bloků redukujeme fragmentaci, zároveň jsou alokace rychlejší (standardní alokátory jsou k tomu optimalizovány). Velké bloky mají v poměru měnší režii než malé bloky.

Otázkou je, jak vůbec provést první bod.

Alokace objektů stejné velikosti

Představme si, že víme, že náš program používá pouze jednu třídu, z níž vytváří mnoho instancí. Třída má vždy stejnou velikost. Tato velikost se může pohybovat od 1 do N bajtů. Napišme jednoduchý alokátor.

Tento úkol spěje k struktuře, kterou známe pod názvem pole. Je to pole dynamicky rozšiřovatelné, do něhož můžeme přidávata nové prvky a zase je mazat. Pole však vyžaduje zvláštní přístup

  • Každý prvek dostane adresu a tato adresa se nesmí v průběhu činnosti měnit
  • ... tedy vymazáním prvku se neprovede posun dat
  • ... je třeba efektivně využít uvolněné místo pro nové prvky
  • ... pole se nemůže rozšiřovat libovolně, ale pouze do určité velikosti dané velikostí alokovaného bloku v němž existuje. Protože další rozšířením by bylo nutné pole zkopírovat do většího alokovaného bloku, čímž bysme porušili první bod.

Chunk

Můj alokátor (stejně tak jako alokátor v výše uvedené knize) používá zvláštní třídy, která se nazývá Chunk. Hlavním účelem chunku je implementovat limitované pole prvků stejné velikosti, do kterého lze přidávat nové prvky, nebo je mazat.

Přidáním prvku se rozumí alokace prostoru, mazáním prvku se rozumí dealokace prostoru

 class Chunk
{
static const unsigned char EndOfChain=255;
unsigned char _firstFree;
unsigned char _usage;
unsigned short _align;
};

Překvapuje vás tak málo informací? Celý chunk se vejde do 2 bajtů. Protože 32-bitové počítače vyžadují zarovnání na 4 bajty, je začleněna položka _align, která chunk nafounke na 4 bajty. To je vlastně jediná škodlivá režie chunku, bohužel nedá se obejít.

Řekl jsem, že Chunk je pole. Kde to pole ale je? Musíme vstoupit na nižší úroveň programování a naimplementujeme třídu tak, že pole bude součástí instance třídy a bude začínat na adresách za _align. Alokace chunku pak nemůže být provedena pomocí new, ale pomocí malloc.

class Chunk
{
....
unsigned char *FirstSlot() const
{
return reinterpret_cast<unsigned char *>(const_cast<Chunk *>(this)+1);
}
};

Funkce vrací adresu prvního prvku v poli.

  • Dále možná hledáte informaci o počtu prvků. Tato informace je zbytečná, protože vše zajistí správce volného prostoru, který si vede stav v proměnné _firstFree. Pouze proměnná _usage obsahuje informaci o počtu alokovaných prvků, to proto, aby zjištění této hodnoty byla operace v konstantním čase.
  • Dále možná postrádáte informaci o velikosti prvku. I tato informace je zbytečná. Náš Chunk bude uložen do kontejneru dalších chunků a všem bude společná velikost prvku. Proto je zbytečně tuto informaci na chunk duplikovat.
  • Pak vás možná překvapí, že si vystačím jen s 8 bitovými položkami. Ano vystačím, protože si dále ukážeme, že Chunk může obsahovat maximálně 256 prvků. Není to žádný problém, jednak vytvářet větší Chunky by nepřineslo žádnou další efektivitu a jednak samotný blok alokovaný pro Chunk musí být předalokován tak, aby alokace v chunku byly uspokojeny bez nutnosti volat new. A snahou je, aby chunky nebyly malé, ani velké. 256 položek je akorát, u větších objektů to bude dokonce až moc.

Jak pracuje chunk

Máme zde dvě položky. Položku _firstFree a položku _usage. Položka _usage plní roli čítače alokovaného prostoru. Pokud je chunk prázdný, najdeme zde nulu. Pokud je plný, najdeme zde číslo odpovídající velikosti chunku.

Hlavní část práce je skryta v položce _firstFree. Ta obsahuje číslo prvního volného prvku. Čísluje se od 0. Pokud není volný prvek (chunk je plný), obsahuje hodnotu EndOfChain(255). Protože prvky na uvolněných pozicích nejsou k ničemu použity, využije je správce volného místa. Na každé volné pozici najdeme číslo dalšího volného prvku. Poslední volný prvek pak obsahuje EndOfChain. Vzniká tak spojový seznam volných bloků. Alokace bloku tedy znamená vyzvednutí prvního prvku ze spojového seznamu. Dealokace pak znamená návrácení bloku do tohoto seznamu.

Algoritmus alokace je jednoduchý.

  1. Vyzvedni _firstFree
  2. Je _firstFree==EndOfChain -> ano, chyba, chunk je plný
  3. zapamatuj si adresu prvku
  4. Přečti z této adresy číslo.
  5. Zapiš číslo do _firstFree
  6. zvyš _usage
  7. vrať zapamatovanou adresu.

Vidíte, že alokace je v konstantním čase.

Algoritmus uvolnění paměti

  1. sniž _usage
  2. přečti _firstFree
  3. zapiš ho na adresu uvolňovaného prvku
  4. do _firstFree zapiš index uvolňovaného prvku

I dealokace je v konstantním čase.

Všimněte si
Používáním 8-bitových indexů pro správu volného místa nám umožňuje vytvářet chunky pro alokaci instancí velikosti právě jednoho byte. Lze takto alokovat až 255 instancí velikosti jednoho byte, s prakticky nulovou režií a v konstantním čase.

Alokace chunku a alokace uvnitř chunku

Následuje výpis funkcí chunku. Alokaci celého chunku hledejte jako druhou funkci. InitChunk "formátuje" chunk. Všimněte si, že velikost prvku a počet prvků v chunky se předává jako parametr.

   void InitChunk(size_t sz, unsigned char maxSlots)
{
unsigned char *chkbeg=FirstSlot();
for (int i=0;i<maxSlots;i++) chkbeg[i*sz]=(unsigned char)(i+1);
chkbeg[(maxSlots-1)*sz]=EndOfChain;
_firstFree=0;
_usage=0;
}

static Chunk *AllocChunk(size_t sz, unsigned char maxSlots)
{
Chunk *chk=reinterpret_cast<Chunk *>(::new char[maxSlots*sz+sizeof(Chunk)]);
if (chk==0) return 0;
chk->InitChunk(sz,maxSlots);
return chk;
}

void *Alloc(size_t sz)
{
if (_firstFree==EndOfChain) return 0;
int choosen=_firstFree;
unsigned char *chkbeg=FirstSlot();
_firstFree=chkbeg[choosen*sz];
_usage++;
return chkbeg+(choosen*sz);
}

void Free(void *what, size_t sz)
{
unsigned char *w=reinterpret_cast<unsigned char *>(what);
unsigned char *chkbeg=FirstSlot();
size_t index=(w-chkbeg)/sz;
*w=_firstFree;
_firstFree=(unsigned char)index;
_usage--;
}

void DeleteChunk()
{
char *c=reinterpret_cast<char *>(this);
delete [] c;
}

Závěr kapitoly

To samozřejmě není vše, ve stavbě efektivního alokátoru budeme pokračovat v další kapitole. Nicméně i teď už máme dobrý základní kámen. Chunk můžeme využít v případě, že píšeme alokátor pro třídu, která zaručeně nebude mít víc jak 255 instancí. Pak alokace a dealokace instancí této třídy bude v konstantním čase a s minimální režií.

Efektivní alokátor malých objektů II

SmallAllocI_Listing.h Úplná implementace Chunku. Obsahuje nějaké funkce, které budeme potřebovat v další kapitole a funkci ReportUsedBlocks pro vypis alokovaných bloků, vhodné když hledáme leaky.
vytvořeno: 23.1.2007 10:02:14, změněno: 23.1.2007 10:02:14
Jsou informace v článku pro Vás užitečné?
  • ()
  • ()
  • ()
  • ()
  • ()
Nick nebo OpenID
Vzkaz
 
2.7.2014 17:46:53

5QbCjqUUHX1

Dobrfd den, re1d bych se sešel s obchodnedm ze1stupcem ohdelně zedske1ned vedce informaced na střešned syste9m. Jsme firma, ktere1 se monte1žemi nadkrokevnedch syste9mů zabfdve1 již od roku 1997 a me1me za sebou mnoho realizaced s několika vfdrobky. Děkuji za odpověď, Engel, 775319861

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ů II

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

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: