Strategie zuzuteilen / Frei viele kleine Objekte

Question

Ich bin liebäugelt mit bestimmtem Caching-Algorithmus, der etwas ist eine Herausforderung. Grundsätzlich braucht es viele kleine Objekte (Doppelarrays, 1 bis 256 Elemente), mit Objekten zugänglich durch kartiert Wert, map[key] = array zuzuteilen. Zeit zu initialisierten Array kann sehr groß sein, in der Regel mehr als 10 Tausend CPU-Zyklen.

Mit viel meine ich Gigabyte insgesamt um. Objekte müssen in einer Zeit, in zufälligen Stellen, ein Objekt je nach Bedarf, in der Regel knallten / geschoben werden. Lebensdauer eines Objekts im Allgemeinen lang, Minuten oder mehr, jedoch kann Gegenstand unter Zuordnung / Aufhebung der Zuordnung mehrmals während Dauer des Programms sein.

Was gute Strategie zu vermeiden Speicherfragmentierung würde, während immer noch angemessen aufrechterhalten zuteilen ausplanen Geschwindigkeit?

Ich bin mit C ++, so dass ich neuer und malloc verwenden kann. Danke.

Ich weiß, dass es eine ähnliche Fragen auf der Website Effizientes viele Zuteilung kurzlebig kleine Objekte , sind etwas anders, Thread-Sicherheit ist nicht sofort Problem für mich.

meine Entwicklungsplattform ist Intel Xeon, Linux-Betriebssystem. Idealerweise würde ich an der Arbeit auf PPC-Linux wie auch, aber es ist nicht das Wichtigste für mich.

Answer 1

Erstellen Sie eine geschlitzte 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).

Das erste Mal, fragt ein Objekt dieses Allocator für Speicher eine Seite zuordnet. eine Seite Zuteilen besteht aus aus der freien Liste zu entfernen (keine Suche, alle Seiten sind gleich groß) und die Größe der Objekte festlegen, die auf dieser Seite zugewiesen werden. Typischerweise diese Größe berechnet, indem die gewünschte Größe zu nehmen und es auf die nächste Potenz von 2 Nachfolgende Zuweisungen von gleicher Größe erfordern nur ein wenig Zeigermathematik und Erhöhen der Anzahl der Objekte auf der Seite gerundet wird.

Fragmentation wird verhindert, da Slots sind alle gleich groß und kann auf nachfolgende Zuweisungen nachgefüllt werden. Effizienz aufrechterhalten wird (in einigen Fällen verbessert), weil es keine memheader pro Zuteilung ist (die einen großen Unterschied macht, wenn die Zuweisungen sind klein, wenn Zuweisungen groß werden diese allocator beginnt fast 50% des verfügbaren Speichers zu verschwenden).

Sowohl Zuweisungen und Freigaben können in konstanter Zeit (keine Durchsuchungen von der freien Liste für die korrekten Steckplatz) durchgeführt werden. Der einzige schwierige Teil über eine Freigabe ist, dass Sie nicht in der Regel eine memheader wollen die Zuordnung vorhergehende, so dass Sie, um herauszufinden, die Seite und den Index in der Seite haben sich ... Es ist Samstag und ich hatte nicht meinen Kaffee so ich keine guten Ratschläge haben, dass über das tut, ist es einfach genug, um von der deallokierten Adresse, um herauszufinden, though.

Edit: Diese Antwort ist ein bisschen langatmig. Wie üblich Schub hat den Rücken.

Answer 2

Wenn Sie die Größe des zugeordneten Objekts vor der Zeit vorherzusagen, kann man wohl am besten sein wird, mit einem linear zugeordnet Teil des Speichers und Ihre eigenen allocator zu gehen (wie @Kerido vorgeschlagen). Um das möchte ich hinzufügen, dass die effizienteste Methode innerhalb der Zuweisung auf Null und Swap für Positionen sein würde und sich keine Sorgen über repartitioning und Verdichten des Array (lassen Totraum zwischen Zuweisungen), so dass Sie nicht mit dem Index-Updates und Index zu tun haben Wartung.

Wenn Sie Ihre Objekte vor der Zeit partitionieren können (dh Sie wissen, dass Sie nicht-feste Größe Elemente, aber die Gruppe leicht) teilen sie in Eimern und vorbelegen Speicherblöcke in jedem Eimer und tauschen Sie die Einzelteile in den entsprechenden Eimer . Wenn Ihre Objekte Größe über ihre Lebensdauer ändern können, die erhalten heikel kann zu verwalten, so diesen Ansatz sorgfältig abwägen.

Answer 3

Wenn Sie die maximale Größe des Arrays Sie wissen, können Sie eine benutzerdefinierte allocator verwenden. Sie werden die allocator Klasse selbst schreiben müssen. Was sollte sie tun, ist ein großer Teil der Speicher zuweisen auf einmal und warf es zu einer verketteten Liste. Jedes Mal, wenn eine Objektinstanz erstellt werden muss, löschen Sie den Schwanz aus der Liste. Jedes Mal, wenn das Objekt Bedürfnisse befreit werden, können Sie einen Eintrag in die Liste aufzunehmen.

EDIT: Hier ist ein Beispiel von Bjarne Stroustrup Die Programmiersprache C ++, 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);
  }
};