1 <!DOCTYPE html PUBLIC
"-//W3C//DTD XHTML 1.0 Transitional//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html xmlns=
"http://www.w3.org/1999/xhtml" xml:
lang=
"en" lang=
"en">
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" />
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
19 <p>(The test was executed with
<a href=
"../../../../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
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">
36 <div id=
"NNTG_tree_text_insert_timing_test_node_tree">
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>
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>
48 <tt>std::map
</tt></li>
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>
56 </div><div style=
"width: 100%; height: 20px"></div></div>
61 <div id=
"NVTG_res_div">
63 <div id=
"NVTG_tree_text_insert_timing_test_vector_tree">
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>
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>
75 <tt>std::map
</tt></li>
77 </div><div style=
"width: 100%; height: 20px"></div></div>
82 <div id=
"NPTG_res_div">
84 <div id=
"NPTG_tree_text_insert_timing_test_pat_trie">
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>
90 <tt>std::map
</tt></li>
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>
98 </div><div style=
"width: 100%; height: 20px"></div></div>
103 <div id=
"NNTM_res_div">
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>
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>
117 <tt>std::map
</tt></li>
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>
125 </div><div style=
"width: 100%; height: 20px"></div></div>
130 <div id=
"NVTM_res_div">
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>
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>
144 <tt>std::map
</tt></li>
146 </div><div style=
"width: 100%; height: 20px"></div></div>
151 <div id=
"NPTM_res_div">
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>
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>
165 <tt>std::map
</tt></li>
167 </div><div style=
"width: 100%; height: 20px"></div></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>
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>
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>
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>