The Perl Advent Calendar needs more articles for 2022. Submit your idea today!

Benchmarks

These are my results from running the benchmark.pl script with various parameters. It compares Tree::RB, Tree::RB::XS, Tree::AVL, and AVLTree, and also Perl's sort for an array of keys and for a hashref of keys for context.

To summarize the findings, Tree::RB::XS is by far the fastest tree module and even 30%-40% faster than building a hash and sorting its keys, as long as the tree is using an internal comparison function and not calling back to a Perl coderef. When calling back to a Perl coderef for each comparison, Tree::RB::XS is only about 12% faster than AVLTree.

Contenders:

Key Types

Since Tree::RB::XS has built-in key comparison functions, I re-run the benchmark with each potential type of key.

"Get Min Value"

This test builds a collection of nodes, starts timing, adds all the nodes to the tree, then looks up the minimum value, then records the elapsed time. For comparison to plain perl, I added tests named 'sort_keys' that builds a hashref of the key/value pairs and then sorts the keys and then gets the value from the hashref. For extra reference, I added a test named 'sort' that shows what it wold be just to sort the keys from an array.

The benchmark was giving a large amount of deviation when I ran these sequentially in the same Perl process (probably because of one algorithm's effects on the memory pool) so I have it shell out to a new Perl process to run each module's test. The benchmark script runs the test I times, the test runs R loops of the algorithm, and the algorithm operates on N nodes.

1M nodes, one iteration per run, for one run

``` Int: 1000000 data items, 1 outer iterations, 1 inner iterations s/iter tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 29.7 -- -56% -86% -95% -97% -99% tree_rb 13.2 125% -- -69% -88% -92% -98% avltree 4.08 627% 223% -- -62% -75% -93% sort_keys 1.55 1814% 750% 163% -- -34% -81% tree_rb_xs 1.02 2808% 1192% 300% 52% -- -71% sort 0.300 9787% 4293% 1260% 417% 240% --

Float: 1000000 data items, 1 outer iterations, 1 inner iterations s/iter tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 32.4 -- -56% -80% -93% -97% -98% tree_rb 14.2 129% -- -53% -84% -93% -96% avltree 6.61 391% 114% -- -67% -85% -92% sort_keys 2.20 1375% 543% 200% -- -56% -75% tree_rb_xs 0.960 3279% 1374% 589% 129% -- -44% sort 0.540 5907% 2520% 1124% 307% 78% --

Shortstr: 1000000 data items, 1 outer iterations, 1 inner iterations s/iter tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 36.2 -- -69% -71% -94% -96% -97% tree_rb 11.3 220% -- -7% -81% -88% -91% avltree 10.5 244% 8% -- -79% -87% -91% sort_keys 2.19 1552% 416% 379% -- -37% -55% tree_rb_xs 1.37 2540% 724% 666% 60% -- -28% sort 0.990 3554% 1040% 961% 121% 38% --

Longstr: 1000000 data items, 1 outer iterations, 1 inner iterations s/iter tree_avl avltree tree_rb sort_keys tree_rb_xs sort tree_avl 38.1 -- -63% -69% -90% -94% -96% avltree 14.1 171% -- -15% -72% -85% -90% tree_rb 11.9 221% 18% -- -67% -82% -88% sort_keys 3.95 866% 256% 201% -- -45% -64% tree_rb_xs 2.17 1658% 548% 448% 82% -- -35% sort 1.42 2587% 890% 737% 178% 53% --

Commonstr: 1000000 data items, 1 outer iterations, 1 inner iterations s/iter tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 36.7 -- -68% -71% -93% -96% -97% tree_rb 11.6 217% -- -7% -79% -86% -90% avltree 10.8 240% 7% -- -78% -85% -89% sort_keys 2.39 1434% 385% 351% -- -32% -51% tree_rb_xs 1.62 2163% 615% 565% 48% -- -28% sort 1.16 3060% 898% 829% 106% 40% --

Ustr: 1000000 data items, 1 outer iterations, 1 inner iterations s/iter tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 36.4 -- -68% -70% -93% -96% -97% tree_rb 11.5 215% -- -5% -79% -86% -90% avltree 10.9 233% 6% -- -78% -86% -90% sort_keys 2.37 1436% 387% 361% -- -34% -52% tree_rb_xs 1.56 2233% 640% 601% 52% -- -28% sort 1.13 3121% 921% 867% 110% 38% --

Obj: 1000000 data items, 1 outer iterations, 1 inner iterations s/iter tree_avl tree_rb avltree tree_rb_xs sort sort_keys tree_avl 35.4 -- -48% -78% -80% -92% -93% tree_rb 18.3 93% -- -57% -62% -85% -86% avltree 7.84 352% 134% -- -10% -66% -68% tree_rb_xs 7.03 404% 161% 12% -- -62% -64% sort 2.66 1231% 589% 195% 164% -- -6% sort_keys 2.50 1316% 633% 214% 181% 6% -- ```

100K nodes, one iteration per run, averaged over 10 runs

``` Int: 100000 data items, 10 outer iterations, 1 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.421/s -- -56% -87% -96% -98% -99% tree_rb 0.948/s 125% -- -72% -92% -95% -98% avltree 3.37/s 700% 255% -- -71% -84% -94% sort_keys 11.5/s 2630% 1113% 241% -- -44% -78% tree_rb_xs 20.4/s 4747% 2053% 506% 78% -- -61% sort 52.6/s 12400% 5453% 1463% 358% 158% --

Float: 100000 data items, 10 outer iterations, 1 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.386/s -- -58% -81% -94% -98% -99% tree_rb 0.913/s 137% -- -55% -85% -96% -97% avltree 2.03/s 426% 122% -- -67% -90% -94% sort_keys 6.13/s 1490% 572% 202% -- -70% -82% tree_rb_xs 20.4/s 5188% 2135% 906% 233% -- -39% sort 33.3/s 8537% 3550% 1543% 443% 63% --

Shortstr: 100000 data items, 10 outer iterations, 1 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.356/s -- -69% -72% -96% -97% -98% tree_rb 1.16/s 227% -- -7% -88% -91% -94% avltree 1.25/s 251% 7% -- -87% -90% -94% sort_keys 9.62/s 2603% 727% 670% -- -23% -52% tree_rb_xs 12.5/s 3414% 975% 901% 30% -- -37% sort 20.0/s 5522% 1620% 1502% 108% 60% --

Longstr: 100000 data items, 10 outer iterations, 1 inner iterations Rate tree_avl avltree tree_rb sort_keys tree_rb_xs sort tree_avl 0.333/s -- -65% -70% -90% -95% -97% avltree 0.948/s 185% -- -14% -73% -86% -92% tree_rb 1.10/s 231% 16% -- -68% -84% -91% sort_keys 3.47/s 943% 266% 215% -- -49% -72% tree_rb_xs 6.76/s 1929% 613% 514% 95% -- -45% sort 12.2/s 3562% 1187% 1007% 251% 80% --

Commonstr: 100000 data items, 10 outer iterations, 1 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.350/s -- -69% -71% -96% -97% -98% tree_rb 1.15/s 228% -- -6% -87% -90% -93% avltree 1.22/s 249% 6% -- -86% -89% -93% sort_keys 8.55/s 2343% 645% 600% -- -23% -49% tree_rb_xs 11.1/s 3076% 869% 810% 30% -- -33% sort 16.7/s 4663% 1353% 1265% 95% 50% --

Ustr: 100000 data items, 10 outer iterations, 1 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.351/s -- -69% -71% -96% -97% -98% tree_rb 1.13/s 222% -- -8% -86% -90% -93% avltree 1.23/s 250% 9% -- -85% -89% -93% sort_keys 8.33/s 2277% 638% 579% -- -26% -51% tree_rb_xs 11.2/s 3106% 896% 816% 35% -- -34% sort 16.9/s 4736% 1402% 1281% 103% 51% --

Obj: 100000 data items, 10 outer iterations, 1 inner iterations Rate tree_avl tree_rb avltree tree_rb_xs sort sort_keys tree_avl 0.375/s -- -49% -81% -84% -95% -95% tree_rb 0.729/s 94% -- -64% -69% -90% -91% avltree 2.02/s 439% 177% -- -15% -72% -74% tree_rb_xs 2.38/s 533% 226% 18% -- -67% -70% sort 7.19/s 1818% 886% 256% 203% -- -8% sort_keys 7.81/s 1983% 971% 287% 229% 9% -- ```

100K nodes, 10 iterations per run, for one run

``` Int: 100000 data items, 1 outer iterations, 10 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.378/s -- -55% -88% -97% -98% -99% tree_rb 0.839/s 122% -- -74% -93% -95% -98% avltree 3.24/s 756% 286% -- -73% -82% -94% sort_keys 11.9/s 3049% 1319% 268% -- -32% -77% tree_rb_xs 17.5/s 4540% 1991% 442% 47% -- -67% sort 52.6/s 13821% 6174% 1526% 342% 200% --

Float: 100000 data items, 1 outer iterations, 10 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.337/s -- -58% -82% -95% -98% -99% tree_rb 0.806/s 140% -- -57% -88% -95% -98% avltree 1.89/s 461% 134% -- -71% -89% -95% sort_keys 6.54/s 1841% 710% 246% -- -63% -81% tree_rb_xs 17.5/s 5111% 2075% 828% 168% -- -49% sort 34.5/s 10141% 4176% 1724% 428% 97% --

Shortstr: 100000 data items, 1 outer iterations, 10 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.320/s -- -68% -74% -97% -97% -98% tree_rb 0.999/s 213% -- -18% -89% -91% -94% avltree 1.23/s 283% 23% -- -87% -89% -93% sort_keys 9.26/s 2797% 827% 656% -- -19% -48% tree_rb_xs 11.4/s 3456% 1037% 827% 23% -- -36% sort 17.9/s 5487% 1687% 1357% 93% 57% --

Longstr: 100000 data items, 1 outer iterations, 10 inner iterations s/iter tree_avl avltree tree_rb sort_keys tree_rb_xs sort tree_avl 3.37 -- -68% -69% -92% -96% -98% avltree 1.09 209% -- -3% -74% -87% -92% tree_rb 1.06 219% 3% -- -73% -87% -92% sort_keys 0.282 1096% 288% 275% -- -50% -70% tree_rb_xs 0.141 2293% 675% 650% 100% -- -40% sort 8.40e-02 3917% 1201% 1158% 236% 68% --

Commonstr: 100000 data items, 1 outer iterations, 10 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.316/s -- -68% -73% -96% -97% -98% tree_rb 0.978/s 209% -- -17% -87% -91% -94% avltree 1.18/s 272% 20% -- -85% -89% -92% sort_keys 7.69/s 2333% 687% 554% -- -28% -51% tree_rb_xs 10.8/s 3301% 1000% 814% 40% -- -31% sort 15.6/s 4842% 1498% 1228% 103% 45% --

Ustr: 100000 data items, 1 outer iterations, 10 inner iterations Rate tree_avl tree_rb avltree sort_keys tree_rb_xs sort tree_avl 0.322/s -- -67% -73% -96% -97% -98% tree_rb 0.972/s 202% -- -18% -87% -91% -94% avltree 1.18/s 266% 21% -- -84% -89% -93% sort_keys 7.52/s 2234% 674% 537% -- -31% -55% tree_rb_xs 10.9/s 3274% 1018% 821% 45% -- -35% sort 16.7/s 5073% 1615% 1312% 122% 53% --

Obj: 100000 data items, 1 outer iterations, 10 inner iterations Rate tree_avl tree_rb avltree tree_rb_xs sort sort_keys tree_avl 0.338/s -- -49% -83% -85% -95% -95% tree_rb 0.665/s 97% -- -67% -71% -91% -91% avltree 2.02/s 499% 204% -- -10% -71% -72% tree_rb_xs 2.26/s 567% 239% 12% -- -68% -69% sort 7.09/s 1997% 966% 250% 214% -- -4% sort_keys 7.35/s 2074% 1005% 263% 226% 4% -- ```

10M nodes, 1 iteration per run, 2 runs

``` Int: 10000000 data items, 2 outer iterations, 1 inner iterations s/iter tree_rb avltree sort_keys tree_rb_xs sort tree_rb 175 -- -66% -89% -91% -98% avltree 58.8 197% -- -68% -73% -94% sort_keys 19.0 819% 210% -- -18% -81% tree_rb_xs 15.6 1016% 276% 21% -- -76% sort 3.68 4642% 1498% 416% 325% --

Float: 10000000 data items, 2 outer iterations, 1 inner iterations s/iter tree_rb avltree sort_keys tree_rb_xs sort tree_rb 187 -- -60% -88% -92% -96% avltree 74.9 149% -- -69% -80% -91% sort_keys 23.2 706% 223% -- -36% -71% tree_rb_xs 14.7 1167% 409% 57% -- -54% sort 6.79 2650% 1004% 241% 117% --

Shortstr: 10000000 data items, 2 outer iterations, 1 inner iterations s/iter tree_rb avltree sort_keys tree_rb_xs sort tree_rb 142 -- -25% -85% -89% -94% avltree 107 33% -- -80% -85% -91% sort_keys 21.6 557% 396% -- -28% -58% tree_rb_xs 15.6 809% 586% 38% -- -42% sort 9.13 1458% 1075% 137% 71% --

Commonstr: 10000000 data items, 2 outer iterations, 1 inner iterations s/iter tree_rb avltree sort_keys tree_rb_xs sort tree_rb 146 -- -26% -85% -88% -93% avltree 108 35% -- -79% -84% -91% sort_keys 22.5 548% 379% -- -25% -58% tree_rb_xs 17.0 761% 537% 33% -- -44% sort 9.51 1435% 1036% 137% 78% --

Ustr: 10000000 data items, 2 outer iterations, 1 inner iterations s/iter tree_rb avltree sort_keys tree_rb_xs sort tree_rb 143 -- -23% -84% -88% -93% avltree 110 30% -- -79% -85% -91% sort_keys 22.9 527% 383% -- -27% -57% tree_rb_xs 16.6 765% 566% 38% -- -41% sort 9.73 1373% 1034% 135% 70% --

Obj: 10000000 data items, 2 outer iterations, 1 inner iterations s/iter tree_rb avltree tree_rb_xs sort tree_rb 249 -- -52% -55% -83% avltree 118 110% -- -6% -65% tree_rb_xs 111 123% 6% -- -62% sort 41.9 494% 183% 166% -- ```