buddy allocator workshop
1.0.0
Dieses Repository enthält einige kleine Beispielimplementierungen von Buddy -Allocatoren. Sie sind so konzipiert, dass sie das physische Gedächtnis zuweisen, obwohl sie für andere Arten der Allokation wie den Haufen verwendet werden könnten. Schließlich wird die beste Leistung in Blume verschmolzen.
Zuerst klonen Sie das Repo. Dann cd in die CD und machen Sie cargo +nightly run , um alle Demo -Allokatoren zu betreiben. Standardmäßig beträgt die Blockgröße 4KIB und die Anzahl der Blöcke beträgt 100 000, sodass dies für das Beispiel für verknüpfte Listen eine Weile dauern kann. Machen Sie sich keine Sorgen, es gibt nichts tatsächlich zu - nur Scheinspeicherblöcke. Pass -h oder --help , um Hilfe zu erhalten und die Verwendung anzusehen. Sie können den Quellcode bearbeiten, um die min/max -Blockgrößen usw. zu ändern, um die Unit -Tests auszuführen und cargo test auszuführen. Leider gibt es noch keine Frachtbenchmarks, aber ich habe es auf meinem Windows -Gerät ziemlich unwissenschaftlich auf meinen Windows -Maschine untersucht.
Ich habe die Algorithmen getestet, indem ich verschiedene Implementierungen mithilfe der integrierten Berichterstattung zeitete und einen Gibyte in 4KIB -Blöcken (mit dem Ausdruck) auf meinem Windows -Computer zuteilt. Wenn Sie andere Benchmarks hinzuzufügen, sehen Sie sich bitte an.
(MSI CX61-2qf)
| Durchführung | Zeit | Durchsatz |
|---|---|---|
| Listen - Vektoren | 2 min | ~ 8.33e-3 gib/s |
| Listen - doppelt verknüpfte Listen | 25 Minuten | ~ 6.66e-4 gib/s |
| RB -Bäume - Vektoren | ~ 0,3s | ~ 3.33 Gib/s |
| RB -Bäume - einzig verknüpfte Listen | ~ 0,5s | ~ 2 Gib/s |
| Bitmapbaum | ~ 0,07s | ~ 14.28 Gib/s |
HINWEIS: Der Durchsatz wird von der Zeit extrapoliert, um 1 Gib in 4kib -Blöcken zuzuweisen. Für Implementierungen mit Komplexität> O (log n) (z. B. der naiven listenbasierten Implementierung) ist dies nicht genau - der Durchsatz wird langsamer, wenn weitere Blöcke zugewiesen werden. Dies sollte für solche, die eine Komplexität von O (log n) oder weniger haben, genau sein.
Diese Implementierung hält eine Liste pro Blockreihenfolge. Es ist generisch über die verwendeten Typof -Listen. Ich habe mich entschlossen, zwei Arten von Listen zu verwenden: Vektoren ( Vec von std ) und doppelt verknüpfte Listen ( LinkedList , ebenfalls von std ). Verknüpfte Listen werden häufig für ihre vorhersehbare Push -Zeit geschätzt (keine zum Schieben erforderlich), während Vektoren eine bessere Cache -Lokalität haben, da die Elemente in einem zusammenhängenden Speicherblock zugewiesen werden. Ich habe doppelt verknüpfte Listen verwendet, da sie für die Indexierung schneller als einzeln verknüpfte Listen sind, da sie von hinten oder Front iterieren können, je nachdem, ob der Index näher am Anfang oder am Ende der Liste liegt. Ich habe mich entschlossen, beide zu testen, um zu sehen, welche insgesamt eine bessere Leistung erbringen würde.
Die Implementierung ist rekursiv. Um einen kostenlosen Bestellblock K zuzuweisen, sucht es zunächst nach kostenlosen Blöcken in der Liste der Bestellk -Blöcke. Es führt keine kostenlose Liste. Wenn keiner gefunden wird, wird es wiederholt, indem versucht wird, einen Block der Bestellung K + 1. zuzuweisen. Schließlich, wenn zu keinem Zeitpunkt freie Blöcke gefunden wurden, gab es auf, dass er aufgibt und Panik. Sobald es einer ist, spaltet es ihn in zwei Hälften, wodurch der ursprüngliche Block aus seiner Bestellliste entfernt und die Hälften sofort auf die Bestellliste gedrückt werden. Anschließend gibt es die Reihenfolge und den Index des ersten Blocks in seiner Bestellliste zurück. Sie finden diesen Algorithmus in find_or_split .
Eine schnelle, unwissenschaftliche Benchmark auf meinem Windows-Maschine besagt, dass es ungefähr zwei Minuten gedauert hat, um eine vollständige Gibibyte (1024^3 Bytes) zuzuweisen. Ich bemerkte, dass ein zweiter Pause ab und zu eine Pause einlässt, als es den gesamten Vektor neu zuordnen musste, um ein Element zu drücken.
std doppelt verknüpfte ListenEin ähnlicher Benchmark besagt, dass es fünfundzwanzig Minuten gedauert hat, um eine vollständige Gibibyte zuzuweisen. Dies ist über zwölfmal langsamer als die gleiche Implementierung mit Vektoren. Diese Implementierung wurde jedoch nicht für verknüpfte Listen optimiert, daher ist sie etwas unfair. Im Gegensatz zur Implementierung mit Vektoren bemerkte ich keine Pausen, aber die Zuordnung wurde allmählich langsamer und langsamer.
Wir können daraus schließen, dass zwar doppelt verknüpfte Listen theoretisch zwar schneller beim Drücken sind als Vektoren, aber immer noch 12 -mal langsamer als Vektoren. Dies könnte daran liegen, dass die Implementierung geringfügig zugunsten von Vektoren (viel Indexierung) war oder dass die Vektoren einen höheren Cache-Ort hatten und daher weniger Cache-Fehlschriften erlebten, während verknüpfte Listen mit hohen Cache-Missen erfahren, da sie individuell heap-zuallozierte Elemente haben.
Diese Implementierung hält einen rot-schwarzen Baum (von intrusive_collections ) für alle Blöcke und eine kostenlose Liste für jede Bestellung. Die kostenlosen Listen wurden für SinglyLinkedList von Vec und intrusive_collections implementiert. Ich habe eine einzig verknüpfte Liste ausgewählt, da es keinen wirklichen Vorteil gegeben hätte, das Verknüpfen zu verdoppeln - die einzige Methode, die (vernachlässigbar so) profitiert hätte, ist FreeList::remove , aber dies wird immer am zweiten Element in dieser freien Liste aufgerufen, sodass es keinen wirklichen Punkt gibt, dies zu optimieren. Der rotschwarze Baum ist einzeln jeden Knoten zu, was die Cache-Effizienz verschlimmert, aber im Gegensatz zu std BTreeSet / BTreeMap ist seine Suche O(log n) , während std eine lineare Suche verwendet, die nicht O(log n) ist (Sie können hier darüber lesen). Die Bäume von std richten jedoch keine einzeln einzeln zu, zuordnen Knoten nicht zu, sodass die Cache -Lokalität besser ist. Ich entschied, dass es zwar wahr war, da ein Buddy -Allocator mit unglaublich großer Anzahl von Blöcken umgehen muss, aber wichtiger war, einen effizienteren Suchalgorithmus zu haben.
Die Implementierung ist rekursiv. Um einen kostenlosen Bestellblock K zuzuweisen, sucht es zunächst nach kostenlosen Blöcken in der kostenlosen Liste der Order K -Blöcke. Wenn keiner gefunden wird, wird es wiederholt, indem versucht wird, einen Block der Bestellung K + 1. zuzuweisen. Schließlich, wenn zu keinem Zeitpunkt freie Blöcke gefunden wurden, gab es auf, dass er aufgibt und Panik. Sobald es einer ist, spaltet es es in zwei Hälften, entfernen Sie den ursprünglichen Block vom Baum und setzen Sie die Hälften ein, drücken Sie ihre Adressen auf die entsprechende freie Liste. Es gibt dann einen Cursor zurück, der auf den ersten Block zeigt. Sie finden diesen Algorithmus in find_or_split . Bei der äußersten Rekursionsschicht (die Funktion, die die rekursive find_or_split -Funktion tatsächlich aufruft) wird der zurückgegebene Block als verwendet markiert und aus der freien Liste entfernt.
Die Verwendung von Vektoren als kostenlose Listen brauchte ~ 0,3s, um eine vollständige Gib zuzuweisen. Dies ist ~ 0,2s schneller als die verknüpften Listen als kostenlose Listenversion. Dies liegt wahrscheinlich daran, dass Vektoren einen besseren Cache -Lokalität haben.
Die Verwendung von verknüpften Listen als kostenlose Listen brauchte ~ 0,5s, um eine vollständige Gib zuzuweisen. Siehe Abschnitt "Free Lists" oben.
Diese Implementierung war 400x schneller als die naive listenbasierte Implementierung (bestenfalls mit Vektoren als kostenlose Listen). Dies ist wahrscheinlich darauf zurückzuführen, dass rot-schwarze Bäume mit O(log n) -Operationen auf der ganzen Linie schneller als die Suchvorgänge, Einfügungen und Entfernungen von Vektoren oder verknüpften Listen sind.
Diese Implementierung ist per se keine Bitmap, sondern eine Änderung eines Bitmap -Systems. Im Wesentlichen speichert jeder Block im Baum die größte Reihenfolge (vollständig zusammengeführt) irgendwo darunter. Zum Beispiel sieht ein Baum, der mit 4 Bestellungen kostenlos ist, wie folgt aus:
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
Wenn wir einen Block der Bestellung 0 zuordnen, sieht es so aus (T ist T acen):
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
Es wird als abgeflachtes Array implementiert, wo für einen Baum wie
1
2 3
Die Darstellung ist 1; 2; 3 . Dies hat die schöne Eigenschaft, dass der Index des linken Kindes eines bestimmten Index 2 * index ist, wenn wir Indizes ab 1 (dh Indizes und nicht Offsets) verwenden, und das rechte Kind einfach 2 * index + 1 . Der Elternteil ist floor(index / 2) . Da alle diese Operationen mit 2S funktionieren, können wir ein effizientes Bitschicht verwenden, um sie auszuführen ( index << 1 , (index << 1) | 1 und index >> 1 ).
Wir können eine binäre Suche durchführen, um einen Block zu finden, der frei von der gewünschten Reihenfolge ist. Zunächst prüfen wir, ob es kostenlos Blöcke der gewünschten Bestellung gibt, indem Sie den Stammblock überprüfen. Wenn es gibt, überprüfen wir, ob das linke Kind genug kostenlos hat. Wenn dies der Fall ist, überprüfen wir erneut, dass es ein übriges Kind usw. ist. Wenn das linke Kind eines Blocks nicht genügend Blöcke frei hat, verwenden wir einfach sein rechtes Kind. Wir wissen, dass das richtige Kind dann genug frei haben muss oder der Stammblock ungültig ist.
Diese Implementierung war sehr schnell. Auf meinem Computer dauerte es nur ~ 0,07s, um 1Gib zuzuweisen. Ich habe gesehen, dass es auf meinem Computer jedoch bis zu 0,04 Sekunden leistet - die Leistung schwankt etwas. Ich gehe davon aus, dass dies mit CPU -Last zu tun hat.
Diese Implementierung hat keine sehr gute Cache -Lokalität, da die Ebenen weit voneinander entfernt sind, sodass ein übergeordneter Block sehr weit von seinem Kind entfernt sein kann. Allerdings ist alles andere noch sehr schnell, so dass es so ausgeht. Es ist auch o (log n), aber praktisch ist es so schnell, dass dies nicht wirklich wichtig ist. Als Referenz: Die Zuordnung von 8Gib hat 0,6 Sekunden lang für mich gekostet, aber ich habe gesehen, dass es bei> 150 ms auf dem Laptop von @Gyy1000 viel besser funktioniert hat.
Wenn Sie etwas hinzufügen können (z. B. eine Bearbeitung an die Readme oder eine andere Implementierung oder einen Benchmark), können Sie eine Pull -Anfrage vorlegen! Sie können auch ein Problem erstellen. Wenn Sie nur chatten möchten, können Sie mich gerne auf die Rost -Zwietracht (Restioson#8323) pingen.
