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.

NTG: Native and tree-based container splits and joins - g++

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

+n_set- +std::set
+splay_tree_set- +tree + with Tag = splay_tree_tag +, and Node_Update = null_tree_node_update +
+rb_tree_set- +tree + with Tag = rb_tree_tag +, and Node_Update = null_tree_node_update +
+ov_tree_set- +tree + with Tag = ov_tree_tag +, and Node_Update = null_tree_node_update +

NTM: Native and tree-based container splits and joins - msvc++

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

+n_set- +std::set
+splay_tree_set- +tree + with Tag = splay_tree_tag +, and Node_Update = null_tree_node_update +
+rb_tree_set- +tree + with Tag = rb_tree_tag +, and Node_Update = null_tree_node_update +
+ov_tree_set- +tree + with Tag = ov_tree_tag +, and Node_Update = null_tree_node_update +

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.