Effizienz des Speichermanagers

[Namenloser]

Hi,

ich arbeite an einer Implementierung von B+-Bäumen (oder sowas ähnlichem zumindest), in-memory. Ich habe da gestern mal mit Benchmarks angefangen, und während die Geschwindigkeit zwar in Ordnung war, ist mir aufgefallen, dass das Programm viel mehr RAM braucht als es eigentlich sollte. Theoretisch sollte es ungefähr 80MB brauchen, tatsächlich waren es hingegen über 230MB.

Ein Speicherleck ist es aber nicht, es wird am Ende alles wieder ordentlich freigegeben.

Der Verdacht lag auf Heap-Fragmentierung, da jeder Endknoten des Baumes in einer verketteten Liste gespeichert ist. Ich wollte das mal mit der HeapTrc-Unit überprüfen, allerdings gibt die mir pro Sekunde ungefähr eine Zeile aus und ist damit bei einer großen Anzahl Objekte leider überhaupt nicht zu gebrauchen. Ich konnte da also keine genaueren Erkenntnisse gewinnen.

Dann habe ich auf StackOverflow den Tipp gefunden, den FPC-eigenen Speichermanager durch den C-Speichermanager auszutauschen, indem man die Unit "cmem" einbindet, eigentlich mit dem Ziel, mit Valgrind debuggen zu können. Allerdings hat sich bei mir das Problem überraschenderweise schon allein durch das Einbinden der Unit erübrigt: Auf einmal braucht das Programm nur noch 90MB, was nahezu perfekt ist (Das Programm braucht nach dem Start ja schon 8MB). Aber nicht nur das: Das Einfügen in den Baum dauert nun nur noch halb so lange wie vorher (~400ms statt vorher ~800ms).

Warum schneidet der FPC-Speichermanager hier im Vergleich zu C so schlecht ab? Was macht C anders?

[Dejan Vu]

Wenn Du sehr viele kleine Fragmente hast, ist der Overhead vielleicht relativ gesehen zu groß. Ich würde nicht immer und überall Klassen verwenden, die guten alten Arrays tun es in vielen Fällen auch: Und die haben fast kein Overhead.

Ich habe als Knotenspeicher nämlich ein Array verwendet. Bei mir sind die Seiten konstant 8k groß, bzw. entsprechen der 'System Page Size', sodaß ich eine Klasse habe, die exakt diese Pagegröße liest und schreibt. Im Umkehrschluss ergibt sich daraus -abzüglich einiger Bytes for Bookkeeping- ca. 8160 Bytes Nutzdaten pro B+-Knoten (bei 8k System Page größe). Je nach länge des Schlüssels passen dann eben mehr oder weniger Daten in das Array. rein.

Schneller geht es imho nicht. Beim laden und persistieren lese ich alles in einem Abwasch ein bzw. flushe es entsprechend performant. An dieser einen Stelle im Code habe ich dann -gut dokumentiert- etwas Adressarithmetik, die aber gekapselt ist.

Ich weiss nicht, ob wir über exakt das gleiche Modell reden, fällt mir gerade ein: Ich habe B-Bäume umgesetzt, keine B+ Bäume. Trotzdem könnte das als Denkanstoß reichen, um den Speicherverbrauch zu optimieren.

[Bernhard Geyer]

Hast du die Exe mit Debug-Infos und/oder Stack-Frames erstellt?

[Namenloser]

Zitat von Dejan Vu:

Wenn Du sehr viele kleine Fragmente hast, ist der Overhead vielleicht relativ gesehen zu groß. Ich würde nicht immer und überall Klassen verwenden, die guten alten Arrays tun es in vielen Fällen auch: Und die haben fast kein Overhead.

Ich habe als Knotenspeicher nämlich ein Array verwendet. Bei mir sind die Seiten konstant 8k groß, bzw. entsprechen der 'System Page Size', sodaß ich eine Klasse habe, die exakt diese Pagegröße liest und schreibt. Im Umkehrschluss ergibt sich daraus -abzüglich einiger Bytes for Bookkeeping- ca. 8160 Bytes Nutzdaten pro B+-Knoten (bei 8k System Page größe). Je nach länge des Schlüssels passen dann eben mehr oder weniger Daten in das Array. rein.

Ich verwende für die Navigationsknoten Records und darin sind die Schlüssel und die Kinder in Arrays mit fester Größe gespeichert. Bei mir haben sich Knotengrade von 16 bis 32 als am schnellsten erwiesen. Wie ich schon schrieb, arbeitet mein Baum nur im RAM, Paging auf die Festplatte usw. ist nicht im Spiel.

Zitat von Dejan Vu:

Ich weiss nicht, ob wir über exakt das gleiche Modell reden, fällt mir gerade ein: Ich habe B-Bäume umgesetzt, keine B+ Bäume. Trotzdem könnte das als Denkanstoß reichen, um den Speicherverbrauch zu optimieren.

Auch ich habe im Eingangspost ein bisschen vereinfacht. Was ich da habe, ist nicht ganz das, was man im Internet als B+-Baum findet. Erstens handelt es sich um einen (a,b)-Baum, was aber fast das gleiche zu sein scheint wie ein B+-Baum, nur ein bisschen allgemeiner (Knotengrade von a bis b, statt von b bis 2b). Zweitens habe ich mich stark daran orientiert, wie es in unserer Algorithmen-Vorlesung gezeigt wurde: „Unter dem Baum“ befindet sich sozusagen eine verkettete Liste. Bei den B+-Bäumen, die man im Internet findet, werden meistens die Daten in die untersten Navigationsknoten geschrieben und diese Knoten dann miteinander in einer Liste verbunden – also mehrere Datensätze pro Knoten. Bei mir ist es hingegen so, dass die unterste Navigationsschicht die Daten nicht selbst enthält, sondern auf spezielle Knoten (Blätter) zeigt, die die Daten enthalten – ein Blatt-Knoten pro Datensatz. Und das scheint das Problem zu sein, denn dadurch entstehen in meinem Benchmark eine Million 48-Byte-Blöcke.
(Ich weiß nicht, ob das ein grundlegender Unterschied zwischen (a,b)-Bäumen und B+-Bäumen ist, oder ob unser Prof das einfach nur anders gemacht hat. Im Internet findet man zu (a,b)-Bäumen sehr wenig Informationen)

Ursprünglich stand das schon länger auf meiner To-Do-Liste, diesen untersten Layer loszuwerden, allerdings ist mir dann aufgefallen, dass das so einen entscheidenden Vorteil hat: Wenn man sich einen Zeiger (Iterator) auf einen Datensatz holt, bleibt der – solange der Datensatz nicht gelöscht wird, natürlich – für immer gültig, egal was sich am Baum verändert. Man kann beliebig Knoten einfügen oder löschen, der Zeiger zeigt trotzdem noch auf den richtigen Knoten. Das ist bei der speichereffizienteren Variante nicht gegeben: Es könnte sein, dass der zugehörige Knoten in der Zwischenzeit aufgespalten oder mit einem anderen Knoten zusammengelegt wurde, wodurch er nicht mehr an der richtigen Stelle im Speicher liegt.

Für meinen Anwendungsfall ist diese Persistenz sogar tatsächlich ein Vorteil. Deshalb wollte ich erst mal in Kauf nehmen, dass meine Lösung nicht die aller speichereffizienteste ist. Dass das allerdings zu so viel Fragmentierung führt, hätte ich nicht erwartet.

Ich werde jetzt wahrscheinlich versuchen, mir nur für diese Records einen eigenen kleinen Speichermanager zu schreiben.

@Bernhard Geyer: Ich hatte mal testweise alle Debug-Informationen rausgenommen, das hat aber nichts verändert.

[Dejan Vu]

Blöde Idee: Erzeuge 1 Mio deiner 48-Byte Blöcke in einem separaten Projekt. Wie hoch ist der Speicherverbrauch?
Jetzt erzeuge 2 Mio Blöcke. Und nun?
Erzeuge 2 Mio, gib die Häfte wieder frei. Und nun?

[BUG]

Zitat von Dejan Vu:

Erzeuge 2 Mio, gib die Häfte wieder frei. Und nun?

Worauf willst du hinaus? Kein normaler Speichermanager gibt jemals wieder Speicher an das Betriebssystem zurück. Wozu auch?

@Namenloser: Ich nehme mal an, das Prinzip ist dir bekannt? Für deinen Anwendungsfall brauchst du nur eine direkte Freiblockliste implementieren

[Namenloser]

Zitat von Dejan Vu:

Blöde Idee: Erzeuge 1 Mio deiner 48-Byte Blöcke in einem separaten Projekt. Wie hoch ist der Speicherverbrauch?
Jetzt erzeuge 2 Mio Blöcke. Und nun?
Erzeuge 2 Mio, gib die Häfte wieder frei. Und nun?

Delphi-Quellcode:

var
  i: integer;
begin
  //   7 MB
  for i := 0 to 1000000 - 1 do
    New(recs[i]);
  //  77 MB
  for i := 1000000 to 2000000 - 1 do
    New(recs[i]);
  // 144 MB
  for i := 0 to 1000000 - 1 do
    Dispose(recs[i]);
  //  83 MB
end;

Und jetzt?

@BUG: Freiblockliste? Nein, sagt mir nichts.

[Bernhard Geyer]

Zitat von BUG:

Zitat von Dejan Vu:

Erzeuge 2 Mio, gib die Häfte wieder frei. Und nun?

Worauf willst du hinaus? Kein normaler Speichermanager gibt jemals wieder Speicher an das Betriebssystem zurück. Wozu auch?

Dann hat wohl Delphi mit integrierten FastMM einen "unnormalen" Speichermanager. Weil er gibt Speicher wieder zurück!
Was ein Speichermanager wie FastMM macht ist das er nicht jedes kleines Byte das freigegeben wird wieder ans OS zurück gibt sondern effektiver und schneller als das OS kleine Speicheranforderungen und Freigaben verwaltet.

[BUG]

Zitat von Namenloser:

Freiblockliste? Nein, sagt mir nichts.

Da du nur eine Blockgröße hast, ist dein Heap mehr oder weniger ein Array aus deinen Records. Einige davon sind belegt, andere frei. Die freien Blöcke kann man in einer direkten Liste ablegen. Das heißt, der Zeiger auf den "nächsten" freien Block steht dort, wo sonst das Record steht. Da die Blöcke alle gleich sind, brauchst du nicht sortieren und kannst einen neu freigegebenen Block in einer O(1)-Operation am Anfang einfügen. Zusätzlich brauchst du nur einen Zeiger auf den Anfang der Liste.

Zitat von Bernhard Geyer:

Weil er gibt Speicher wieder zurück!

War mir nicht bekannt, danke für den Hinweis Ist das irgendwo dokumentiert / unter Windows üblich?

[Namenloser]

Also hier unter Linux gibt der FPC-Speichermanager auch den Speicher zurück. Der C-Manager hingegen behält ihn. Finde ich aber nicht so toll, ich finde, der Speicher sollte schon zurückgegeben werden, es laufen schließlich noch andere Programme auf dem Rechner.