Effiziente Heap-Manager für schwere Churn, winzige Allocs?

StackOverflow https://stackoverflow.com/questions/228081

Frage

Ich bin auf der Suche nach Ideen für einen Heap-Manager eine ganz bestimmte Situation zu behandeln: Viele, viele sehr kleine Zuweisungen, die jeweils 12 bis 64 Bytes reichen. Alles, was größer ist, werde ich zu dem regulären Heap-Manager weitergeben, so dass nur kleine Blöcke müssen für sein gesorgt. Nur 4-Byte-Ausrichtung benötigt wird.

Meine Hauptanliegen sind

  1. Overhead. Der reguläre libc Heap wird eine Zuordnung zu einem Vielfachen von 16 Bytes normalerweise aufrunden, dann einem weiteren 16-Byte-Header hinzufügen - das bedeutet über 50% Overhead auf einer 20-Byte-Zuordnung, die saugt
    2. .
  2. Performance

Ein hilfreicher Aspekt ist, dass Lua (die der Benutzer dieses Heap ist) wird Ihnen die Größe des Blocks es befreit ist, wenn es frei () ruft - diese bestimmte Optimierungen ermöglichen kann,

.

Ich werde meinen derzeitigen Ansatz veröffentlichen, die funktionieren ok, aber ich möchte auf sie verbessern, wenn überhaupt möglich. Irgendwelche Ideen?

War es hilfreich?

Lösung

Es ist möglich, einen Heap-Manager zu bauen, die sehr effizient für Objekte, die alle die gleiche Größe haben. Sie könnten einer dieser Haufen für jede Größe des Objekts erstellen, die Sie benötigen, oder wenn Sie nicht ein wenig Platz mit nichts dagegen, eine für 16-Byte-Objekte erstellen, eine für 32 und eine für 64. Der maximale Aufwand wäre 31 Bytes für eine 33-Byte-Zuordnung (die auf den 64 Blockhaufen gehen würde).

Andere Tipps

zu erweitern, was Greg Hewgill sagt, ein Weg, um eine hocheffiziente fester Größe Haufen zu tun ist:

  1. Split einen großen Puffer in Knoten. Knotengröße muss mindestens sizeof (void *) sein.
  2. String sie zusammen in eine einfach verknüpften Liste (die „freie Liste“), die erste sizeof (void *) Bytes jeden freien Knoten als Verknüpfungszeiger verwenden. Zugeordnete Knoten keinen Link Zeiger benötigen, so pro-Knoten Kopf 0 ist.
  3. Weisen durch den Kopf der Liste zu entfernen und wiederkehr es (2 Lasten, 1 Speicher).
  4. Geben Sie durch an der Spitze der Liste (1 Last, 2 Speicher) eingesetzt wird.

Offensichtlich Schritt 3 muss auch prüfen, ob die Liste der leer ist, und wenn ja, ein paar Arbeit tun, um einen neuen großen Puffer bekommen (oder nicht).

Noch effizienter, als Greg D und hazzen sagen, ist durch Erhöhen oder Erniedrigen einen Zeiger (1 Last, 1 Speicher) zuzuordnen, und nicht einen Weg bieten einen einzelnen Knoten überhaupt zu befreien.

Edit: In beiden Fällen frei mit der Komplikation „etwas größer ich auf den regulären heap-Manager übergeben“ beschäftigen, indem die hilfreiche Tatsache, dass Sie die Größe zurück in den Anruf erhalten zu befreien. Sonst würden werden Sie entweder bei der Suche einer Flagge (Overhead wahrscheinlich 4 Byte pro Knoten) oder auch eine Suche in einer Art Aufzeichnung des Puffers (s) Sie verwendet haben.

Die Antwort kann für diese Objekte auf die Lebensdauer Muster ab. Wenn die Objekte alle instanziiert werden, wie Sie vorgehen, und dann alle auf einen Schlag entfernt, kann es sinnvoll sein, einen sehr einfachen Heap-Manager zu erstellen, die Speicher zuweist, indem Sie einfach einen Zeiger erhöht wird. Dann, wenn Sie fertig sind, blasen den gesamten Haufen weg.

Raymond Chen hat diese interessanten Beitrag dass kann Ihnen helfen, zu begeistern. :)

Ich mag onebyones Antwort.

Sie können auch die Buddy-System für Ihre Sätze von festen Größe Haufen betrachten.

Wenn ein Haufen Speicher zugeordnet wird, verwendet wird, und befreit, bevor die nächste Runde der Zuteilung an bewegten, würde ich die einfachste allocator möglich schlägt vor, mit: 

typedef struct _allocator {
    void* buffer;
    int start;
    int max;
} allocator;

void init_allocator(size_t size, allocator* alloc) {
    alloc->buffer = malloc(size);
    alloc->start = 0;
    alloc->max = size;
}

void* allocator_malloc(allocator* alloc, size_t amount) {
    if (alloc->max - alloc->start < 0) return NULL;
    void* mem = alloc->buffer + alloc->start;
    alloc->start += bytes;
    return mem;
}

void allocator_free(allocator* alloc) {
    alloc->start = 0;
}

Ich verwende einen meist O (1) Small Block Memory Manager (SBMM). Im Grunde funktioniert es so:

1) Es weist größere Super von dem O und verfolgt die Start + End-Adressen als Bereich an. Die Größe des Superblocks ist einstellbar, aber 1MB macht eine ziemlich gute Größe.

2) Die Super in Blöcke unterteilt ist (auch in der Größe verstellbar ... 4K-64K ist gut, je nach Ihrer Anwendung). Jeder dieser Blöcke Griffe Zuordnungen von einer bestimmten Größe und speichert all Elemente in dem Block als einfach verkettete Liste. Wenn Sie einen Superblock zuordnen, können Sie eine verknüpfte Liste der freien Blöcke machen.

3) ein Element Zuweisungsmittel A) überprüfen Sie, ob es einen Block mit kostenlosen Produkten ist, dass die Größe der Handhabung - und wenn nicht, einen neuen Block von der Super zuzuordnet. B) Entfernen der Artikel aus der freien Liste Blockade.

4) unter der Adresse eines Elements Befreit bedeutet A) Finding Superblock enthält Adresse (*) B) Finding-Block in Superblock (subtrahieren Superblock-Startadresse und dividieren durch Blockgröße) C) Pushing Artikel zurück an den freien Artikelliste des Blocks.

Wie ich bereits sagte, ist dies SBMM sehr schnell, wie es läuft mit O (1) Leistung (*). In der Version, die ich umgesetzt haben, verwende ich einen AtomicSList (ähnlich SLIST in Windows), so dass es nicht nur O (1) Leistung, sondern auch THREAD und LockFree bei der Umsetzung. Sie könnten den Algorithmus Win32 SLIST tatsächlich implementieren, wenn man wollte.

Interessanterweise ist der Algorithmus für die Blöcke aus dem Super oder Artikel des Block Ergebnis in fast identicaly Code (sie sind beid O (1) Zuteilungen aus einer Freien Liste) zugewiesen wird.

(*) Die Superblöcke werden in einem rangemap mit O (1) angeordnet durchschnittliche Leistung (aber ein Potential O (Lg N) für die Worst-Case wobei N die Anzahl der Superblöcke ist). Die Breite des rangemap hängt davon ab, zu wissen, etwa wie vielen Speicher Sie, um brauchen werden die O (1) Leistung zu erhalten. Wenn Sie überschreiten, werden Sie ein wenig Speicher verschwenden, aber immer noch O (1) Leistung. Wenn Sie unterschreiten, werden Sie O (Lg N) Leistung nähern, aber die N ist für den Superblock zählen - nicht die Punktezählung. Da der Superblock Zahl ist sehr gering im Vergleich zu dem Postenzähler (um etwa 20 binäre Größenordnung in meinem Code), ist es nicht so kritisch wie der Rest des Allocator ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top