Effizienz des Speichermanagers

[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

[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.

[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.

[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.

[BUG]

Zitat von Namenloser:

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.

Das ist halt eine Kostenabwägung.

Wenn man Speicher wieder an das System zurück geben will, muss man eine Speicherwaltung implementieren, in der dieser Fall auch wirklich auftritt.
Damit sind aber bestimmte Strategien nicht möglich (z.B. Next-Fit oder Worst-Fit sollten sich nicht wirklich mit dieser Anforderung vertragen) und der Verwaltungsaufwand steigt.

Oft ist es auch unnötig, den Speicher zurückgeben:
Ein zyklisch ablaufendes Programm wird den Speicher bald wieder benötigen.
Ein Programm, was sich bald wieder beendet, gibt ihn dann frei.

[Namenloser]

Ich habe das mit der eigenen Speicherverwaltung jetzt so weit umgesetzt. Komme jetzt mit dem FPC-Speichermanager in Kombination mit meiner eigenen Speicherverwaltung auf ca 98 MB, also geringfügig mehr als mit dem C-Speichermanager. Geschwindigkeitsmäßig kann die Implementierung ebenfalls mithalten. Und es wird sogar der Speicher am Ende vollständig wieder freigegeben.

Wäre vielleicht auch was für die CodeLib, wenn ich den Code jetzt noch etwas aufräume...

[Dejan Vu]

Zitat von Namenloser:

Zitat von Dejan Vu:

Blöde Idee...

Delphi-Quellcode:

...
  //   7 MB
...
  //  77 MB
...
  // 144 MB
...
  //  83 MB

Und jetzt?

Seufz.
Der Speicherbedarf ist linear. Ich hätte zwar mit 147 MB gerechnet (weil 7 + (77-7)*2 = 147) aber egal. Vielleicht nimmst Du mich auch nicht ernst und hast dir die Zahlen zurechtgerechnet (und dabei einen Fehler gemacht?). Interessant ist aber: Wieso kommt zum Schluß nicht 77 MB heraus? Arbeitet also der FPC-Speichermanager nicht optimal? Wäre das eine Möglichkeit, weshalb in der Tendenz der FPC-Speichermanager degeneriert?

Zitat von Namenloser:

@BUG: Freiblockliste? Nein, sagt mir nichts.

Wusstest Du, das der MS SQL-Server einen eigenen Speichermanager hat, der (zumindest bezogen auf die Systempages) diese selbst verwaltet? Der arbeitet genau mit dieser sehr simplen 'Freiblockliste' (als linked stack)

Zitat von Namenloser:

Wäre vielleicht auch was für die CodeLib, wenn ich den Code jetzt noch etwas aufräume...

Ketzerische Frage: Welchen Wert, außer dem Lehrinhalt, hätte eine B+-Baum-Implementierung, die nicht mit einem externen Speicher arbeitet (oder kann deine Version das jetzt)? B-Bäume wurde ja gerade dafür erfunden. Eine schnelle sortierte Liste bekommt man mit einer Skiplist oder einem Binärbaum hin (Die müssten sogar schneller sein). Eine im Suchen sehr schnelle unsortierte Liste mit einem Dictionary, oder irre ich mich?

[Namenloser]

Zitat von Dejan Vu:

Seufz.
Der Speicherbedarf ist linear. Ich hätte zwar mit 147 MB gerechnet (weil 7 + (77-7)*2 = 147) aber egal. Vielleicht nimmst Du mich auch nicht ernst und hast dir die Zahlen zurechtgerechnet (und dabei einen Fehler gemacht?).

Die Zahlen stammen so 1:1 aus dem Systemmonitor.

Zitat von Dejan Vu:

Zitat von Namenloser:

Wäre vielleicht auch was für die CodeLib, wenn ich den Code jetzt noch etwas aufräume...

Ketzerische Frage: Welchen Wert, außer dem Lehrinhalt, hätte eine B+-Baum-Implementierung, die nicht mit einem externen Speicher arbeitet (oder kann deine Version das jetzt)? B-Bäume wurde ja gerade dafür erfunden. Eine schnelle sortierte Liste bekommt man mit einer Skiplist oder einem Binärbaum hin (Die müssten sogar schneller sein). Eine im Suchen sehr schnelle unsortierte Liste mit einem Dictionary, oder irre ich mich?

Ich meinte eigentlich die Speicherverwaltung. Denn das kann man ja sicher mal wieder gebrauchen. Den Baum werde ich aber möglicherweise auch als Open Source veröffentlichen.

B+-Bäume machen auch im Arbeitsspeicher Sinn, weil sie deutlich cachefreundlicher sind als etwa Rot-Schwarz-Bäume. Falls dich Zahlen interessieren, unser Übungsleiter hatte da mal die Performance von Rot-Schwarz-Bäumen (aus der STL) und B+-Bäumen verschiedener Größen verglichen: http://panthema.net/2007/stx-btree/speedtest/ (lustigerweise bin ich erst über einen unabhängigen Link auf StackOverflow wieder darauf gestoßen, dann fiel mir wieder ein, dass das in einer Vorlesung auch mal erwähnt wurde...)

Eine Hashmap nützt mir nichts, weil ich wirklich eine sortierte Liste brauche.

Eine Skiplist habe ich nicht ausprobiert, aber soweit ich weiß nähert diese sich auch letztlich propabilistisch an die Struktur eines Baumes an. Ob das jetzt nun schneller ist oder nicht, müsste man testen. Allerdings ist zu bedenken, dass eine Skiplist auch wieder eine verkettete Liste ist, das bedeutet tendenziell schlechte Cache-Effizienz und wieder Fragmentierungs-Probleme. Ich hätte so oder so beides neu implementieren müssen, und mit den Bäumen kannte ich mich besser aus .