1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 4<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 5<head> 6<meta name="generator" content="HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" /> 7<title>Tree Split Join Timing Test</title> 8<meta http-equiv="Content-Type" content="text/html; charset=us-ascii" /> 9</head> 10<body> 11<div id="page"> 12<h1>Tree Split-Join Timing Test</h1> 13<h2><a name="description" id="description">Description</a></h2> 14<p>This test a container, inserts into a number of values, 15 splits the container at the median, and joins the two 16 containers. (If the containers are one of <tt>pb_ds</tt> 's 17 trees, it splits and joins with the <tt>split</tt> and 18 <tt>join</tt> method; otherwise, it uses the <tt>erase</tt> and 19 <tt>insert</tt> methods.) It measures the time for splitting 20 and joining the containers as a function of the number of 21 values inserted.</p> 22<p>(The test was executed with <a href="http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/performance/ext/pb_ds/tree_split_join_timing.cc"><tt>tree_split_join_timing_test</tt></a> 23 200 200 2100)</p> 24<h2><a name="purpose" id="purpose">Purpose</a></h2> 25<p>The test checks the performance difference of <tt>join</tt> 26 as opposed to a sequence of <tt>insert</tt> operations; by 27 implication, this test checks the most efficient way to erase a 28 sub-sequence from a tree-like-based container, since this can 29 always be performed by a small sequence of splits and joins 30 (see <a href="motivation.html#assoc_split_join_methods">Motivation::Associative 31 Containers::Slightly Different Methods::Methods Related to 32 Split and Join</a> and <a href="tree_based_containers.html#add_methods">Design::Associative 33 Containers::Tree-Based Containers::Additional Methods</a> 34 .)</p> 35<h2><a name="results" id="results">Results</a></h2> 36<p>Figures <a href="#NTG">NTG</a>, <a href="#NTM">NTM</a>, and 37 <a href="#NTL">NTL</a> show the results for the native and 38 tree-based containers in <a href="assoc_performance_tests.html#gcc"><u>g++</u></a>, <a href="assoc_performance_tests.html#msvc"><u>msvc++</u></a>, and 39 <a href="assoc_performance_tests.html#local"><u>local</u></a>, 40 respectively.</p> 41<div id="NTG_res_div"> 42<div id="NTG_gcc"> 43<div id="NTG_tree_split_join_timing_test"> 44<div id="NTG_assoc"> 45<div id="NTG_Native_and_tree-based_container_splits_and_joins"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NTG" id="NTG"><img src="tree_split_join_timing_test_gcc.png" alt="no image" /></a></h6>NTG: Native and tree-based container splits and joins - <a href="assoc_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p> 46<ol> 47<li> 48n_set- 49<tt>std::set</tt></li> 50<li> 51splay_tree_set- 52<a href="tree.html"><tt>tree</tt></a> 53 with <tt>Tag</tt> = <a href="splay_tree_tag.html"><tt>splay_tree_tag</tt></a> 54, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 55</li> 56<li> 57rb_tree_set- 58<a href="tree.html"><tt>tree</tt></a> 59 with <tt>Tag</tt> = <a href="rb_tree_tag.html"><tt>rb_tree_tag</tt></a> 60, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 61</li> 62<li> 63ov_tree_set- 64<a href="tree.html"><tt>tree</tt></a> 65 with <tt>Tag</tt> = <a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a> 66, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 67</li> 68</ol> 69</div><div style="width: 100%; height: 20px"></div></div> 70</div> 71</div> 72</div> 73</div> 74<div id="NTM_res_div"> 75<div id="NTM_msvc"> 76<div id="NTM_tree_split_join_timing_test"> 77<div id="NTM_assoc"> 78<div id="NTM_Native_and_tree-based_container_splits_and_joins"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NTM" id="NTM"><img src="tree_split_join_timing_test_msvc.png" alt="no image" /></a></h6>NTM: Native and tree-based container splits and joins - <a href="assoc_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p> 79<ol> 80<li> 81n_set- 82<tt>std::set</tt></li> 83<li> 84splay_tree_set- 85<a href="tree.html"><tt>tree</tt></a> 86 with <tt>Tag</tt> = <a href="splay_tree_tag.html"><tt>splay_tree_tag</tt></a> 87, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 88</li> 89<li> 90rb_tree_set- 91<a href="tree.html"><tt>tree</tt></a> 92 with <tt>Tag</tt> = <a href="rb_tree_tag.html"><tt>rb_tree_tag</tt></a> 93, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 94</li> 95<li> 96ov_tree_set- 97<a href="tree.html"><tt>tree</tt></a> 98 with <tt>Tag</tt> = <a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a> 99, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 100</li> 101</ol> 102</div><div style="width: 100%; height: 20px"></div></div> 103</div> 104</div> 105</div> 106</div> 107<div id="NTL_res_div"> 108<div id="NTL_local"> 109<div id="NTL_tree_split_join_timing_test"> 110<div id="NTL_assoc"> 111<div id="NTL_Native_and_tree-based_container_splits_and_joins"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NTL" id= "NTL"><img src="tree_split_join_timing_test_local.png" alt="no image" /></a></h6>NTL: Native and tree-based container splits and joins - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 112</div> 113</div> 114</div> 115</div> 116<h2><a name="observations" id="observations">Observations</a></h2> 117<p>In this test, the native red-black trees must be split and 118 joined externally, through a sequence of <tt>erase</tt> and 119 <tt>insert</tt> operations. This is clearly super-linear, and 120 it is not that surprising that the cost is high.</p> 121<p><tt>pb_ds</tt> 's tree-based containers use in this test the 122 <tt>split</tt> and <tt>join</tt> methods, which have lower 123 complexity: the <tt>join</tt> method of a splay tree ( <a href="tree.html"><tt>tree</tt></a> 124 with <tt>Tag =</tt> <a href="splay_tree_tag.html"><tt>splay_tree_tag</tt></a> ) is 125 quadratic in the length of the longest root-leaf path, and 126 linear in the total number of elements; the <tt>join</tt> 127 method of a red-black tree ( <a href="tree.html"><tt>tree</tt></a> 128 with <tt>Tag =</tt> <a href="rb_tree_tag.html"><tt>rb_tree_tag</tt></a> ) or an 129 ordered-vector tree ( <a href="tree.html"><tt>tree</tt></a> 130 with <tt>Tag =</tt> <a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a> ) is linear 131 in the number of elements.</p> 132<p>Asides from orders of growth, <tt>pb_ds</tt> 's trees access 133 their allocator very little in these operations, and some of 134 them do not access it at all. This leads to lower constants in 135 their complexity, and, for some containers, to exception-free 136 splits and joins (which can be determined via <a href="assoc_container_traits.html"><tt>container_traits</tt></a>).</p> 137<p>It is important to note that <tt>split</tt> and 138 <tt>join</tt> are not esoteric methods - they are the most 139 efficient means of erasing a contiguous range of values from a 140 tree based container.</p> 141</div> 142</body> 143</html> 144