[C++] memory pools en destructors

[Verwijderd]

Voor een scenegraph 3D engine (win32/DirectX) wil ik graag gebruik maken van memory pools. Voor degenen die daar nog niet mee bekend zijn: het idee is dat je uit een pool geheugen kunt alloceren en als je d'r mee klaar bent alle allocaties uit die pool in 1x vrij kunt geven; iets wat wel erg handig is als je met (potentieel) veel dynamisch gealloceerde objecten werkt.

Nu heb ik echter een probleempje met de precieze implementatie. Het alloceren van objecten gaat probleemloos: gewoon operator new op een handige plek overriden met een extra placement argument (om de te gebruiken pool aan te geven). Ik zie alleen niet heel erg goed hoe ik dat vrijgeven moet implementeren.

Ja, natuurlijk kan ik 't geheugen wat de pool heeft gealloceerd teruggeven aan 't systeem. Echter, een scenegraph node heeft verwijzingen naar o.a. textures en meshes, die (in dit geval) door DirectX gealloceerd en beheerd worden. Die moeten natuurlijk ook vrijgegeven worden, en de aangewezen plaats daarvoor is de destructor van een scenegraph node. En dus moet ik mijn pool allocator zo ver krijgen dat 'ie die aanroept.

Nu is een hele simpele oplossing natuurlijk om m'n memory pool class een template te maken die de class waarvoor geheugen te alloceren valt als argument neemt. Dat is in dit geval helaas geen handige oplossing, aangezien ik ook met sub-pools wil werken.

Wat ik in gedachten had was een SafePoolObject class te maken, die een virtual destructor heeft. Als van een class objecten in een pool terecht komen en de destructor dient daarop te worden aangeroepen, dan moet deze SafePoolObject subclassen. Deze laatste heeft z'n eigen operator new en methoden en members om te zorgen dat binnen de pool een linked list van SafePoolObject's wordt aangelegd. Als 't geheugen van een pool vrijgegeven wordt word eerst even deze lijst afgelopen, wordt elk element naar een SafePoolObject gecast en daarop de destructor aangeroepen.

Ik vraag me echter af of dat wel goed gaat. Want het SafePoolObject-deel van een object staat niet noodzakelijkerwijs als eerste in 't geheugen natuurlijk.

Kan iemand met wat meer verstand van de win32 C++ ABI dan ik hier misschien zijn/haar licht over laten schijnen? Of weet iemand misschien een handiger manier om nette destructie van pool-gealloceerde objecten te implementeren?

[ Voor 1% gewijzigd door Verwijderd op 19-08-2006 16:19 . Reden: Linkje naar APR memory pool beschrijving toegevoegd ]

[The - DDD]

Je zou ook over kunnen stappen op C#
Scheelt je een boel geheugen management.

[DeadLock]

ja, mss wel, maar dat wil ook zeggen dat je minder controle hebt over wat er gebeurd

[Soultaker]

Verwijderd schreef op zaterdag 19 augustus 2006 @ 16:15:
Ik vraag me echter af of dat wel goed gaat. Want het SafePoolObject-deel van een object staat niet noodzakelijkerwijs als eerste in 't geheugen natuurlijk.

Waar het in het geheugen staat, daar hoef jij je geen zorgen over te maken. Als het object afstamt van een SafePoolObject, dan kun je 'm casten, en met de virtual destructor ook goed vrijgeven.

Ik zou trouwens het hele gebeuren met placement new eruit laten. Dat betekent wel dat je handmatig objecten in de pool moet stoppen. Zoiets dan:

C++:

class PoolObject
{
    virtual ~PoolObject() { };
};

class Pool
{
    std::vector<PoolObject*> objects;

public:
    ~Pool() {
        clear();
    }

    template<class T> T *add(T *inst) {
        objects.push_back(inst);
        return inst;
    }

    void clear() {
        for(std::vector<PoolObject*>::iterator i = objects.begin(); i != objects.end(); ++i)
            delete *i;
        objects.clear();
    }
};

// .. code ..
{
    Pool pool;
    pool.insert(new SomeClass(123))->doeIets;
} // pool wordt automatisch gecleart.

Is iets meer werk, maar je hakt wat minder zwaar in op het hele allocatie/deallocatie-gebeuren. (Je eist alleen dat het object een virtual destructor heeft.)

[ Voor 49% gewijzigd door Soultaker op 19-08-2006 17:01 ]

[DroogKloot]

Tabsels schreef::
Ja, natuurlijk kan ik 't geheugen wat de pool heeft gealloceerd teruggeven aan 't systeem. Echter, een scenegraph node heeft verwijzingen naar o.a. textures en meshes, die (in dit geval) door DirectX gealloceerd en beheerd worden. Die moeten natuurlijk ook vrijgegeven worden, en de aangewezen plaats daarvoor is de destructor van een scenegraph node. En dus moet ik mijn pool allocator zo ver krijgen dat 'ie die aanroept.

Dat is niet zo'n groot probleem lijkt me?

C++:

class MemPool {
    public:
        void* alloc(size_t nbytes);
        void dealloc(void* p);

    private:
        char pool[POOL_SIZE];
        // andere data members
};
 
void* MemPool::alloc(size_t nbytes) {
    // doe iets met de pool
}

void MemPool::dealloc(void* p) {
    // doe iets met de pool
}

Alloceren gaat dan simpel:

C++:

    MemPool memPool;
    void* addr = memPool.alloc(sizeof(Foo));
    Foo* foo = new(addr) Foo();

En de-alloceren ook:

C++:

    foo -> ~Foo();
    memPool.dealloc(foo);

_{Over elegantie heb ik niets gezegd.}

[Soultaker]

@DroogKloot: het punt van een memory pool is dat je niet handmatig meer destructors hoeft aan te roepen, maar simpelweg in één keer alle objecten (bijvoorbeeld een scene graph ) kunt vrijgeven. Met jouw voorbeeld moet je alsnog handmatig dealloceren. Het punt is juist dat de pool dat moet doen.

[TheNameless]

Is de BOOST pool library niet iets voor jou: http://boost.org/libs/pool/doc/index.html
En anders is het misschien in inspiratie bron

[Verwijderd]

The - DDD schreef op zaterdag 19 augustus 2006 @ 16:51:
Je zou ook over kunnen stappen op C#
Scheelt je een boel geheugen management.

Ja, dat zou ik ook liever doen. Maar 't is een engine voor demo's, en bij een boel competities is c#/.net niet toegestaan.

---

Soultaker schreef op zaterdag 19 augustus 2006 @ 16:55:
[...]

Waar het in het geheugen staat, daar hoef jij je geen zorgen over te maken. Als het object afstamt van een SafePoolObject, dan kun je 'm casten, en met de virtual destructor ook goed vrijgeven.

Maar ik ga een void pointer casten naar een SafePoolObject, dus dan lijkt me dat 't wel uitmaakt. Geen idee of C++ dat goed snapt...

Ik zou trouwens het hele gebeuren met placement new eruit laten. Dat betekent wel dat je handmatig objecten in de pool moet stoppen. Zoiets dan:
[...]

Misschien ook niet een heel gekke oplossing. Het betekend wel dat m'n code "weet" welk type object d'r precies in de pool gestopt wordt, ook in het geval van een wat minder conventionele inheritance boom. Ik kan dan evt. 't volgende doen:

C++:

class MemoryPool {
   // ...
   template <typename T>
   void Insert(T *obj)
   {
      // plaats object in linked list en associeer T::~T met object.
   }
}

Waardoor ik meteen in 1x de juiste destructor heb. Weet alleen niet of 't ueberhaupt kan (die referentie naar T::~T moet ik eigenlijk even testen).

---

MayaFreak schreef op zaterdag 19 augustus 2006 @ 22:57:
Is de BOOST pool library niet iets voor jou: http://boost.org/libs/pool/doc/index.html
En anders is het misschien in inspiratie bron

object_pool komt inderdaad in de buurt. Echter, als 't even mogelijk is wil ik m'n pool type-agnostisch maken (dus dat ik elk willekeurig type uit 'n pool kan alloceren), omdat me dat praktischer lijkt.

[ Voor 0% gewijzigd door Verwijderd op 20-08-2006 15:34 . Reden: Korecktie van tickvaudten ]

[Soultaker]

Verwijderd schreef op zondag 20 augustus 2006 @ 15:33:
Maar ik ga een void pointer casten naar een SafePoolObject, dus dan lijkt me dat 't wel uitmaakt. Geen idee of C++ dat goed snapt...

Hmm, waarom ga je dan een void* casten? Je kunt toch overal met SafePoolObject*'s werken?

De conversie via void* kan misgaan bij multiple inheritance, maar anders niet. Als je continu met SafePoolObject*'s werkt, gaat het wel goed; je hoeft dan nooit 'omhoog' te casten, maar de virtual destructor is wel een vereiste om te zorgen dat alle destructors worden aangeroepen.

Het betekend wel dat m'n code "weet" welk type object d'r precies in de pool gestopt wordt, ook in het geval van een wat minder conventionele inheritance boom.
[..]
Waardoor ik meteen in 1x de juiste destructor heb. Weet alleen niet of 't ueberhaupt kan (die referentie naar T::~T moet ik eigenlijk even testen).

Ik denk dat het niet kan, omdat de destructor geen gewone member is. Maar probeer het vooral uit.

[Verwijderd]

Soultaker schreef op zondag 20 augustus 2006 @ 16:51:
[...]

Hmm, waarom ga je dan een void* casten? Je kunt toch overal met SafePoolObject*'s werken?

De conversie via void* kan misgaan bij multiple inheritance, maar anders niet. Als je continu met SafePoolObject*'s werkt, gaat het wel goed; je hoeft dan nooit 'omhoog' te casten, maar de virtual destructor is wel een vereiste om te zorgen dat alle destructors worden aangeroepen.

Ja, daar zit wat in. Probleem is echter dat operator new alleen met void pointers werkt.

Wat natuurlijk wel kan is wat jij al eerder voorstelde: objecten gewoon uit de systeem-heap alloceren en later pas associeren met een pool. Dan heb ik als voordeel van m'n pools dat ze automagisch objecten de-alloceren.

Echter, d'r is nog een belangrijk voordeel van het gebruik van pools t.o.v. de systeem heap: ik kan m'n pool een grote allocatie uit de systeem-heap laten doen, en met gebruik van een heel simpel algorithme dit weer in stukjes uitgeven aan m'n programma. Dat kan omdat ik niet hoef bij te houden wat ik nu precies gealloceerd heb (aangezien ik 't toch in 1x weer vrijgeef). Dat is veel sneller dan de systeem-heap direct gebruiken.

Nog 'ns Stroustrup's boek goed doorlezen maar.

Ik denk dat het niet kan, omdat de destructor geen gewone member is. Maar probeer het vooral uit.

Het kan niet

[MSalters]

DroogKloot schreef op zaterdag 19 augustus 2006 @ 17:25:

C++:

    MemPool memPool;
    void* addr = memPool.alloc(sizeof(Foo));
    Foo* foo = new(addr) Foo();

En de-alloceren ook:

C++:

    foo -> ~Foo();
    memPool.dealloc(foo);

_{Over elegantie heb ik niets gezegd.}

Nee, maar 't is wel het goede antwoord. Uiteraard is memPool.dealloc() niet nodig. 't Is net zoiets als ostream::close(), als je het niet doet dan doet de dtor (van memPool resp. ostream) het wel voor je.

[MSalters]

Verwijderd schreef op zaterdag 19 augustus 2006 @ 16:15:
Voor een scenegraph 3D engine (win32/DirectX) wil ik graag gebruik maken van memory pools. V
Nu heb ik echter een probleempje met de precieze implementatie. Het alloceren van objecten gaat probleemloos: gewoon operator new op een handige plek overriden met een extra placement argument (om de te gebruiken pool aan te geven). Ik zie alleen niet heel erg goed hoe ik dat vrijgeven moet implementeren.

De destructor aanroepen, zoals ^^ eerder gezegd.

Ja, natuurlijk kan ik 't geheugen wat de pool heeft gealloceerd teruggeven aan 't systeem. Echter, een scenegraph node heeft verwijzingen naar o.a. textures en meshes, die (in dit geval) door DirectX gealloceerd en beheerd worden. Die moeten natuurlijk ook vrijgegeven worden, en de aangewezen plaats daarvoor is de destructor van een scenegraph node. En dus moet ik mijn pool allocator zo ver krijgen dat 'ie die aanroept.

Nee, sorry. Een pool allocator is een memory manager. De Java/C# crowd verwart resource management vaak met memory management, maar resources zijn breder. Dit is zo'n geval waarin dat duidelijk wordt. Een texture is een resource maar geen "gewoon geheugen". Een pool allocator is puur en alleen om geheugen te beheren.

Voorbeeld: als je een pool allocator aan std::vector meegeeft, dan doet std::vector nog steeds alle non-memory resourcemanagament. In C++ is dat simpelweg Foo::~Foo aanroepen, "toevallig" precies wat jij wil.

[Verwijderd]

MSalters schreef op zondag 20 augustus 2006 @ 23:52:
[...]

De destructor aanroepen, zoals ^^ eerder gezegd.

Maar ik wil graag dat m'n memory pool dat voor me doet.

Nee, sorry. Een pool allocator is een memory manager. De Java/C# crowd verwart resource management vaak met memory management, maar resources zijn breder. Dit is zo'n geval waarin dat duidelijk wordt. Een texture is een resource maar geen "gewoon geheugen". Een pool allocator is puur en alleen om geheugen te beheren.

Goed, resource management, wat jij wilt. Feit is dat ik een pool-geval wil die voor mij objecten kan new()'en en als de pool gedestroyed wordt alle objecten meeneemt.

Overigens heb ik inmiddels een oplossing gevonden. Blijkt dat ik niet de enige ben en dat iemand anders 't al eens heeft uitgewerkt. Niet echt heel simpel, met (partial) template specialisation en alles, maar 't doet wel precies wat ik wil

[Soultaker]

Ik denk dat wat MSalters zegt, erop neerkomt dat allocatie/deallocatie van geheugen een taak op zichzelf is, en het beheer van (de levensduur van) objecten een andere taak. Mijn eerste voorstel doet uitsluitend het tweede (objecten beheren) en niet het eerste. Natuurlijk kun je beide dingen optimaliseren, maar het is de vraag of het verstandig is ze in één klasse te combineren terwijl het twee verschillende functies zijn.

Verwijderd schreef op maandag 21 augustus 2006 @ 11:29:
Overigens heb ik inmiddels een oplossing gevonden. Blijkt dat ik niet de enige ben en dat iemand anders 't al eens heeft uitgewerkt. Niet echt heel simpel, met (partial) template specialisation en alles, maar 't doet wel precies wat ik wil

Ik betwijfel of zijn oplossing erg robuust is, maar je kunt het altijd proberen.

Zijn rant is verder niet helemaal terecht. De vergelijking met C gaat gewoon niet op, bij gebrek aan constructors en destructors bestaat er helemaal geen onderscheid tussen geheugenallocatie en initialisatie/deïnitialisatie van objecten.

[ Voor 11% gewijzigd door Soultaker op 21-08-2006 13:16 ]

[Verwijderd]

Soultaker schreef op maandag 21 augustus 2006 @ 13:14:
Ik denk dat wat MSalters zegt, erop neerkomt dat allocatie/deallocatie van geheugen een taak op zichzelf is, en het beheer van (de levensduur van) objecten een andere taak. Mijn eerste voorstel doet uitsluitend het tweede (objecten beheren) en niet het eerste. Natuurlijk kun je beide dingen optimaliseren, maar het is de vraag of het verstandig is ze in één klasse te combineren terwijl het twee verschillende functies zijn.

Maar dat is precies wat m'n memory pool doet: objecten beheren. Dat 'ie d'r ook geheugen voor beheert is slechts een bij-effect. Hij zou best voor alle objecten statisch gealloceerd geheugen kunnen gebruiken.

Ik betwijfel of zijn oplossing erg robuust is, maar je kunt het altijd proberen.

Nou, 't gaat een beetje mis met references. Dat is op zich niet heel onlogisch: als ik "Type &a" heb, dan is 't type daarvan "Type", en niet "Type &". Bij pointers ligt dat anders: daarbij is het type van "Type *a", "Type *", dus daarbij gaat de type inference wel goed.

Met "niet goed" bedoel ik hier overigens dat d'r alsnog een kopie van 't object gemaakt wordt, en dat d'r dus niet gebeurd wat je verwacht. Maar daar valt wel omheen te werken verder denk ik.

Zijn rant is verder niet helemaal terecht. De vergelijking met C gaat gewoon niet op, bij gebrek aan constructors en destructors bestaat er helemaal geen onderscheid tussen geheugenallocatie en initialisatie/deïnitialisatie van objecten.

Waar zijn rant terecht op wijst is dat wat dit soort dingen betreft C een stuk "generieker" is dan C++. En wat dat betreft ben ik 't wel met 'm eens: over 't algemeen is C++ mooi generiek, maar d'r zijn een aantal dingen (waaronder operator new) die wel heel erg specifiek op specifieke functionaliteit zijn toegespitst en daardoor niet te gebruiken zijn als de toepassing ook maar een beetje afwijkt van dat waar 't voor ontworpen is.

[Jrz]

Soultaker schreef op zaterdag 19 augustus 2006 @ 17:50:
@DroogKloot: het punt van een memory pool is dat je niet handmatig meer destructors hoeft aan te roepen, maar simpelweg in één keer alle objecten (bijvoorbeeld een scene graph ) kunt vrijgeven. Met jouw voorbeeld moet je alsnog handmatig dealloceren. Het punt is juist dat de pool dat moet doen.

Hmm volgens mij is het punt van een memorypool dat je niet veel overhead hebt bij het alloceren door je OS.

Jij doelt op smartpointers denk ik.

[MSalters]

Nogmaals - scheid je verantwoordelijkheden. Pak een goed STL boek (Josuttis of Austern bijvoorbeeld). Het bestaansrecht van een memorypool is dat je het geheugen van een T[ ] niet T voor T hoeft vrij te geven. Evengoed moet je T::~T wel voor elke T aanroepen, bij voorkeur met enige locality of reference. Dat zijn andere eisen.

[Soultaker]

Jrz schreef op maandag 21 augustus 2006 @ 20:52:
Hmm volgens mij is het punt van een memorypool dat je niet veel overhead hebt bij het alloceren door je OS.

De term is op beide dingen van toepassing. Zoals bv. in het artikel staat dat Tabsel in de topic start aanhaalt, gebruikt Apache pools primair om op een handige manier gealloceerd geheugen te tracken en vrij te geven op het juiste moment, om daarmee geheugenlekken te voorkomen. Dat heeft niets met efficiëntie te maken, maar alles met correctheid.

Verwijderd schreef op maandag 21 augustus 2006 @ 20:47:
Nou, 't gaat een beetje mis met references. Dat is op zich niet heel onlogisch: als ik "Type &a" heb, dan is 't type daarvan "Type", en niet "Type &". Bij pointers ligt dat anders: daarbij is het type van "Type *a", "Type *", dus daarbij gaat de type inference wel goed.

Met "niet goed" bedoel ik hier overigens dat d'r alsnog een kopie van 't object gemaakt wordt, en dat d'r dus niet gebeurd wat je verwacht. Maar daar valt wel omheen te werken verder denk ik.

Heb je hier een voorbeeld bij, van waarmee het mis gaat?

[Verwijderd]

MSalters schreef op maandag 21 augustus 2006 @ 20:53:
Nogmaals - scheid je verantwoordelijkheden. Pak een goed STL boek (Josuttis of Austern bijvoorbeeld).

Bah, STL is bloated en overdesigned. Het zal vast wel "mooi" zijn in de zin dat sommige Haskell code mooi is, maar dat betekend nog niet dat 't enigszins vooruit te branden is (dat code geinlined is betekend niet noodzakelijk dat 't snel is).

Het bestaansrecht van een memorypool is dat je het geheugen van een T[ ] niet T voor T hoeft vrij te geven. Evengoed moet je T::~T wel voor elke T aanroepen, bij voorkeur met enige locality of reference. Dat zijn andere eisen.

Je moet m'n memory pool denk ik zien als een speciale vorm van een garbage collector: hij doet op commando één sweep over z'n geheugen en ontdoet zich van alle daarin gealloceerde objecten.

---

Jrz schreef op maandag 21 augustus 2006 @ 20:52:
[...]

Hmm volgens mij is het punt van een memorypool dat je niet veel overhead hebt bij het alloceren door je OS.

Jij doelt op smartpointers denk ik.

Het punt is dat-ie beiden doet. En sommige puristen zint dat niet geloof ik

[ Voor 0% gewijzigd door Verwijderd op 21-08-2006 21:22 . Reden: garbage allocator -> garbage collector ]

[Verwijderd]

Soultaker schreef op maandag 21 augustus 2006 @ 21:12:
[...]

De term is op beide dingen van toepassing. Zoals bv. in het artikel staat dat Tabsel in de topic start aanhaalt, gebruikt Apache pools primair om op een handige manier gealloceerd geheugen te tracken en vrij te geven op het juiste moment, om daarmee geheugenlekken te voorkomen. Dat heeft niets met efficiëntie te maken, maar alles met correctheid.

Stiekem ook een beetje met efficientie hoor. De pool-allocator kan immers heel simpel zijn (gewoon een pointertje veranderen) aangezien 'ie geen losse allocaties bij hoeft te houden. Plus dat m'n working set kleiner (en consistenter) blijft en daardoor meer in 't L1/L2 cache past. Maar 't was me vooral te doen om de correctheid inderdaad.

Heb je hier een voorbeeld bij, van waarmee het mis gaat?

Even een simpele test-case gebakken die net zo werkt als mijn code:

C++:

#include <stdio.h>

class Test
{
    public:
        Test()
            : i(42)
        { printf("Constructor\n"); }

        Test(Test &t)
            : i(t.i)
        { printf("Copy constructor\n"); }

        ~Test()
        { printf("Destructor\n"); }

        unsigned int i;
};

class Reference
{
    public:
        static void Invoke(Test &t)
        {
            printf("Reference: i=%d\n", t.i);
        }
};

class Pointer
{
    public:
        static void Invoke(Test *t)
        {
            printf("Pointer: i=%d\n", t->i);
        }
};

class Invoker
{
    public:
        template <typename T, typename A1>
        static void Invoke(A1 a1)
        {
            T::Invoke(a1);
        }
};

int main(int argc, const char* argv[])
{
    Test t;

    Invoker::Invoke<Reference>(t);
    Invoker::Invoke<Pointer>(&t);

    return 0;
}

Deze geeft als output:

code:

Constructor
Copy constructor
Reference: i=42
Destructor
Pointer: i=42
Destructor

Wat aangeeft dat voor de by-reference alsnog een kopie gemaakt wordt.

[.oisyn]

Het geeft aan dat Al=Test ipv Test& bij Invoke<Reference>. Je kunt er omheen werken door een overload te maken voor een Invoke(Al &)