Effizienz des Speichermanagers

[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(?)

[Namenloser]

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

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

[Dejan Vu]

Zitat von Namenloser:

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.

[BUG]

Zitat von Dejan Vu:

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

[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

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

[Dejan Vu]

Zitat von Patito:

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

[JamesTKirk]

Zitat von Patito:

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 ). Wenn du -Oodeadstore, -Oodeadvalues und -Ooconstprop unter -O- bis -O2 einsetzen willst, musst du auch noch -Oodfa aktivieren.

Gruß,
Sven