Tree Split-Join Timing Test

Description

This test a container, inserts into a number of values, splits the container at the median, and joins the two containers. (If the containers are one of pb_ds 's trees, it splits and joins with the split and join method; otherwise, it uses the erase and insert methods.) It measures the time for splitting and joining the containers as a function of the number of values inserted.

(The test was executed with tree_split_join_timing_test 200 200 2100)

Purpose

The test checks the performance difference of join as opposed to a sequence of insert operations; by implication, this test checks the most efficient way to erase a sub-sequence from a tree-like-based container, since this can always be performed by a small sequence of splits and joins (see Motivation::Associative Containers::Slightly Different Methods::Methods Related to Split and Join and Design::Associative Containers::Tree-Based Containers::Additional Methods .)

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 splits and joins - g++

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

  1. n_set- std::set
  2. splay_tree_set- tree with Tag = splay_tree_tag , and Node_Update = null_tree_node_update
  3. rb_tree_set- tree with Tag = rb_tree_tag , and Node_Update = null_tree_node_update
  4. ov_tree_set- tree with Tag = ov_tree_tag , and Node_Update = null_tree_node_update
no image
NTM: Native and tree-based container splits and joins - msvc++

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

  1. n_set- std::set
  2. splay_tree_set- tree with Tag = splay_tree_tag , and Node_Update = null_tree_node_update
  3. rb_tree_set- tree with Tag = rb_tree_tag , and Node_Update = null_tree_node_update
  4. ov_tree_set- tree with Tag = ov_tree_tag , and Node_Update = null_tree_node_update
no image
NTL: Native and tree-based container splits and joins - local

Observations

In this test, the native red-black trees must be split and joined externally, through a sequence of erase and insert operations. This is clearly super-linear, and it is not that surprising that the cost is high.

pb_ds 's tree-based containers use in this test the split and join methods, which have lower complexity: the join method of a splay tree ( tree with Tag = splay_tree_tag ) is quadratic in the length of the longest root-leaf path, and linear in the total number of elements; the join method of a red-black tree ( tree with Tag = rb_tree_tag ) or an ordered-vector tree ( tree with Tag = ov_tree_tag ) is linear in the number of elements.

Asides from orders of growth, pb_ds 's trees access their allocator very little in these operations, and some of them do not access it at all. This leads to lower constants in their complexity, and, for some containers, to exception-free splits and joins (which can be determined via container_traits).

It is important to note that split and join are not esoteric methods - they are the most efficient means of erasing a contiguous range of values from a tree based container.