l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.4/doc/html/ext/pb_ds/tree_split_join_timing_test.html

   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>
  48 n_set-
  49 <tt>std::set</tt></li>
  50 <li>
  51 splay_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>
  57 rb_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>
  63 ov_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>
  81 n_set-
  82 <tt>std::set</tt></li>
  83 <li>
  84 splay_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>
  90 rb_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>
  96 ov_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>