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:

Zitat von Dejan Vu (Beitrag 1255392)

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:

Zitat von Dejan Vu (Beitrag 1255392)

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:

Zitat von Dejan Vu (Beitrag 1255443)

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 :wink:

[Namenloser]

Zitat:

Zitat von Dejan Vu (Beitrag 1255443)

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:

Zitat von BUG (Beitrag 1255444)

Zitat:

Zitat von Dejan Vu (Beitrag 1255443)

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:

Zitat von Namenloser (Beitrag 1255445)

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:

Zitat von Bernhard Geyer (Beitrag 1255448)

Weil er gibt Speicher wieder zurück!

War mir nicht bekannt, danke für den Hinweis :wink: 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:

Zitat von Namenloser (Beitrag 1255457)

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:

Zitat von Namenloser (Beitrag 1255445)

Zitat:

Zitat von Dejan Vu (Beitrag 1255443)

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:

Zitat von Namenloser (Beitrag 1255445)

@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:

Zitat von Namenloser (Beitrag 1255465)

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:

Zitat von Dejan Vu (Beitrag 1255467)

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:

Zitat von Dejan Vu (Beitrag 1255467)

Zitat:

Zitat von Namenloser (Beitrag 1255465)

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. :thumb:

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

[Namenloser]

Zitat:

Zitat von Patito (Beitrag 1255598)

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 :oops:. 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.

[Dejan Vu]

Zitat:

Zitat von Namenloser (Beitrag 1255629)

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

Eben. Gut ;-) Du testest mit Sonderbedingungen (aufsteigend, absteigend einfügen). Da wirst Du -zumindest im AVL und RB- eine Worst Case erwischen. Die müssen ja beinahe bei jedem Einfügen ausbalanciert werden.

Hmmm... oder gleicht sich das aus? :gruebel:

Teste doch mal zusätzlich mit Random-Werten. Achtung: Die Skiplist ist nicht ohne weiteres geeignet zur Aufnahme identischer Werte, müsstest du prüfen. Alternativ erstellst Du dir eine Liste mit 1Mio Einträgen, mischst die mit Fisher-Yates und fügst dann die Werte ein. Ist ja auch Random.

Ich teste jedenfalls immer so.

[Patito]

Zitat:

Zitat von Namenloser (Beitrag 1255627)

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:

Zitat von Namenloser (Beitrag 1255627)

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.

[Patito]

Zitat:

Zitat von Dejan Vu (Beitrag 1255691)

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

Nunja, Einfügen in sortierter Reihenfolge ist eben je nach Containern-Implementierung gern mal 3x so schnell
wie Einfügen in chaotischer Reihenfolge.

Bei der Implementierung von Containern hat man an manchen Stellen die Wahl, ob man Sachen eher links oder rechts
einfügt, und ob man zuerst auf < oder > prüft. Damit kann man dem Container eine Lieblings-Reihenfolge einprogrammieren,
die dann schneller funktioniert.

[Dejan Vu]

Zitat:

Zitat von Patito (Beitrag 1255692)

Zitat:

Zitat von Dejan Vu (Beitrag 1255691)

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

Nunja, Einfügen in sortierter Reihenfolge ist eben je nach Containern-Implementierung gern mal 3x so schnell
wie Einfügen in chaotischer Reihenfolge.

Dann kennst Du aber Dictionaries schlecht. Die sind O(1), im Gegensatz zu den hier vorgestellten Strukturen, deren Einfügeverhalten vom Aufwand O(log n) ist. Auch Suchen, Löschen etc. ist bei Dictionaries O(1), würde also alle hier vorgestellten Strukturen um *Längen* schlagen. Es ist übrigens -gut programmiert- vollkommen egal, ob man 1000 oder 100.000.000.000 Elemente in einer Dictionary vorhält (solange der RAM das aushält). Der Aufwand ist immer gleich, die Teile sind also immer gleich schnell. Ein Baum wächst und somit wird das Laufzeitverhalten auch immer schlechter, ist zwar sublinear, also log n, aber immer noch schlechter als gar keine Verlangsamung.

Nebenbei kannst Du hier keine Faktoren angeben, denn z.B. das Einfügen in eine sortierte Liste ist (ggü einer unsortierten Liste) nicht gerne mal 3x so schnell, sondern -je nach Anzahl- auch ruhig mal 10000000000x so schnell.

Zitat:

Zitat von Patito (Beitrag 1255692)

Damit kann man dem Container eine Lieblings-Reihenfolge einprogrammieren,
die dann schneller funktioniert.

Wenn man den Container auch noch an die speziellen Bedürfnisse anpassen muss, taugt so ein Container ja nur bedingt.

Die Frage lautet also: Wozu muss die Liste sortiert sein? Der Namenlose hat den B+-Baum im Rahmen einer Lehrveranstaltung Programmiert (klasse), aber im Allgemeinen haben diese Strukturen keine sonderliche Verbreitung, weil man eben nicht sonderlich oft sortierte Listen benötigt.

Ach, wurde ein (binomial) Heap schon probiert? Müsste ich mal raussuchen...

[Namenloser]

Zitat:

Zitat von Dejan Vu (Beitrag 1255698)

Die Frage lautet also: Wozu muss die Liste sortiert sein? Der Namenlose hat den B+-Baum im Rahmen einer Lehrveranstaltung Programmiert (klasse)

Naja, nur dafür hätte ich es wohl auch nicht gemacht. Eine sortierte Liste braucht man z.B. hierfür. Ein Binomialheap ist da auch schon im Einsatz, reicht aber nur für eine der beiden Datenstrukturen.

Zitat:

Zitat von Patito (Beitrag 1255663)

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.

Ich hatte erst mal nur Sorted-Inserts getestet, weil es eigentlich spannender ist. Für wirklich zufällige Inserts bräuchte man theoretisch gar keinen balancierten Baum.

Für einen umfangreichen Test muss natürlich beides getestet werden, das ist klar.

[Dejan Vu]

Zitat:

Zitat von Namenloser;1255722...Eine sortierte Liste braucht man z.B. [url=https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm

hierfür[/url].

Alles klar.

Zitat:

Für wirklich zufällige Inserts bräuchte man theoretisch gar keinen balancierten Baum.

Aber Du weißt ja nicht, wie die Sachen reinkommen. Daher neben der theoretischen Betrachtung der Standardfälle (aufsteigend, absteigend sortiert, zufällig) auch Laufzeitmessungen über alle Szenarien, um das Verhalten im Code zu analysieren und versteckte Bottlenecks zu lokalisieren. Aber das hättest Du ja gemacht, wie Du schreibst.

Schnellste sortierte Liste (bezüglich Insert/Update/Delete/Locate/)? Interessante Aufgabenstellung.

[Namenloser]

So, ich habe jetzt noch mal einen saubereren Test in einem neuen Projekt geschrieben.

Delphi-Quellcode:

B+ Tree

Ascending linear (1000000)
Insert: 451 ms
Locate: 273 ms
Remove: 543 ms

Descending linear (1000000)
Insert: 661 ms
Locate: 332 ms
Remove: 340 ms

Random (1000000)
Insert: 1858 ms
Locate: 1006 ms
Remove half: 810 ms
Reinsert half: 976 ms

AVL Tree

Ascending linear (1000000)
Insert: 340 ms
Locate: 270 ms
Remove: 255 ms

Descending linear (1000000)
Insert: 314 ms
Locate: 274 ms
Remove: 265 ms

Random (1000000)
Insert: 1604 ms
Locate: 1499 ms
Remove half: 946 ms
Reinsert half: 933 ms

Skiplist

Ascending linear (1000000)
Insert: 370 ms
Locate: 204 ms
Remove: 180 ms

Descending linear (1000000)
Insert: 233 ms
Locate: 255 ms
Remove: 337 ms

Random (1000000)
Insert: 3095 ms
Locate: 3490 ms
Remove half: 1758 ms
Reinsert half: 1818 ms

RB Tree

Ascending linear (1000000)
Insert: 865 ms
Locate: 387 ms
Remove: 1319 ms

Descending linear (1000000)
Insert: 1043 ms
Locate: 383 ms
Remove: 1643 ms

Random (1000000)
Insert: 3282 ms
Locate: 1682 ms
Remove half: 2139 ms
Reinsert half: 1780 ms

Einige Beobachtungen:

• Aus irgendeinem seltsamen Grund tritt im neuen Projekt der Engpass mit dem FPC-Speichermanager nicht mehr auf – wovon der AVL-Baum jetzt erheblich profitiert.
  
• Das Optimierungslevel hat starken Einfluss auf die Performance beim B+-Baum. Der Benchmark ist mit -O3 kompiliert, wie das Testprogramm zuvor auch. Mit der Standardeinstellung -O1 hab ich mich gefragt, warum das Teil plötzlich so langsam ist im Vergleich.
  
• Beim AVL-Baum hat sich bestätigt, dass das Löschen etwas schneller ist als das Finden. Caching-Effekte? Edit: Achso, nein, ist ja klar: Während dem Löschen wird der Baum ja auch kleiner und dadurch wird das Auffinden der Knoten immer schneller.
  
• Gewundert hat mich, dass der B+-Baum beim linearen Suchen eher langsamer ist als der AVL-Baum, ihn dafür aber deutlich und reproduzierbar bei der Random-Suche schlägt.

Eine Sache habe ich am B+-Baum übrigens noch geändert, und zwar habe ich innerhalb der Knoten von linearer auf binäre Suche umgestellt. Ich hatte schon vorher für beides den Quellcode dastehen, aber hatte standardmäßig die lineare Suche verwendet, weil sie im Mittel schneller schien. Allerdings ist das vor allem darauf zurückzuführen, dass das aufsteigende Einfügen schneller geht. Das absteigende Einfügen ist dafür deutlich langsamer (ist auch logisch). Deshalb setze ich jetzt aus Gründen der Vorhersagbarkeit wieder auf binäre Suche.

Source Code für den Benchmark ist im Anhang, falls jemand seine eigenen Implementierungen testen will. Am Anfang des Programms sind $DEFINES für die zu testenden Klassen, sodass ihr das Programm auch leicht kompilieren könnt, wenn ihr nicht alle Units habt (z.B. unter Delphi). Mitgeliefert wird nur die Skiplist von alzaimar.

[Dejan Vu]

Ich würde noch vergleichen, wie sich die Strukturen bei kleineren Datenmengen verhalten. Hier macht sich der generelle Overhead stärker bemerkbar. Bei sehr kleinen Listen ist ein einfaches sortiertes Array oft schneller als ein Baum, weil eigentlich kein Overhead vorhanden ist.

Man muss wirklich aufpassen ob und wann man diese 'Ungetüme' (300+ Zeilen für eine 'einfache Liste' ist schon happig) verwenden sollte und wann nicht.

Alzaimar hat ja hier einen ganz netten Vergleich geschrieben, der das Verhalten bei kleineren Datenmengen analysiert, da kommt sogar der AVL-Baum und die Skplist vor. Allerdings ist dort die Skiplist viel schneller als der AVL-Baum. Vielleicht, weil es auch viel weniger Daten sind(?)

[Patito]

Zitat:

Zitat von Namenloser (Beitrag 1255744)

So, ich habe jetzt noch mal einen saubereren Test in einem neuen Projekt geschrieben.

Sehr schön. Ich habe es gleich mal getestet, und die Ergebnisse sind interessant.
Ich habe mal -O1 und -O3 getestet und dazu das ganze auch mal mit Delphi7 mit FastMM ausprobiert:

FPC 2.7.1 -O1

AVL Tree
AL (1000000) I:203 L:109 R:94 ms
DL (1000000) I:172 L:94 R:109 ms
RD (1000000) I:577 L:452 ms Remove half: 344 ms Reinsert half: 374 ms

Skiplist
AL (1000000) I:265 L:188 R:124 ms
DL (1000000) I:125 L:203 R:250 ms
RD (1000000) I:1216 L:1389 ms Remove half: 671 ms Reinsert half: 733 ms

RBMap (ohne Pooling)
AL (1000000) I:312 L:171 R:125 ms
DL (1000000) I:312 L:172 R:140 ms
RD (1000000) I:842 L:640 ms Remove half: 406 ms Reinsert half: 452 ms

RBMultiMap (Pooled)
AL (1000000) I:203 L:109 R:62 ms
DL (1000000) I:203 L:109 R:78 ms
RD (1000000) I:593 L:515 ms Remove half: 312 ms Reinsert half: 374 ms


FPC 2.7.1 -O3

AVL Tree
AL (1000000)I: 203 L: 93 R: 110
DL (1000000)I: 187 L: 93 R: 110
RD (1000000)I: 592 L: 468 RH: 328 RIH: 406

Skiplist
AL (1000000)I: 249 L: 94 R: 93
DL (1000000)I: 125 L: 109 R: 172
RD (1000000)I: 1357 L: 1326 RH: 655 RIH: 749

RBMap
AL (1000000)I: 218 L: 125 R: 109
DL (1000000)I: 219 L: 125 R: 109
RD (1000000)I: 764 L: 609 RH: 390 RIH: 421

RBMultiMap (Pooled)
AL (1000000)I: 109 L: 62 R: 47
DL (1000000)I: 125 L: 62 R: 47
RD (1000000)I: 562 L: 452 RH: 297 RIH: 327

Delphi 7 - FastMM

AVL Tree
AL (1000000)I: 125 L: 93 R: 94
DL (1000000)I: 140 L: 94 R: 78
RD (1000000)I: 515 L: 468 RH: 312 RIH: 359

Skiplist
AL (1000000)I: 218 L: 203 R: 62
DL (1000000)I: 78 L: 188 R: 234
RD (1000000)I: 1154 L: 1373 RH: 639 RIH: 687

RBMap
AL (1000000)I: 141 L: 46 R: 47
DL (1000000)I: 125 L: 62 R: 47
RD (1000000)I: 515 L: 437 RH: 296 RIH: 312

RBMultiMap (Pooled)
AL (1000000)I: 94 L: 62 R: 31
DL (1000000)I: 94 L: 62 R: 31
RD (1000000)I: 515 L: 437 RH: 281 RIH: 296


Fazit:
- Für Inserts ist die Skiplist Descending Linear am schnellsten, allerdings leidet der Lookup deutlich darunter
- An den AVL-Tree komm ich unter FPC ohne Node-Pooling kaum heran. Unter Delphi kann FastMM die Lücke recht gut ausbügeln
- Gepooltes RedBlack und AVL-Tree liegen recht eng beieinander. Vom Algorithmus her sind beide in der Praxis wohl ziemlich gleich.
Den Unterschied machen wohl nur ein paar Tricks in der Implementierung aus
- Beim schnellsten Container liegen FPC und Delphi von der Geschwindigkeit in derselben Region.
Der Speichermanager unter Delphi hilft eingen weniger optimierten Containern deutlich
- Wegen der Messtoleranz sind 1000000 Nodes fast schon zu wenig...

[Dejan Vu]

Zitat:

Zitat von Patito (Beitrag 1255781)

- Wegen der Messtoleranz sind 1000000 Nodes fast schon zu wenig...

Wiederhole die Tests einfach ein paar Mal. Es geht hier eh nur um relative Performance (wer ist schneller?).

Wenn Du weißt, das 1 Mio Einträge ungefähr 100ms brauchen, dann misst Du einfach 10 Mio / N mal, wobei N die Anzahl der Samples sind. Dann bist Du pro Test bei ca. 1 Sekunde und im sicheren Bereich (von wegen Messfehler etc.)

[Namenloser]

Zitat:

Zitat von Dejan Vu (Beitrag 1255750)

Ich würde noch vergleichen, wie sich die Strukturen bei kleineren Datenmengen verhalten. Hier macht sich der generelle Overhead stärker bemerkbar. Bei sehr kleinen Listen ist ein einfaches sortiertes Array oft schneller als ein Baum, weil eigentlich kein Overhead vorhanden ist.

Man muss wirklich aufpassen ob und wann man diese 'Ungetüme' (300+ Zeilen für eine 'einfache Liste' ist schon happig) verwenden sollte und wann nicht.

Ich hatte deswegen auch erst überlegt, einfach ein Array zu nehmen. Aber dann kam der Perfektionist in mir wieder durch und dachte sich, es wäre doch schön, wenn trotzdem garantiert wäre, dass die asymptotische Laufzeit nicht aus dem Ruder läuft. Hab mir dann erst überlegt, ob man das Array vielleicht irgendwie erweitern könnte, aber habe dann nach einer Weile gemerkt, dass ich eigentlich gerade Bäume neu erfinde... und dann habe gedacht, okay, dann kann ich auch gleich die richtigen Dinger implementieren. Dachte anfangs auch nicht, dass das so aus dem Ruder läuft, denn auf den Folien sah das nach einem sehr einfachen Konzept aus. Ist es ja eigentlich auch. Aber wenn man es dann implementiert, tun sich doch plötzlich Sonderfälle auf, die man durch bloßes Draufschauen niemals gesehen hätte... und auf einmal ist der Code viel länger als man gedacht hätte.

Zum Glück sind bei Pascal die Kompilierzeiten kurz, da kann man sich solche „Ungetüme“ wenigstens noch leisten...

[JamesTKirk]

Zitat:

Zitat von Patito (Beitrag 1255781)

FPC 2.7.1 -O1

...

FPC 2.7.1 -O3

Blöde Frage: hast du verwendeten Units (insbesondere den AVLTree aus der FCL) jedesmal vom Source kompiliert? Wenn nicht solltest du zumindest die AVLTree Unit kopieren, weil standardmäßig werden die Units in Packages (und die RTL sowie der Compiler) mit -O2 kompiliert.

Kleine Info noch nebenbei: in 2.7.1 gibt as auch noch -O4 und für -O3 könntest du noch -Oodeadvalues(damit fehlt nur noch das Field Reordering für -O4) und -Oodeadstore bzw. für -O4 nur -Oodeadstore noch einschalten (eine aktuelle 2.7.1 vorausgesetzt :mrgreen: ). Wenn du -Oodeadstore, -Oodeadvalues und -Ooconstprop unter -O- bis -O2 einsetzen willst, musst du auch noch -Oodfa aktivieren.

Gruß,
Sven

[Dejan Vu]

Zitat:

Zitat von Namenloser (Beitrag 1255858)

Zum Glück sind bei Pascal die Kompilierzeiten kurz, da kann man sich solche „Ungetüme“ wenigstens noch leisten...

Na ja. Mein Compiler kompiliert nur das, was ich geändert habe.

Was ich meinte war: Wenn eine Datenstruktur bei 10 Mio Einträgen wunderbar performant ist, aber mein Anwendungsfall nur 10 Elemente beinhaltet (das aber 1 Mio x pro Sekunde) muss man sich 2x überlegen, ob meine Datenstruktur die geeignete ist.

Compilerzeiten und Dateigrößen sind da (für mich) zweitrangig.

Boyer-Moore z.B. ist bekanntermaßen der schnellste Stringmatcher. Aber nur bei großen Alphabeten und langen zu suchenden Strings in noch längeren Zeichenketten.

[Patito]

[QUOTE=JamesTKirk;1255922]

Zitat:

Zitat von Patito (Beitrag 1255781)

FPC 2.7.1 -O1

...

FPC 2.7.1 -O3

Blöde Frage: hast du verwendeten Units (insbesondere den AVLTree aus der FCL) jedesmal vom Source kompiliert? Wenn nicht solltest du zumindest die AVLTree Unit kopieren, weil standardmäßig werden die Units in Packages (und die RTL sowie der Compiler) mit -O2 kompiliert.

Sieht ganz danach aus. Mit -O3 sollte es ja eigentlich nicht langsamer werden.
Ich habe die Unit jetzt mal ins Projekt reingenommen:

FPC 2.7.1 -O1
AVL Tree
AL (1000000)I: 234 L: 141 R: 156
DL (1000000)I: 202 L: 156 R: 156
RD (1000000)I: 656 L: 530 RH: 374 RIH: 437

FPC 2.7.1 -O3
AVL Tree
AL (1000000)I: 203 L: 94 R: 109
DL (1000000)I: 171 L: 94 R: 125
RD (1000000)I: 577 L: 436 RH: 328 RIH: 390

Das sollte jetzt passen. -O4 klingt interessant... mal schauen...

[BUG]

Zitat:

Zitat von Dejan Vu (Beitrag 1255923)

Wenn eine Datenstruktur bei 10 Mio Einträgen wunderbar performant ist, aber mein Anwendungsfall nur 10 Elemente beinhaltet (das aber 1 Mio x pro Sekunde) muss man sich 2x überlegen, ob meine Datenstruktur die geeignete ist.

Jup, das wird in der C++ Gemeinde auch gerne diskutiert. Alles was als gesamte Collection in eine Speicherseite passt, soll in in einem (sortierten) Vektor ganz gut aufgehoben sein.
Lokalität und wenig Speicherverwaltung FTW :wink:

[Namenloser]

Eine Speicherseite (4096 Bytes) erscheint mir recht viel. Bei der Größe würde es mich doch wundern, wenn ein Baum nicht schneller wäre. Ich kann mir vorstellen, dass Arrays bis ~100 oder vielleicht 200 Elemente (sagen wir mal Ints) überlegen sind.

[BUG]

Naja, wenn man etwas schielt, ist die binäre Suche in einem sortierten Vector/Array eine Suche in einem Binärbaum. Damit hat man maximal log_2(4096) = 12 Schritte, um einen Eintrag zu finden.
Den Vorteil hat man dann aber nur beim Suchen, beim Einfügen/Löschen können Kopieroperationen teuer werden.

Dabei kommt es natürlich auch darauf an, wie die anderen Datenstrukturen verwaltet werden.
Ein Baum, der durch seine Verteilung im Speicher auch nur einen Pagefault mehr auslöst, sollte dadurch für mostly-read-Fälle deutlich unattraktiver werden :mrgreen:

[Namenloser]

Das Suchen ist wohl auch eher nicht das Problem. Aber das Einfügen und Löschen eines Elements ist beim Array O(n), weil die Elemente im Speicher umkopiert werden müssen.

[Dejan Vu]

Zitat:

Zitat von Namenloser (Beitrag 1256070)

weil die Elemente im Speicher umkopiert werden müssen.

... was dann widerum erstens ein ASM Befehl und zweitens bei kleinen Arrays im Cache und drittens in wenigen Takten, also mitnichten unbedingt so viel Langsamer ist. Denn während das kleine Array -schwupps- kopiert wurde, muss ja beim Baum vom Speichermanager ein Speicherblock angefordert und diverse Zeiger umgebogen werden. Unterm Strich u.U. mehr Takte also so ein hurtiges Copy.

"Big Oh ist nicht alles. Es gibt auch noch diese häßliche Konstante"