OLD | NEW |
| (Empty) |
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), se
e 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*/tr
unk/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::Associat
ive | |
31 Containers::Slightly Different Methods::Methods Related to | |
32 Split and Join</a> and <a href="tree_based_containers.html#add_methods">Desi
gn::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="borde
r-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a n
ame="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="ass
oc_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the l
egends 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="borde
r-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a n
ame="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="as
soc_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 = "bor
der-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 i
mage" /></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_trait
s.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> | |
OLD | NEW |