Effizienz des Speichermanagers

[Dejan Vu]

Zitat von Namenloser:

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?

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

[Patito]

Zitat von Dejan Vu:

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 von Patito:

Zitat von Dejan Vu:

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 von Patito:

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 von Dejan Vu:

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 von Patito:

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 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 von Namenloser:

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