Tree Order-Statistics Timing Test

Description

This test creates a container, inserts random integers into the the container, and then checks the order-statistics of the container's values. (If the container is one of pb_ds 's trees, it does this with the order_of_key method of tree_order_statistics_node_update ; otherwise, it uses the find method and std::distance .) It measures the average time for such queries as a function of the number of values inserted.

(The test was executed with tree_order_statistics_timing_test 200 200 2100)

Purpose

The test checks the performance difference of policies based on node-invariant as opposed to a external functions. (see Design::Associative Containers::Tree-Based Containers::Node Invariants .)

Results

Figures NTG, NTM, and NTL show the results for the native and tree-based containers in g++, msvc++, and local, respectively.

no image
NTG: Native and tree-based container order-statistics queries - g++

In the above figure, the names in the legends have the following meaning:

  1. n_set- std::set
  2. splay_tree_ost_set- tree with Tag = splay_tree_tag , and Node_Update = tree_order_statistics_node_update
  3. rb_tree_ost_set- tree with Tag = rb_tree_tag , and Node_Update = tree_order_statistics_node_update
no image
NTM: Native and tree-based container order-statistics queries - msvc++

In the above figure, the names in the legends have the following meaning:

  1. n_set- std::set
  2. splay_tree_ost_set- tree with Tag = splay_tree_tag , and Node_Update = tree_order_statistics_node_update
  3. rb_tree_ost_set- tree with Tag = rb_tree_tag , and Node_Update = tree_order_statistics_node_update
no image
NTL: Native and tree-based container order-statistics queries - local

Observations

In this test, the native red-black tree can support order-statistics queries only externally, by performing a find (alternatively, lower_bound or upper_bound ) and then using std::distance . This is clearly linear, and it is not that surprising that the cost is high.

pb_ds 's tree-based containers use in this test the order_of_key method of tree_order_statistics_node_update. This method has only linear complexity in the length of the root-node path. Unfortunately, the average path of a splay tree (tree with Tag = splay_tree_tag ) can be higher than logarithmic; the longest path of a red-black tree (tree with Tag = rb_tree_tag ) is logarithmic in the number of elements. Consequently, the splay tree has worse performance than the red-black tree.