Der doppelköpfige Stack-Allocator: So stoppten Blizzard-Entwickler Speicherfragmentierung
The Double Headed Stack Allocator
Ein Stack-Allocator macht Speicherzuweisung so schnell wie eine Ganzzahl-Addition. Doch bei zwei Systemen mit unabhängigen Lebenszyklen – etwa Level-Geometrie und Charakterformen in einem Open-World-Spiel – zersplittert der Speicher. Die Lösung: ein doppelköpfiger Stack-Allocator, bei dem ein Stack von unten nach oben und der andere von oben nach unten wächst. Der Artikel zeigt die Technik anhand eines Beispiels mit 100 MB und erklärt, wie sie auch variable Objekte mit wahlfreiem Zugriff effizient speichert.
Wenn Sie einen Stack-Allocator allgemeiner für alle temporären Speicherzuweisungen während eines Frames verwenden, setzen Sie ihn möglicherweise zu Beginn des Frames auf 0 zurück.
- tom_
Das funktioniert auch mit einem gewöhnlichen Allocator gut. Bei einem früheren Arbeitgeber hatten wir eine Option „allocate high“ für den normalen Speichermanager, die die höchstmögliche Adresse statt der niedrigsten suchte. Ziemlich gut für Situationen, in denen man einige flüchtige Daten allokieren musste, während man persistente Daten erstellte, ohne unnötige Fragmentierung einzuführen.
- Panzerschrek
> Stellen Sie sich vor, Sie hätten ein Streaming-Weltspiel, bei dem, während der Spieler durch die Welt läuft, alte Levelgeometrie freigegeben und neue Levelgeometrie allokiert und von der Festplatte gestreamt wird.
In einem solchen Fall ist ein stackartiger Allocator nicht die beste Strategie. Man kann stattdessen eine Art zyklischen Allocator verwenden. Soweit ich weiß, hat Quake dies für den Oberflächen-Cache getan.
- kevin_thibedeau
Bipartite Puffer sind besser zum Speichern einer Sequenz von Objekten variabler Größe. Es funktioniert wie ein Ringpuffer und man bleibt nicht mit einer Speichererschöpfung des Bump-Allocators hängen. Dies erfordert sequenzielle Iteration, aber man braucht für solche Dinge selten wahlfreien Zugriff.
- windenntw
Und deshalb erlaubte AmigaOS eine MEMF_REVERSE-Option im Aufruf des Speicher-Allocators ( http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodo... )
Irgendwann 95 oder 96 erinnere ich mich, einen sehr sehr einfachen OS-Patch erstellt zu haben, der alle Allokationen > X Größe (1KB oder so ähnlich) zwang, MEMF_REVERSE zu verwenden, und das bewirkte Wunder bei der Reduzierung der Speicherfragmentierung :)
- saagarjha
Diese Art von Muster ist ziemlich verbreitet, wenn man es mit Pipelining irgendeiner Art zu tun hat. Eine andere Lösung, die ich früher implementiert habe, als ich mit dem Streamen von Gewichten in eine GPU zu tun hatte, ist, dass man den Bereich zweimal spiegelt und Zeiger in der Reihenfolge aus dem ersten Bereich ausgibt, aber es erlaubt, dass sie mithilfe virtueller Adressierung an den Anfang umbrechen. Ich habe festgestellt, dass dies etwas leistungsfähiger ist, da es erlaubt, mehrere Stufen im Voraus zu allokieren, weil einem nicht die „Seiten“ zum Allokieren ausgehen. Der doppelseitige Allocator erlaubt leider nur wirklich 1 zusätzliche Stufe für Ihre Pipeline.