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
GarbageCollector v C++, prototyp - Bredyho blog - Ondřej Novák
Bredyho blog - Ondřej Novák

GarbageCollector v C++, prototyp

Neustále slýchám, jak v C++ chybí Garbage Collector. Ač si o tomto nástroji myslím své, a v zásadě jsem proti zavedení GC v C++, přijal jsem tyto nářky jako výzvu.


GC v C++ je už dávno!

Nejprve malé popíchnutí. Ti co neustále volají po zavedení GC v C++ (jelikož GC je dnes v módě), neuvědomují si nebo nevědí, že Garbage Collector je v C++ přítomen už od svého vzniku. Že jste si ho zatím nevšimli? Tak se prosím zamyslete nad svými znalostmi v programování.

Tím skrytým, tajemným a úžasným Garbage Collectorem je přece zásobník! Vskutku! Vždyť po nás uklízí všechny lokální proměnné, ať už to jsou objekty nebo ne. A pokud se náhodou uklízí i objekty, pak zásobník volá jejich destruktory. A díky těmto destruktorům může posléze dojít k úklidu celé paměti, včetně paměti ležící mimo zásobník.

Zásobník v C++ je velice silný nástroj. Dokonce silnější než v Javě. Zkuste v Javu donutit finalizovat objekty na konci funkce...! Vhodným používáním zásobníku přijdeme na to, že klasický "módní" GC nám v C++ až tak nechybí.

Tolik na úvod, více o GC obecně najdete v článku Kritika Garbage Collectoru.

Požadavky na GC v C++

Podívejme se tedy na možnost implementace klasického "módního" GC, tak jak jej známe z Javy nebo C#. Nejprve si ale sepišme podmínky na Garbage Collector

  • vede si informace o existenci všech dynamicky alokovaných objektů.
  • provádí transitivní uzávěry všech referencí v rámci celého systému
  • definuje skupinu ukazatelů, jejichž existence a reference přes transitivní uzávěr na objektu způsobí, že tento objekt bude považován za referencovaný
  • v definovaných intervalech provádí destrukci nereferencovaných objektů
  • provádí tuto činnost na pozadí, nebo na požádání.

GCUkazatel

Je zřejmé, že základem celého systému je vhodně navržený typ ukazatele. Nemusím asi dokazovat, že se standardním ukazatelem si nevystačíme. Náš ukazatel musí být chytrý, budeme od něho totiž vyžadovat, aby informoval Garbage Collector o všech cílech, na které během své existence ukazuje a samozřejmě též o svém vzniku a zániku. I tady s výhodou často použijeme vlastnosti zásobníku, kdykoliv budeme vytvářet ukazatele na něm a chtít po zásobníku, aby se ukazatele destruovali na konci své platnosti.

Nazvěme si tento ukazatel GCRef. Bude se jednat o šablonu. Použití je zřejmé

GCRef<Okno> okno = new Okno;

Ukazatel (říkejme mu GCUkazatel, aby se nepletl se standardním ukazatelem) musí být deklarován tak, aby práce s ním se nelišila od práce se standardním ukazatelem. Jediným rozdílem bude vyšší náročnost na výkon, protože GCUkazatel bude každou svou změnu oznamovat objektu GC. Časté změny, zánik a vznik GCUkazatelů tedy povede k vyšším výkonovým nárokům.

GCUkazatel (GCRef) si probereme podrobněji dále. Nyní postačí znát, že GCUkazatel (GCRef) je prostě objektem, který musíme používat ve spojení s naším GC. Pouze na základě těchto ukazatelů může GC rozhodovat o tom, který objekt zdestruuje a který nechá žít. Pokud neexistuje žádná reference na objekt prostřednictvím GCUkazatele, Garbage Collector ho bez milosti zničí, i přesto, že může existovat spoustu referencí jiného druhu (jiné ukazatele, ukazatele uložené v celých číslech, serializované ukazatele ve streamech, atd).

Mapa paměti

Aby Garbage Collector měl přehled o objektech, které spravuje, musí si vést mapu paměti. Přesněji, musí mít přehled o tom, na kterých adresách paměti leží který objekt. Mapu paměti naleznete ve zdrojácích v GCMain.h pod názvem MemoryList. Je deklarovaná takto:

typedef std::set<MemoryDesc> MemoryList; 

Samotný deskriptor paměti má tento formát:

struct MemoryDesc
{
char *address;
std::size_t size;
void (*delFunction)(void *instance);
char *hang;
// další položky jsou vynechány, nejsou relevantní...
};

Víceméně to je k mapě paměti vše. Každý nově vzniklý objekt má záznam v mapě. GC si zaznamená adresu objektu, jeho velikost a funkci, která se zavolá pro zničení objektu. Už tady si všimněte, že GC nepředpokládá, že by se o likvidaci objektu staral sám. Pro GC se likvidací objektů smrskne jen na zavolání callback funkce a následné odstranění záznamu z mapy paměti. Samotný objekt ale vůbec nemusí být zničen, to záleží na definici callback funkce.

O položce hang viz dále.

Mapa referencí

Kromě mapy paměti musí GC spravovat mapu referencí. Jsou to dvojice adres. První z dvojice udává kam reference ukazuje, druhá z dvojice udává odkud (kde leží instance ukazatele). Mapa referencí je organizována podle první a pak podle druhé položky. Sestavit tedy seznam referencí referencující zvolený objekt má logaritmickou složitost.

Každý založený nebo zničení GCUkazatel a veškeré změny v hodnotě ukazatele se zaznamenávají do této mapy.

Další mapy

Tohle to byly základní mapy pro běh GC. Uveďme si další mapy, které pomohou pochopit celý systém.

FocusedMemory
Představuje mapu podezřelých objektů. U těchto objektů by GC měl v nejbližší době provést transitivní uzávěr a ověřit, zda existují nějaké externí reference. Pakliže takové nenajde, podezřelý objekt je zničen. V opačném případě je takový objekt vyřazen se seznamu podezřelých objektů. Zpět na seznam se může opět dostat v okamžiku, kdy dojde ke zrušení nějaké reference na tento objekt.
MarkedMemory
Při výpočtu transitivního uzávěru se prošlé paměťové bloky označkují značkami. Seznam značek jsou uloženy v této mapě. Jakmile existuje reference na označkovanou paměť, GC se referencí dále nezabývá. Jakmile je nalezen externí link, který vede do označkované paměti, algoritmus končí a nic se nedealokuje. Jakmile je označkováno vše co může být označkováno a není nalezen jediný externí link, jsou všechny označkobané paměťové bloky zničeny.
Tracker
Představuje frontu nalezených referencí, které GC ještě neprošel. Všechny nově nalezené reference vedoucí do neoznačkované paměti jsou zaznamenané do této fronty a označkovány. Použití fronty vede na prohledávání do šířky. Je v tomto případě efektivní, protože stačí odhalit první nejbližší externí link a hledání končí.
Hang
Představuje optimalizaci hledání. Aby se nemusel transitivní uzávěr vytvářet pokaždé znovu, je každý záznam v mapě paměti opatřen věšákem, ve kterým drží adresu paměťového bloku, na který ukazuje přímá externí reference. V okamžiku prověřování podezřelých bloku se GC věnuje i hangu, a je-li zjištěno, že ukazuje na platný blok v mapě paměti, je hledání zastaveno. Případ, kdy nebude hang ukazovat na platný blok nastane v okamžiku, kdy tento blok přestane existovat z důvodu zrušení všech jeho přímých referencí. V okamžiku existence nepřímých referencí blok stále existuje, a postačí pouze resynchronizovat hangy na vzájem (provést transitivní uzávěr hangů)

Jak GC používat

Aby bylo možné GC použít, je třeba v programu deklarovat singleton. Knihovna toto sama neudělá

#include "GCMain.h"
#include "GCRef.h"


using namespace BredyGC;

GCMain gc;

Jedná se o singleton, takže třída GCMain by měla existovat jen v jedné instanci.Další spolupráce programu s GC se děje většinou přes GCRef. Celá deklarace GCRef má následující formu:

GCRef< Type, DeleteOp /*= GCStdObject*/> 

Většinou budeme pracovat s variantou GCRef<Type>. Tahle varianta předpokládá, že objekty alokujeme pomocí standardního new. Když nahlédneme do GCStdObject najdeme tam funkci DeleteObject(void *ptr) a v ní operátor delete. Pro alokaci polí v GC musíme už použít jako DeleteOp třídu GCStdArrayOfObjects. Tato třída předpokládá alokaci pomocí new [] a adekvátně volá delete []

Samozřejmě máme možnost deklarovat vlastní mazací operátory, pakliže objekty alokujeme jinak. Příkladem může být použití továren, kdy nemáme jistotu, že továrna skutečně alokovala objekt pomocí new. Taková továrna buď sama obsahuje i destrukční funkci, nebo samotný objekt obsahuje nějakou takovou funkci. Pak je nepřijatelné, aby zničení objektu bylo prováděno standardním operátorem.

Registrace objektu do GC

Jak už jste asi zjistili, GC neprovádí alokaci a ani s pamětí nijak nemanipuluje. Nově alokované objekty je třeba do GC registrovat. To se naštěstí děje samo, zajistí nám to konstruktor GCRef

 template<class OtherType>
GCRef(OtherType *ptr)

GCRef přijme v konstruktoru ukazatel na libovolný typ a předpokládá, že tento ukazatel lze převést na typ Type (když to nelze, ohlásí překladač chybu) ve funkci GCRef::Reg). Funkce je určená pro registaci potomků!, je-li využito polymorfismu a používáme referenci na předka.

GCRef<Predek> ref = new Potomek;

Konstruktor se instanciuje s typem potomka a může registrovat nový objekt správně, protože zná jeho adresu a velikost. Pokud bysme však registrovali předka

Predek iref = new Potomek
GCRef<Predek> ref = iref; //chyba!

Dojde k tomu, že GC zaregistruje pouze rozhraní, a všechny odkazy alokované v potomkovi bude považovat za externí. (PS: Tento problém lze částečně řešit pomocí RTTI a dynamic_cast, nicméně prototyp toto neumí, bude to součástí dalšího vývoje).

Nemusím připomínat, že jakmile se objekt registruje do GC, důrazně se nedoporučuje přistupovat k němu pomocí standardního ukazatele. Jedinou výjimkou je uložení standardního ukazatele souběžně s GCRef za účelem zrychlení přístupu (bez nutnosti jít přes GCRef). Podmínkou je souběžná existence obou ukazatelů.

Operace s GCRef

GCRef je navržen tak, aby se s ním dalo pracovat jako s běžným ukazatelem, ale můžete narazit na odlišnosti. Spíš použijte GCRef na uložení ukazatelů, než na matematické operace s ukazateli. GCRef nemusí ukazovat na začátek objektu, může ukazovat kamkoliv doprostřed. Takto lze ukazovat i doprostřed pole. GC bude považovat referenci doprostřed pole jako referenci na celé pole.

Kdy se provede Collect?

Manuálně lze Collect vyvolat funkcí GCRef::Collect()

GC provede automaticky Collect v průměru jednou za sekundu. Podmínkou je, že musí program zavolat kteroukoliv operaci GC, například registraci nového GCRef. Tato hodnota se dá nastavit v konstruktoru GCMain.

Příklad

struct TestGC
{
int index;
GCRef<TestGC> ptr1;
GCRef<TestGC> ptr2;
TestGC(int i):index(i)
{
// printf("Alloc: %d %X\n",index,this);
}

~TestGC()
{
// printf("Dealloc: %d %X\n",index,this);
}
};

typedef GCRef<TestGC> PTestGC;

int main(int argc, char *argv[])
{
using namespace BredyGC;

int cnt = 100000;
GCRef<PTestGC,GCStdArrayOfObjects> array(new PTestGC[cnt]);

for (int i = 0; i < cnt; i++) array[i] = new TestGC(i);

puts("creating links");

for (int i = 0; i < 3 * cnt; i++)
{
int a = rand() % cnt;
int b = rand() % 2;
int c = rand() % cnt;

GCRef<TestGC> &p=b ? array[a]->ptr1: array[a]->ptr2;
p = array[c];
}

puts("collecting...");

array.Collect();

array = 0;

array.Collect();

}

Příklad alokuje 100000 objektů a pak je prolinkuje. Provede Collect aby se ověřilo, že žádný objekt nevisí volně ve vzduchu. Poté se vynuluje ukazatel na pole obsahující tyto objekty. Následující Collect zjistí, že zmizela jediná externí reference a postupně uvolní všechny alokované objekty.

Zdrojáky ke stažení

BredyGC.tar.gz Zdrojáky lze otevřít v Eclipse pomocí CDT pluginu. S nastavením projektu by pak neměl být žádný problém. V jiném systému si makefile a vcprojekty musíte udělat vlastní.
vytvořeno: 9.3.2007 11:00:40, změněno: 9.3.2007 11:07:53
Jsou informace v článku pro Vás užitečné?
  • (7)
  • (1)
  • (1)
  • (1)
  • (0)
Nick nebo OpenID
Vzkaz
 
25.7.2016 18:42:29

ppVFPcaxFpM

Din bok tuurdfiydnskker er så lekker. Jeg sitter ofte å ser i den, men vet ikke om jeg finner motet til å prøve meg på en dukke..... Jo, en dag SKAL jeg :) God påske :)
2.3.2008 13:48:19

Ondra

Ruku na srdce... ani v Jave jsem nikdy nenapsal program hned na poprve bez chyby. Jako že v Javě programovat umím, byť jsem se tedy nedostal na takovou úroveň jako v C++. To že je vývoj v Javě rychlejší je hlavně danné tím, že Java přichází s hromadou knihoven, narozdíl od C++, kde se člověk často musí spolehnout pouze na zabugované a kontroverzní STL. Mít knihovní podporu v C++ jako v Javě, tak nebude mít Java tolik příznivců. Jenže C/C++ tady je, jeho pozice je takové divná. Céčko dodnes používají systémoví programátoři. C++ se hodně používá tam, kde je potřeba hlavně honit výkon (i v Seznamu se třeba píšou všechny backendy v C++, nemusí se jednat jen o hry). Jazyk C/C++ prostě pořád pověst jazyka pro velké odborníky. Bohužel nikdy dnes nemá snahu udělat z C/C++ jazyk přístupný pro masy. OpenSource komunita je na to příliš slabá, velké firmy většinou nasadí vlastní řešení, aby nalákali ovečky, včetně Microsoftu, což mu hodně zazlývám. Proč knihovní podporu která je v C# nepřikládá i k C++ (přihládá, ale pouze k managed verzi). A hned si odpovím. Není to z hlediska marketinku žádoucí. Výtěžnost z takového řešení je prakticky nulová, náklady vysoké.

Díky za příspěvky.
1.3.2008 23:42:46

Jiří Billig

No vidím, že se vyznáte ;-). C++ je nádherný jazyk plný netušených možností, ale v dnešním světe businessu nemá možnost uspět jednoduše proto, že většina lidí nemá zdroje na to ho dokonale ovládnout. Vývoj v javě je díky věcem jako GC prostě rychlejší - člověk se může soustředit na modelování problému z reality a ne se zabývat "nízkou úrovní", kterou si C++ nese z dob neobjektových jazyků. Na rozdíl od javy je ale programování v C++ opravdová zábava - a pokud píšete např. hry, není ani jiná alternativa.

Ale ruku na srdce, opravdu se Vám u "složitých" věcí (výjimky v destruktoru atp.) opravdu podařilo vždy napoprvé napsat program bez chyby ? ;-)
25.1.2008 17:53:26

Ondra

Článek nemá ambice navrhnout dokonale vyladěný GC pod C++. Byla to jen ukázka jakéhosi řešení. Věřím, že GC v Javě je vymakaný, to se nehádám. Ale problém stojí na jiné rovině. GC je módní záležitost, uměle vytvořená věc řešící v zásadě jen jedno jediné a to neschopnost meně inteligentních programátorů. Za dobu co píši v C++ jsem nikdy GC nepotřeboval. Vždycky se ukázalo, že existuje jiné, lepší řešení. Například za použití Distributora (viz jiný článek v blogu), s použitím alokačních poolů (plánuju o tom něco napsat), a v těch opravdu komplikovaných situací často postačilo obyčejné počítání referencí. Jakkoliv optimalizovaný GC bude vždycky buď pomalejší a nebo paměťově náročný a pro příslušný problém "kanónem na vrabce"
25.1.2008 15:21:06

Jiří Billig

Takhle hloupý Garbage Collector ale Java neobsahuje ;-). Co takhle optimalizace výkonu, vlákna v ISO C++ nejsou ....

Podobné články

Garbage collector - automatický úklid objektů v C++

Článek navazuje na GarbageCollector v C++, prototyp, kde jsme si představili prototyp třídy provádějící automatický úklid objektů známy jako "garbage collector". Dnes si ukážeme další verzi, nazvěme ji "alfa"

Tanečky na obecném poli (GenericArray)

Jak sloučit dvě pole, aniž by bylo třeba alokovat jediný bajt? Jak smazat dvě hodnoty z prostřed pole, aniž by se muselo pole fyzicky posouvat? Jak vyzvednout subpole? Jak přerovnat pole bez fyzického přesunu prvku?

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

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

V předchozím díle jsme si ukázali, jak pomocí templatů vytvořit funkci přijímající libovolný počet argumentů stejného typu. Šlo by to udělat i pro argumenty libovolných typů?
Reklama: