Rmalloc
Rmalloc ist eine malloc-Implementierung, d.h. es stellt eine dynamische Speicherverwaltung zur Verfügung.
Ein Grund für die Programmierung von Rmalloc war ein Problem auf welches ich beim Testen eines meiner Programme gestossen bin. Dabei ergab sich bei der Verwendung von meheren Gigabytes eine sehr schlechte Laufzeit, welche im Widerspruch zur theoretischen Komplexität stand. Das Besondere des Verwendeten Programmes bestand darin, dass der Speicher aufgeteilt war in viele kleine Speicherblöcke, welche ständig neu angelegt und wieder freigegeben wurden. Dieses Verhalten stellte für alle von mir getesten Speicherverwaltungen ein Problem dar, insbesondere, falls dies parallel in mehreren Threads erfolgte. Als Konsequenz daraus habe ich mich entschlossen, selbst eine Speicherverwaltung zu schreiben, welche an das Problem angepasst war und deutlich bessere Resultate lieferte. Daneben zeigte Rmalloc auch bei anderen Programmen grosse Verbesserungen im Laufzeitverhalten und ist als allgemeine Speicherverwaltung einzustufen.
Die erste Version von Rmalloc folgte dem Prinzip des simple segregated storage, d.h. ohne Speicherbreiche zu trennen bzw. zusammenzufügen. Obwohl diese Technik sehr schnell ist und auch sehr gut bzgl. der Prozessoranzahl skaliert, trat hierbei eine grosse Fragmentierung bei bestimmten Anwendungsfällen auf. Somit beschränkte sich das Einsatzspektrum dieser Version auf Programme, bei welchen die angeforderten Speichergrössen in eine kleine Anzahl von Grössenklassen zerfallen.
Um die Fragmentierung einzugrenzen wurden Speicherblöcke getrennt und wieder zusammengefügt. Nun arbeitet Rmalloc ähnlich zu LKmalloc, d.h. es verwendet private Heaps für jeden Thread und alle Speicherblöcke sind fest an einen Heap gebunden.
Die Hauptunterschiede zwischen Rmalloc und KLmalloc betriffen die Art und Weise, wie kleine Speicherblöcke verwaltet werden, die Allokation vom Betriebssystem und die Abbildung von threads zu heaps.
Aus Gründen der Schnelligkeit werden kleine Blöcke in Rmalloc mittels Containern verwaltet, welche viele Blöcke gleicher Grösse beinhalten (analog zu hoard). Besonders im Falle eine grossen Zahl von Allokationen von kleinen Speicherblöcken (etwa bei der Arbeit mit Listen etc.) tritt hierbei ein deutlicher Laufzeitunterschied zutage. Diese Technik vermeidet zusätzlich das Trennen und Zusammenfügen von Blöcken ohne eine zusätzliche Fragmentierung zu verursachen.
Speicher wird vom Betriebssystem in Blöcken angefordert, deren Grösse dynamisch an den aktuellen Speicherverbrauch angepasst wird. Hierdurch wird die Anzahl der teuren Systemaufrufe (malloc, mmap oder sbrk) reduziert. LKmalloc verwendet hier eine konstante Grösse von 4 MB.
Die Zuweisung von Heaps zu Threads erfolgt mittels thread-privaten Daten (mittels PThread-Funktionen). Hierdurch ist die Anzahl von heaps identisch zur Anzahl der parallelen Threads. Diese Anpassung erfolgt automatisch und ist nicht auf eine vorherige Initialisierung (wie bei LKmalloc) angewiesen.