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 Text Insert 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-Based and Trie-Based Text Insert Timing Test</h1> 13<h2><a name="description" id="description">Description</a></h2> 14<p>This test inserts a number of values with keys from an 15 arbitrary text ([ <a href="references.html#wickland96thirty">wickland96thirty</a> ]) into 16 a container using <tt>insert</tt> . It measures the average 17 time for <tt>insert</tt> as a function of the number of values 18 inserted.</p> 19<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_text_insert_timing.cc"><tt>tree_text_insert_timing_test</tt></a> 20 thirty_years_among_the_dead_preproc.txt 200 200 2100)</p> 21<h2><a name="purpose" id="purpose">Purpose</a></h2> 22<p>The test checks the effect of different underlying 23 data structures.</p> 24<h2><a name="results" id="results">Results</a></h2> 25<p>Figures <a href="#NNTG">NNTG</a>, <a href="#NVTG">NVTG</a>, 26 and <a href="#NPTG">NPTG</a> show the results for the native 27 tree and <tt>pb_ds</tt>'s node-based trees, the native tree and 28 <tt>pb_ds</tt>'s vector-based trees, and the native tree 29 and<tt>pb_ds</tt>'s PATRICIA-trie, respectively, in <a href="assoc_performance_tests.html#gcc"><u>g++</u></a>; Figures 30 <a href="#NNTM">NNTM</a>, <a href="#NVTM">NVTM</a>, and 31 <a href="#NPTM">NPTM</a> show the same in <a href="assoc_performance_tests.html#msvc"><u>msvc++</u></a>; Figures 32 <a href="#NNTL">NNTL</a>, <a href="#NVTL">NVTL</a>, and 33 <a href="#NPTL">NPTL</a> show the same in <a href="assoc_performance_tests.html#local"><u>local</u></a>.</p> 34<div id="NNTG_res_div"> 35<div id="NNTG_gcc"> 36<div id="NNTG_tree_text_insert_timing_test_node_tree"> 37<div id="NNTG_assoc"> 38<div id="NNTG_Native_tree_and_node-based_trees_text_insert_timing_test_using__tt_insert_455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NNTG" id="NNTG"><img src="tree_text_insert_timing_test_node_tree_gcc.png" alt="no image" /></a></h6>NNTG: Native tree and node-based trees text insert timing test using <tt>insert</tt> - <a href="assoc_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p> 39<ol> 40<li> 41splay_tree_map- 42<a href="tree.html"><tt>tree</tt></a> 43 with <tt>Tag</tt> = <a href="splay_tree_tag.html"><tt>splay_tree_tag</tt></a> 44, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 45</li> 46<li> 47n_map- 48<tt>std::map</tt></li> 49<li> 50rb_tree_map- 51<a href="tree.html"><tt>tree</tt></a> 52 with <tt>Tag</tt> = <a href="rb_tree_tag.html"><tt>rb_tree_tag</tt></a> 53, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 54</li> 55</ol> 56</div><div style="width: 100%; height: 20px"></div></div> 57</div> 58</div> 59</div> 60</div> 61<div id="NVTG_res_div"> 62<div id="NVTG_gcc"> 63<div id="NVTG_tree_text_insert_timing_test_vector_tree"> 64<div id="NVTG_assoc"> 65<div id="NVTG_Native_tree_and_vector-based_tree_text_insert_timing_test_using__tt_insert_455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NVTG" id="NVTG"><img src="tree_text_insert_timing_test_vector_tree_gcc.png" alt="no image" /></a></h6>NVTG: Native tree and vector-based tree text insert timing test using <tt>insert</tt> - <a href="assoc_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p> 66<ol> 67<li> 68ov_tree_map- 69<a href="tree.html"><tt>tree</tt></a> 70 with <tt>Tag</tt> = <a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a> 71, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 72</li> 73<li> 74n_map- 75<tt>std::map</tt></li> 76</ol> 77</div><div style="width: 100%; height: 20px"></div></div> 78</div> 79</div> 80</div> 81</div> 82<div id="NPTG_res_div"> 83<div id="NPTG_gcc"> 84<div id="NPTG_tree_text_insert_timing_test_pat_trie"> 85<div id="NPTG_assoc"> 86<div id="NPTG_Native_tree_and_PATRICIA_trie_text_insert_timing_test_using__tt_insert_455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPTG" id="NPTG"><img src="tree_text_insert_timing_test_pat_trie_gcc.png" alt="no image" /></a></h6>NPTG: Native tree and PATRICIA trie text insert timing test using <tt>insert</tt> - <a href="assoc_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p> 87<ol> 88<li> 89n_map- 90<tt>std::map</tt></li> 91<li> 92pat_trie_map- 93<a href="trie.html"><tt>trie</tt></a> 94 with <tt>Tag</tt> = <a href="pat_trie_tag.html"><tt>pat_trie_tag</tt></a> 95, and <tt>Node_Update</tt> = <a href="null_trie_node_update.html"><tt>null_trie_node_update</tt></a> 96</li> 97</ol> 98</div><div style="width: 100%; height: 20px"></div></div> 99</div> 100</div> 101</div> 102</div> 103<div id="NNTM_res_div"> 104<div id="NNTM_msvc"> 105<div id="NNTM_tree_text_insert_timing_test_node_tree"> 106<div id="NNTM_assoc"> 107<div id="NNTM_Native_tree_and_node-based_trees_text_insert_timing_test_using__tt_insert_455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NNTM" id="NNTM"><img src="tree_text_insert_timing_test_node_tree_msvc.png" alt="no image" /></a></h6>NNTM: Native tree and node-based trees text insert timing test using <tt>insert</tt> - <a href="assoc_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p> 108<ol> 109<li> 110splay_tree_map- 111<a href="tree.html"><tt>tree</tt></a> 112 with <tt>Tag</tt> = <a href="splay_tree_tag.html"><tt>splay_tree_tag</tt></a> 113, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 114</li> 115<li> 116n_map- 117<tt>std::map</tt></li> 118<li> 119rb_tree_map- 120<a href="tree.html"><tt>tree</tt></a> 121 with <tt>Tag</tt> = <a href="rb_tree_tag.html"><tt>rb_tree_tag</tt></a> 122, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 123</li> 124</ol> 125</div><div style="width: 100%; height: 20px"></div></div> 126</div> 127</div> 128</div> 129</div> 130<div id="NVTM_res_div"> 131<div id="NVTM_msvc"> 132<div id="NVTM_tree_text_insert_timing_test_vector_tree"> 133<div id="NVTM_assoc"> 134<div id="NVTM_Native_tree_and_vector-based_tree_text_insert_timing_test_using__tt_insert_455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NVTM" id="NVTM"><img src="tree_text_insert_timing_test_vector_tree_msvc.png" alt="no image" /></a></h6>NVTM: Native tree and vector-based tree text insert timing test using <tt>insert</tt> - <a href="assoc_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p> 135<ol> 136<li> 137ov_tree_map- 138<a href="tree.html"><tt>tree</tt></a> 139 with <tt>Tag</tt> = <a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a> 140, and <tt>Node_Update</tt> = <a href="null_tree_node_update.html"><tt>null_tree_node_update</tt></a> 141</li> 142<li> 143n_map- 144<tt>std::map</tt></li> 145</ol> 146</div><div style="width: 100%; height: 20px"></div></div> 147</div> 148</div> 149</div> 150</div> 151<div id="NPTM_res_div"> 152<div id="NPTM_msvc"> 153<div id="NPTM_tree_text_insert_timing_test_pat_trie"> 154<div id="NPTM_assoc"> 155<div id="NPTM_Native_tree_and_PATRICIA_trie_text_insert_timing_test_using__tt_insert_455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPTM" id="NPTM"><img src="tree_text_insert_timing_test_pat_trie_msvc.png" alt="no image" /></a></h6>NPTM: Native tree and PATRICIA trie text insert timing test using <tt>insert</tt> - <a href="assoc_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p> 156<ol> 157<li> 158pat_trie_map- 159<a href="trie.html"><tt>trie</tt></a> 160 with <tt>Tag</tt> = <a href="pat_trie_tag.html"><tt>pat_trie_tag</tt></a> 161, and <tt>Node_Update</tt> = <a href="null_trie_node_update.html"><tt>null_trie_node_update</tt></a> 162</li> 163<li> 164n_map- 165<tt>std::map</tt></li> 166</ol> 167</div><div style="width: 100%; height: 20px"></div></div> 168</div> 169</div> 170</div> 171</div> 172<div id="NNTL_res_div"> 173<div id="NNTL_local"> 174<div id="NNTL_tree_text_insert_timing_test_node_tree"> 175<div id="NNTL_assoc"> 176<div id="NNTL_Native_tree_and_node-based_trees_text_insert_timing_test_using__tt_insert_455tt_"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NNTL" id= "NNTL"><img src="tree_text_insert_timing_test_node_tree_local.png" alt="no image" /></a></h6>NNTL: Native tree and node-based trees text insert timing test using <tt>insert</tt> - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 177</div> 178</div> 179</div> 180</div> 181<div id="NVTL_res_div"> 182<div id="NVTL_local"> 183<div id="NVTL_tree_text_insert_timing_test_vector_tree"> 184<div id="NVTL_assoc"> 185<div id="NVTL_Native_tree_and_vector-based_tree_text_insert_timing_test_using__tt_insert_455tt_"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NVTL" id= "NVTL"><img src="tree_text_insert_timing_test_vector_tree_local.png" alt="no image" /></a></h6>NVTL: Native tree and vector-based tree text insert timing test using <tt>insert</tt> - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 186</div> 187</div> 188</div> 189</div> 190<div id="NPTL_res_div"> 191<div id="NPTL_local"> 192<div id="NPTL_tree_text_insert_timing_test_pat_trie"> 193<div id="NPTL_assoc"> 194<div id="NPTL_Native_tree_and_PATRICIA_trie_text_insert_timing_test_using__tt_insert_455tt_"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPTL" id= "NPTL"><img src="tree_text_insert_timing_test_pat_trie_local.png" alt="no image" /></a></h6>NPTL: Native tree and PATRICIA trie text insert timing test using <tt>insert</tt> - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 195</div> 196</div> 197</div> 198</div> 199<h2><a name="observations" id="observations">Observations</a></h2> 200<p>Observing Figure <a href="#NNTG">NNTG</a> , for this 201 setting, a splay tree, ( <a href="tree.html"><tt>tree</tt></a> 202 with <tt>Tag =</tt> <a href="splay_tree_tag.html"><tt>splay_tree_tag</tt></a> ) does 203 not do well. This was covered in <a href="tree_text_find_find_timing_test.html">Tree-Based and 204 Trie-Based Text <tt>find</tt> Find Timing Test</a> . The two 205 red-black trees perform better.</p> 206<p>Observing Figure <a href="#NVTG">NVTG</a>, an ordered-vector 207 tree ( <a href="tree.html"><tt>tree</tt></a> 208 with <tt>Tag =</tt> <a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a>) performs 209 abysmally. Inserting into this type of tree has linear 210 complexity [ <a href="references.html#austern00noset">austern00noset</a>].</p> 211<p>Observing Figure <a href="#NPTG">NPTG</a> , A PATRICIA trie 212 ( <a href="trie.html"><tt>trie</tt></a> 213 with <tt>Tag =</tt> <a href="pat_trie_tag.html"><tt>pat_trie_tag</tt></a> ) has 214 abysmal performance, as well. This is not that surprising, 215 since a large-fan-out PATRICIA trie works like a hash table with 216 collisions resolved by a sub-trie. Each time a collision is 217 encountered, a new "hash-table" is built A large fan-out 218 PATRICIA trie, however, doe does well in look-ups (see <a href="tree_text_find_find_timing_test.html">Tree-Based and 219 Trie-Based Text <tt>find</tt> Find Timing Test</a> ). It is 220 possibly beneficial to semi-static settings, therefore.</p> 221<p><a href="assoc_performance_tests.html#tree_like_based_types">Observations::Tree-Like-Based 222 Container Types</a> summarizes some observations on tree-based 223 and trie-based containers.</p> 224</div> 225</body> 226</html> 227
