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