Strategie zum Zuweisen/Freigeben vieler kleiner Objekte

Question

Ich spiele mit bestimmten Caching-Algorithmus, der etwas herausfordernd ist. Im Grunde muss es viele kleine Objekte (doppelte Arrays, 1 bis 256 Elemente) mit Objekten zuweisen, auf die über den zugeordneten Wert map[key] = array zugegriffen werden kann. Die Zeit bis zum initialisierten Array kann ziemlich groß sein, im Allgemeinen mehr als 10 Tausend CPU-Zyklen.

Mit vielen meine ich rund Gigabyte insgesamt. Objekte müssen möglicherweise nach Bedarf gepoppt/geschoben werden, im Allgemeinen an zufälligen Stellen, jeweils ein Objekt. Lebensdauer eines Objekts ist in der Regel lang, Minuten oder mehr, jedoch kann Objekt während der Dauer des Programms mehrfach zugeordnet/freigegeben werden.

Was wäre eine gute Strategie, um Speicherfragmentierung zu vermeiden, während immer noch vernünftige Zuteilung deallocate Geschwindigkeit beibehalten?

Ich benutze C++, damit ich neue und malloc verwenden kann. Danke.

Ich kenne dort eine ähnliche Fragen auf der Website, Efficiently allocating many short-lived small objects, sind etwas anders, Thread Sicherheit ist nicht unmittelbar für mich.

Meine Entwicklungsplattform ist Intel Xeon, Linux-Betriebssystem. Idealerweise würde ich gerne auch an PPC Linux arbeiten, aber das ist nicht das Wichtigste für mich.

Answer 1

erstellen geschlitzten Allocator:

Allocator ist mit vielen Speicherseite erstellt, die jeweils von gleicher Größe (512k, 256k, sollte die Größe für Ihre Anwendung abgestimmt werden).

Wenn ein Objekt diesen Zuordner zum ersten Mal nach Speicher fragt, weist er eine Seite zu. Das Zuweisen einer Seite besteht darin, sie aus der freien Liste zu entfernen (keine Suche, alle Seiten haben die gleiche Größe) und die Größe der Objekte festzulegen, die auf dieser Seite zugewiesen werden. Typischerweise wird diese Größe berechnet, indem die angeforderte Größe genommen und auf die nächste Potenz von 2 aufgerundet wird. Nachfolgende Zuordnungen derselben Größe erfordern nur ein wenig Zeigermathematik und inkrementieren die Anzahl der Objekte auf der Seite.

Die Fragmentierung wird verhindert, da die Slots alle dieselbe Größe haben und bei nachfolgenden Zuordnungen wieder aufgefüllt werden können. Die Effizienz wird beibehalten (in einigen Fällen verbessert), da für jede Zuweisung kein Memheader vorhanden ist (was bei kleinen Zuordnungen einen großen Unterschied macht, sobald die Zuweisungen groß werden, beginnt dieser Zuordner fast 50% des verfügbaren Speichers zu verschwenden).

Sowohl Zu- und Abmeldungen können in konstanter Zeit ausgeführt werden (keine Suche in der freien Liste nach korrekten Steckplätzen). Der einzige knifflige Teil einer Deallokation ist, dass du normalerweise keinen Memheader vor der Zuweisung haben willst, also musst du die Seite und den Index auf der Seite selbst herausfinden ... Es ist Samstag und ich habe meinen Kaffee nicht getrunken, also ich Ich habe dazu keinen guten Ratschlag, aber es ist einfach, aus der freigewordenen Adresse herauszufinden.

Edit: Diese Antwort ist ein wenig langatmig. Wie immer boost hat Ihren Rücken.

Answer 2

Wenn Sie die maximale Größe Ihrer Arrays kennen, können Sie einen benutzerdefinierten Zuordner verwenden. Sie müssen die Zuweisungsklasse selbst schreiben. Es sollte einen großen Teil des Speichers auf einmal zuweisen und in eine verknüpfte Liste umwandeln. Jedes Mal, wenn eine Objektinstanz erstellt werden muss, löschen Sie den Schwanz aus der Liste. Jedes Mal, wenn das Objekt freigegeben werden muss, fügen Sie der Liste einen Eintrag hinzu.

EDIT: Hier ist ein Beispiel von Bjarne Stroustrup Die C++ Programmiersprache, 3. Auflage:

class Pool 
{ 
private: 
    struct Link 
    { Link * next; }; 

    struct Chunk 
    { 
    enum {size = 8*1024-16}; 

    Chunk * next; 
    char mem[size]; 
    }; 

private: 
    Chunk * chunks; 
    const unsigned int esize; 
    Link * head; 

private: 
    Pool (const Pool &) { }  // copy protection 
    void operator = (Pool &) { } // copy protection 

public: 
    // sz is the size of elements 
    Pool(unsigned int sz) 
    : esize(sz < sizeof(Link*) ? sizeof(Link*) : sz), 
     head(0), chunks(0) 
    { } 

    ~Pool() 
    { 
    Chunk * n = chunks; 

    while(n) 
    { 
     Chunk * p = n; 
     n = n->next; 
     delete p; 
    } 
    } 


public: 

    // allocate one element 
    void * alloc() 
    { 
    if(head == 0) 
     grow(); 

    Link * p = head; 
    head = p->next; 

    return p; 
    } 

    // put an element back into the pool 
    void free(void * b) 
    { 
    Link * p = static_cast<Link*>(b); 
    p->next = head; //put b back as first element 
    head = p; 
    } 

private: 
    // make pool larger 
    void grow() 
    { 
    Chunk* n = new Chunk; 
    n->next = chunks; 
    chunks = n; 

    const int nelem = Chunk::size/esize; 
    char * start = n->mem; 
    char * last = &start [ (nelem - 1) * esize ]; 

    for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize 
     reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize); 

    reinterpret_cast<Link *>(last)->next = 0; 
    head = reinterpret_cast<Link *>(start); 
    } 
}; 

Answer 3

Wenn Sie die Größe des zugeordneten Objekts vorhersagen können, vor der Zeit werden Sie wahrscheinlich am besten sein, mit zu gehen ein linear zugewiesener Speicherabschnitt und Ihr eigener benutzerdefinierter Zuordner (wie von @Kerido vorgeschlagen). Dazu würde ich hinzufügen, dass die effizienteste Methode darin besteht, Positionen innerhalb der Zuweisung auf Null zu setzen und zu tauschen und sich nicht um die Neupartitionierung und Verdichtung des Arrays zu kümmern (toten Raum zwischen den Zuweisungen lassen), so dass Sie sich nicht mit Indexaktualisierungen und Indizes befassen müssen Instandhaltung.

Wenn Sie Ihre Objekte im Voraus partitionieren können (dh Sie wissen, dass Sie nicht feste Größenelemente haben, aber die Gruppe leicht), teilen Sie sie in Buckets und weisen Sie jedem Speicher Buckets vor und ordnen Sie die Objekte den entsprechenden Elementen zu Eimer. Wenn Ihre Objekte die Größe im Laufe ihrer Lebensdauer ändern können, kann dies schwierig werden. Berücksichtigen Sie diese Vorgehensweise sorgfältig.