Memory-Manager und diverse Allocator-Fragen



  • Hi,

    habe mich bis vor kurzem nie mit Allokatoren beschäftigt. Jetzt interessiert mich die Thematik aber und ich habe einige Artikel dazu gelesen. Wozu Allokatoren praktisch sind, verstehe ich bereits. Ich bin mir aber unsicher, wie man die Allokatoren organisiert. Ich schreibe Mal ein paar Dinge, bei denen ich unsicher bin, ob die stimmen (korrigiert mich bitte, das wäre super!) und habe aber im Anschluss auch direkte Fragen (wenn ihr mein Gefasel vorher nicht korrekturlesen wollt, könnt ihr gerne zu den Absätzen springen, die mit einem ? enden, das sind dann meine Fragen).

    Nehmen wir beispielsweise einen Pool-Allokator. boost::pool_allocator hat ja einen Allokator für jede Typgröße, soweit ich das verstanden habe. Jetzt bin ich Mal etwas in den Code und anscheinend wird ein Singleton genutzt, um für jede Ausgestaltung der Argumente (also Typgröße) einen eigenen Pool zu basteln.

    Man übergibt Allokatoren üblicherweise als Template-Argumente für Container (wie vector). vector allokiert Speicher mit allocate und erstellt z.B. bei resize mit standard-ctor die Objekte über ein placement-new (oder construct des Allocators).

    Aber jeder vector (auch vom selben Typ) instanziiert ein eigenes Allocator-Objekt. Das bedeutet ja eigentlich, dass jeder Allocator seinen eigenen Speicher hat. Darum machen Allokatoren wie pool die erforderlichen Methoden und Attribute static, sodass die ganzen Operationen eben pro Typ anfallen und der Typ somit zero-sized ist und kostenlos instanziiert werden kann. Stimmt das so weit?

    Und wenn man jetzt weiterdenkt an einen Memory-Manager, der tracken können sollen, wer was angelegt hat, wie gestaltet man das am Besten? Sollte der zB eine create-Methode haben, die einen allocator akzeptiert und dann intern (wenn man möchte) trackt, wie viel (evtl. mit welchem Allocator) angelegt wurde?

    Wie wäre eine übliche/best practice Aufrufsyntax für so einen Memory-Manager?

    MemoryManager memory;
    T* t = memory.create<T>(10); // das soll jetzt bereits Std-ctor für alle T aufrufen, also wie ein vector::resize
    
    memory.delete(t, 10); // <- hm, muss man die Anzahl angeben? Wir müssen ja die dtors aufrufen
    

    Okay, das ist jetzt aber sehr unschön. Vermutlich nimmt man dann einen unique_ptr und lässt sich von memory einen custom-deleter geben, ist das so üblich?

    Und noch eine nächste Anschlussfrage: Wie kann man jetzt z.B. vector mit einem Allokator in Verbindung bringen, der dann aber über den Memory-Manager läuft? Würde man so was schreiben wie:

    template<typename Allocator>
    class memoryManagedAllocator
    {
    // ...
    };
    

    als eine Art Decorator, der alle Aufrufe an den übergebenen Allocator weiterleitet und zwischendurch aber dem Memory-Manager berichtet, was so abläuft? Das aber würde wiederum heißen, dass der MemoryManager statisch/Singleton/global sein müsste, damit der memoryManagedAllocator ihm eben auch berichten kann. Ist das so üblich?

    Wäre super, wenn ihr mir ein paar Fragen beantworten könntet. 🙂 Ansonsten nehme ich gerne auch Verweise zu guten Artikeln oder, falls ihr das für sinnvoll haltet, Büchern entgegen!

    Herzlichen Dank im Voraus und beste Grüße!
    Eisflamme



  • du mußt zunächst einmal prüfen, ob du mit C++03 oder C++11 arbeitest

    All custom allocators also must be stateless. (until C++11)

    Custom allocators may contain state. Each container or another allocator-aware object stores an instance of the supplied allocator and controls allocator replacement through std::allocator_traits. (since C++11)

    http://en.cppreference.com/w/cpp/memory/allocator

    stateless bedeutet, daß alle Member statisch sind



  • Und das ist sehr wichtig? Wir könnten ja einfach restriktiverweise davon ausgehen, dass wir immer stateless sind und schon sind wir auf der sicheren Seite. Oder beeinflusst das die Antworten auf meine Fragen maßgeblich?



  • Ausgehend von der Diskrepanz der gewöhnlichen Antwortgeschwindigkeit mit der hier statt gefunden habenden würde ich mich kurz erdreisten zu fragen, ob:
    - ich zu viele Fragen gestellt habe
    - die Fragen zu unpräzise/schwammig/unklar sind
    - hier niemand viel mit Allokatoren gemacht hat

    Vielleicht hätte ich auch eine Frage auf einmal stellen sollen? Wären dann halt 5 Threads oder so geworden. 🙂



  • Naja, ich selbst hätte dir gerne geantwortet, auch da mich das Thema Allokatoren nicht kalt lässt, aber ich hab leider keine Ahnung davon und auch grad keine Zeit mich da reinzuarbeiten.

    Deine Fragen gehen nämlich schon eher tiefergehend und die wenigesten hier haben sich schonmal selbst einen Allokator geschrieben, denke ich.

    Kommt Zeit, kommt Rat...


  • Mod

    Eisflamme schrieb:

    - ich zu viele Fragen gestellt habe

    Zumindest für mich, ja. Ich habe mir die ersten paar Fragen im Kopf überlegt, was die Antwort wäre und das war schon ganz schon viel zu antworten. Und dann kamen immer mehr Fragen. Das hätte ewig gedauert, die zu beantworten. Aber eine halbe (oder eher: eine viertel) Antwort wollte ich auch nicht geben, das sähe dann ja so aus als wollte ich dich mit den schwierigen Fragen alleine lassen.



  • ich hatte mich nur mal überblicksweise mit std::allocator beschäftigt für den Fall, daß ich es mal brauche. dabei war mit gleich zuerst aufgefallen, daß es zwischen C++03 und C++11 gewisse Unterschiede gibt, das hatte ich weiter oben schon geschrieben

    die meisten C++ User programmieren keine eigenen Allokatoren, weil
    1. der vordefinierte Allokator meistens ausreicht
    2. bei der Implementierung von einem eigenen Allokator eine ganze Reihe Bedingungen zu beachten sind und man auch rel. viel testen muß

    ich würde jetzt in zwei Schritten vorgehen:
    1. wozu brauche ich den Allokator?
    2. wie implementiere ich ihn?

    zur ersten Frage gibt es u.a. folgende Antworten:
    1.1 ich habe sehr viele kleine Speicherblöcke
    1.1.1 ich möchte den Speicherverbrauch reduzieren, denn bei kleinen Speicherblöcken ist das Verhältnis von Nutzdaten und Verwaltungsdaten besonders ungünstig
    1.1.2 ich möchte die Rechengeschwindigkeit erhöhen, denn bei kleinen Speicherblöcken kann der Heap stark fragmentieren und das Allokieren/Freigeben wird sehr langsam
    1.2 ich habe sehr viele gleich große Speicherblöcke
    1.3 ich möchte alle Allokationen/Freigaben protokollieren
    1.4 ich möchte Speicher in bestimmten Bereichen verwenden und nicht im normalen Heap, z.B. Shared Memory

    möchtest du einen Allokator implementieren, der für viele unterschiedliche Zwecke einsetzbar ist oder nur für einen bestimmten Zweck? soll der Allokator mit MSVC und/oder GCC laufen und mit neueren und/oder älteren Compilern?



  • Okay, erstmal vielen Dank!

    SeppJ:
    Blöd, hatte ich befürchtet. Aber die Teilantworten würden mich natürlich auch brennend interessieren. Wenn Du nicht alles beantwortest, gehe ich natürlich davon aus, dass es einfach zu viel ist, nicht irgendwas anderes. 🙂 Oder sollte ich den Thread irgendwie ummodeln/kürzen?

    dd++:
    Ich würde sehr gerne einfach bei meinen Fragen bleiben, irgendwie gehen Deine Antworten auf Allokatoren ein, nicht aber auf meine Fragen... das meiste dazu konnte ich mir schon anlesen. Bis auf die Fragen im letzten Absatz, die sind anscheinend wesentlich:

    möchtest du einen Allokator implementieren, der für viele unterschiedliche Zwecke einsetzbar ist oder nur für einen bestimmten Zweck? soll der Allokator mit MSVC und/oder GCC laufen und mit neueren und/oder älteren Compilern?

    Na ja, was heißt Zweck? Also sagen wir Mal, ich würde gerne auf Dauer einen Stack-Allocator (also FIFO-like) und einen Pool-Allocator (sagen wir wie bei boost, also je Typgröße einen eigenen Speicherbereich; wobei es wohl meist eh ein Pool ist, bin mir bei der Terminologie nicht ganz so sicher) haben. Jetzt soll man Tracing ein- und ausschalten können. Und der sollte schon so portabel sein wie möglich, mindestens compiler-portabel, am Besten Standard-portabel (also 03/11)...

    Es muss natürlich auch nicht alles rein. Ich will gerade auch nicht akut so ein Ding schreiben, ich will das Verständnis v.a. über die ein oder anderen Artikel hinaus kriegen. 🙂



  • Das könnte dich interessieren: http://home.roadrunner.com/~hinnant/stack_alloc.html

    (Btw, SeppJ behauptet das jetzt nur um die schweren Fragen nicht beantworten zu müssen)



  • Okay, cool, danke. 🙂

    Ich weiß nicht genau, was C++11 alles für Allocators fordert, aber wenn C++11 da eh abwärtskompatibel ist, würde ich wohl schon die Variante bevorzugen. Ich meine, vermutlich kommen die typedefs und Methoden wie construct oder anderer Boilerplate dazu (wenn ich das im Artikel richtig las), das stört mich aber überhaupt nicht, solange man nicht eingeschränkt wird.



  • ich kann nicht auf alle deine Fragen antworten, die weiter oben stehen. aber wir können versuchen, uns in dem Sumpf immer einem kleinen Schritt weiter vorwärts zu bewegen

    zunächst möchte ich noch mal einen Schritt zurück gehen und darauf hinweisen, das Speicherverwaltungs-Konzepte/Implementierungen und Std C++ Allokatoren zwei unterschiedliche Dinge sind

    für Speicherverwaltung gibt es z.B. http://www.canonware.com/jemalloc/ und http://goog-perftools.sourceforge.net/doc/tcmalloc.html usw. usw.

    die Std C++ Allokatoren müssen bestimmte Bedingungen erfüllen, und das muß man dann auch übeprüfen. ich würde zum Testen mindestens std::string und std::vector nehmen. dazu muß man z.B. auch wissen, daß std::string bei GCC und MSVC komplett anders implementiert ist (und bei neueren und älteren auch noch mal anders), d.h. wenn mein Allokator mit MSVC 9.0 std::string funktioniert, bedeutet das noch nicht, daß er auch mit MSVC 11.0, GCC 4.3 oder GCC 4.7 geht

    wenn du C++03 kompatibel sein möchtest, muß der Allokator stateless sein, d.h. du kannst keine TrackingId im Allokator speichern, jede Allokatorinstanz muß Speicher freigeben können, der von einer anderen Allokatorinstanz angefordert wurde usw.



  • wenn du C++03 kompatibel sein möchtest, muß der Allokator stateless sein, d.h. du kannst keine TrackingId im Allokator speichern, jede Allokatorinstanz muß Speicher freigeben können, der von einer anderen Allokatorinstanz angefordert wurde usw.

    Okay, ich fang jetzt Mal an die Einzelfragen aufzuschreiben, weil das hier gerade passt.

    Wird ein Allocator üblicherweise nicht ohnehin von string/vector/Containern für jedes Objekt neu instanziiert, weil er eben stateless ist und das Instanziieren somit kostenlos bzgl. Speicher und Performance ist? Oder ist das implementierungsabhängig?

    Soweit ich das kapiert habe, müsste man Tracing-Variablen sowieso per Klasse speichern, also static. Dann würde die statelessness ja nicht angegriffen. Was spricht dagegen?



  • in C++03 sind Allokatoren stateless, d.h. sie haben keine non-static data member. nun könnte man eigentlich die member functions alle static machen und mit alloc_class::function aufrufen. die member functions sind aber nicht static, d.h. man kann sie im string/container nur mit member.function aufrufen, also jeder string/container hat einen Allokator member.

    in C++ belegt jeder non-static data member einer Klasse mind. ein Byte (damit untersch. data member untersch. Adressen haben). eine leere Basisklasse belegt aber keinen Speicher. deshalb haben die C++03 Alloaktor Anwender alle eine Basisklasse, in der sich ein Allokator member befindet. bei MSVC heißt das z.B. _String_base

    wenn ich jetzt zwei oder mehr Memory Pools habe, aus denen sich die Allokatoren bedienen sollen, dann brauche ich bei C++03 für jeden Memory Pool eine eigene Allokatorklasse, denn der Allokator ist stateless und kann keinen Pointer auf einen Pool speichern. d.h. die Anzahl der Memory Pools muß schon zur Compile Time feststehen. diese unterschiedlichen Allokatorklassen werden dann z.B. an std::string übergeben und führen zu unterschiedlichen std::string-Klassen

    aus diesem und anderen Gründen wurde das bei C++11 geändert



  • Hi,

    die member functions sind aber nicht static, d.h. man kann sie im string/container nur mit member.function aufrufen, also jeder string/container hat einen Allokator member.

    Soweit ich das bei boost::pool_allocator gesehen habe, ist das eben nicht notwendig. Die Allokatoren werden als Template-Parameter übergeben. Ich kann doch auf einem Objekt eine nicht-statische Methode über dieselbe Syntax aufrufen, also können problemlos auch alle Funktionen statische Funktionen sein. Zum Vergleich hier das standardkonforme boost::pool_allocator ( http://www.boost.org/doc/libs/1_48_0/libs/pool/doc/html/boost/pool_allocator.html ), keine Ahnung, ob das auch C++03-konform ist. Aber da (und auch hier: http://www.boost.org/doc/libs/1_48_0/libs/pool/doc/html/header/boost/pool/pool_alloc_hpp.html ) steht keine diesbezügliche Einschränkung, was bei Boost normalerweise üblich ist, oder?

    in C++ belegt jeder non-static data member einer Klasse mind. ein Byte (damit untersch. data member untersch. Adressen haben). eine leere Basisklasse belegt aber keinen Speicher. deshalb haben die C++03 Alloaktor Anwender alle eine Basisklasse, in der sich ein Allokator member befindet. bei MSVC heißt das z.B. _String_base

    Es würde mir persönlich wirklich helfen, wenn aus Deinen Antworten irgendwie hervorginge, auf welche Frage sich das bezieht. War das bezugnehmend auf

    Wird ein Allocator üblicherweise nicht ohnehin von string/vector/Containern für jedes Objekt neu instanziiert

    ?

    Falls ja, wäre ein "Ja", "Nein" oder "Kann man so nicht beantworten" (und dann im Anschluss die Infos) einfacher für mich persönlich gewesen zu verstehen. Sorry, aber ich brauch den Bezug, sonst brauch ich immer 5 Minuten um hin- und herzumatchen, welche Aussage zu welcher Frage gehört.

    Hm, ich verstehe nicht, wieso das Problem (welches überhaupt?) jetzt plötzlich gelöst ist, wenn vector/string (also die Nutzer des Allocators) das in die Basisklasse schieben. Weil ein nicht-statischer Member Speicher belegt? Da fehlt mir irgendwie das Bindeglied. 🙂

    diese unterschiedlichen Allokatorklassen werden dann z.B. an std::string übergeben und führen zu unterschiedlichen std::string-Klassen

    Klar, das ist syntaktisch impliziert. Aber werden bei C++11 die Allokatoren nicht mehr über Template-Argumente übergeben oder wie verbessert man das hier? (hat sich durch Ethons nächsten Post beantwortet!)

    Vielen Dank schon Mal!!



  • Klar, das ist syntaktisch impliziert. Aber werden bei C++11 die Allokatoren nicht mehr über Template-Argumente übergeben oder wie verbessert man das hier?

    Der Vorteil ist wie gesagt dass jeder Allocator jetzt seinen eigenen Kram mitschleppen kann.

    Pool p1;
    Pool p2;
    
    typedef std::vector<int, MyAllocator<int>> IntVector;
    
    IntVector v1(MyAllocator<int>(&p1));
    IntVector v2(MyAllocator<int>(&p2));
    

    War davor nicht möglich da der Allocator keinen Zeiger auf einen Pool halten konnte.



  • Ah, so läuft das, okay!

    Aber ein statischer Pointer würde ja auch funktionieren (vergesst meine Verwirrung über das mit statischen Elementen und stateless-heit... ich hab die Aussage einfach nicht einordnen können, oben). Klar verliert man einiges an Flexibilität und alles muss jetzt blöderweise statisch sein, aber funktionieren würde es doch wohl?



  • tut mir leid, wenn hier Anworten auf Fragen hineinrutschen, die gar nicht gestellt wurden, aber das Thema ist sehr umfangreich und komplex. bestimmte Zusatzinfos gehören zu anderen Infos einfach dazu ...

    ich habe gerade mal in ISO/IEC 14882:2003 20.1.5 Allocator requirements hineingeschaut. da steht u.a.

    4 Implementations of containers described in this International Standard are permitted to assume that their Allocator template parameter meets the following two additional requirements beyond those in Table 32.
    — All instances of a given allocator type are required to be interchangeable and always compare equal to each other.
    — The typedef members pointer, const_pointer, size_type, and difference_type are required to be T*,T const*, size_t, and ptrdiff_t, respectively.

    es wird nicht gefordert, das Member Functions static sein müssen. der Allokator Programmierer kann sie static deklarieren, der Allokator Anwender kann sich aber nicht darauf verlassen, daß sie static sind, und muß so oder so einen Allokator Member anlegen



  • Ne, ich finde das schon super und verstehe auch, dass die Infos notwendig sind. 🙂 Wäre nur super, wenn Du die Anknüpfungspunkte für mich Dummerchen noch etwas deutlicher machen könntest - sofern es sie denn gibt (vll. war das gerade auch einfach nicht der Fall, dann wäre gut, wenn Du irgendwie verdeutlichst, warum die Aussage gerade für das Thema relevant ist).

    Nach diesen Requirements kann ich ja aber alles statisch machen. Wenn alles statisch ist, kostet die Instanziierung nichts und der ruft immer brav meine statischen Methoden auf. Zwar ist die Instanziierung dann witzlos, aber sie schadet ja auch nicht. Und auf statischer Ebene kann ich dann ja auch einen Memorypool dazuschieben.

    Setzt aber eben alles voraus, dass jeder einzige Allocator statisch ist und auch der Memory-Pool statisch ist, richtig? Wenn ich also zwei Allocator für zwei Pools will, muss ich wohl so was machen:

    typedef Pool<1> Pool1;
    typedef Pool<2> Pool2;
    
    typedef PoolAllocator<int, Pool1> PoolAllocator1; // schöner mit neuem using template-Ausdruck, aber wir sind ja jetzt Mal C++03
    typedef PoolAllocator<int, Pool2> PoolAllocator2;
    
    typedef std::vector<int, PoolAllocator1> pool1_vector;
    typedef std::vector<int, PoolAllocator2> pool2_vector;
    

    Also echt unschön ggü. der C++11-Implementierung, aber für C++03 müsste man das wohl so gestalten, oder?



  • ja genau. man muß solche Konfigurationen zur Compile Time anlegen, d.h. eigene Template-Instanzen oder Klassen. das unschöne ist dabei u.a., daß die beiden vector-Klassen dann nicht mehr so schön interagieren können (swap, assignment usw.)



  • Hier ergaenzend: http://blogs.msdn.com/b/vcblog/archive/2008/08/28/the-mallocator.aspx

    Und fuer ist der Hauptgrund, aligned memory in std::vector zu haben. Normalerweise wird sich in der Standardbibliothek schon um "ich habe sehr viele kleine Speicherblöcke" etc. gekuemmert, indem zwischen Gross und Klein unterschieden wird.


Anmelden zum Antworten