Ich suche nach Ideen für einen Heap-Manager, um eine ganz spezielle Situation zu bewältigen: Viele und sehr kleine Zuweisungen von jeweils 12 bis 64 Bytes. Alles, was größer ist, werde ich an den normalen Heap-Manager weiterleiten, so dass nur kleine Blöcke berücksichtigt werden müssen. Nur 4-Byte-Ausrichtung ist erforderlich.
Meine Hauptsorgen sind
Ein hilfreicher Aspekt ist, dass Lua (der Benutzer dieses Heapspeichers) Ihnen die Größe des Blocks mitteilen wird, den es freigeben wird, wenn es free () aufruft - dies kann bestimmte Optimierungen ermöglichen.
Ich werde meinen derzeitigen Ansatz posten, der in Ordnung ist, aber ich würde es gerne verbessern, wenn irgend möglich. Irgendwelche Ideen?
Es ist möglich, einen Heap-Manager zu erstellen, der für Objekte mit derselben Größe sehr effizient ist. Sie können einen dieser Heaps für jede benötigte Objektgröße erstellen oder, falls Sie etwas Speicherplatz benötigen, einen für 16 Byte-Objekte erstellen, einen für 32 und einen für 64. Der maximale Aufwand wäre 31 Bytes für eine 33-Byte-Zuweisung (die auf dem 64-Blöcke-Heap gehen würde).
Um zu erweitern, was Greg Hewgill sagt, ist eine Möglichkeit, einen ultra-effizienten Heap mit fester Größe zu machen:
Offensichtlich muss Schritt 3 auch prüfen, ob die Liste leer ist, und wenn das der Fall ist, muss ein großer neuer Puffer angelegt werden (oder fehlschlagen).
Noch effizienter, wie Greg D und hazzen sagen, ist die Zuweisung durch Inkrementieren oder Dekrementieren eines Zeigers (1 Ladevorgang, 1 Speichervorgang) und keine Möglichkeit, einen einzelnen Knoten freizugeben.
Edit: In beiden Fällen kann free mit der Komplikation umgehen "etwas Größeres vererbe ich den normalen Heap-Manager" durch die hilfreiche Tatsache, dass man die Größe im Call wieder frei bekommt. Andernfalls würdest du entweder ein Flag (Overhead, wahrscheinlich 4 Bytes pro Knoten) betrachten oder aber eine Suche in einer Art von Datensatz von den Puffern, die du benutzt hast.
Die Antwort hängt möglicherweise von den Lebensdauermustern für diese Objekte ab. Wenn die Objekte alle instanziiert werden, während Sie fortfahren, und dann alle auf einen Schlag entfernt werden, kann es sinnvoll sein, einen sehr einfachen Heap-Manager zu erstellen, der Speicher durch einfaches Inkrementieren eines Zeigers zuweist. Dann, wenn du fertig bist, blase den gesamten Haufen weg.
Raymond Chen hat einen interessanten Beitrag verfasst, der dazu beitragen könnte, Sie zu inspirieren. :)
Ich mag Onebyones Antwort.
Sie können auch das Buddy-System für Ihre Sets von Fixed-Size-Heaps in Betracht ziehen.
Ich benutze einen meist O (1) Small Block Memory Manager (SBMM). Grundsätzlich funktioniert es so:
1) Es weist größere SuperBlocks vom Betriebssystem zu und verfolgt die Start- und Endadressen als Bereich. Die Größe des SuperBlock ist einstellbar, aber 1MB macht eine ziemlich gute Größe.
2) Die Superblöcke sind in Blöcke aufgeteilt (auch in der Größe einstellbar ... 4K-64K ist gut, abhängig von Ihrer App). Jeder dieser Blöcke verarbeitet Zuweisungen einer bestimmten Größe und speichert alle Elemente im Block als eine einfach verknüpfte Liste. Wenn Sie einen SuperBlock zuweisen, erstellen Sie eine verknüpfte Liste von Freien Blöcken.
3) Das Zuweisen eines Elements bedeutet, dass A) überprüft wird, ob ein Block mit freien Elementen vorhanden ist, der diese Größe verarbeitet - und falls dies nicht der Fall ist, wird ein neuer Block den SuperBlocks zugewiesen. B) Entfernen des Elements aus der freien Liste des Blocks.
4) Ein Objekt nach Adresse freizugeben bedeutet, dass A) SuperBlock mit Adresse (*) gefunden wird. B) Block in SuperBlock finden (SuperBlock Startadresse subtrahieren und durch Blockgröße dividieren). C) Objekt zurück in die Freie Elementliste des Blocks schieben / p>
Wie gesagt, dieses SBMM ist sehr schnell, da es mit O (1) -Leistung (*) läuft. In der von mir implementierten Version verwende ich eine AtomicSList (ähnlich wie SLIST in Windows), so dass es nicht nur O (1) Performance sondern auch ThreadSafe und LockFree in der Implementierung gibt. Sie könnten den Algorithmus tatsächlich mit Win32 SLIST implementieren, wenn Sie möchten.
Interessanterweise ergibt der Algorithmus zum Zuweisen von Blöcken aus den SuperBlocks oder Elementen aus den Blöcken nahezu identischen Code (sie sind beide O (1) -Zuordnungen von einer Freien Liste).
(*) Die SuperBlocks sind in einer Rangliste mit O (1) Durchschnittsleistung angeordnet (aber ein Potential O (Lg N) für worstcase, wobei N die Anzahl der SuperBlocks ist). Die Breite der Rangemap hängt davon ab, wie viel Speicher Sie benötigen, um die O (1) -Leistung zu erhalten. Wenn Sie überschwingen, verschwenden Sie ein wenig Speicher, erhalten aber trotzdem O (1) Leistung. Wenn Sie unterschwingen, nähern Sie sich der Leistung O (Lg N), aber das N ist für die SuperBlock-Zählung - nicht die Anzahl der Elemente. Da die SuperBlock-Zählung im Vergleich zur Anzahl der Elemente sehr gering ist (um etwa 20 binäre Größenordnungen in meinem Code), ist sie nicht so kritisch wie der Rest des Allokators.
Tags und Links c performance memory-management heap lua