de | en

Beschreibung

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.

Quelltext

RMalloc ist freie Software, wobei frei durch die LGPL definiert ist.

rmalloc.c
rmalloc-1.1.c
rmalloc-1.0.3.c
rmalloc-1.0.2.c
rmalloc-1.0.1.c
rmalloc-1.0.c
rmalloc-1.0-pre5.c
rmalloc-1.0-pre4.c
rmalloc-1.0-pre3.c
rmalloc-1.0-pre2.c
rmalloc-1.0-pre1.c
rmalloc-0.98.3.c
rmalloc-0.98.2.c
rmalloc-0.98.1.c
rmalloc-0.98.c
rmalloc-0.97.c
rmalloc-0.96.c
rmalloc-0.95.c
rmalloc-0.94.c
rmalloc-0.93.c
rmalloc-0.92.c
rmalloc-0.91.c
rmalloc-0.90.c
rmalloc.h
rmalloc-0.95.h
rmalloc-0.94.h
rmalloc-0.93.h
rmalloc-0.92.h
rmalloc-0.91.h

Änderungen

v1.1

  • Freigabe von nichtgenutzten Datensegmenten bei genügend freiem Speicher implementiert
  • nichtleere Wildnisblöcke werden nun von der Speicherverwaltung für mittlere Blöcke verwaltet, um eine “Good-Fit”-Strategie zu nutzen (reduziert die interne Fragmentierung unter Umständen beträchtlich)
  • Unterstützung von 16 Byte Datenausrichtung hinzugefügt (für SSE-Anwendungen)
  • Fehler beim Setzen der Größe von geteilten Blöcken beseitigt
  • Standard- und Fehlerausgabe modifiziert
  • Protokollierung von mehr Daten bei RMALLOC_TRACE
  • STAT_FRAGMENTATION entfernt (wurde nicht mehr genutzt)
  • “munmap” durch einen Mutex geschützt (scheint nicht Multithread-sicher zu sein)
  • nicht direkt verwaltete, sehr grosse Speicherbloecke werden nun ebenfalls in der Statistik geführt

v1.0.3

  • Lizenz zu LGPL geändert
  • nach Win32 portiert
  • spezielle Funktionen (mmap, getpagesize, etc.) durch “Defines” geschützt
  • anstelle von trace.fd nun trace.file (file-IO und nicht read/write)
  • C++-Operatoren werfen nun wirklich std::bad_alloc

v1.0.2

  • Handhabung von fehlgeschlagener Allokation verbessert; anstelle von ABORT werden nun NULL-Zeiger zurückgegeben

v1.0.1

  • in check_rmalloc: globaler Heap wurde nicht überprüft
  • Überprüfung der Konsistenz von Wildnis und vollen/nicht-leeren Containern
  • anpassung der Grösse bei der Heap-Allokation

v1.0

  • Fehler in r_realloc beseitigt (falsche Grösse für gegebenen Block)

v1.0-pre5

  • NO_OF_CLASSES, NO_OF_SMALL müssen gerade sein; abgeändert

v1.0-pre4

  • interne Fragmentierung für kleine Blöcke durch Verwendung von eigenem Typ (sblock_t) reduziert
  • kleinere Fehler bei nicht-PThread-Modus beseitigt

v1.0-pre3

  • USE_THR_HACKS für Simulation von thread-spezifischen Daten hinzugefügt
  • Neustrukturierung der Container-Verwaltung

v1.0-pre2

  • überflüssige Daten-Segment-Struktur entfernt
  • überflüssige Empty-Listen für Container entfernt

v1.0-pre1

  • wieder vieles neu-/umgeschrieben: Zusammenfügen und Teilen von Blöcken ala LKmalloc hinzugefügt
  • Container-Verwaltung für kleine Speicherblöcke beibehalten; Zusammenfügen nur für mittlere Speicherblöcke
  • Aufrunden der Speichergrössen entfernt
  • kein Speichertransfer mehr zwischen den Heaps

v0.99

  • grosse Teile umgeschrieben mit Containern, welche von verschiedenen Grössenklassen benutzt werden können => führt leider zu massiver Fragmentierung

v0.98.3

  • verschiedenste Säuberungen im Code
  • generierung der Grössenklassen nun in eigenem Programm

v0.98.2

  • echte thread-private Daten durch simulierte ersetzt

v0.98.1

  • Fragmentierungs-Statistik mit STAT_FRAGMENTATION; gibt “realen” Verbrauch aus
  • top_pad nach Data-Segment-Struktur verschoben

v0.98

  • überflüssiger Speicher eines jeden Datensegments werden für zukünftige Anfragen verwendet (weniger Speicherverbrauch)

v0.97

  • kleinere Fehler beseitigt
  • top_pad ist nun heap-spezifisch und wird dynamisch angepasst (1/TOP_PAD_FRACTION von mem_used)
  • überflüssige Aufrufe von size_to_class vermieden
  • Verwaltung von Speicherblöcke größer als grösste Speicherklasse an Betriebssystem übergeben (via malloc oder mmap)
  • Fehlerbehandlung falls kein Speicher mehr vorhanden abgeändert; sendet nun KILL-Signal an eigenen Prozess anstelle von exit(1))
  • zusätzliche Protokollierungsart (per allokation) hinzugefügt

v0.96

  • Speicherblock-Handhabung neu geschrieben: heap -> block -> chunk
  • Austausch von Blöcken zwischen Thread-Heaps und Global-Heaps um Speicherverbrauch zu reduzieren

v0.95

  • Speichergrößen werden auf nächste Grössenklasse aufgerundet, um Suche zu vermeiden
  • Anzahl der Grössenklassen erhöht; size_to_class benutzt nun binäre Suche anstelle der linearen
  • Ok, vielleicht sind 10 MB für DEFAULT_TOP_PAD doch besser ?
  • Protokollierung für Thread-Heaps implementiert

v0.94

  • Code für System-Allokation umstrukturiert (mmap und malloc waren zu ähnlich, um sie getrennt zu handhaben)
  • die meisten mutex-bezogenen (falls locked) Ausgeben wurden entfernt
  • MMAP ist nun Standard, falls malloc nicht überladen werden soll
  • “r_mallinfo” zu “rmallinfo” abgeändert und Deklaration in rmalloc.h hinzugefügt

v0.93

  • Heap-Behandlung geändert: jeder Thread besitzt jetzt eigenen Heap; falls der Thread beendet wird, kann der Heap von einem neuen Thread wiederbenutzt werden
  • kein automatisches Anlegen des ersten Heaps; erfolgt nun auf Verlangen in r_malloc
  • DEFAULT_TOP_PAD reduziert auf 5 MB (sollte genügen)
  • Liste der Heaps ist nicht mehr zirkulär, sondern linear
  • Heaps können nun bezüglich der Cachezeilengröße ausgerichtet werden (ALIGN_TO_CACHE_SIZE); standardmässig aber aus
  • Wrapper für mallinfo implementiert, welcher internes r_mallinfo aufruft (r_mallinfo benutzt mallinfo-struct mit ulong-feldern)

v0.92

  • simulierte thread-spezifische Daten durch echte ersetzt

v0.91

  • Fehler bei der Benutzung von malloc als System-alloc beseitigt (lediglich Blöcke der gewünschten Grösse wurden angefordert, nicht plus DEFAULT_TOP_PAD)

v0.90

  • erste öffentliche Version

Benchmarks

Diese Benchmarks sind ähnlich zu denen, welche bei den Tests für hoard verwendet wurden.

ThreadBench-Eq

Dieser Benchmark allokiert viele kleine, gleichgrosse Blöcke in jedem Thread und testet die parallele Effizienz.

Die folgende Tabelle zeigt die Zeit für die verschiedenen Speicherverwaltungen bei Verwendung eines Prozessors.

Sun-malloc MT-malloc Hoard PTmalloc Rmalloc
132.2 sec 219.7 sec 131.7 sec 119.8 sec 115.7 sec

Der Speedup bezüglich der Anzahl der Prozessoren ist in der folgenden Abbildung dargestellt speedup in thrbench-eq

Larson

Dieser Benchmark simuliert das Allokations-Verhalten einer typischen Serveranwendung mit mehreren Threads.

Die Anzahl von Speicheranforderungen pro Zeiteinheit auf einem Prozessor ist in der folgenden Tabelle dargestellt:

Sun-malloc MT-malloc Hoard PTmalloc Rmalloc
579345 580463 622875 577604 753322

Auch hier wieder die Darstellung der Skalierung bezüglich verschiedener Prozessorzahlen: speedup in larson