Strategie zur Zuweisung/Freigabe vieler kleiner Objekte

Question

Ich bin toying mit bestimmten Caching-Algorithmus, der etwas herausfordernd ist. Grundsätzlich muss es viele kleine Objekte (Double Arrays, 1 bis 256 Elemente) zuweisen, mit Objekten, die durch gemappte Wert zugänglich, map[key] = array Die Zeit bis zur Initialisierung des Arrays kann recht groß sein, im Allgemeinen mehr als 10 Tausend CPU-Zyklen.

Mit "viel" meine ich insgesamt etwa ein Gigabyte. Objekte müssen je nach Bedarf gepoppt/geschoben werden, in der Regel an zufälligen Stellen, ein Objekt nach dem anderen. Die Lebensdauer eines Objekts ist in der Regel lang, Minuten oder mehr, jedoch kann das Objekt während der Programmdauer mehrmals zugewiesen/freigegeben werden.

Was wäre eine gute Strategie, um eine Speicherfragmentierung zu vermeiden und gleichzeitig eine vernünftige Geschwindigkeit beim Zuweisen und Freigeben beizubehalten?

Ich verwende C++, also kann ich new und malloc verwenden. Danke.

Ich weiß, dass es auf der Website ähnliche Fragen gibt, Effiziente Zuweisung vieler kurzlebiger kleiner Objekte sind etwas anders, Fadensicherheit ist für mich kein unmittelbares Thema.

meine Entwicklungsplattform ist Intel Xeon, Betriebssystem Linux. Idealerweise würde ich gerne auch auf PPC-Linux arbeiten, aber es ist nicht das wichtigste für mich.

Answer 1

Erstellen Sie einen Slot-Zuweiser:

Der Allocator wird mit vielen Speicherseiten erstellt, die alle gleich groß sind (512k, 256k, die Größe sollte auf Ihre Bedürfnisse abgestimmt werden).

Das erste Mal, wenn ein Objekt diesen Allokator um Speicher bittet, wird eine Seite zugewiesen. Die Zuweisung einer Seite besteht darin, sie aus der Liste der freien Seiten zu entfernen (keine Suche, alle Seiten sind gleich groß) und die Größe der Objekte festzulegen, die auf dieser Seite zugewiesen werden sollen. Normalerweise wird diese Größe berechnet, indem die angeforderte Größe genommen und auf die nächste Potenz von 2 aufgerundet wird. Nachfolgende Zuweisungen derselben Größe erfordern nur ein wenig Zeigerberechnung und die Erhöhung der Anzahl der Objekte auf der Seite.

Eine Fragmentierung wird verhindert, da die Slots alle die gleiche Größe haben und bei späteren Zuweisungen wieder aufgefüllt werden können. Die Effizienz wird beibehalten (in einigen Fällen verbessert), da es keinen Memheader pro Zuweisung gibt (was einen großen Unterschied macht, wenn die Zuweisungen klein sind, sobald die Zuweisungen groß werden, beginnt dieser Allokator fast 50% des verfügbaren Speichers zu verschwenden).

Sowohl Allokationen als auch Deallokationen können in konstanter Zeit durchgeführt werden (kein Durchsuchen der freien Liste nach korrekten Slots). Das einzig Knifflige an einer Deallokation ist, dass man normalerweise keinen Memheader vor der Allokation haben möchte, also muss man die Seite und den Index in der Seite selbst herausfinden... Es ist Samstag und ich habe noch keinen Kaffee getrunken, also habe ich keine guten Ratschläge, wie man das macht, aber es ist einfach genug, es anhand der deallokierten Adresse herauszufinden.

Edit: Diese Antwort ist ein bisschen langatmig. Wie üblich erhöhen hält Ihnen den Rücken frei.

Answer 2

Wenn Sie die Größe des zugewiesenen Objekts im Voraus vorhersagen können, ist es wahrscheinlich am besten, mit einem linear zugewiesenen Speicherstück und Ihrem eigenen benutzerdefinierten Allokator zu arbeiten (wie @Kerido vorgeschlagen hat). Dazu würde ich hinzufügen, dass die effizienteste Methode wäre, Null und Swap für Positionen innerhalb der Zuweisung, und nicht über Repartitionierung und Verdichtung des Arrays (verlassen toten Raum zwischen Zuweisungen) kümmern, so dass Sie nicht mit Index-Updates und Index Wartung beschäftigen müssen.

Wenn Sie Ihre Objekte im Voraus partitionieren können (d.h. Sie wissen, dass Sie Elemente mit nicht fester Größe haben, die sich aber leicht gruppieren lassen), teilen Sie sie in Buckets auf, weisen jedem Bucket Speicherbereiche zu und tauschen die Elemente in den entsprechenden Bucket aus. Wenn Ihre Objekte während ihrer Lebensdauer ihre Größe ändern können, kann das schwierig zu handhaben sein, daher sollten Sie diesen Ansatz sorgfältig prüfen.

Answer 3

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

EDIT: hier ist ein Beispiel aus Bjarne Stroustrup's 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);
  }
};