Effizienz des Speichermanagers

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

[Namenloser]

Ich hab mir jetzt selber auch noch mal den Spaß gemacht und drei verschiedene Varianten gegeneinander getestet:
1. Rot-Schwarz-Baum aus der FCL-STL
2. alzaimars Skiplist (habe die maximale Tiefe allerdings von 8 auf 20 erhöht)
3. mein eigener B+-Baum

Ergebnis eines Testlaufs (alle Zeiten in ms):

B+-Baum:
B+ 1000000 Inserts: 472
B+ 1000000 Locates: 303
B+ 500000 Removes: 285
B+ 500000 Reinserts: 311

Skiplist:
SL 1000000 Inserts: 721
SL 1000000 Locates: 223
SL 500000 Removes: 322
SL 500000 Reinserts: 399

Rot-Schwarz-Baum:
RB 1000000 Inserts: 1337
RB 1000000 Locates: 859
RB 500000 Removes: 1243
RB 500000 Reinserts: 634

Die Werte schwanken natürlich etwas von einem Durchlauf auf den anderen, aber so ungefähr passt das.

Die Skiplist hat mich echt überrascht. Vor allem, wenn man bedenkt, dass die Unit nur 300 Zeilen lang ist, während der B+-Baum es auf über 1100 Zeilen bringt (wobei die Skiplist allerdings auch weniger Features hat). Wenn man an die Skiplist noch die gleiche Speicherverwaltung dranbasteln würde, von der der B+-Baum aktuell profitiert, dann könnte man vermutlich die Insert-Zeiten und den Speicherverbrauch auch noch senken – denn letzterer ist mit über 300 MB recht happig im Vergleich zu ca. 100 MB beim B+-Baum. Der Rot-Schwarz-Baum bringt es ebenfalls auf über 300 MB und gibt den Speicher zudem nicht vollständig wieder frei, außerdem ist er, wie man sieht, bei der Geschwindigkeit weit abgeschlagen.

Trotz des guten Abschneidens der Skiplist kann man aber als Fazit sagen, dass B+-Bäume durchaus gut als RAM-interne Datenstruktur geeignet sind.

Bei der Skiplist muss man natürlich außerdem noch berücksichtigen, dass sie propabilistisch arbeitet – bei so großen Anzahlen von Elementen kann sie damit natürlich alle ihre Vorteile ausspielen. Je kleiner die Anzahl, desto größer wäre aber die Wahrscheinlichkeit, dass ihre reale Laufzeit sich in Richtung der Worst-Case-Laufzeit verschiebt.

[Patito]

Dein B+-Tree schlägt sich offensichtlich ganz gut. Der RBTree aus der FPC-STL ist aber wohl nicht gerade der beste.
Interessant wäre noch, wenn Du das ganze noch mit dem TAVLTree aus der FCL vergleichst.

In meinem Speed-Test sieht die Skiplist im Vergleich mit dem AVL-Tree oder meinem eigenen RB-Tree recht langsam aus.

[Dejan Vu]

Ich hätte jetzt nicht gedacht, das der B+ Baum in-memory so gut abschneidet.

Die Skiplist hat einen ziemlichen Overhead, sodaß sie sich nicht zum Speichern kleiner Happen eignet.

[Namenloser]

Zitat von Patito:

Dein B+-Tree schlägt sich offensichtlich ganz gut. Der RBTree aus der FPC-STL ist aber wohl nicht gerade der beste.
Interessant wäre noch, wenn Du das ganze noch mit dem TAVLTree aus der FCL vergleichst.

Der scheint wirklich ziemlich schnell zu sein, zumindest wenn er erst mal einen Pool an TreeNodes angelegt hat, die er dann recyclen kann:

Code:

B+ 1000000 Inserts: 447
B+ 1000000 Locates: 280
B+ 500000 Removes: 201
B+ 500000 Reinserts: 241

SL 1000000 Inserts: 713
SL 1000000 Locates: 212
SL 500000 Removes: 324
SL 500000 Reinserts: 347

AVL 1000000 Inserts: 623
AVL 1000000 Locates: 259
AVL 500000 Removes: 73
AVL 500000 Reinserts: 91

RB 1000000 Inserts: 1345
RB 1000000 Locates: 849
RB 500000 Removes: 1050
RB 500000 Reinserts: 721

Falls die Zahlen etwas anders sind: Ich hab in meinem Benchmark-Code etwas Unsinn gefunden und ausgebessert... war halt schnell mit Copy & Paste-Programmierung zusammengestrickt . Allerdings wurden trotzdem alle unter den gleichen Umständen getestet.

Das Ergebnis finde ich interessant, weil man, wenn man bei Google nach Empfehlungen für balancierte Bäume sucht, eigentlich immer liest, dass AVL-Bäume bei häufigen Einfüge- und Löschoperationen wegen häufigem Rebalancing nicht so gut geeignet seien, insbesondere im Vergleich zu Rot-Schwarz-Bäumen.

Mich wundert es allerdings, dass die Removes hier schneller zu gehen scheinen als die Locates. Vielleicht sollte langsam mal ein repräsentativerer Test her...

[Dejan Vu]

Kannst Du den Testcode posten? Wie verhalten sich die Datenstrukturen beim Einfügen aufsteigender bzw. absteigender Schlüssel?

[Namenloser]

Der Testcode ist ziemlich hässlich und mit heißer Nadel gestrickt, aber gut:

Delphi-Quellcode:

const
  c = 500000;
begin
  Tree := TABTree.Create;

  t0 := GetTickCount64();
  for i := 1 to c do
    Tree.Insert(i,i);
  for i := 2*c downto c+1 do
    Tree.Insert(i,i);
  t1 := GetTickCount64();
  for i := 1 to c do
    Tree.Locate(i);
  for i := 2*c downto c+1 do
    Tree.Locate(i);
  t2 := GetTickCount64();
  for i :=  c - c div 2 to c do
    Tree.Remove(i);
  for i :=  c + c div 2 downto c do
    Tree.Remove(i);
  t3 := GetTickCount64;
  for i :=  c - c div 2 to c do
    Tree.Insert(i,i);
  for i :=  c + c div 2 downto c do
    Tree.Insert(i,i);
  t4 := GetTickCount64;

  Memo1.Append(Format('B+ %d Inserts: %d', [2*c, t1-t0]));
  Memo1.Append(Format('B+ %d Locates: %d', [2*c, t2-t1]));
  Memo1.Append(Format('B+ %d Removes: %d', [c, t3-t2]));
  Memo1.Append(Format('B+ %d Reinserts: %d', [c, t4-t3]));

  Tree.Free;

Analog sieht er für die anderen Datenstrukturen aus.

Also es werden immer zur Hälfte aufsteigend und zur Hälfte absteigend Daten eingefügt, gesucht, gelöscht etc.

[Patito]

Zitat von Namenloser:

Das Ergebnis finde ich interessant, weil man, wenn man bei Google nach Empfehlungen für balancierte Bäume sucht, eigentlich immer liest, dass AVL-Bäume bei häufigen Einfüge- und Löschoperationen wegen häufigem Rebalancing nicht so gut geeignet seien, insbesondere im Vergleich zu Rot-Schwarz-Bäumen.

Die AVL-Trees sollten wohl etwas langsamer beim Insert/Remove und dafür etwas schneller beim Locate seien.
Meinen eigenen RB-Tree verwende ich deshalb so gerne, da er ein wenig schneller bei den Masseninserts ist als der AVL-Tree.

Massen-Inserts habe ich immer - Locates und andere Operationen treten oft nicht so gehäuft auf.
Daher denke ich, dass für die Praxis ein RB-Tree oder B-Tree etwas besser als der AVL-Tree sein sollte.
Den AVL-Tree der FCL zu schlagen ist aber nicht leicht.

Zitat von Namenloser:

Mich wundert es allerdings, dass die Removes hier schneller zu gehen scheinen als die Locates. Vielleicht sollte langsam mal ein repräsentativerer Test her...

Ich teste meine Container einmal mit einer sortierten Liste, und einmal mit einer zufällig zusammengewürfelten Liste.
Die sorted Inserts finde ich recht wichtig, da man damit Masseninserts oft wesentlich beschleunigen kann.

Am Memory-Manager kann man natürlich auch viel herumspielen...
Bei Single-Threaded Sachen hat mir das keinen wirklichen Vorteil gebracht - da poolt der Speichermanager oft selber gut genug.
Sobald aber Multi-Threading ins Spiel gekommen ist, ist bei mir Pooling richtig wichtig geworden.

[Dejan Vu]

Kurze Zwischenfrage: Müssen die Elemente eigentlich sortiert sein? Braucht man doch gar nicht so häufig.