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 Locality of Reference Find Timing Test
</title>
8 <meta http-equiv=
"Content-Type" content=
"text/html; charset=us-ascii" />
12 <h1>Tree-Based Locality-of-Reference Text
<tt>find
</tt> Find
14 <h2><a name=
"description" id=
"description">Description
</a></h2>
15 <p>This test inserts a number of values with keys from an
16 arbitrary text ([
<a href=
"references.html#wickland96thirty">wickland96thirty
</a> ]) into
17 a container, then performs a series of finds using
18 <tt>find
</tt> . It is different than
<a href=
"tree_text_find_find_timing_test.html">Tree-Based and
19 Trie-Based Text
<tt>find
</tt> Find Timing Test
</a> in the
20 sequence of finds it performs: this test performs multiple
21 <tt>find
</tt> s on the same key before moving on to the next
22 key. It measures the average time for
<tt>find
</tt> as a
23 function of the number of values inserted.
</p>
24 <p>(The test was executed with
<a href=
"../../../../testsuite/performance/ext/pb_ds/tree_text_lor_find_timing.cc"><tt>tree_text_lor_find_timing_test
</tt></a>
25 thirty_years_among_the_dead_preproc.txt
200 200 2100)
</p>
26 <h2><a name=
"purpose" id=
"purpose">Purpose
</a></h2>
27 <p>The test checks the effect of different underlying
28 data structures in a locality-of-reference setting.
</p>
29 <h2><a name=
"results" id=
"results">Results
</a></h2>
30 <p>Figures
<a href=
"#NTG">NTG
</a>,
<a href=
"#NTM">NTM
</a>, and
31 <a href=
"#NTL">NTL
</a> show the results for the native and
32 <tt>pb_ds
</tt> tree-based types in
<a href=
"assoc_performance_tests.html#gcc"><u>g++
</u></a>,
<a href=
"assoc_performance_tests.html#msvc"><u>msvc++
</u></a> and
33 <a href=
"assoc_performance_tests.html#local"><u>local
</u></a>,
35 <div id=
"NTG_res_div">
37 <div id=
"NTG_tree_text_lor_find_timing_test">
39 <div id=
"NTG_Native_and_tree-based_locality-of-reference_text_find_timing_test_using__tt_find_455tt_"><div style=
"border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class=
"c1"><a name=
"NTG" id=
"NTG"><img src=
"tree_text_lor_find_timing_test_gcc.png" alt=
"no image" /></a></h6>NTG: Native and tree-based locality-of-reference text find timing test using
<tt>find
</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>
43 <a href=
"tree.html"><tt>tree
</tt></a>
44 with
<tt>Tag
</tt> =
<a href=
"ov_tree_tag.html"><tt>ov_tree_tag
</tt></a>
45 , and
<tt>Node_Update
</tt> =
<a href=
"null_tree_node_update.html"><tt>null_tree_node_update
</tt></a>
49 <a href=
"tree.html"><tt>tree
</tt></a>
50 with
<tt>Tag
</tt> =
<a href=
"rb_tree_tag.html"><tt>rb_tree_tag
</tt></a>
51 , and
<tt>Node_Update
</tt> =
<a href=
"null_tree_node_update.html"><tt>null_tree_node_update
</tt></a>
55 <tt>std::map
</tt></li>
58 <a href=
"tree.html"><tt>tree
</tt></a>
59 with
<tt>Tag
</tt> =
<a href=
"splay_tree_tag.html"><tt>splay_tree_tag
</tt></a>
60 , and
<tt>Node_Update
</tt> =
<a href=
"null_tree_node_update.html"><tt>null_tree_node_update
</tt></a>
63 </div><div style=
"width: 100%; height: 20px"></div></div>
68 <div id=
"NTM_res_div">
70 <div id=
"NTM_tree_text_lor_find_timing_test">
72 <div id=
"NTM_Native_and_tree-based_locality-of-reference_text_find_timing_test_using__tt_find_455tt_"><div style=
"border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class=
"c1"><a name=
"NTM" id=
"NTM"><img src=
"tree_text_lor_find_timing_test_msvc.png" alt=
"no image" /></a></h6>NTM: Native and tree-based locality-of-reference text find timing test using
<tt>find
</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>
76 <a href=
"tree.html"><tt>tree
</tt></a>
77 with
<tt>Tag
</tt> =
<a href=
"ov_tree_tag.html"><tt>ov_tree_tag
</tt></a>
78 , and
<tt>Node_Update
</tt> =
<a href=
"null_tree_node_update.html"><tt>null_tree_node_update
</tt></a>
82 <a href=
"tree.html"><tt>tree
</tt></a>
83 with
<tt>Tag
</tt> =
<a href=
"rb_tree_tag.html"><tt>rb_tree_tag
</tt></a>
84 , and
<tt>Node_Update
</tt> =
<a href=
"null_tree_node_update.html"><tt>null_tree_node_update
</tt></a>
88 <tt>std::map
</tt></li>
91 <a href=
"tree.html"><tt>tree
</tt></a>
92 with
<tt>Tag
</tt> =
<a href=
"splay_tree_tag.html"><tt>splay_tree_tag
</tt></a>
93 , and
<tt>Node_Update
</tt> =
<a href=
"null_tree_node_update.html"><tt>null_tree_node_update
</tt></a>
96 </div><div style=
"width: 100%; height: 20px"></div></div>
101 <div id=
"NTL_res_div">
103 <div id=
"NTL_tree_text_lor_find_timing_test">
105 <div id=
"NTL_Native_and_tree-based_locality-of-reference_text_find_timing_test_using__tt_find_455tt_"><div style =
"border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class=
"c1"><a name=
"NTL" id=
"NTL"><img src=
"tree_text_lor_find_timing_test_local.png" alt=
"no image" /></a></h6>NTL: Native and tree-based locality-of-reference text find timing test using
<tt>find
</tt> -
<a href =
"assoc_performance_tests.html#local">local
</a></div><div style =
"width: 100%; height: 20px"></div></div>
110 <h2><a name=
"observations" id=
"observations">Observations
</a></h2>
111 <p>For this setting, an ordered-vector tree (
<a href=
"tree.html"><tt>tree
</tt></a>
112 with
<tt>Tag =
</tt> <a href=
"ov_tree_tag.html"><tt>ov_tree_tag
</tt></a> ), a
113 red-black tree (
<a href=
"tree.html"><tt>tree
</tt></a>
114 with
<tt>Tag =
</tt> <a href=
"splay_tree_tag.html"><tt>rb_tree_tag
</tt></a> ), and the
115 native red-black tree all share approximately the same
117 <p>A splay tree (
<a href=
"tree.html"><tt>tree
</tt></a>
118 with
<tt>Tag =
</tt> <a href=
"splay_tree_tag.html"><tt>splay_tree_tag
</tt></a> ) does
119 much better, since each (successful) find
"bubbles" the
120 corresponding node to the root of the tree.
</p>
121 <p><a href=
"assoc_performance_tests.html#tree_like_based_types">Observations::Tree-Like-Based
122 Container Types
</a> summarizes some observations on tree-based
123 and trie-based containers.
</p>