1 <html><head><meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"><title>Testing
</title><meta name=
"generator" content=
"DocBook XSL-NS Stylesheets V1.76.1"><meta name=
"keywords" content=
"
21 "><meta name=
"keywords" content=
"
25 "><meta name=
"keywords" content=
"
31 "><link rel=
"home" href=
"../index.html" title=
"The GNU C++ Library"><link rel=
"up" href=
"policy_data_structures.html" title=
"Chapter 22. Policy-Based Data Structures"><link rel=
"prev" href=
"policy_data_structures_design.html" title=
"Design"><link rel=
"next" href=
"policy_data_structures_biblio.html" title=
"Acknowledgments"></head><body bgcolor=
"white" text=
"black" link=
"#0000FF" vlink=
"#840084" alink=
"#0000FF"><div class=
"navheader"><table width=
"100%" summary=
"Navigation header"><tr><th colspan=
"3" align=
"center">Testing
</th></tr><tr><td width=
"20%" align=
"left"><a accesskey=
"p" href=
"policy_data_structures_design.html">Prev
</a> </td><th width=
"60%" align=
"center">Chapter
22. Policy-Based Data Structures
</th><td width=
"20%" align=
"right"> <a accesskey=
"n" href=
"policy_data_structures_biblio.html">Next
</a></td></tr></table><hr></div><div class=
"section" title=
"Testing"><div class=
"titlepage"><div><div><h2 class=
"title" style=
"clear: both"><a name=
"pbds.test"></a>Testing
</h2></div></div></div><div class=
"section" title=
"Regression"><div class=
"titlepage"><div><div><h3 class=
"title"><a name=
"pbds.test.regression"></a>Regression
</h3></div></div></div><p>The library contains a single comprehensive regression test.
32 For a given container type in this library, the test creates
33 an object of the container type and an object of the
34 corresponding standard type (e.g.,
<code class=
"classname">std::set
</code>). It
35 then performs a random sequence of methods with random
36 arguments (e.g., inserts, erases, and so forth) on both
37 objects. At each operation, the test checks the return value of
38 the method, and optionally both compares this library's
39 object with the standard's object as well as performing other
40 consistency checks on this library's object (e.g.,
41 order preservation, when applicable, or node invariants, when
42 applicable).
</p><p>Additionally, the test integrally checks exception safety
43 and resource leaks. This is done as follows. A special
44 allocator type, written for the purpose of the test, both
45 randomly throws an exceptions when allocations are performed,
46 and tracks allocations and de-allocations. The exceptions thrown
47 at allocations simulate memory-allocation failures; the
48 tracking mechanism checks for memory-related bugs (e.g.,
49 resource leaks and multiple de-allocations). Both
50 this library's containers and the containers' value-types are
51 configured to use this allocator.
</p><p>For granularity, the test is split into the
52 several sources, each checking only some containers.
</p><p>For more details, consult the files in
53 <code class=
"filename">testsuite/ext/pb_ds/regression
</code>.
</p></div><div class=
"section" title=
"Performance"><div class=
"titlepage"><div><div><h3 class=
"title"><a name=
"pbds.test.performance"></a>Performance
</h3></div></div></div><div class=
"section" title=
"Hash-Based"><div class=
"titlepage"><div><div><h4 class=
"title"><a name=
"performance.hash"></a>Hash-Based
</h4></div></div></div><p></p><div class=
"section" title=
"Text find"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.hash.text_find"></a>
54 Text
<code class=
"function">find
</code>
55 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.text_find.info"></a>
57 </h6></div></div></div><p>
58 This test inserts a number of values with keys from an
59 arbitrary text (
<a class=
"xref" href=
"policy_data_structures.html#biblio.wickland96thirty" title=
"Thirty Years Among the Dead">[biblio.wickland96thirty]
</a>) into a container,
60 then performs a series of finds using
61 <code class=
"function">find
</code> . It measures the average
62 time for
<code class=
"function">find
</code> as a function of
63 the number of values inserted.
</p><p>
64 It uses the test file:
65 <code class=
"filename">
66 performance/ext/pb_ds/text_find_timing_test.cc
69 And uses the data file:
70 <code class=
"filename">
71 filethirty_years_among_the_dead_preproc.txt
73 </p><p>The test checks the effect of different range-hashing
74 functions, trigger policies, and cache-hashing policies.
75 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.text_find.results"></a>
77 </h6></div></div></div><p>The graphic below show the results for the native
78 and collision-chaining hash types the the function
79 applied being a text find timing test using
80 <code class=
"function">find
</code>.
81 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_hash_text_find.png" align=
"middle"></div></div><p>
82 The abbreviated names in the legend of the graphic above are
83 instantiated with the types in the following table.
84 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
86 </td></tr><tr><td align=
"left">
87 <code class=
"classname">std::tr1::unordered_map
</code>
88 </td><td align=
"left">
89 <code class=
"classname">cache_hash_code
</code>
90 </td><td align=
"left">
91 <code class=
"constant">false
</code>
92 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
93 cc_hash_mod_prime_1div1_nsth_map
94 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
95 <code class=
"classname">cc_hash_table
</code>
96 </td><td align=
"left">
97 <code class=
"classname">Comb_Hash_Fn
</code>
98 </td><td align=
"left">
99 <code class=
"classname">direct_mod_range_hashing
</code>
100 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
101 <code class=
"classname">Resize_Policy
</code>
102 </td><td rowspan=
"2" align=
"left" valign=
"top">
103 <code class=
"classname">hash_standard_resize_policy
</code>
104 </td><td align=
"left">
105 <code class=
"classname">Size_Policy
</code>
106 </td><td align=
"left">
107 <code class=
"classname">hash_prime_size_policy
</code>
108 </td></tr><tr><td align=
"left" valign=
"top">
109 <code class=
"classname">Trigger_Policy
</code>
110 </td><td align=
"left">
111 <code class=
"classname">hash_load_check_resize_trigger
</code> with
112 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
113 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
114 cc_hash_mask_exp_1div2_sth_map
115 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
116 <code class=
"classname">
119 </td><td align=
"left">
120 <code class=
"classname">Comb_Hash_Fn
</code>
121 </td><td align=
"left">
122 <code class=
"classname">direct_mask_range_hashing
</code>
123 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
124 <code class=
"classname">Resize_Policy
</code>
125 </td><td rowspan=
"2" align=
"left" valign=
"top">
126 <code class=
"classname">hash_standard_resize_policy
</code>
127 </td><td align=
"left">
128 <code class=
"classname">Size_Policy
</code>
129 </td><td align=
"left">
130 <code class=
"classname">hash_exponential_size_policy
</code>
131 </td></tr><tr><td align=
"left" valign=
"top">
132 <code class=
"classname">Trigger_Policy
</code>
133 </td><td align=
"left">
134 <code class=
"classname">hash_load_check_resize_trigger
</code> with
135 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
136 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
137 cc_hash_mask_exp_1div1_nsth_map
138 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
139 <code class=
"classname">cc_hash_table
</code>
140 </td><td align=
"left">
141 <code class=
"classname">Comb_Hash_Fn
</code>
142 </td><td align=
"left">
143 <code class=
"classname">direct_mask_range_hashing
</code>
144 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
145 <code class=
"classname">Resize_Policy
</code>
146 </td><td rowspan=
"2" align=
"left" valign=
"top">
147 <code class=
"classname">hash_standard_resize_policy
</code>
148 </td><td align=
"left">
149 <code class=
"classname">Size_Policy
</code>
150 </td><td align=
"left">
151 <code class=
"classname">hash_exponential_size_policy
</code>
152 </td></tr><tr><td align=
"left" valign=
"top">
153 <code class=
"classname">Trigger_Policy
</code>
154 </td><td align=
"left">
155 <code class=
"classname">hash_load_check_resize_trigger
</code> with
156 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
157 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
158 cc_hash_mask_exp_1div2_nsth_map
159 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
160 <code class=
"classname">cc_hash_table
</code>
161 </td><td align=
"left">
162 <code class=
"classname">Comb_Hash_Fn
</code>
163 </td><td align=
"left">
164 <code class=
"classname">direct_mask_range_hashing
</code>
165 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
166 <code class=
"classname">Resize_Policy
</code>
167 </td><td rowspan=
"2" align=
"left" valign=
"top">
168 <code class=
"classname">hash_standard_resize_policy
</code>
169 </td><td align=
"left">
170 <code class=
"classname">Size_Policy
</code>
171 </td><td align=
"left">
172 <code class=
"classname">hash_exponential_size_policy
</code>
173 </td></tr><tr><td align=
"left" valign=
"top">
174 <code class=
"classname">Trigger_Policy
</code>
175 </td><td align=
"left">
176 <code class=
"classname">hash_load_check_resize_trigger
</code> with
177 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
178 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.text_find.observations"></a>
180 </h6></div></div></div><p>In this setting, the range-hashing scheme affects performance
181 more than other policies. As the results show, containers using
182 mod-based range-hashing (including the native hash-based container,
183 which is currently hard-wired to this scheme) have lower performance
184 than those using mask-based range-hashing. A modulo-based
185 range-hashing scheme's main benefit is that it takes into account
186 all hash-value bits. Standard string hash-functions are designed to
187 create hash values that are nearly-uniform as is (
<a class=
"xref" href=
"policy_data_structures.html#biblio.knuth98sorting" title=
"The Art of Computer Programming - Sorting and Searching">[biblio.knuth98sorting]
</a>).
</p><p>Trigger policies, i.e. the load-checks constants, affect
188 performance to a lesser extent.
</p><p>Perhaps surprisingly, storing the hash value alongside each
189 entry affects performance only marginally, at least in this
190 library's implementation. (Unfortunately, it was not possible to run
191 the tests with
<code class=
"classname">std::tr1::unordered_map
</code> 's
192 <code class=
"classname">cache_hash_code = true
</code> , as it appeared to
193 malfuntion.)
</p></div></div><div class=
"section" title=
"Integer find"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.hash.int_find"></a>
194 Integer
<code class=
"function">find
</code>
195 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_find.info"></a>
197 </h6></div></div></div><p>This test inserts a number of values with uniform
198 integer keys into a container, then performs a series of finds
199 using
<code class=
"function">find
</code>. It measures the average time
200 for
<code class=
"function">find
</code> as a function of the number of values
202 It uses the test file:
203 <code class=
"filename">
204 performance/ext/pb_ds/random_int_find_timing.cc
206 </p><p>The test checks the effect of different underlying
208 range-hashing functions, and trigger policies.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_find.results"></a>
210 </h6></div></div></div><p>
211 There are two sets of results for this type, one for
212 collision-chaining hashes, and one for general-probe hashes.
213 </p><p>The first graphic below shows the results for the native and
214 collision-chaining hash types. The function applied being a random
215 integer timing test using
<code class=
"function">find
</code>.
216 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_cc_hash_int_find.png" align=
"middle"></div></div><p>
217 The abbreviated names in the legend of the graphic above are
218 instantiated with the types in the following table.
219 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
221 </td></tr><tr><td align=
"left">
222 <code class=
"classname">std::tr1::unordered_map
</code>
223 </td><td align=
"left">
224 <code class=
"classname">cache_hash_code
</code>
225 </td><td align=
"left">
226 <code class=
"constant">false
</code>
227 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
228 cc_hash_mod_prime_1div1_nsth_map
229 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
230 <code class=
"classname">cc_hash_table
</code>
231 </td><td align=
"left">
232 <code class=
"classname">Comb_Hash_Fn
</code>
233 </td><td align=
"left">
234 <code class=
"classname">direct_mod_range_hashing
</code>
235 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
236 <code class=
"classname">Resize_Policy
</code>
237 </td><td rowspan=
"2" align=
"left" valign=
"top">
238 <code class=
"classname">hash_standard_resize_policy
</code>
239 </td><td align=
"left">
240 <code class=
"classname">Size_Policy
</code>
241 </td><td align=
"left">
242 <code class=
"classname">hash_prime_size_policy
</code>
243 </td></tr><tr><td align=
"left" valign=
"top">
244 <code class=
"classname">Trigger_Policy
</code>
245 </td><td align=
"left">
246 <code class=
"classname">hash_load_check_resize_trigger
</code> with
247 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
248 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
249 cc_hash_mod_prime_1div2_nsth_map
250 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
251 <code class=
"classname">
254 </td><td align=
"left">
255 <code class=
"classname">Comb_Hash_Fn
</code>
256 </td><td align=
"left">
257 <code class=
"classname">direct_mod_range_hashing
</code>
258 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
259 <code class=
"classname">Resize_Policy
</code>
260 </td><td rowspan=
"2" align=
"left" valign=
"top">
261 <code class=
"classname">hash_standard_resize_policy
</code>
262 </td><td align=
"left">
263 <code class=
"classname">Size_Policy
</code>
264 </td><td align=
"left">
265 <code class=
"classname">hash_prime_size_policy
</code>
266 </td></tr><tr><td align=
"left" valign=
"top">
267 <code class=
"classname">Trigger_Policy
</code>
268 </td><td align=
"left">
269 <code class=
"classname">hash_load_check_resize_trigger
</code> with
270 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
271 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
272 cc_hash_mask_exp_1div1_nsth_map
273 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
274 <code class=
"classname">cc_hash_table
</code>
275 </td><td align=
"left">
276 <code class=
"classname">Comb_Hash_Fn
</code>
277 </td><td align=
"left">
278 <code class=
"classname">direct_mask_range_hashing
</code>
279 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
280 <code class=
"classname">Resize_Policy
</code>
281 </td><td rowspan=
"2" align=
"left" valign=
"top">
282 <code class=
"classname">hash_standard_resize_policy
</code>
283 </td><td align=
"left">
284 <code class=
"classname">Size_Policy
</code>
285 </td><td align=
"left">
286 <code class=
"classname">hash_exponential_size_policy
</code>
287 </td></tr><tr><td align=
"left" valign=
"top">
288 <code class=
"classname">Trigger_Policy
</code>
289 </td><td align=
"left">
290 <code class=
"classname">hash_load_check_resize_trigger
</code> with
291 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
292 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
293 cc_hash_mask_exp_1div2_nsth_map
294 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
295 <code class=
"classname">cc_hash_table
</code>
296 </td><td align=
"left">
297 <code class=
"classname">Comb_Hash_Fn
</code>
298 </td><td align=
"left">
299 <code class=
"classname">direct_mask_range_hashing
</code>
300 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
301 <code class=
"classname">Resize_Policy
</code>
302 </td><td rowspan=
"2" align=
"left" valign=
"top">
303 <code class=
"classname">hash_standard_resize_policy
</code>
304 </td><td align=
"left">
305 <code class=
"classname">Size_Policy
</code>
306 </td><td align=
"left">
307 <code class=
"classname">hash_exponential_size_policy
</code>
308 </td></tr><tr><td align=
"left" valign=
"top">
309 <code class=
"classname">Trigger_Policy
</code>
310 </td><td align=
"left">
311 <code class=
"classname">hash_load_check_resize_trigger
</code> with
312 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
313 </td></tr></tbody></table></div><p>
315 </p><p>And the second graphic shows the results for the native and
316 general-probe hash types. The function applied being a random
317 integer timing test using
<code class=
"function">find
</code>.
318 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_gp_hash_int_find.png" align=
"middle"></div></div><p>
319 The abbreviated names in the legend of the graphic above are
320 instantiated with the types in the following table.
321 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
323 </td></tr><tr><td align=
"left">
324 <code class=
"classname">std::tr1::unordered_map
</code>
325 </td><td align=
"left">
326 <code class=
"classname">cache_hash_code
</code>
327 </td><td align=
"left">
328 <code class=
"constant">false
</code>
329 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
330 gp_hash_mod_quadp_prime_1div2_nsth_map
331 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
332 <code class=
"classname">gp_hash_table
</code>
333 </td><td align=
"left">
334 <code class=
"classname">Comb_Hash_Fn
</code>
335 </td><td align=
"left">
336 <code class=
"classname">direct_mod_range_hashing
</code>
337 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
338 <code class=
"classname">Probe_Fn
</code>
339 </td><td align=
"left">
340 <code class=
"classname">quadratic_probe_fn
</code>
341 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
342 <code class=
"classname">Resize_Policy
</code>
343 </td><td rowspan=
"2" align=
"left" valign=
"top">
344 <code class=
"classname">hash_standard_resize_policy
</code>
345 </td><td align=
"left">
346 <code class=
"classname">Size_Policy
</code>
347 </td><td align=
"left">
348 <code class=
"classname">hash_prime_size_policy
</code>
349 </td></tr><tr><td align=
"left" valign=
"top">
350 <code class=
"classname">Trigger_Policy
</code>
351 </td><td align=
"left">
352 <code class=
"classname">hash_load_check_resize_trigger
</code> with
353 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
354 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
355 gp_hash_mask_linp_exp_1div2_nsth_map
356 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
357 <code class=
"classname">
360 </td><td align=
"left">
361 <code class=
"classname">Comb_Hash_Fn
</code>
362 </td><td align=
"left">
363 <code class=
"classname">direct_mask_range_hashing
</code>
364 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
365 <code class=
"classname">Probe_Fn
</code>
366 </td><td align=
"left">
367 <code class=
"classname">linear_probe_fn
</code>
368 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
369 <code class=
"classname">Resize_Policy
</code>
370 </td><td rowspan=
"2" align=
"left" valign=
"top">
371 <code class=
"classname">hash_standard_resize_policy
</code>
372 </td><td align=
"left">
373 <code class=
"classname">Size_Policy
</code>
374 </td><td align=
"left">
375 <code class=
"classname">hash_exponential_size_policy
</code>
376 </td></tr><tr><td align=
"left" valign=
"top">
377 <code class=
"classname">Trigger_Policy
</code>
378 </td><td align=
"left">
379 <code class=
"classname">hash_load_check_resize_trigger
</code> with
380 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
381 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_find.observations"></a>
383 </h6></div></div></div><p>In this setting, the choice of underlying hash-table affects
384 performance most, then the range-hashing scheme and, only finally,
385 other policies.
</p><p>When comparing probing and chaining containers, it is
386 apparent that the probing containers are less efficient than the
387 collision-chaining containers (
388 <code class=
"classname">std::tr1::unordered_map
</code> uses
389 collision-chaining) in this case.
</p><p>Hash-Based Integer Subscript Insert Timing Test shows
390 a different case, where the situation is reversed;
391 </p><p>Within each type of hash-table, the range-hashing scheme
392 affects performance more than other policies; Hash-Based Text
393 <code class=
"function">find
</code> Find Timing Test also shows this. In the
394 above graphics should be noted that
395 <code class=
"classname">std::tr1::unordered_map
</code> are hard-wired
396 currently to mod-based schemes.
397 </p></div></div><div class=
"section" title=
"Integer Subscript find"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.hash.int_subscript_find"></a>
398 Integer Subscript
<code class=
"function">find
</code>
399 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_subscript_find.info"></a>
401 </h6></div></div></div><p>This test inserts a number of values with uniform
402 integer keys into a container, then performs a series of finds
403 using
<code class=
"function">operator[]
</code>. It measures the average time
404 for
<code class=
"function">operator[]
</code> as a function of the number of
405 values inserted.
</p><p>
406 It uses the test file:
407 <code class=
"filename">
408 performance/ext/pb_ds/random_int_subscript_find_timing.cc
410 </p><p>The test checks the effect of different underlying
411 hash-tables, range-hashing functions, and trigger policies.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_subscript_find.results"></a>
413 </h6></div></div></div><p>
414 There are two sets of results for this type, one for
415 collision-chaining hashes, and one for general-probe hashes.
416 </p><p>The first graphic below shows the results for the native
417 and collision-chaining hash types, using as the function
418 applied an integer subscript timing test with
419 <code class=
"function">find
</code>.
420 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_cc_hash_int_subscript_find.png" align=
"middle"></div></div><p>
421 The abbreviated names in the legend of the graphic above are
422 instantiated with the types in the following table.
423 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
425 </td></tr><tr><td align=
"left">
426 <code class=
"classname">std::tr1::unordered_map
</code>
427 </td><td align=
"left">
428 <code class=
"classname">cache_hash_code
</code>
429 </td><td align=
"left">
430 <code class=
"constant">false
</code>
431 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
432 cc_hash_mod_prime_1div1_nsth_map
433 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
434 <code class=
"classname">cc_hash_table
</code>
435 </td><td align=
"left">
436 <code class=
"classname">Comb_Hash_Fn
</code>
437 </td><td align=
"left">
438 <code class=
"classname">direct_mod_range_hashing
</code>
439 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
440 <code class=
"classname">Resize_Policy
</code>
441 </td><td rowspan=
"2" align=
"left" valign=
"top">
442 <code class=
"classname">hash_standard_resize_policy
</code>
443 </td><td align=
"left">
444 <code class=
"classname">Size_Policy
</code>
445 </td><td align=
"left">
446 <code class=
"classname">hash_prime_size_policy
</code>
447 </td></tr><tr><td align=
"left" valign=
"top">
448 <code class=
"classname">Trigger_Policy
</code>
449 </td><td align=
"left">
450 <code class=
"classname">hash_load_check_resize_trigger
</code> with
451 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
452 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
453 cc_hash_mod_prime_1div2_nsth_map
454 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
455 <code class=
"classname">cc_hash_table
</code>
456 </td><td align=
"left">
457 <code class=
"classname">Comb_Hash_Fn
</code>
458 </td><td align=
"left">
459 <code class=
"classname">direct_mod_range_hashing
</code>
460 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
461 <code class=
"classname">Resize_Policy
</code>
462 </td><td rowspan=
"2" align=
"left" valign=
"top">
463 <code class=
"classname">hash_standard_resize_policy
</code>
464 </td><td align=
"left">
465 <code class=
"classname">Size_Policy
</code>
466 </td><td align=
"left">
467 <code class=
"classname">hash_prime_size_policy
</code>
468 </td></tr><tr><td align=
"left" valign=
"top">
469 <code class=
"classname">Trigger_Policy
</code>
470 </td><td align=
"left">
471 <code class=
"classname">hash_load_check_resize_trigger
</code> with
472 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
473 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
474 cc_hash_mask_exp_1div1_nsth_map
475 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
476 <code class=
"classname">cc_hash_table
</code>
477 </td><td align=
"left">
478 <code class=
"classname">Comb_Hash_Fn
</code>
479 </td><td align=
"left">
480 <code class=
"classname">direct_mask_range_hashing
</code>
481 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
482 <code class=
"classname">Resize_Policy
</code>
483 </td><td rowspan=
"2" align=
"left" valign=
"top">
484 <code class=
"classname">hash_standard_resize_policy
</code>
485 </td><td align=
"left">
486 <code class=
"classname">Size_Policy
</code>
487 </td><td align=
"left">
488 <code class=
"classname">hash_exponential_size_policy
</code>
489 </td></tr><tr><td align=
"left" valign=
"top">
490 <code class=
"classname">Trigger_Policy
</code>
491 </td><td align=
"left">
492 <code class=
"classname">hash_load_check_resize_trigger
</code> with
493 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
494 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
495 cc_hash_mask_exp_1div2_nsth_map
496 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
497 <code class=
"classname">cc_hash_table
</code>
498 </td><td align=
"left">
499 <code class=
"classname">Comb_Hash_Fn
</code>
500 </td><td align=
"left">
501 <code class=
"classname">direct_mask_range_hashing
</code>
502 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
503 <code class=
"classname">Resize_Policy
</code>
504 </td><td rowspan=
"2" align=
"left" valign=
"top">
505 <code class=
"classname">hash_standard_resize_policy
</code>
506 </td><td align=
"left">
507 <code class=
"classname">Size_Policy
</code>
508 </td><td align=
"left">
509 <code class=
"classname">hash_exponential_size_policy
</code>
510 </td></tr><tr><td align=
"left" valign=
"top">
511 <code class=
"classname">Trigger_Policy
</code>
512 </td><td align=
"left">
513 <code class=
"classname">hash_load_check_resize_trigger
</code> with
514 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
515 </td></tr></tbody></table></div><p>
517 </p><p>And the second graphic shows the results for the native and
518 general-probe hash types. The function applied being a random
519 integer timing test using
<code class=
"function">find
</code>.
520 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_gp_hash_int_subscript_find.png" align=
"middle"></div></div><p>
521 The abbreviated names in the legend of the graphic above are
522 instantiated with the types in the following table.
523 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
525 </td></tr><tr><td align=
"left">
526 <code class=
"classname">std::tr1::unordered_map
</code>
527 </td><td align=
"left">
528 <code class=
"classname">cache_hash_code
</code>
529 </td><td align=
"left">
530 <code class=
"constant">false
</code>
531 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
532 gp_hash_mod_quadp_prime_1div2_nsth_map
533 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
534 <code class=
"classname">gp_hash_table
</code>
535 </td><td align=
"left">
536 <code class=
"classname">Comb_Hash_Fn
</code>
537 </td><td align=
"left">
538 <code class=
"classname">direct_mod_range_hashing
</code>
539 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
540 <code class=
"classname">Probe_Fn
</code>
541 </td><td align=
"left">
542 <code class=
"classname">quadratic_probe_fn
</code>
543 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
544 <code class=
"classname">Resize_Policy
</code>
545 </td><td rowspan=
"2" align=
"left" valign=
"top">
546 <code class=
"classname">hash_standard_resize_policy
</code>
547 </td><td align=
"left">
548 <code class=
"classname">Size_Policy
</code>
549 </td><td align=
"left">
550 <code class=
"classname">hash_prime_size_policy
</code>
551 </td></tr><tr><td align=
"left" valign=
"top">
552 <code class=
"classname">Trigger_Policy
</code>
553 </td><td align=
"left">
554 <code class=
"classname">hash_load_check_resize_trigger
</code> with
555 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
556 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
557 gp_hash_mask_linp_exp_1div2_nsth_map
558 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
559 <code class=
"classname">
562 </td><td align=
"left">
563 <code class=
"classname">Comb_Hash_Fn
</code>
564 </td><td align=
"left">
565 <code class=
"classname">direct_mask_range_hashing
</code>
566 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
567 <code class=
"classname">Probe_Fn
</code>
568 </td><td align=
"left">
569 <code class=
"classname">linear_probe_fn
</code>
570 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
571 <code class=
"classname">Resize_Policy
</code>
572 </td><td rowspan=
"2" align=
"left" valign=
"top">
573 <code class=
"classname">hash_standard_resize_policy
</code>
574 </td><td align=
"left">
575 <code class=
"classname">Size_Policy
</code>
576 </td><td align=
"left">
577 <code class=
"classname">hash_exponential_size_policy
</code>
578 </td></tr><tr><td align=
"left" valign=
"top">
579 <code class=
"classname">Trigger_Policy
</code>
580 </td><td align=
"left">
581 <code class=
"classname">hash_load_check_resize_trigger
</code> with
582 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
583 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_subscript_find.observations"></a>
585 </h6></div></div></div><p>This test shows similar results to Hash-Based
586 Integer
<code class=
"classname">find
</code> Find Timing test.
</p></div></div><div class=
"section" title=
"Integer Subscript insert"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.hash.int_subscript_insert"></a>
587 Integer Subscript
<code class=
"function">insert
</code>
588 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_subscript_insert.info"></a>
590 </h6></div></div></div><p>This test inserts a number of values with uniform i.i.d.
591 integer keys into a container, using
592 <code class=
"function">operator[]
</code>. It measures the average time for
593 <code class=
"function">operator[]
</code> as a function of the number of
594 values inserted.
</p><p>
595 It uses the test file:
596 <code class=
"filename">
597 performance/ext/pb_ds/random_int_subscript_insert_timing.cc
599 </p><p>The test checks the effect of different underlying
600 hash-tables.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_subscript_insert.results"></a>
602 </h6></div></div></div><p>
603 There are two sets of results for this type, one for
604 collision-chaining hashes, and one for general-probe hashes.
605 </p><p>The first graphic below shows the results for the native
606 and collision-chaining hash types, using as the function
607 applied an integer subscript timing test with
608 <code class=
"function">insert
</code>.
609 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_cc_hash_int_subscript_insert.png" align=
"middle"></div></div><p>
610 The abbreviated names in the legend of the graphic above are
611 instantiated with the types in the following table.
612 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
614 </td></tr><tr><td align=
"left">
615 <code class=
"classname">std::tr1::unordered_map
</code>
616 </td><td align=
"left">
617 <code class=
"classname">cache_hash_code
</code>
618 </td><td align=
"left">
619 <code class=
"constant">false
</code>
620 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
621 cc_hash_mod_prime_1div1_nsth_map
622 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
623 <code class=
"classname">cc_hash_table
</code>
624 </td><td align=
"left">
625 <code class=
"classname">Comb_Hash_Fn
</code>
626 </td><td align=
"left">
627 <code class=
"classname">direct_mod_range_hashing
</code>
628 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
629 <code class=
"classname">Resize_Policy
</code>
630 </td><td rowspan=
"2" align=
"left" valign=
"top">
631 <code class=
"classname">hash_standard_resize_policy
</code>
632 </td><td align=
"left">
633 <code class=
"classname">Size_Policy
</code>
634 </td><td align=
"left">
635 <code class=
"classname">hash_prime_size_policy
</code>
636 </td></tr><tr><td align=
"left" valign=
"top">
637 <code class=
"classname">Trigger_Policy
</code>
638 </td><td align=
"left">
639 <code class=
"classname">hash_load_check_resize_trigger
</code> with
640 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
641 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
642 cc_hash_mod_prime_1div2_nsth_map
643 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
644 <code class=
"classname">cc_hash_table
</code>
645 </td><td align=
"left">
646 <code class=
"classname">Comb_Hash_Fn
</code>
647 </td><td align=
"left">
648 <code class=
"classname">direct_mod_range_hashing
</code>
649 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
650 <code class=
"classname">Resize_Policy
</code>
651 </td><td rowspan=
"2" align=
"left" valign=
"top">
652 <code class=
"classname">hash_standard_resize_policy
</code>
653 </td><td align=
"left">
654 <code class=
"classname">Size_Policy
</code>
655 </td><td align=
"left">
656 <code class=
"classname">hash_prime_size_policy
</code>
657 </td></tr><tr><td align=
"left" valign=
"top">
658 <code class=
"classname">Trigger_Policy
</code>
659 </td><td align=
"left">
660 <code class=
"classname">hash_load_check_resize_trigger
</code> with
661 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
662 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
663 cc_hash_mask_exp_1div1_nsth_map
664 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
665 <code class=
"classname">cc_hash_table
</code>
666 </td><td align=
"left">
667 <code class=
"classname">Comb_Hash_Fn
</code>
668 </td><td align=
"left">
669 <code class=
"classname">direct_mask_range_hashing
</code>
670 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
671 <code class=
"classname">Resize_Policy
</code>
672 </td><td rowspan=
"2" align=
"left" valign=
"top">
673 <code class=
"classname">hash_standard_resize_policy
</code>
674 </td><td align=
"left">
675 <code class=
"classname">Size_Policy
</code>
676 </td><td align=
"left">
677 <code class=
"classname">hash_exponential_size_policy
</code>
678 </td></tr><tr><td align=
"left" valign=
"top">
679 <code class=
"classname">Trigger_Policy
</code>
680 </td><td align=
"left">
681 <code class=
"classname">hash_load_check_resize_trigger
</code> with
682 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
683 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
684 cc_hash_mask_exp_1div2_nsth_map
685 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
686 <code class=
"classname">cc_hash_table
</code>
687 </td><td align=
"left">
688 <code class=
"classname">Comb_Hash_Fn
</code>
689 </td><td align=
"left">
690 <code class=
"classname">direct_mask_range_hashing
</code>
691 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
692 <code class=
"classname">Resize_Policy
</code>
693 </td><td rowspan=
"2" align=
"left" valign=
"top">
694 <code class=
"classname">hash_standard_resize_policy
</code>
695 </td><td align=
"left">
696 <code class=
"classname">Size_Policy
</code>
697 </td><td align=
"left">
698 <code class=
"classname">hash_exponential_size_policy
</code>
699 </td></tr><tr><td align=
"left" valign=
"top">
700 <code class=
"classname">Trigger_Policy
</code>
701 </td><td align=
"left">
702 <code class=
"classname">hash_load_check_resize_trigger
</code> with
703 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
704 </td></tr></tbody></table></div><p>
706 </p><p>And the second graphic shows the results for the native and
707 general-probe hash types. The function applied being a random
708 integer timing test using
<code class=
"function">find
</code>.
709 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_gp_hash_int_subscript_insert.png" align=
"middle"></div></div><p>
710 The abbreviated names in the legend of the graphic above are
711 instantiated with the types in the following table.
712 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
714 </td></tr><tr><td align=
"left">
715 <code class=
"classname">std::tr1::unordered_map
</code>
716 </td><td align=
"left">
717 <code class=
"classname">cache_hash_code
</code>
718 </td><td align=
"left">
719 <code class=
"constant">false
</code>
720 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
721 gp_hash_mod_quadp_prime_1div2_nsth_map
722 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
723 <code class=
"classname">gp_hash_table
</code>
724 </td><td align=
"left">
725 <code class=
"classname">Comb_Hash_Fn
</code>
726 </td><td align=
"left">
727 <code class=
"classname">direct_mod_range_hashing
</code>
728 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
729 <code class=
"classname">Probe_Fn
</code>
730 </td><td align=
"left">
731 <code class=
"classname">quadratic_probe_fn
</code>
732 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
733 <code class=
"classname">Resize_Policy
</code>
734 </td><td rowspan=
"2" align=
"left" valign=
"top">
735 <code class=
"classname">hash_standard_resize_policy
</code>
736 </td><td align=
"left">
737 <code class=
"classname">Size_Policy
</code>
738 </td><td align=
"left">
739 <code class=
"classname">hash_prime_size_policy
</code>
740 </td></tr><tr><td align=
"left" valign=
"top">
741 <code class=
"classname">Trigger_Policy
</code>
742 </td><td align=
"left">
743 <code class=
"classname">hash_load_check_resize_trigger
</code> with
744 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
745 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
746 gp_hash_mask_linp_exp_1div2_nsth_map
747 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
748 <code class=
"classname">
751 </td><td align=
"left">
752 <code class=
"classname">Comb_Hash_Fn
</code>
753 </td><td align=
"left">
754 <code class=
"classname">direct_mask_range_hashing
</code>
755 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
756 <code class=
"classname">Probe_Fn
</code>
757 </td><td align=
"left">
758 <code class=
"classname">linear_probe_fn
</code>
759 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
760 <code class=
"classname">Resize_Policy
</code>
761 </td><td rowspan=
"2" align=
"left" valign=
"top">
762 <code class=
"classname">hash_standard_resize_policy
</code>
763 </td><td align=
"left">
764 <code class=
"classname">Size_Policy
</code>
765 </td><td align=
"left">
766 <code class=
"classname">hash_exponential_size_policy
</code>
767 </td></tr><tr><td align=
"left" valign=
"top">
768 <code class=
"classname">Trigger_Policy
</code>
769 </td><td align=
"left">
770 <code class=
"classname">hash_load_check_resize_trigger
</code> with
771 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
772 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.int_subscript_insert.observations"></a>
774 </h6></div></div></div><p>In this setting, as in Hash-Based Text
775 <code class=
"function">find
</code> Find Timing test and Hash-Based
776 Integer
<code class=
"function">find
</code> Find Timing test , the choice
777 of underlying hash-table underlying hash-table affects performance
778 most, then the range-hashing scheme, and
779 finally any other policies.
</p><p>There are some differences, however:
</p><div class=
"orderedlist"><ol class=
"orderedlist" type=
"1"><li class=
"listitem"><p>In this setting, probing tables function sometimes more
780 efficiently than collision-chaining tables.
781 This is explained shortly.
</p></li><li class=
"listitem"><p>The performance graphs have a
"saw-tooth" shape. The
782 average insert time rises and falls. As values are inserted
783 into the container, the load factor grows larger. Eventually,
784 a resize occurs. The reallocations and rehashing are
785 relatively expensive. After this, the load factor is smaller
786 than before.
</p></li></ol></div><p>Collision-chaining containers use indirection for greater
787 flexibility; probing containers store values contiguously, in
788 an array (see Figure Motivation::Different
789 underlying data structures A and B, respectively). It
790 follows that for simple data types, probing containers access
791 their allocator less frequently than collision-chaining
792 containers, (although they still have less efficient probing
793 sequences). This explains why some probing containers fare
794 better than collision-chaining containers in this case.
</p><p>
795 Within each type of hash-table, the range-hashing scheme affects
796 performance more than other policies. This is similar to the
797 situation in Hash-Based Text
798 <code class=
"function">find
</code> Find Timing Test and Hash-Based
799 Integer
<code class=
"function">find
</code> Find Timing Test.
800 Unsurprisingly, however, containers with lower α
<sub>max
</sub> perform worse in this case,
801 since more re-hashes are performed.
</p></div></div><div class=
"section" title=
"Integer find with Skewed-Distribution"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.hash.zlob_int_find"></a>
802 Integer
<code class=
"function">find
</code> with Skewed-Distribution
803 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.zlob_int_find.info"></a>
805 </h6></div></div></div><p>This test inserts a number of values with a markedly
806 non-uniform integer keys into a container, then performs
807 a series of finds using
<code class=
"function">find
</code>. It measures the average
808 time for
<code class=
"function">find
</code> as a function of the number of values in
809 the containers. The keys are generated as follows. First, a
810 uniform integer is created. Then it is then shifted left
8 bits.
</p><p>
811 It uses the test file:
812 <code class=
"filename">
813 performance/ext/pb_ds/hash_zlob_random_int_find_timing.cc
815 </p><p>The test checks the effect of different range-hashing
816 functions and trigger policies.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.zlob_int_find.results"></a>
818 </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
819 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_hash_zlob_int_find.png" align=
"middle"></div></div><p>
820 The abbreviated names in the legend of the graphic above are
821 instantiated with the types in the following table.
822 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
824 </td></tr><tr><td align=
"left">
825 <code class=
"classname">std::tr1::unordered_map
</code>
826 </td><td align=
"left">
827 <code class=
"classname">cache_hash_code
</code>
828 </td><td align=
"left">
829 <code class=
"constant">false
</code>
830 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
831 cc_hash_mod_prime_1div1_nsth_map
832 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
833 <code class=
"classname">cc_hash_table
</code>
834 </td><td align=
"left">
835 <code class=
"classname">Comb_Hash_Fn
</code>
836 </td><td align=
"left">
837 <code class=
"classname">direct_mod_range_hashing
</code>
838 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
839 <code class=
"classname">Resize_Policy
</code>
840 </td><td rowspan=
"2" align=
"left" valign=
"top">
841 <code class=
"classname">hash_standard_resize_policy
</code>
842 </td><td align=
"left">
843 <code class=
"classname">Size_Policy
</code>
844 </td><td align=
"left">
845 <code class=
"classname">hash_prime_size_policy
</code>
846 </td></tr><tr><td align=
"left" valign=
"top">
847 <code class=
"classname">Trigger_Policy
</code>
848 </td><td align=
"left">
849 <code class=
"classname">hash_load_check_resize_trigger
</code> with
850 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
851 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
852 cc_hash_mask_exp_1div1_nsth_map
853 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
854 <code class=
"classname">
857 </td><td align=
"left">
858 <code class=
"classname">Comb_Hash_Fn
</code>
859 </td><td align=
"left">
860 <code class=
"classname">direct_mask_range_hashing
</code>
861 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
862 <code class=
"classname">Resize_Policy
</code>
863 </td><td rowspan=
"2" align=
"left" valign=
"top">
864 <code class=
"classname">hash_standard_resize_policy
</code>
865 </td><td align=
"left">
866 <code class=
"classname">Size_Policy
</code>
867 </td><td align=
"left">
868 <code class=
"classname">hash_exponential_size_policy
</code>
869 </td></tr><tr><td align=
"left" valign=
"top">
870 <code class=
"classname">Trigger_Policy
</code>
871 </td><td align=
"left">
872 <code class=
"classname">hash_load_check_resize_trigger
</code> with
873 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
874 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
875 gp_hash_mod_quadp_prime_1div2_nsth_map
876 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
877 <code class=
"classname">gp_hash_table
</code>
878 </td><td align=
"left">
879 <code class=
"classname">Comb_Hash_Fn
</code>
880 </td><td align=
"left">
881 <code class=
"classname">direct_mod_range_hashing
</code>
882 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
883 <code class=
"classname">Probe_Fn
</code>
884 </td><td align=
"left">
885 <code class=
"classname">quadratic_probe_fn
</code>
886 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
887 <code class=
"classname">Resize_Policy
</code>
888 </td><td rowspan=
"2" align=
"left" valign=
"top">
889 <code class=
"classname">hash_standard_resize_policy
</code>
890 </td><td align=
"left">
891 <code class=
"classname">Size_Policy
</code>
892 </td><td align=
"left">
893 <code class=
"classname">hash_prime_size_policy
</code>
894 </td></tr><tr><td align=
"left" valign=
"top">
895 <code class=
"classname">Trigger_Policy
</code>
896 </td><td align=
"left">
897 <code class=
"classname">hash_load_check_resize_trigger
</code> with
898 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
899 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.zlob_int_find.observations"></a>
901 </h6></div></div></div><p>In this setting, the distribution of keys is so skewed that
902 the underlying hash-table type affects performance marginally.
903 (This is in contrast with Hash-Based Text
904 <code class=
"function">find
</code> Find Timing Test, Hash-Based
905 Integer
<code class=
"function">find
</code> Find Timing Test, Hash-Based
906 Integer Subscript Find Timing Test and Hash-Based
907 Integer Subscript Insert Timing Test.)
</p><p>The range-hashing scheme affects performance dramatically. A
908 mask-based range-hashing scheme effectively maps all values
909 into the same bucket. Access degenerates into a search within
910 an unordered linked-list. In the graphic above, it should be noted that
911 <code class=
"classname">std::tr1::unordered_map
</code> is hard-wired currently to mod-based and mask-based schemes,
912 respectively.
</p><p>When observing the settings of this test, it is apparent
913 that the keys' distribution is far from natural. One might ask
914 if the test is not contrived to show that, in some cases,
915 mod-based range hashing does better than mask-based range
916 hashing. This is, in fact just the case. A
917 more natural case in which mod-based range hashing is better was not encountered.
918 Thus the inescapable conclusion: real-life key distributions are handled better
919 with an appropriate hash function and a mask-based
920 range-hashing function. (
<code class=
"filename">pb_ds/example/hash_shift_mask.cc
</code>
921 shows an example of handling this a-priori known skewed
922 distribution with a mask-based range-hashing function). If hash
923 performance is bad, a χ
<sup>2</sup> test can be used
924 to check how to transform it into a more uniform
925 distribution.
</p><p>For this reason, this library's default range-hashing
926 function is mask-based.
</p></div></div><div class=
"section" title=
"Erase Memory Use"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.hash.erase_mem"></a>
928 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.erase_mem.info"></a>
930 </h6></div></div></div><p>This test inserts a number of uniform integer keys
931 into a container, then erases all keys except one. It measures
932 the final size of the container.
</p><p>
933 It uses the test file:
934 <code class=
"filename">
935 performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc
937 </p><p>The test checks how containers adjust internally as their
938 logical size decreases.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.erase_mem.results"></a>
940 </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
941 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_hash_int_erase_mem.png" align=
"middle"></div></div><p>
942 The abbreviated names in the legend of the graphic above are
943 instantiated with the types in the following table.
944 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
946 </td></tr><tr><td align=
"left">
947 <code class=
"classname">std::tr1::unordered_map
</code>
948 </td><td align=
"left">
949 <code class=
"classname">cache_hash_code
</code>
950 </td><td align=
"left">
951 <code class=
"constant">false
</code>
952 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
953 cc_hash_mod_prime_1div1_nsth_map
954 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
955 <code class=
"classname">cc_hash_table
</code>
956 </td><td align=
"left">
957 <code class=
"classname">Comb_Hash_Fn
</code>
958 </td><td align=
"left">
959 <code class=
"classname">direct_mod_range_hashing
</code>
960 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
961 <code class=
"classname">Resize_Policy
</code>
962 </td><td rowspan=
"2" align=
"left" valign=
"top">
963 <code class=
"classname">hash_standard_resize_policy
</code>
964 </td><td align=
"left">
965 <code class=
"classname">Size_Policy
</code>
966 </td><td align=
"left">
967 <code class=
"classname">hash_prime_size_policy
</code>
968 </td></tr><tr><td align=
"left" valign=
"top">
969 <code class=
"classname">Trigger_Policy
</code>
970 </td><td align=
"left">
971 <code class=
"classname">hash_load_check_resize_trigger
</code> with
972 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
1
973 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
974 cc_hash_mask_exp_1div2_nsth_map
975 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
976 <code class=
"classname">
979 </td><td align=
"left">
980 <code class=
"classname">Comb_Hash_Fn
</code>
981 </td><td align=
"left">
982 <code class=
"classname">direct_mask_range_hashing
</code>
983 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
984 <code class=
"classname">Resize_Policy
</code>
985 </td><td rowspan=
"2" align=
"left" valign=
"top">
986 <code class=
"classname">hash_standard_resize_policy
</code>
987 </td><td align=
"left">
988 <code class=
"classname">Size_Policy
</code>
989 </td><td align=
"left">
990 <code class=
"classname">hash_exponential_size_policy
</code>
991 </td></tr><tr><td align=
"left" valign=
"top">
992 <code class=
"classname">Trigger_Policy
</code>
993 </td><td align=
"left">
994 <code class=
"classname">hash_load_check_resize_trigger
</code> with
995 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
996 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"5" align=
"left">
997 gp_hash_mask_linp_exp_1div2_nsth_set
998 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
999 <code class=
"classname">gp_hash_table
</code>
1000 </td><td align=
"left">
1001 <code class=
"classname">Comb_Hash_Fn
</code>
1002 </td><td align=
"left">
1003 <code class=
"classname">direct_mask_range_hashing
</code>
1004 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
1005 <code class=
"classname">Probe_Fn
</code>
1006 </td><td align=
"left">
1007 <code class=
"classname">linear_probe_fn
</code>
1008 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1009 <code class=
"classname">Resize_Policy
</code>
1010 </td><td rowspan=
"2" align=
"left" valign=
"top">
1011 <code class=
"classname">hash_standard_resize_policy
</code>
1012 </td><td align=
"left">
1013 <code class=
"classname">Size_Policy
</code>
1014 </td><td align=
"left">
1015 <code class=
"classname">hash_exponential_size_policy
</code>
1016 </td></tr><tr><td align=
"left" valign=
"top">
1017 <code class=
"classname">Trigger_Policy
</code>
1018 </td><td align=
"left">
1019 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1020 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1021 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"hash.erase_mem.observations"></a>
1023 </h6></div></div></div><p>The standard's hash-based containers act very differently than trees in
1024 this respect. When erasing numerous keys from an standard
1025 associative-container, the resulting memory user varies greatly
1026 depending on whether the container is tree-based or hash-based.
1027 This is a fundamental consequence of the standard's interface for
1028 associative containers, and it is not due to a specific
1029 implementation.
</p></div></div></div><div class=
"section" title=
"Branch-Based"><div class=
"titlepage"><div><div><h4 class=
"title"><a name=
"performance.branch"></a>Branch-Based
</h4></div></div></div><p></p><div class=
"section" title=
"Text insert"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.branch.text_insert"></a>
1030 Text
<code class=
"function">insert
</code>
1031 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_insert.info"></a>
1033 </h6></div></div></div><p>This test inserts a number of values with keys from an arbitrary
1034 text ([ wickland96thirty ]) into a container
1035 using
<code class=
"function">insert
</code> . It measures the average time
1036 for
<code class=
"function">insert
</code> as a function of the number of
1037 values inserted.
</p><p>The test checks the effect of different underlying
1038 data structures.
</p><p>
1039 It uses the test file:
1040 <code class=
"filename">
1041 performance/ext/pb_ds/tree_text_insert_timing.cc
1043 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_insert.results"></a>
1045 </h6></div></div></div><p>The three graphics below show the results for the native
1046 tree and this library's node-based trees, the native tree and
1047 this library's vector-based trees, and the native tree
1048 and this library's PATRICIA-trie, respectively.
1049 </p><p>The graphic immediately below shows the results for the
1050 native tree type and several node-based tree types.
1051 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_tree_text_insert_node.png" align=
"middle"></div><p>
1052 The abbreviated names in the legend of the graphic above are
1053 instantiated with the types in the following table.
1054 </p></div><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1056 </td></tr><tr><td align=
"left">
1057 <code class=
"classname">std::map
</code>
1058 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1060 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1061 <code class=
"classname">tree
</code>
1062 </td><td align=
"left">
1063 <code class=
"classname">Tag
</code>
1064 </td><td align=
"left">
1065 <code class=
"classname">splay_tree_tag
</code>
1066 </td></tr><tr><td align=
"left">
1067 <code class=
"classname">Node_update
</code>
1068 </td><td align=
"left">
1069 <code class=
"classname">null_node_update
</code>
1070 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1072 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1073 <code class=
"classname">tree
</code>
1074 </td><td align=
"left">
1075 <code class=
"classname">Tag
</code>
1076 </td><td align=
"left">
1077 <code class=
"classname">rb_tree_tag
</code>
1078 </td></tr><tr><td align=
"left">
1079 <code class=
"classname">Node_update
</code>
1080 </td><td align=
"left">
1081 <code class=
"classname">null_node_update
</code>
1082 </td></tr></tbody></table></div><p>The graphic below shows the results for the
1083 native tree type and a vector-based tree type.
1084 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_tree_text_insert_vector.png" align=
"middle"></div></div><p>
1085 The abbreviated names in the legend of the graphic above are
1086 instantiated with the types in the following table.
1087 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1089 </td></tr><tr><td align=
"left">
1090 <code class=
"classname">std::map
</code>
1091 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1093 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1094 <code class=
"classname">tree
</code>
1095 </td><td align=
"left">
1096 <code class=
"classname">Tag
</code>
1097 </td><td align=
"left">
1098 <code class=
"classname">ov_tree_tag
</code>
1099 </td></tr><tr><td align=
"left">
1100 <code class=
"classname">Node_update
</code>
1101 </td><td align=
"left">
1102 <code class=
"classname">null_node_update
</code>
1103 </td></tr></tbody></table></div><p>The graphic below shows the results for the
1104 native tree type and a PATRICIA trie type.
1105 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_tree_text_insert_trie.png" align=
"middle"></div></div><p>
1106 The abbreviated names in the legend of the graphic above are
1107 instantiated with the types in the following table.
1108 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1110 </td></tr><tr><td align=
"left">
1111 <code class=
"classname">std::map
</code>
1112 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1114 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1115 <code class=
"classname">tree
</code>
1116 </td><td align=
"left">
1117 <code class=
"classname">Tag
</code>
1118 </td><td align=
"left">
1119 <code class=
"classname">pat_trie_tag
</code>
1120 </td></tr><tr><td align=
"left">
1121 <code class=
"classname">Node_update
</code>
1122 </td><td align=
"left">
1123 <code class=
"classname">null_node_update
</code>
1124 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_insert.observations"></a>
1126 </h6></div></div></div><p>Observing the first graphic implies that for this setting, a splay tree
1127 (
<code class=
"classname">tree
</code> with
<code class=
"classname">Tag
1128 </code> =
<code class=
"classname">splay_tree_tag
</code>) does not do
1129 well. See also the Branch-Based
1130 Text
<code class=
"function">find
</code> Find Timing Test. The two
1131 red-black trees perform better.
</p><p>Observing the second graphic, an ordered-vector tree
1132 (
<code class=
"classname">tree
</code> with
<code class=
"classname">Tag
1133 </code> =
<code class=
"classname">ov_tree_tag
</code>) performs
1134 abysmally. Inserting into this type of tree has linear complexity
1135 [ austern00noset].
</p><p>Observing the third and last graphic, A PATRICIA trie
1136 (
<code class=
"classname">trie
</code> with
<code class=
"classname">Tag
1137 </code> =
<code class=
"classname">pat_trie_tag
</code>) has abysmal
1138 performance, as well. This is not that surprising, since a
1139 large-fan-out PATRICIA trie works like a hash table with
1140 collisions resolved by a sub-trie. Each time a collision is
1141 encountered, a new
"hash-table" is built A large fan-out PATRICIA
1142 trie, however, doe does well in look-ups (see Branch-Based
1143 Text
<code class=
"function">find
</code> Find Timing Test). It may be
1144 beneficial in semi-static settings.
</p></div></div><div class=
"section" title=
"Text find"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.branch.text_find"></a>
1145 Text
<code class=
"function">find
</code>
1146 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_find.info"></a>
1148 </h6></div></div></div><p>This test inserts a number of values with keys from an
1149 arbitrary text ([wickland96thirty]) into
1150 a container, then performs a series of finds using
1151 <code class=
"function">find
</code>. It measures the average time
1152 for
<code class=
"function">find
</code> as a function of the number of
1153 values inserted.
</p><p>
1154 It uses the test file:
1155 <code class=
"filename">
1156 performance/ext/pb_ds/text_find_timing.cc
1158 </p><p>The test checks the effect of different underlying
1159 data structures.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_find.results"></a>
1161 </h6></div></div></div><p>The graphic immediately below shows the results for the
1162 native tree type and several other tree types.
1163 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_tree_text_find.png" align=
"middle"></div></div><p>
1164 The abbreviated names in the legend of the graphic above are
1165 instantiated with the types in the following table.
1166 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1168 </td></tr><tr><td align=
"left">
1169 <code class=
"classname">std::map
</code>
1170 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1172 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1173 <code class=
"classname">tree
</code>
1174 </td><td align=
"left">
1175 <code class=
"classname">Tag
</code>
1176 </td><td align=
"left">
1177 <code class=
"classname">splay_tree_tag
</code>
1178 </td></tr><tr><td align=
"left">
1179 <code class=
"classname">Node_Update
</code>
1180 </td><td align=
"left">
1181 <code class=
"classname">null_node_update
</code>
1182 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1184 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1185 <code class=
"classname">tree
</code>
1186 </td><td align=
"left">
1187 <code class=
"classname">Tag
</code>
1188 </td><td align=
"left">
1189 <code class=
"classname">rb_tree_tag
</code>
1190 </td></tr><tr><td align=
"left">
1191 <code class=
"classname">Node_Update
</code>
1192 </td><td align=
"left">
1193 <code class=
"classname">null_node_update
</code>
1194 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1196 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1197 <code class=
"classname">tree
</code>
1198 </td><td align=
"left">
1199 <code class=
"classname">Tag
</code>
1200 </td><td align=
"left">
1201 <code class=
"classname">ov_tree_tag
</code>
1202 </td></tr><tr><td align=
"left">
1203 <code class=
"classname">Node_Update
</code>
1204 </td><td align=
"left">
1205 <code class=
"classname">null_node_update
</code>
1206 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1208 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1209 <code class=
"classname">tree
</code>
1210 </td><td align=
"left">
1211 <code class=
"classname">Tag
</code>
1212 </td><td align=
"left">
1213 <code class=
"classname">pat_trie_tag
</code>
1214 </td></tr><tr><td align=
"left">
1215 <code class=
"classname">Node_Update
</code>
1216 </td><td align=
"left">
1217 <code class=
"classname">null_node_update
</code>
1218 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_find.observations"></a>
1220 </h6></div></div></div><p>For this setting, a splay tree (
<code class=
"classname">tree
</code>
1221 with
<code class=
"classname">Tag
1222 </code> =
<code class=
"classname">splay_tree_tag
</code>) does not do
1223 well. This is possibly due to two reasons:
</p><div class=
"orderedlist"><ol class=
"orderedlist" type=
"1"><li class=
"listitem"><p>A splay tree is not guaranteed to be balanced [motwani95random]. If a
1224 splay tree contains n nodes, its average root-leaf
1225 path can be m
>> log(n).
</p></li><li class=
"listitem"><p>Assume a specific root-leaf search path has length
1226 m, and the search-target node has distance m'
1227 from the root. A red-black tree will require m +
1
1228 comparisons to find the required node; a splay tree will
1229 require
2 m' comparisons. A splay tree, consequently,
1230 can perform many more comparisons than a red-black tree.
</p></li></ol></div><p>An ordered-vector tree (
<code class=
"classname">tree
</code>
1231 with
<code class=
"classname">Tag
</code> =
<code class=
"classname">ov_tree_tag
</code>), a red-black
1232 tree (
<code class=
"classname">tree
</code>
1233 with
<code class=
"classname">Tag
</code> =
<code class=
"classname">rb_tree_tag
</code>), and the
1234 native red-black tree all share approximately the same
1235 performance.
</p><p>An ordered-vector tree is slightly slower than red-black
1236 trees, since it requires, in order to find a key, more math
1237 operations than they do. Conversely, an ordered-vector tree
1238 requires far lower space than the others. ([austern00noset], however,
1239 seems to have an implementation that is also faster than a
1240 red-black tree).
</p><p>A PATRICIA trie (
<code class=
"classname">trie
</code>
1241 with
<code class=
"classname">Tag
</code> =
<code class=
"classname">pat_trie_tag
</code>) has good
1242 look-up performance, due to its large fan-out in this case. In
1243 this setting, a PATRICIA trie has look-up performance comparable
1244 to a hash table (see Hash-Based Text
1245 <code class=
"classname">find
</code> Timing Test), but it is order
1246 preserving. This is not that surprising, since a large-fan-out
1247 PATRICIA trie works like a hash table with collisions resolved
1248 by a sub-trie. A large-fan-out PATRICIA trie does not do well on
1249 modifications (see Tree-Based and Trie-Based
1250 Text Insert Timing Test). Therefore, it is possibly beneficial in
1251 semi-static settings.
</p></div></div><div class=
"section" title=
"Text find with Locality-of-Reference"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.branch.text_lor_find"></a>
1252 Text
<code class=
"function">find
</code> with Locality-of-Reference
1253 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_lor_find.info"></a>
1255 </h6></div></div></div><p>This test inserts a number of values with keys from an
1256 arbitrary text ([ wickland96thirty ]) into
1257 a container, then performs a series of finds using
1258 <code class=
"function">find
</code>. It is different than Tree-Based and
1259 Trie-Based Text
<code class=
"function">find
</code> Find Timing Test in the
1260 sequence of finds it performs: this test performs multiple
1261 <code class=
"function">find
</code>s on the same key before moving on to the next
1262 key. It measures the average time for
<code class=
"function">find
</code> as a
1263 function of the number of values inserted.
</p><p>
1264 It uses the test file:
1265 <code class=
"filename">
1266 performance/ext/pb_ds/tree_text_lor_find_timing.cc
1268 </p><p>The test checks the effect of different underlying
1269 data structures in a locality-of-reference setting.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_lor_find.results"></a>
1271 </h6></div></div></div><p>The graphic immediately below shows the results for the
1272 native tree type and several other tree types.
1273 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_tree_text_lor_find.png" align=
"middle"></div></div><p>
1274 The abbreviated names in the legend of the graphic above are
1275 instantiated with the types in the following table.
1276 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1278 </td></tr><tr><td align=
"left">
1279 <code class=
"classname">std::map
</code>
1280 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1282 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1283 <code class=
"classname">tree
</code>
1284 </td><td align=
"left">
1285 <code class=
"classname">Tag
</code>
1286 </td><td align=
"left">
1287 <code class=
"classname">splay_tree_tag
</code>
1288 </td></tr><tr><td align=
"left">
1289 <code class=
"classname">Node_Update
</code>
1290 </td><td align=
"left">
1291 <code class=
"classname">null_node_update
</code>
1292 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1294 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1295 <code class=
"classname">tree
</code>
1296 </td><td align=
"left">
1297 <code class=
"classname">Tag
</code>
1298 </td><td align=
"left">
1299 <code class=
"classname">rb_tree_tag
</code>
1300 </td></tr><tr><td align=
"left">
1301 <code class=
"classname">Node_Update
</code>
1302 </td><td align=
"left">
1303 <code class=
"classname">null_node_update
</code>
1304 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1306 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1307 <code class=
"classname">tree
</code>
1308 </td><td align=
"left">
1309 <code class=
"classname">Tag
</code>
1310 </td><td align=
"left">
1311 <code class=
"classname">ov_tree_tag
</code>
1312 </td></tr><tr><td align=
"left">
1313 <code class=
"classname">Node_Update
</code>
1314 </td><td align=
"left">
1315 <code class=
"classname">null_node_update
</code>
1316 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1318 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1319 <code class=
"classname">tree
</code>
1320 </td><td align=
"left">
1321 <code class=
"classname">Tag
</code>
1322 </td><td align=
"left">
1323 <code class=
"classname">pat_trie_tag
</code>
1324 </td></tr><tr><td align=
"left">
1325 <code class=
"classname">Node_Update
</code>
1326 </td><td align=
"left">
1327 <code class=
"classname">null_node_update
</code>
1328 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.text_lor_find.observations"></a>
1330 </h6></div></div></div><p>For this setting, an ordered-vector tree
1331 (
<code class=
"classname">tree
</code> with
<code class=
"classname">Tag
</code>
1332 =
<code class=
"classname">ov_tree_tag
</code>), a red-black tree
1333 (
<code class=
"classname">tree
</code> with
<code class=
"classname">Tag
</code>
1334 =
<code class=
"classname">rb_tree_tag
</code>), and the native red-black
1335 tree all share approximately the same performance.
</p><p>A splay tree (
<code class=
"classname">tree
</code>
1336 with
<code class=
"classname">Tag
</code> =
<code class=
"classname">splay_tree_tag
</code>) does
1337 much better, since each (successful) find
"bubbles" the
1338 corresponding node to the root of the tree.
</p></div></div><div class=
"section" title=
"split and join"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.branch.split_join"></a>
1339 <code class=
"function">split
</code> and
<code class=
"function">join
</code>
1340 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.split_join.info"></a>
1342 </h6></div></div></div><p>This test a container, inserts into a number of values, splits
1343 the container at the median, and joins the two containers. (If the
1344 containers are one of this library's trees,
1345 it splits and joins with the
<code class=
"function">split
</code> and
1346 <code class=
"function">join
</code> method; otherwise, it uses the
<code class=
"function">erase
</code> and
1347 <code class=
"function">insert
</code> methods.) It measures the time for splitting
1348 and joining the containers as a function of the number of
1349 values inserted.
</p><p>
1350 It uses the test file:
1351 <code class=
"filename">
1352 performance/ext/pb_ds/tree_split_join_timing.cc
1354 </p><p>The test checks the performance difference of
<code class=
"function">join
</code>
1355 as opposed to a sequence of
<code class=
"function">insert
</code> operations; by
1356 implication, this test checks the most efficient way to erase a
1357 sub-sequence from a tree-like-based container, since this can
1358 always be performed by a small sequence of splits and joins.
1359 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.split_join.results"></a>
1361 </h6></div></div></div><p>The graphic immediately below shows the results for the
1362 native tree type and several other tree types.
1363 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_tree_split_join.png" align=
"middle"></div></div><p>
1364 The abbreviated names in the legend of the graphic above are
1365 instantiated with the types in the following table.
1366 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1368 </td></tr><tr><td align=
"left">
1369 <code class=
"classname">std::set
</code>
1370 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1372 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1373 <code class=
"classname">tree
</code>
1374 </td><td align=
"left">
1375 <code class=
"classname">Tag
</code>
1376 </td><td align=
"left">
1377 <code class=
"classname">splay_tree_tag
</code>
1378 </td></tr><tr><td align=
"left">
1379 <code class=
"classname">Node_Update
</code>
1380 </td><td align=
"left">
1381 <code class=
"classname">null_node_update
</code>
1382 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1384 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1385 <code class=
"classname">tree
</code>
1386 </td><td align=
"left">
1387 <code class=
"classname">Tag
</code>
1388 </td><td align=
"left">
1389 <code class=
"classname">rb_tree_tag
</code>
1390 </td></tr><tr><td align=
"left">
1391 <code class=
"classname">Node_Update
</code>
1392 </td><td align=
"left">
1393 <code class=
"classname">null_node_update
</code>
1394 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1396 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1397 <code class=
"classname">tree
</code>
1398 </td><td align=
"left">
1399 <code class=
"classname">Tag
</code>
1400 </td><td align=
"left">
1401 <code class=
"classname">ov_tree_tag
</code>
1402 </td></tr><tr><td align=
"left">
1403 <code class=
"classname">Node_Update
</code>
1404 </td><td align=
"left">
1405 <code class=
"classname">null_node_update
</code>
1406 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1408 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1409 <code class=
"classname">tree
</code>
1410 </td><td align=
"left">
1411 <code class=
"classname">Tag
</code>
1412 </td><td align=
"left">
1413 <code class=
"classname">pat_trie_tag
</code>
1414 </td></tr><tr><td align=
"left">
1415 <code class=
"classname">Node_Update
</code>
1416 </td><td align=
"left">
1417 <code class=
"classname">null_node_update
</code>
1418 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.split_join.observations"></a>
1420 </h6></div></div></div><p>In this test, the native red-black trees must be split and
1421 joined externally, through a sequence of
<code class=
"function">erase
</code> and
1422 <code class=
"function">insert
</code> operations. This is clearly
1423 super-linear, and it is not that surprising that the cost is
1424 high.
</p><p>This library's tree-based containers use in this test the
1425 <code class=
"function">split
</code> and
<code class=
"function">join
</code> methods,
1426 which have lower complexity: the
<code class=
"function">join
</code> method
1427 of a splay tree (
<code class=
"classname">tree
</code>
1428 with
<code class=
"classname">Tag
</code>
1429 =
<code class=
"classname">splay_tree_tag
</code>) is quadratic in the
1430 length of the longest root-leaf path, and linear in the total
1431 number of elements; the
<code class=
"function">join
</code> method of a
1432 red-black tree (
<code class=
"classname">tree
</code>
1433 with
<code class=
"classname">Tag
</code>
1434 =
<code class=
"classname">rb_tree_tag
</code>) or an ordered-vector tree
1435 (
<code class=
"classname">tree
</code> with
<code class=
"classname">Tag
</code>
1436 =
<code class=
"classname">ov_tree_tag
</code>) is linear in the number of
1437 elements.
</p><p>Asides from orders of growth, this library's trees access their
1438 allocator very little in these operations, and some of them do not
1439 access it at all. This leads to lower constants in their
1440 complexity, and, for some containers, to exception-free splits and
1441 joins (which can be determined
1442 via
<code class=
"classname">container_traits
</code>).
</p><p>It is important to note that
<code class=
"function">split
</code> and
1443 <code class=
"function">join
</code> are not esoteric methods - they are the most
1444 efficient means of erasing a contiguous range of values from a
1445 tree based container.
</p></div></div><div class=
"section" title=
"Order-Statistics"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.branch.order_statistics"></a>
1447 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.order_statistics.info"></a>
1449 </h6></div></div></div><p>This test creates a container, inserts random integers into the
1450 the container, and then checks the order-statistics of the
1451 container's values. (If the container is one of this
1452 library's trees, it does this with
1453 the
<code class=
"function">order_of_key
</code> method of
1454 <code class=
"classname">tree_order_statistics_node_update
</code>
1455 ; otherwise, it uses the
<code class=
"function">find
</code> method and
1456 <code class=
"function">std::distance
</code>.) It measures the average
1457 time for such queries as a function of the number of values
1459 It uses the test file:
1460 <code class=
"filename">
1461 performance/ext/pb_ds/tree_order_statistics_timing.cc
1463 </p><p>The test checks the performance difference of policies based
1464 on node-invariant as opposed to a external functions.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.order_statistics.results"></a>
1466 </h6></div></div></div><p>The graphic immediately below shows the results for the
1467 native tree type and several other tree types.
1468 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_tree_order_statistics.png" align=
"middle"></div></div><p>
1469 The abbreviated names in the legend of the graphic above are
1470 instantiated with the types in the following table.
1471 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1473 </td></tr><tr><td align=
"left">
1474 <code class=
"classname">std::set
</code>
1475 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1477 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1478 <code class=
"classname">tree
</code>
1479 </td><td align=
"left">
1480 <code class=
"classname">Tag
</code>
1481 </td><td align=
"left">
1482 <code class=
"classname">splay_tree_tag
</code>
1483 </td></tr><tr><td align=
"left">
1484 <code class=
"classname">Node_Update
</code>
1485 </td><td align=
"left">
1486 <code class=
"classname">tree_order_statistics_node_update
</code>
1487 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
1489 </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1490 <code class=
"classname">tree
</code>
1491 </td><td align=
"left">
1492 <code class=
"classname">Tag
</code>
1493 </td><td align=
"left">
1494 <code class=
"classname">rb_tree_tag
</code>
1495 </td></tr><tr><td align=
"left">
1496 <code class=
"classname">Node_Update
</code>
1497 </td><td align=
"left">
1498 <code class=
"classname">tree_order_statistics_node_update
</code>
1499 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"branch.order_statistics.observations"></a>
1501 </h6></div></div></div><p>In this test, the native red-black tree can support
1502 order-statistics queries only externally, by performing a
1503 <code class=
"classname">find
</code> (alternatively,
<code class=
"classname">lower_bound
</code> or
1504 <code class=
"classname">upper_bound
</code> ) and then using
<code class=
"classname">std::distance
</code> .
1505 This is clearly linear, and it is not that surprising that the
1506 cost is high.
</p><p>This library's tree-based containers use in this test the
1507 <code class=
"classname">order_of_key
</code> method of
<code class=
"classname">tree_order_statistics_node_update
</code>.
1508 This method has only linear complexity in the length of the
1509 root-node path. Unfortunately, the average path of a splay tree
1510 (
<code class=
"classname">tree
</code>
1511 with
<code class=
"classname">Tag =
</code> <code class=
"classname">splay_tree_tag
</code> ) can
1512 be higher than logarithmic; the longest path of a red-black
1513 tree (
<code class=
"classname">tree
</code>
1514 with
<code class=
"classname">Tag =
</code> <code class=
"classname">rb_tree_tag
</code> ) is
1515 logarithmic in the number of elements. Consequently, the splay
1516 tree has worse performance than the red-black tree.
</p></div></div></div><div class=
"section" title=
"Multimap"><div class=
"titlepage"><div><div><h4 class=
"title"><a name=
"performance.multimap"></a>Multimap
</h4></div></div></div><p></p><div class=
"section" title=
"Text find with Small Secondary-to-Primary Key Ratios"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.multimap.text_find_small"></a>
1517 Text
<code class=
"function">find
</code> with Small Secondary-to-Primary Key Ratios
1518 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_find_small.info"></a>
1520 </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1521 first item of each pair is a string from an arbitrary text
1522 [wickland96thirty], and
1523 the second is a uniform i.i.d.integer. The container is a
1524 "multimap" - it considers the first member of each pair as a
1525 primary key, and the second member of each pair as a secondary
1526 key (see Motivation::Associative
1527 Containers::Alternative to Multiple Equivalent Keys). There
1528 are
400 distinct primary keys, and the ratio of secondary keys
1529 to primary keys ranges from
1 to
5.
</p><p>The test measures the average find-time as a function of the
1530 number of values inserted. For this library's containers, it
1531 finds the secondary key from a container obtained from finding
1532 a primary key. For the native multimaps, it searches a range
1533 obtained using
<code class=
"classname">std::equal_range
</code> on a primary key.
</p><p>
1534 It uses the test file:
1535 <code class=
"filename">
1536 performance/ext/pb_ds/multimap_text_find_timing_small.cc
1538 </p><p>The test checks the find-time scalability of different
1539 "multimap" designs.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_find_small.results"></a>
1541 </h6></div></div></div><p>The graphic below show the results for
"multimaps" which
1542 use a tree-based container for primary keys.
1543 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_find_small_s2p_tree.png" align=
"middle"></div></div><p>
1544 The abbreviated names in the legend of the graphic above are
1545 instantiated with the types in the following table.
1546 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1548 </td></tr><tr><td align=
"left">
1549 <code class=
"classname">std::multimap
</code>
1550 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1551 rb_tree_mmap_lu_mtf_set
1552 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
1553 <code class=
"classname">tree
</code>
1554 </td><td align=
"left">
1555 <code class=
"classname">Tag
</code>
1556 </td><td align=
"left">
1557 <code class=
"classname">rb_tree_tag
</code>
1558 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1559 <code class=
"classname">Node_Update
</code>
1560 </td><td align=
"left">
1561 <code class=
"classname">null_node_update
</code>
1562 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1563 <code class=
"classname">Mapped
</code>
1564 </td><td align=
"left">
1565 <code class=
"classname">list_update
</code>
1566 </td><td align=
"left">
1567 <code class=
"classname">Update_Policy
</code>
1568 </td><td align=
"left">
1569 <code class=
"classname">lu_move_to_front_policy
</code>
1570 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1571 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1572 </td></tr><tr><td rowspan=
"5" align=
"left" valign=
"top">
1573 <code class=
"classname">tree
</code>
1574 </td><td align=
"left">
1575 <code class=
"classname">Tag
</code>
1576 </td><td align=
"left">
1577 <code class=
"classname">rb_tree_tag
</code>
1578 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1579 <code class=
"classname">Node_Update
</code>
1580 </td><td align=
"left">
1581 <code class=
"classname">null_node_update
</code>
1582 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
1583 <code class=
"classname">Mapped
</code>
1584 </td><td rowspan=
"3" align=
"left" valign=
"top">
1585 <code class=
"classname">cc_hash_table
</code>
1586 </td><td align=
"left">
1587 <code class=
"classname">Comb_Hash_Fn
</code>
1588 </td><td align=
"left">
1589 <code class=
"classname">direct_mask_range_hashing
</code>
1590 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1591 <code class=
"classname">Resize_Policy
</code>
1592 </td><td rowspan=
"2" align=
"left" valign=
"top">
1593 <code class=
"classname">hash_standard_resize_policy
</code>
1594 </td><td align=
"left">
1595 <code class=
"classname">Size_Policy
</code>
1596 </td><td align=
"left">
1597 <code class=
"classname">hash_exponential_size_policy
</code>
1598 </td></tr><tr><td align=
"left" valign=
"top">
1599 <code class=
"classname">Trigger_Policy
</code>
1600 </td><td align=
"left">
1601 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1602 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1603 </td></tr></tbody></table></div><p>The graphic below show the results for
"multimaps" which
1604 use a hash-based container for primary keys.
1605 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_find_small_s2p_hash.png" align=
"middle"></div></div><p>
1606 The abbreviated names in the legend of the graphic above are
1607 instantiated with the types in the following table.
1608 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1610 </td></tr><tr><td align=
"left">
1611 <code class=
"classname">std::tr1::unordered_multimap
</code>
1612 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1613 rb_tree_mmap_lu_mtf_set
1614 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
1615 <code class=
"classname">
1618 </td><td align=
"left">
1619 <code class=
"classname">Comb_Hash_Fn
</code>
1620 </td><td align=
"left">
1621 <code class=
"classname">direct_mask_range_hashing
</code>
1622 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1623 <code class=
"classname">Resize_Policy
</code>
1624 </td><td rowspan=
"2" align=
"left" valign=
"top">
1625 <code class=
"classname">hash_standard_resize_policy
</code>
1626 </td><td align=
"left">
1627 <code class=
"classname">Size_Policy
</code>
1628 </td><td align=
"left">
1629 <code class=
"classname">hash_exponential_size_policy
</code>
1630 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
1631 <code class=
"classname">Trigger_Policy
</code>
1632 </td><td align=
"left">
1633 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1634 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1635 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
1636 <code class=
"classname">Mapped
</code>
1637 </td><td align=
"left">
1638 <code class=
"classname">list_update
</code>
1639 </td><td align=
"left">
1640 <code class=
"classname">Update_Policy
</code>
1641 </td><td align=
"left">
1642 <code class=
"classname">lu_move_to_front_policy
</code>
1643 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1644 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1645 </td></tr><tr><td rowspan=
"6" align=
"left" valign=
"top">
1646 <code class=
"classname">
1649 </td><td align=
"left">
1650 <code class=
"classname">Comb_Hash_Fn
</code>
1651 </td><td align=
"left">
1652 <code class=
"classname">direct_mask_range_hashing
</code>
1653 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1654 <code class=
"classname">Resize_Policy
</code>
1655 </td><td rowspan=
"2" align=
"left" valign=
"top">
1656 <code class=
"classname">hash_standard_resize_policy
</code>
1657 </td><td align=
"left">
1658 <code class=
"classname">Size_Policy
</code>
1659 </td><td align=
"left">
1660 <code class=
"classname">hash_exponential_size_policy
</code>
1661 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
1662 <code class=
"classname">Trigger_Policy
</code>
1663 </td><td align=
"left">
1664 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1665 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1666 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
1667 <code class=
"classname">Mapped
</code>
1668 </td><td rowspan=
"3" align=
"left" valign=
"top">
1669 <code class=
"classname">cc_hash_table
</code>
1670 </td><td align=
"left">
1671 <code class=
"classname">Comb_Hash_Fn
</code>
1672 </td><td align=
"left">
1673 <code class=
"classname">direct_mask_range_hashing
</code>
1674 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1675 <code class=
"classname">Resize_Policy
</code>
1676 </td><td rowspan=
"2" align=
"left" valign=
"top">
1677 <code class=
"classname">hash_standard_resize_policy
</code>
1678 </td><td align=
"left">
1679 <code class=
"classname">Size_Policy
</code>
1680 </td><td align=
"left">
1681 <code class=
"classname">hash_exponential_size_policy
</code>
1682 </td></tr><tr><td align=
"left" valign=
"top">
1683 <code class=
"classname">Trigger_Policy
</code>
1684 </td><td align=
"left">
1685 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1686 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1687 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_find_small.observations"></a>
1689 </h6></div></div></div><p>See Observations::Mapping-Semantics
1690 Considerations.
</p></div></div><div class=
"section" title=
"Text find with Large Secondary-to-Primary Key Ratios"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.multimap.text_find_large"></a>
1691 Text
<code class=
"function">find
</code> with Large Secondary-to-Primary Key Ratios
1692 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_find_large.info"></a>
1694 </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1695 first item of each pair is a string from an arbitrary text
1696 [wickland96thirty], and
1697 the second is a uniform integer. The container is a
1698 "multimap" - it considers the first member of each pair as a
1699 primary key, and the second member of each pair as a secondary
1701 are
400 distinct primary keys, and the ratio of secondary keys
1702 to primary keys ranges from
1 to
5.
</p><p>The test measures the average find-time as a function of the
1703 number of values inserted. For this library's containers, it
1704 finds the secondary key from a container obtained from finding
1705 a primary key. For the native multimaps, it searches a range
1706 obtained using
<code class=
"classname">std::equal_range
</code> on a primary key.
</p><p>
1707 It uses the test file:
1708 <code class=
"filename">
1709 performance/ext/pb_ds/multimap_text_find_timing_large.cc
1711 </p><p>The test checks the find-time scalability of different
1712 "multimap" designs.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_find_large.results"></a>
1714 </h6></div></div></div><p>The graphic below show the results for
"multimaps" which
1715 use a tree-based container for primary keys.
1716 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_find_large_s2p_tree.png" align=
"middle"></div></div><p>
1717 The abbreviated names in the legend of the graphic above are
1718 instantiated with the types in the following table.
1719 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1721 </td></tr><tr><td align=
"left">
1722 <code class=
"classname">std::multimap
</code>
1723 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1724 rb_tree_mmap_lu_mtf_set
1725 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
1726 <code class=
"classname">tree
</code>
1727 </td><td align=
"left">
1728 <code class=
"classname">Tag
</code>
1729 </td><td align=
"left">
1730 <code class=
"classname">rb_tree_tag
</code>
1731 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1732 <code class=
"classname">Node_Update
</code>
1733 </td><td align=
"left">
1734 <code class=
"classname">null_node_update
</code>
1735 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1736 <code class=
"classname">Mapped
</code>
1737 </td><td align=
"left">
1738 <code class=
"classname">list_update
</code>
1739 </td><td align=
"left">
1740 <code class=
"classname">Update_Policy
</code>
1741 </td><td align=
"left">
1742 <code class=
"classname">lu_move_to_front_policy
</code>
1743 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1744 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1745 </td></tr><tr><td rowspan=
"5" align=
"left" valign=
"top">
1746 <code class=
"classname">tree
</code>
1747 </td><td align=
"left">
1748 <code class=
"classname">Tag
</code>
1749 </td><td align=
"left">
1750 <code class=
"classname">rb_tree_tag
</code>
1751 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1752 <code class=
"classname">Node_Update
</code>
1753 </td><td align=
"left">
1754 <code class=
"classname">null_node_update
</code>
1755 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
1756 <code class=
"classname">Mapped
</code>
1757 </td><td rowspan=
"3" align=
"left" valign=
"top">
1758 <code class=
"classname">cc_hash_table
</code>
1759 </td><td align=
"left">
1760 <code class=
"classname">Comb_Hash_Fn
</code>
1761 </td><td align=
"left">
1762 <code class=
"classname">direct_mask_range_hashing
</code>
1763 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1764 <code class=
"classname">Resize_Policy
</code>
1765 </td><td rowspan=
"2" align=
"left" valign=
"top">
1766 <code class=
"classname">hash_standard_resize_policy
</code>
1767 </td><td align=
"left">
1768 <code class=
"classname">Size_Policy
</code>
1769 </td><td align=
"left">
1770 <code class=
"classname">hash_exponential_size_policy
</code>
1771 </td></tr><tr><td align=
"left" valign=
"top">
1772 <code class=
"classname">Trigger_Policy
</code>
1773 </td><td align=
"left">
1774 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1775 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1776 </td></tr></tbody></table></div><p>The graphic below show the results for
"multimaps" which
1777 use a hash-based container for primary keys.
1778 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_find_large_s2p_hash.png" align=
"middle"></div></div><p>
1779 The abbreviated names in the legend of the graphic above are
1780 instantiated with the types in the following table.
1781 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1783 </td></tr><tr><td align=
"left">
1784 <code class=
"classname">std::tr1::unordered_multimap
</code>
1785 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1786 rb_tree_mmap_lu_mtf_set
1787 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
1788 <code class=
"classname">
1791 </td><td align=
"left">
1792 <code class=
"classname">Comb_Hash_Fn
</code>
1793 </td><td align=
"left">
1794 <code class=
"classname">direct_mask_range_hashing
</code>
1795 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1796 <code class=
"classname">Resize_Policy
</code>
1797 </td><td rowspan=
"2" align=
"left" valign=
"top">
1798 <code class=
"classname">hash_standard_resize_policy
</code>
1799 </td><td align=
"left">
1800 <code class=
"classname">Size_Policy
</code>
1801 </td><td align=
"left">
1802 <code class=
"classname">hash_exponential_size_policy
</code>
1803 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
1804 <code class=
"classname">Trigger_Policy
</code>
1805 </td><td align=
"left">
1806 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1807 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1808 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
1809 <code class=
"classname">Mapped
</code>
1810 </td><td align=
"left">
1811 <code class=
"classname">list_update
</code>
1812 </td><td align=
"left">
1813 <code class=
"classname">Update_Policy
</code>
1814 </td><td align=
"left">
1815 <code class=
"classname">lu_move_to_front_policy
</code>
1816 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1817 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1818 </td></tr><tr><td rowspan=
"6" align=
"left" valign=
"top">
1819 <code class=
"classname">
1822 </td><td align=
"left">
1823 <code class=
"classname">Comb_Hash_Fn
</code>
1824 </td><td align=
"left">
1825 <code class=
"classname">direct_mask_range_hashing
</code>
1826 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1827 <code class=
"classname">Resize_Policy
</code>
1828 </td><td rowspan=
"2" align=
"left" valign=
"top">
1829 <code class=
"classname">hash_standard_resize_policy
</code>
1830 </td><td align=
"left">
1831 <code class=
"classname">Size_Policy
</code>
1832 </td><td align=
"left">
1833 <code class=
"classname">hash_exponential_size_policy
</code>
1834 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
1835 <code class=
"classname">Trigger_Policy
</code>
1836 </td><td align=
"left">
1837 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1838 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1839 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
1840 <code class=
"classname">Mapped
</code>
1841 </td><td rowspan=
"3" align=
"left" valign=
"top">
1842 <code class=
"classname">cc_hash_table
</code>
1843 </td><td align=
"left">
1844 <code class=
"classname">Comb_Hash_Fn
</code>
1845 </td><td align=
"left">
1846 <code class=
"classname">direct_mask_range_hashing
</code>
1847 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1848 <code class=
"classname">Resize_Policy
</code>
1849 </td><td rowspan=
"2" align=
"left" valign=
"top">
1850 <code class=
"classname">hash_standard_resize_policy
</code>
1851 </td><td align=
"left">
1852 <code class=
"classname">Size_Policy
</code>
1853 </td><td align=
"left">
1854 <code class=
"classname">hash_exponential_size_policy
</code>
1855 </td></tr><tr><td align=
"left" valign=
"top">
1856 <code class=
"classname">Trigger_Policy
</code>
1857 </td><td align=
"left">
1858 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1859 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1860 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_find_large.observations"></a>
1862 </h6></div></div></div><p>See Observations::Mapping-Semantics
1863 Considerations.
</p></div></div><div class=
"section" title=
"Text insert with Small Secondary-to-Primary Key Ratios"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.multimap.text_insert_small"></a>
1864 Text
<code class=
"function">insert
</code> with Small
1865 Secondary-to-Primary Key Ratios
1866 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_small.info"></a>
1868 </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1869 first item of each pair is a string from an arbitrary text
1870 [wickland96thirty], and
1871 the second is a uniform integer. The container is a
1872 "multimap" - it considers the first member of each pair as a
1873 primary key, and the second member of each pair as a secondary
1875 are
400 distinct primary keys, and the ratio of secondary keys
1876 to primary keys ranges from
1 to
5.
</p><p>The test measures the average insert-time as a function of
1877 the number of values inserted. For this library's containers,
1878 it inserts a primary key into the primary associative
1879 container, then a secondary key into the secondary associative
1880 container. For the native multimaps, it obtains a range using
1881 <code class=
"classname">std::equal_range
</code>, and inserts a value only if it was
1882 not contained already.
</p><p>
1883 It uses the test file:
1884 <code class=
"filename">
1885 performance/ext/pb_ds/multimap_text_insert_timing_small.cc
1887 </p><p>The test checks the insert-time scalability of different
1888 "multimap" designs.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_small.results"></a>
1890 </h6></div></div></div><p>The graphic below show the results for
"multimaps" which
1891 use a tree-based container for primary keys.
1892 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_insert_small_s2p_tree.png" align=
"middle"></div></div><p>
1893 The abbreviated names in the legend of the graphic above are
1894 instantiated with the types in the following table.
1895 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1897 </td></tr><tr><td align=
"left">
1898 <code class=
"classname">std::multimap
</code>
1899 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1900 rb_tree_mmap_lu_mtf_set
1901 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
1902 <code class=
"classname">tree
</code>
1903 </td><td align=
"left">
1904 <code class=
"classname">Tag
</code>
1905 </td><td align=
"left">
1906 <code class=
"classname">rb_tree_tag
</code>
1907 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1908 <code class=
"classname">Node_Update
</code>
1909 </td><td align=
"left">
1910 <code class=
"classname">null_node_update
</code>
1911 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1912 <code class=
"classname">Mapped
</code>
1913 </td><td align=
"left">
1914 <code class=
"classname">list_update
</code>
1915 </td><td align=
"left">
1916 <code class=
"classname">Update_Policy
</code>
1917 </td><td align=
"left">
1918 <code class=
"classname">lu_move_to_front_policy
</code>
1919 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1920 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1921 </td></tr><tr><td rowspan=
"5" align=
"left" valign=
"top">
1922 <code class=
"classname">tree
</code>
1923 </td><td align=
"left">
1924 <code class=
"classname">Tag
</code>
1925 </td><td align=
"left">
1926 <code class=
"classname">rb_tree_tag
</code>
1927 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
1928 <code class=
"classname">Node_Update
</code>
1929 </td><td align=
"left">
1930 <code class=
"classname">null_node_update
</code>
1931 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
1932 <code class=
"classname">Mapped
</code>
1933 </td><td rowspan=
"3" align=
"left" valign=
"top">
1934 <code class=
"classname">cc_hash_table
</code>
1935 </td><td align=
"left">
1936 <code class=
"classname">Comb_Hash_Fn
</code>
1937 </td><td align=
"left">
1938 <code class=
"classname">direct_mask_range_hashing
</code>
1939 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1940 <code class=
"classname">Resize_Policy
</code>
1941 </td><td rowspan=
"2" align=
"left" valign=
"top">
1942 <code class=
"classname">hash_standard_resize_policy
</code>
1943 </td><td align=
"left">
1944 <code class=
"classname">Size_Policy
</code>
1945 </td><td align=
"left">
1946 <code class=
"classname">hash_exponential_size_policy
</code>
1947 </td></tr><tr><td align=
"left" valign=
"top">
1948 <code class=
"classname">Trigger_Policy
</code>
1949 </td><td align=
"left">
1950 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1951 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1952 </td></tr></tbody></table></div><p>The graphic below show the results for
"multimaps" which
1953 use a hash-based container for primary keys.
1954 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_find_small_s2p_hash.png" align=
"middle"></div></div><p>
1955 The abbreviated names in the legend of the graphic above are
1956 instantiated with the types in the following table.
1957 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1959 </td></tr><tr><td align=
"left">
1960 <code class=
"classname">std::tr1::unordered_multimap
</code>
1961 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1962 rb_tree_mmap_lu_mtf_set
1963 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
1964 <code class=
"classname">
1967 </td><td align=
"left">
1968 <code class=
"classname">Comb_Hash_Fn
</code>
1969 </td><td align=
"left">
1970 <code class=
"classname">direct_mask_range_hashing
</code>
1971 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
1972 <code class=
"classname">Resize_Policy
</code>
1973 </td><td rowspan=
"2" align=
"left" valign=
"top">
1974 <code class=
"classname">hash_standard_resize_policy
</code>
1975 </td><td align=
"left">
1976 <code class=
"classname">Size_Policy
</code>
1977 </td><td align=
"left">
1978 <code class=
"classname">hash_exponential_size_policy
</code>
1979 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
1980 <code class=
"classname">Trigger_Policy
</code>
1981 </td><td align=
"left">
1982 <code class=
"classname">hash_load_check_resize_trigger
</code> with
1983 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
1984 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
1985 <code class=
"classname">Mapped
</code>
1986 </td><td align=
"left">
1987 <code class=
"classname">list_update
</code>
1988 </td><td align=
"left">
1989 <code class=
"classname">Update_Policy
</code>
1990 </td><td align=
"left">
1991 <code class=
"classname">lu_move_to_front_policy
</code>
1992 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
1993 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1994 </td></tr><tr><td rowspan=
"6" align=
"left" valign=
"top">
1995 <code class=
"classname">
1998 </td><td align=
"left">
1999 <code class=
"classname">Comb_Hash_Fn
</code>
2000 </td><td align=
"left">
2001 <code class=
"classname">direct_mask_range_hashing
</code>
2002 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2003 <code class=
"classname">Resize_Policy
</code>
2004 </td><td rowspan=
"2" align=
"left" valign=
"top">
2005 <code class=
"classname">hash_standard_resize_policy
</code>
2006 </td><td align=
"left">
2007 <code class=
"classname">Size_Policy
</code>
2008 </td><td align=
"left">
2009 <code class=
"classname">hash_exponential_size_policy
</code>
2010 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
2011 <code class=
"classname">Trigger_Policy
</code>
2012 </td><td align=
"left">
2013 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2014 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2015 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2016 <code class=
"classname">Mapped
</code>
2017 </td><td rowspan=
"3" align=
"left" valign=
"top">
2018 <code class=
"classname">cc_hash_table
</code>
2019 </td><td align=
"left">
2020 <code class=
"classname">Comb_Hash_Fn
</code>
2021 </td><td align=
"left">
2022 <code class=
"classname">direct_mask_range_hashing
</code>
2023 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2024 <code class=
"classname">Resize_Policy
</code>
2025 </td><td rowspan=
"2" align=
"left" valign=
"top">
2026 <code class=
"classname">hash_standard_resize_policy
</code>
2027 </td><td align=
"left">
2028 <code class=
"classname">Size_Policy
</code>
2029 </td><td align=
"left">
2030 <code class=
"classname">hash_exponential_size_policy
</code>
2031 </td></tr><tr><td align=
"left" valign=
"top">
2032 <code class=
"classname">Trigger_Policy
</code>
2033 </td><td align=
"left">
2034 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2035 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2036 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_small.observations"></a>
2038 </h6></div></div></div><p>See Observations::Mapping-Semantics
2039 Considerations.
</p></div></div><div class=
"section" title=
"Text insert with Small Secondary-to-Primary Key Ratios"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.multimap.text_insert_large"></a>
2040 Text
<code class=
"function">insert
</code> with Small
2041 Secondary-to-Primary Key Ratios
2042 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_large.info"></a>
2044 </h6></div></div></div><p>This test inserts a number of pairs into a container. The
2045 first item of each pair is a string from an arbitrary text
2046 [wickland96thirty], and
2047 the second is a uniform integer. The container is a
2048 "multimap" - it considers the first member of each pair as a
2049 primary key, and the second member of each pair as a secondary
2051 are
400 distinct primary keys, and the ratio of secondary keys
2052 to primary keys ranges from
1 to
5.
</p><p>The test measures the average insert-time as a function of
2053 the number of values inserted. For this library's containers,
2054 it inserts a primary key into the primary associative
2055 container, then a secondary key into the secondary associative
2056 container. For the native multimaps, it obtains a range using
2057 <code class=
"classname">std::equal_range
</code>, and inserts a value only if it was
2058 not contained already.
</p><p>
2059 It uses the test file:
2060 <code class=
"filename">
2061 performance/ext/pb_ds/multimap_text_insert_timing_large.cc
2063 </p><p>The test checks the insert-time scalability of different
2064 "multimap" designs.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_large.results"></a>
2066 </h6></div></div></div><p>The graphic below show the results for
"multimaps" which
2067 use a tree-based container for primary keys.
2068 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_insert_large_s2p_tree.png" align=
"middle"></div></div><p>
2069 The abbreviated names in the legend of the graphic above are
2070 instantiated with the types in the following table.
2071 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2073 </td></tr><tr><td align=
"left">
2074 <code class=
"classname">std::multimap
</code>
2075 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2076 rb_tree_mmap_lu_mtf_set
2077 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2078 <code class=
"classname">tree
</code>
2079 </td><td align=
"left">
2080 <code class=
"classname">Tag
</code>
2081 </td><td align=
"left">
2082 <code class=
"classname">rb_tree_tag
</code>
2083 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2084 <code class=
"classname">Node_Update
</code>
2085 </td><td align=
"left">
2086 <code class=
"classname">null_node_update
</code>
2087 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2088 <code class=
"classname">Mapped
</code>
2089 </td><td align=
"left">
2090 <code class=
"classname">list_update
</code>
2091 </td><td align=
"left">
2092 <code class=
"classname">Update_Policy
</code>
2093 </td><td align=
"left">
2094 <code class=
"classname">lu_move_to_front_policy
</code>
2095 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2096 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2097 </td></tr><tr><td rowspan=
"5" align=
"left" valign=
"top">
2098 <code class=
"classname">tree
</code>
2099 </td><td align=
"left">
2100 <code class=
"classname">Tag
</code>
2101 </td><td align=
"left">
2102 <code class=
"classname">rb_tree_tag
</code>
2103 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2104 <code class=
"classname">Node_Update
</code>
2105 </td><td align=
"left">
2106 <code class=
"classname">null_node_update
</code>
2107 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2108 <code class=
"classname">Mapped
</code>
2109 </td><td rowspan=
"3" align=
"left" valign=
"top">
2110 <code class=
"classname">cc_hash_table
</code>
2111 </td><td align=
"left">
2112 <code class=
"classname">Comb_Hash_Fn
</code>
2113 </td><td align=
"left">
2114 <code class=
"classname">direct_mask_range_hashing
</code>
2115 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2116 <code class=
"classname">Resize_Policy
</code>
2117 </td><td rowspan=
"2" align=
"left" valign=
"top">
2118 <code class=
"classname">hash_standard_resize_policy
</code>
2119 </td><td align=
"left">
2120 <code class=
"classname">Size_Policy
</code>
2121 </td><td align=
"left">
2122 <code class=
"classname">hash_exponential_size_policy
</code>
2123 </td></tr><tr><td align=
"left" valign=
"top">
2124 <code class=
"classname">Trigger_Policy
</code>
2125 </td><td align=
"left">
2126 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2127 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2128 </td></tr></tbody></table></div><p>The graphic below show the results for
"multimaps" which
2129 use a hash-based container for primary keys.
2130 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_find_large_s2p_hash.png" align=
"middle"></div></div><p>
2131 The abbreviated names in the legend of the graphic above are
2132 instantiated with the types in the following table.
2133 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2135 </td></tr><tr><td align=
"left">
2136 <code class=
"classname">std::tr1::unordered_multimap
</code>
2137 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2138 rb_tree_mmap_lu_mtf_set
2139 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
2140 <code class=
"classname">
2143 </td><td align=
"left">
2144 <code class=
"classname">Comb_Hash_Fn
</code>
2145 </td><td align=
"left">
2146 <code class=
"classname">direct_mask_range_hashing
</code>
2147 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2148 <code class=
"classname">Resize_Policy
</code>
2149 </td><td rowspan=
"2" align=
"left" valign=
"top">
2150 <code class=
"classname">hash_standard_resize_policy
</code>
2151 </td><td align=
"left">
2152 <code class=
"classname">Size_Policy
</code>
2153 </td><td align=
"left">
2154 <code class=
"classname">hash_exponential_size_policy
</code>
2155 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
2156 <code class=
"classname">Trigger_Policy
</code>
2157 </td><td align=
"left">
2158 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2159 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2160 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
2161 <code class=
"classname">Mapped
</code>
2162 </td><td align=
"left">
2163 <code class=
"classname">list_update
</code>
2164 </td><td align=
"left">
2165 <code class=
"classname">Update_Policy
</code>
2166 </td><td align=
"left">
2167 <code class=
"classname">lu_move_to_front_policy
</code>
2168 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2169 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2170 </td></tr><tr><td rowspan=
"6" align=
"left" valign=
"top">
2171 <code class=
"classname">
2174 </td><td align=
"left">
2175 <code class=
"classname">Comb_Hash_Fn
</code>
2176 </td><td align=
"left">
2177 <code class=
"classname">direct_mask_range_hashing
</code>
2178 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2179 <code class=
"classname">Resize_Policy
</code>
2180 </td><td rowspan=
"2" align=
"left" valign=
"top">
2181 <code class=
"classname">hash_standard_resize_policy
</code>
2182 </td><td align=
"left">
2183 <code class=
"classname">Size_Policy
</code>
2184 </td><td align=
"left">
2185 <code class=
"classname">hash_exponential_size_policy
</code>
2186 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
2187 <code class=
"classname">Trigger_Policy
</code>
2188 </td><td align=
"left">
2189 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2190 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2191 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2192 <code class=
"classname">Mapped
</code>
2193 </td><td rowspan=
"3" align=
"left" valign=
"top">
2194 <code class=
"classname">cc_hash_table
</code>
2195 </td><td align=
"left">
2196 <code class=
"classname">Comb_Hash_Fn
</code>
2197 </td><td align=
"left">
2198 <code class=
"classname">direct_mask_range_hashing
</code>
2199 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2200 <code class=
"classname">Resize_Policy
</code>
2201 </td><td rowspan=
"2" align=
"left" valign=
"top">
2202 <code class=
"classname">hash_standard_resize_policy
</code>
2203 </td><td align=
"left">
2204 <code class=
"classname">Size_Policy
</code>
2205 </td><td align=
"left">
2206 <code class=
"classname">hash_exponential_size_policy
</code>
2207 </td></tr><tr><td align=
"left" valign=
"top">
2208 <code class=
"classname">Trigger_Policy
</code>
2209 </td><td align=
"left">
2210 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2211 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2212 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_large.observations"></a>
2214 </h6></div></div></div><p>See Observations::Mapping-Semantics
2215 Considerations.
</p></div></div><div class=
"section" title=
"Text insert with Small Secondary-to-Primary Key Ratios Memory Use"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.multimap.text_insert_mem_small"></a>
2216 Text
<code class=
"function">insert
</code> with Small
2217 Secondary-to-Primary Key Ratios Memory Use
2218 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_mem_small.info"></a>
2220 </h6></div></div></div><p>This test inserts a number of pairs into a container. The
2221 first item of each pair is a string from an arbitrary text
2222 [wickland96thirty], and
2223 the second is a uniform integer. The container is a
2224 "multimap" - it considers the first member of each pair as a
2225 primary key, and the second member of each pair as a secondary
2227 are
100 distinct primary keys, and the ratio of secondary keys
2228 to primary keys ranges to about
20.
</p><p>The test measures the memory use as a function of the number
2229 of values inserted.
</p><p>
2230 It uses the test file:
2231 <code class=
"filename">
2232 performance/ext/pb_ds/multimap_text_insert_mem_usage_small.cc
2234 </p><p>The test checks the memory scalability of different
2235 "multimap" designs.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_mem_small.results"></a>
2237 </h6></div></div></div><p>The graphic below show the results for
"multimaps" which
2238 use a tree-based container for primary keys.
2239 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_insert_mem_small_s2p_tree.png" align=
"middle"></div></div><p>
2240 The abbreviated names in the legend of the graphic above are
2241 instantiated with the types in the following table.
2242 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2244 </td></tr><tr><td align=
"left">
2245 <code class=
"classname">std::multimap
</code>
2246 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2247 rb_tree_mmap_lu_mtf_set
2248 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2249 <code class=
"classname">tree
</code>
2250 </td><td align=
"left">
2251 <code class=
"classname">Tag
</code>
2252 </td><td align=
"left">
2253 <code class=
"classname">rb_tree_tag
</code>
2254 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2255 <code class=
"classname">Node_Update
</code>
2256 </td><td align=
"left">
2257 <code class=
"classname">null_node_update
</code>
2258 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2259 <code class=
"classname">Mapped
</code>
2260 </td><td align=
"left">
2261 <code class=
"classname">list_update
</code>
2262 </td><td align=
"left">
2263 <code class=
"classname">Update_Policy
</code>
2264 </td><td align=
"left">
2265 <code class=
"classname">lu_move_to_front_policy
</code>
2266 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2267 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2268 </td></tr><tr><td rowspan=
"5" align=
"left" valign=
"top">
2269 <code class=
"classname">tree
</code>
2270 </td><td align=
"left">
2271 <code class=
"classname">Tag
</code>
2272 </td><td align=
"left">
2273 <code class=
"classname">rb_tree_tag
</code>
2274 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2275 <code class=
"classname">Node_Update
</code>
2276 </td><td align=
"left">
2277 <code class=
"classname">null_node_update
</code>
2278 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2279 <code class=
"classname">Mapped
</code>
2280 </td><td rowspan=
"3" align=
"left" valign=
"top">
2281 <code class=
"classname">cc_hash_table
</code>
2282 </td><td align=
"left">
2283 <code class=
"classname">Comb_Hash_Fn
</code>
2284 </td><td align=
"left">
2285 <code class=
"classname">direct_mask_range_hashing
</code>
2286 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2287 <code class=
"classname">Resize_Policy
</code>
2288 </td><td rowspan=
"2" align=
"left" valign=
"top">
2289 <code class=
"classname">hash_standard_resize_policy
</code>
2290 </td><td align=
"left">
2291 <code class=
"classname">Size_Policy
</code>
2292 </td><td align=
"left">
2293 <code class=
"classname">hash_exponential_size_policy
</code>
2294 </td></tr><tr><td align=
"left" valign=
"top">
2295 <code class=
"classname">Trigger_Policy
</code>
2296 </td><td align=
"left">
2297 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2298 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2299 </td></tr></tbody></table></div><p>The graphic below show the results for
"multimaps" which
2300 use a hash-based container for primary keys.
2301 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_find_large_s2p_hash.png" align=
"middle"></div></div><p>
2302 The abbreviated names in the legend of the graphic above are
2303 instantiated with the types in the following table.
2304 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2306 </td></tr><tr><td align=
"left">
2307 <code class=
"classname">std::tr1::unordered_multimap
</code>
2308 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2309 rb_tree_mmap_lu_mtf_set
2310 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
2311 <code class=
"classname">
2314 </td><td align=
"left">
2315 <code class=
"classname">Comb_Hash_Fn
</code>
2316 </td><td align=
"left">
2317 <code class=
"classname">direct_mask_range_hashing
</code>
2318 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2319 <code class=
"classname">Resize_Policy
</code>
2320 </td><td rowspan=
"2" align=
"left" valign=
"top">
2321 <code class=
"classname">hash_standard_resize_policy
</code>
2322 </td><td align=
"left">
2323 <code class=
"classname">Size_Policy
</code>
2324 </td><td align=
"left">
2325 <code class=
"classname">hash_exponential_size_policy
</code>
2326 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
2327 <code class=
"classname">Trigger_Policy
</code>
2328 </td><td align=
"left">
2329 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2330 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2331 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
2332 <code class=
"classname">Mapped
</code>
2333 </td><td align=
"left">
2334 <code class=
"classname">list_update
</code>
2335 </td><td align=
"left">
2336 <code class=
"classname">Update_Policy
</code>
2337 </td><td align=
"left">
2338 <code class=
"classname">lu_move_to_front_policy
</code>
2339 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2340 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2341 </td></tr><tr><td rowspan=
"6" align=
"left" valign=
"top">
2342 <code class=
"classname">
2345 </td><td align=
"left">
2346 <code class=
"classname">Comb_Hash_Fn
</code>
2347 </td><td align=
"left">
2348 <code class=
"classname">direct_mask_range_hashing
</code>
2349 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2350 <code class=
"classname">Resize_Policy
</code>
2351 </td><td rowspan=
"2" align=
"left" valign=
"top">
2352 <code class=
"classname">hash_standard_resize_policy
</code>
2353 </td><td align=
"left">
2354 <code class=
"classname">Size_Policy
</code>
2355 </td><td align=
"left">
2356 <code class=
"classname">hash_exponential_size_policy
</code>
2357 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
2358 <code class=
"classname">Trigger_Policy
</code>
2359 </td><td align=
"left">
2360 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2361 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2362 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2363 <code class=
"classname">Mapped
</code>
2364 </td><td rowspan=
"3" align=
"left" valign=
"top">
2365 <code class=
"classname">cc_hash_table
</code>
2366 </td><td align=
"left">
2367 <code class=
"classname">Comb_Hash_Fn
</code>
2368 </td><td align=
"left">
2369 <code class=
"classname">direct_mask_range_hashing
</code>
2370 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2371 <code class=
"classname">Resize_Policy
</code>
2372 </td><td rowspan=
"2" align=
"left" valign=
"top">
2373 <code class=
"classname">hash_standard_resize_policy
</code>
2374 </td><td align=
"left">
2375 <code class=
"classname">Size_Policy
</code>
2376 </td><td align=
"left">
2377 <code class=
"classname">hash_exponential_size_policy
</code>
2378 </td></tr><tr><td align=
"left" valign=
"top">
2379 <code class=
"classname">Trigger_Policy
</code>
2380 </td><td align=
"left">
2381 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2382 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2383 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_mem_small.observations"></a>
2385 </h6></div></div></div><p>See Observations::Mapping-Semantics
2386 Considerations.
</p></div></div><div class=
"section" title=
"Text insert with Small Secondary-to-Primary Key Ratios Memory Use"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.multimap.text_insert_mem_large"></a>
2387 Text
<code class=
"function">insert
</code> with Small
2388 Secondary-to-Primary Key Ratios Memory Use
2389 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_mem_large.info"></a>
2391 </h6></div></div></div><p>This test inserts a number of pairs into a container. The
2392 first item of each pair is a string from an arbitrary text
2393 [wickland96thirty], and
2394 the second is a uniform integer. The container is a
2395 "multimap" - it considers the first member of each pair as a
2396 primary key, and the second member of each pair as a secondary
2398 are
100 distinct primary keys, and the ratio of secondary keys
2399 to primary keys ranges to about
20.
</p><p>The test measures the memory use as a function of the number
2400 of values inserted.
</p><p>
2401 It uses the test file:
2402 <code class=
"filename">
2403 performance/ext/pb_ds/multimap_text_insert_mem_usage_large.cc
2405 </p><p>The test checks the memory scalability of different
2406 "multimap" designs.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_mem_large.results"></a>
2408 </h6></div></div></div><p>The graphic below show the results for
"multimaps" which
2409 use a tree-based container for primary keys.
2410 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_insert_mem_large_s2p_tree.png" align=
"middle"></div></div><p>
2411 The abbreviated names in the legend of the graphic above are
2412 instantiated with the types in the following table.
2413 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2415 </td></tr><tr><td align=
"left">
2416 <code class=
"classname">std::multimap
</code>
2417 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2418 rb_tree_mmap_lu_mtf_set
2419 </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2420 <code class=
"classname">tree
</code>
2421 </td><td align=
"left">
2422 <code class=
"classname">Tag
</code>
2423 </td><td align=
"left">
2424 <code class=
"classname">rb_tree_tag
</code>
2425 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2426 <code class=
"classname">Node_Update
</code>
2427 </td><td align=
"left">
2428 <code class=
"classname">null_node_update
</code>
2429 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2430 <code class=
"classname">Mapped
</code>
2431 </td><td align=
"left">
2432 <code class=
"classname">list_update
</code>
2433 </td><td align=
"left">
2434 <code class=
"classname">Update_Policy
</code>
2435 </td><td align=
"left">
2436 <code class=
"classname">lu_move_to_front_policy
</code>
2437 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2438 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2439 </td></tr><tr><td rowspan=
"5" align=
"left" valign=
"top">
2440 <code class=
"classname">tree
</code>
2441 </td><td align=
"left">
2442 <code class=
"classname">Tag
</code>
2443 </td><td align=
"left">
2444 <code class=
"classname">rb_tree_tag
</code>
2445 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td align=
"left">
2446 <code class=
"classname">Node_Update
</code>
2447 </td><td align=
"left">
2448 <code class=
"classname">null_node_update
</code>
2449 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2450 <code class=
"classname">Mapped
</code>
2451 </td><td rowspan=
"3" align=
"left" valign=
"top">
2452 <code class=
"classname">cc_hash_table
</code>
2453 </td><td align=
"left">
2454 <code class=
"classname">Comb_Hash_Fn
</code>
2455 </td><td align=
"left">
2456 <code class=
"classname">direct_mask_range_hashing
</code>
2457 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2458 <code class=
"classname">Resize_Policy
</code>
2459 </td><td rowspan=
"2" align=
"left" valign=
"top">
2460 <code class=
"classname">hash_standard_resize_policy
</code>
2461 </td><td align=
"left">
2462 <code class=
"classname">Size_Policy
</code>
2463 </td><td align=
"left">
2464 <code class=
"classname">hash_exponential_size_policy
</code>
2465 </td></tr><tr><td align=
"left" valign=
"top">
2466 <code class=
"classname">Trigger_Policy
</code>
2467 </td><td align=
"left">
2468 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2469 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2470 </td></tr></tbody></table></div><p>The graphic below show the results for
"multimaps" which
2471 use a hash-based container for primary keys.
2472 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_multimap_text_find_large_s2p_hash.png" align=
"middle"></div></div><p>
2473 The abbreviated names in the legend of the graphic above are
2474 instantiated with the types in the following table.
2475 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"><col align=
"left" class=
"c7"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2477 </td></tr><tr><td align=
"left">
2478 <code class=
"classname">std::tr1::unordered_multimap
</code>
2479 </td><td colspan=
"6" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2480 rb_tree_mmap_lu_mtf_set
2481 </td></tr><tr><td rowspan=
"4" align=
"left" valign=
"top">
2482 <code class=
"classname">
2485 </td><td align=
"left">
2486 <code class=
"classname">Comb_Hash_Fn
</code>
2487 </td><td align=
"left">
2488 <code class=
"classname">direct_mask_range_hashing
</code>
2489 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2490 <code class=
"classname">Resize_Policy
</code>
2491 </td><td rowspan=
"2" align=
"left" valign=
"top">
2492 <code class=
"classname">hash_standard_resize_policy
</code>
2493 </td><td align=
"left">
2494 <code class=
"classname">Size_Policy
</code>
2495 </td><td align=
"left">
2496 <code class=
"classname">hash_exponential_size_policy
</code>
2497 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
2498 <code class=
"classname">Trigger_Policy
</code>
2499 </td><td align=
"left">
2500 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2501 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2502 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left">
2503 <code class=
"classname">Mapped
</code>
2504 </td><td align=
"left">
2505 <code class=
"classname">list_update
</code>
2506 </td><td align=
"left">
2507 <code class=
"classname">Update_Policy
</code>
2508 </td><td align=
"left">
2509 <code class=
"classname">lu_move_to_front_policy
</code>
2510 </td><td colspan=
"2" align=
"left"> </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"7" align=
"left">
2511 rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2512 </td></tr><tr><td rowspan=
"6" align=
"left" valign=
"top">
2513 <code class=
"classname">
2516 </td><td align=
"left">
2517 <code class=
"classname">Comb_Hash_Fn
</code>
2518 </td><td align=
"left">
2519 <code class=
"classname">direct_mask_range_hashing
</code>
2520 </td><td colspan=
"4" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2521 <code class=
"classname">Resize_Policy
</code>
2522 </td><td rowspan=
"2" align=
"left" valign=
"top">
2523 <code class=
"classname">hash_standard_resize_policy
</code>
2524 </td><td align=
"left">
2525 <code class=
"classname">Size_Policy
</code>
2526 </td><td align=
"left">
2527 <code class=
"classname">hash_exponential_size_policy
</code>
2528 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td align=
"left" valign=
"top">
2529 <code class=
"classname">Trigger_Policy
</code>
2530 </td><td align=
"left">
2531 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2532 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2533 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"3" align=
"left" valign=
"top">
2534 <code class=
"classname">Mapped
</code>
2535 </td><td rowspan=
"3" align=
"left" valign=
"top">
2536 <code class=
"classname">cc_hash_table
</code>
2537 </td><td align=
"left">
2538 <code class=
"classname">Comb_Hash_Fn
</code>
2539 </td><td align=
"left">
2540 <code class=
"classname">direct_mask_range_hashing
</code>
2541 </td><td colspan=
"2" align=
"left"> </td></tr><tr><td rowspan=
"2" align=
"left" valign=
"top">
2542 <code class=
"classname">Resize_Policy
</code>
2543 </td><td rowspan=
"2" align=
"left" valign=
"top">
2544 <code class=
"classname">hash_standard_resize_policy
</code>
2545 </td><td align=
"left">
2546 <code class=
"classname">Size_Policy
</code>
2547 </td><td align=
"left">
2548 <code class=
"classname">hash_exponential_size_policy
</code>
2549 </td></tr><tr><td align=
"left" valign=
"top">
2550 <code class=
"classname">Trigger_Policy
</code>
2551 </td><td align=
"left">
2552 <code class=
"classname">hash_load_check_resize_trigger
</code> with
2553 α
<sub>min
</sub> =
1/
8 and α
<sub>max
</sub> =
1/
2
2554 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"multimap.text_insert_mem_large.observations"></a>
2556 </h6></div></div></div><p>See Observations::Mapping-Semantics
2557 Considerations.
</p></div></div></div><div class=
"section" title=
"Priority Queue"><div class=
"titlepage"><div><div><h4 class=
"title"><a name=
"performance.priority_queue"></a>Priority Queue
</h4></div></div></div><div class=
"section" title=
"Text push"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.priority_queue.text_push"></a>
2558 Text
<code class=
"function">push
</code>
2559 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_push.info"></a>
2561 </h6></div></div></div><p>This test inserts a number of values with keys from an
2562 arbitrary text ([ wickland96thirty ]) into
2563 a container using
<code class=
"function">push
</code>. It measures the average time
2564 for
<code class=
"function">push
</code> as a function of the number of values
2566 It uses the test file:
2567 <code class=
"filename">
2568 performance/ext/pb_ds/priority_queue_text_push_timing.cc
2570 </p><p>The test checks the effect of different underlying data
2572 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_push.results"></a>
2574 </h6></div></div></div><p>The two graphics below show the results for the native
2575 priority_queues and this library's priority_queues.
2576 </p><p>The graphic immediately below shows the results for the
2577 native priority_queue type instantiated with different underlying
2578 container types versus several different versions of library's
2580 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_priority_queue_text_push.png" align=
"middle"></div></div><p>
2581 The abbreviated names in the legend of the graphic above are
2582 instantiated with the types in the following table.
2583 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2585 </td></tr><tr><td align=
"left">
2586 <code class=
"classname">std::priority_queue
</code>
2587 </td><td align=
"left">
2588 <code class=
"classname">Sequence
</code>
2589 </td><td align=
"left">
2590 <code class=
"classname">std::vector
</code>
2591 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2593 </td></tr><tr><td align=
"left">
2594 <code class=
"classname">std::priority_queue
</code>
2595 </td><td align=
"left">
2596 <code class=
"classname">Sequence
</code>
2597 </td><td align=
"left">
2598 <code class=
"classname">std::deque
</code>
2599 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2601 </td></tr><tr><td align=
"left">
2602 <code class=
"classname">priority_queue
</code>
2603 </td><td align=
"left">
2604 <code class=
"classname">Tag
</code>
2605 </td><td align=
"left">
2606 <code class=
"classname">binary_heap_tag
</code>
2607 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2609 </td></tr><tr><td align=
"left">
2610 <code class=
"classname">priority_queue
</code>
2611 </td><td align=
"left">
2612 <code class=
"classname">Tag
</code>
2613 </td><td align=
"left">
2614 <code class=
"classname">binomial_heap_tag
</code>
2615 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2617 </td></tr><tr><td align=
"left">
2618 <code class=
"classname">priority_queue
</code>
2619 </td><td align=
"left">
2620 <code class=
"classname">Tag
</code>
2621 </td><td align=
"left">
2622 <code class=
"classname">rc_binomial_heap_tag
</code>
2623 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2625 </td></tr><tr><td align=
"left">
2626 <code class=
"classname">priority_queue
</code>
2627 </td><td align=
"left">
2628 <code class=
"classname">Tag
</code>
2629 </td><td align=
"left">
2630 <code class=
"classname">thin_heap_tag
</code>
2631 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2633 </td></tr><tr><td align=
"left">
2634 <code class=
"classname">priority_queue
</code>
2635 </td><td align=
"left">
2636 <code class=
"classname">Tag
</code>
2637 </td><td align=
"left">
2638 <code class=
"classname">pairing_heap_tag
</code>
2639 </td></tr></tbody></table></div><p>The graphic below shows the results for the binary-heap
2640 based native priority queues and this library's pairing-heap
2641 priority_queue data structures.
2642 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_pairing_priority_queue_text_push.png" align=
"middle"></div></div><p>
2643 The abbreviated names in the legend of the graphic above are
2644 instantiated with the types in the following table.
2645 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2647 </td></tr><tr><td align=
"left">
2648 <code class=
"classname">std::priority_queue
</code>
2649 </td><td align=
"left">
2650 <code class=
"classname">Sequence
</code>
2651 </td><td align=
"left">
2652 <code class=
"classname">std::vector
</code>
2653 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2655 </td></tr><tr><td align=
"left">
2656 <code class=
"classname">std::priority_queue
</code>
2657 </td><td align=
"left">
2658 <code class=
"classname">Sequence
</code>
2659 </td><td align=
"left">
2660 <code class=
"classname">std::deque
</code>
2661 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2663 </td></tr><tr><td align=
"left">
2664 <code class=
"classname">priority_queue
</code>
2665 </td><td align=
"left">
2666 <code class=
"classname">Tag
</code>
2667 </td><td align=
"left">
2668 <code class=
"classname">thin_heap_tag
</code>
2669 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2671 </td></tr><tr><td align=
"left">
2672 <code class=
"classname">priority_queue
</code>
2673 </td><td align=
"left">
2674 <code class=
"classname">Tag
</code>
2675 </td><td align=
"left">
2676 <code class=
"classname">pairing_heap_tag
</code>
2677 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_push.observations"></a>
2679 </h6></div></div></div><p>Pairing heaps (
<code class=
"classname">priority_queue
</code> with
2680 <code class=
"classname">Tag
</code> =
<code class=
"classname">pairing_heap_tag
</code>)
2681 are the most suited for sequences of
<code class=
"function">push
</code> and
2682 <code class=
"function">pop
</code> operations of non-primitive types (e.g.
2683 <code class=
"classname">std::string
</code>s). (See Priority Queue
2684 Text
<code class=
"function">push
</code> and
<code class=
"function">pop
</code> Timing Test.) They are
2685 less constrained than binomial heaps, e.g., and since
2686 they are node-based, they outperform binary heaps. (See
2688 Queue Random Integer
<code class=
"function">push
</code> Timing Test for the case
2689 of primitive types.)
</p><p>The standard's priority queues do not seem to perform well in
2690 this case: the
<code class=
"classname">std::vector
</code> implementation needs to
2691 perform a logarithmic sequence of string operations for each
2692 operation, and the deque implementation is possibly hampered by
2693 its need to manipulate a relatively-complex type (deques
2694 support a O(
1)
<code class=
"function">push_front
</code>, even though it is
2695 not used by
<code class=
"classname">std::priority_queue
</code>.)
</p></div></div><div class=
"section" title=
"Text push and pop"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.priority_queue.text_push_pop"></a>
2696 Text
<code class=
"function">push
</code> and
<code class=
"function">pop
</code>
2697 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_push_pop.info"></a>
2699 </h6></div></div></div><p>This test inserts a number of values with keys from an
2700 arbitrary text ([ wickland96thirty ]) into
2701 a container using
<code class=
"classname">push
</code> , then removes them using
2702 <code class=
"classname">pop
</code> . It measures the average time for
<code class=
"classname">push
</code>
2703 as a function of the number of values.
</p><p>
2704 It uses the test file:
2705 <code class=
"filename">
2706 performance/ext/pb_ds/priority_queue_text_push_pop_timing.cc
2708 </p><p>The test checks the effect of different underlying data
2710 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_push_pop.results"></a>
2712 </h6></div></div></div><p>The two graphics below show the results for the native
2713 priority_queues and this library's priority_queues.
2714 </p><p>The graphic immediately below shows the results for the
2715 native priority_queue type instantiated with different underlying
2716 container types versus several different versions of library's
2718 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_priority_queue_text_push_pop.png" align=
"middle"></div></div><p>
2719 The abbreviated names in the legend of the graphic above are
2720 instantiated with the types in the following table.
2721 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2723 </td></tr><tr><td align=
"left">
2724 <code class=
"classname">std::priority_queue
</code>
2725 </td><td align=
"left">
2726 <code class=
"classname">Sequence
</code>
2727 </td><td align=
"left">
2728 <code class=
"classname">std::vector
</code>
2729 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2731 </td></tr><tr><td align=
"left">
2732 <code class=
"classname">std::priority_queue
</code>
2733 </td><td align=
"left">
2734 <code class=
"classname">Sequence
</code>
2735 </td><td align=
"left">
2736 <code class=
"classname">std::deque
</code>
2737 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2739 </td></tr><tr><td align=
"left">
2740 <code class=
"classname">priority_queue
</code>
2741 </td><td align=
"left">
2742 <code class=
"classname">Tag
</code>
2743 </td><td align=
"left">
2744 <code class=
"classname">binary_heap_tag
</code>
2745 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2747 </td></tr><tr><td align=
"left">
2748 <code class=
"classname">priority_queue
</code>
2749 </td><td align=
"left">
2750 <code class=
"classname">Tag
</code>
2751 </td><td align=
"left">
2752 <code class=
"classname">binomial_heap_tag
</code>
2753 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2755 </td></tr><tr><td align=
"left">
2756 <code class=
"classname">priority_queue
</code>
2757 </td><td align=
"left">
2758 <code class=
"classname">Tag
</code>
2759 </td><td align=
"left">
2760 <code class=
"classname">rc_binomial_heap_tag
</code>
2761 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2763 </td></tr><tr><td align=
"left">
2764 <code class=
"classname">priority_queue
</code>
2765 </td><td align=
"left">
2766 <code class=
"classname">Tag
</code>
2767 </td><td align=
"left">
2768 <code class=
"classname">thin_heap_tag
</code>
2769 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2771 </td></tr><tr><td align=
"left">
2772 <code class=
"classname">priority_queue
</code>
2773 </td><td align=
"left">
2774 <code class=
"classname">Tag
</code>
2775 </td><td align=
"left">
2776 <code class=
"classname">pairing_heap_tag
</code>
2777 </td></tr></tbody></table></div><p>The graphic below shows the results for the native priority
2778 queues and this library's pairing-heap priority_queue data
2780 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_pairing_priority_queue_text_push_pop.png" align=
"middle"></div></div><p>
2781 The abbreviated names in the legend of the graphic above are
2782 instantiated with the types in the following table.
2783 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2785 </td></tr><tr><td align=
"left">
2786 <code class=
"classname">std::priority_queue
</code> adapting
<code class=
"classname">std::vector
</code>
2787 </td><td align=
"left">
2788 <code class=
"classname">Sequence
</code>
2789 </td><td align=
"left">
2790 <code class=
"classname">std::vector
</code>
2791 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2793 </td></tr><tr><td align=
"left">
2794 <code class=
"classname">std::priority_queue
</code>
2795 </td><td align=
"left">
2796 <code class=
"classname">Sequence
</code>
2797 </td><td align=
"left">
2798 <code class=
"classname">std::deque
</code>
2799 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2801 </td></tr><tr><td align=
"left">
2802 <code class=
"classname">priority_queue
</code>
2803 </td><td align=
"left">
2804 <code class=
"classname">Tag
</code>
2805 </td><td align=
"left">
2806 <code class=
"classname">pairing_heap_tag
</code>
2807 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_push_pop.observations"></a>
2809 </h6></div></div></div><p>These results are very similar to Priority Queue Text
2810 <code class=
"function">push
</code> Timing Test. As stated there, pairing heaps
2811 (
<code class=
"classname">priority_queue
</code> with
2812 <code class=
"classname">Tag
</code>
2813 =
<code class=
"classname">pairing_heap_tag
</code>) are most suited
2814 for
<code class=
"function">push
</code> and
<code class=
"function">pop
</code>
2815 sequences of non-primitive types such as strings. Observing these
2816 two tests, one can note that a pairing heap outperforms the others
2817 in terms of
<code class=
"function">push
</code> operations, but equals
2818 binary heaps (
<code class=
"classname">priority_queue
</code> with
2819 <code class=
"classname">Tag
</code>
2820 =
<code class=
"classname">binary_heap_tag
</code>) if the number
2821 of
<code class=
"function">push
</code> and
<code class=
"function">pop
</code>
2822 operations is equal. As the number of
<code class=
"function">pop
</code>
2823 operations is at most equal to the number
2824 of
<code class=
"function">push
</code> operations, pairing heaps are better
2825 in this case. See Priority Queue Random
2826 Integer
<code class=
"function">push
</code> and
<code class=
"function">pop
</code>
2827 Timing Test for a case which is different.
</p></div></div><div class=
"section" title=
"Integer push"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.priority_queue.int_push"></a>
2828 Integer
<code class=
"function">push
</code>
2829 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.int_push.info"></a>
2831 </h6></div></div></div><p>This test inserts a number of values with integer keys
2832 into a container using
<code class=
"function">push
</code>. It
2833 measures the average time for
<code class=
"function">push
</code> as a
2834 function of the number of values.
</p><p>
2835 It uses the test file:
2836 <code class=
"filename">
2837 performance/ext/pb_ds/priority_queue_random_int_push_timing.cc
2839 </p><p>The test checks the effect of different underlying data
2841 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.int_push.results"></a>
2843 </h6></div></div></div><p>The two graphics below show the results for the native
2844 priority_queues and this library's priority_queues.
2845 </p><p>The graphic immediately below shows the results for the
2846 native priority_queue type instantiated with different underlying
2847 container types versus several different versions of library's
2849 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_priority_queue_int_push.png" align=
"middle"></div></div><p>
2850 The abbreviated names in the legend of the graphic above are
2851 instantiated with the types in the following table.
2852 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2854 </td></tr><tr><td align=
"left">
2855 <code class=
"classname">std::priority_queue
</code>
2856 </td><td align=
"left">
2857 <code class=
"classname">Sequence
</code>
2858 </td><td align=
"left">
2859 <code class=
"classname">std::vector
</code>
2860 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2862 </td></tr><tr><td align=
"left">
2863 <code class=
"classname">std::priority_queue
</code>
2864 </td><td align=
"left">
2865 <code class=
"classname">Sequence
</code>
2866 </td><td align=
"left">
2867 <code class=
"classname">std::deque
</code>
2868 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2870 </td></tr><tr><td align=
"left">
2871 <code class=
"classname">priority_queue
</code>
2872 </td><td align=
"left">
2873 <code class=
"classname">Tag
</code>
2874 </td><td align=
"left">
2875 <code class=
"classname">binary_heap_tag
</code>
2876 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2878 </td></tr><tr><td align=
"left">
2879 <code class=
"classname">priority_queue
</code>
2880 </td><td align=
"left">
2881 <code class=
"classname">Tag
</code>
2882 </td><td align=
"left">
2883 <code class=
"classname">binomial_heap_tag
</code>
2884 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2886 </td></tr><tr><td align=
"left">
2887 <code class=
"classname">priority_queue
</code>
2888 </td><td align=
"left">
2889 <code class=
"classname">Tag
</code>
2890 </td><td align=
"left">
2891 <code class=
"classname">rc_binomial_heap_tag
</code>
2892 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2894 </td></tr><tr><td align=
"left">
2895 <code class=
"classname">priority_queue
</code>
2896 </td><td align=
"left">
2897 <code class=
"classname">Tag
</code>
2898 </td><td align=
"left">
2899 <code class=
"classname">thin_heap_tag
</code>
2900 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2902 </td></tr><tr><td align=
"left">
2903 <code class=
"classname">priority_queue
</code>
2904 </td><td align=
"left">
2905 <code class=
"classname">Tag
</code>
2906 </td><td align=
"left">
2907 <code class=
"classname">pairing_heap_tag
</code>
2908 </td></tr></tbody></table></div><p>The graphic below shows the results for the binary-heap
2909 based native priority queues and this library's
2910 priority_queue data structures.
2911 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_binary_priority_queue_int_push.png" align=
"middle"></div></div><p>
2912 The abbreviated names in the legend of the graphic above are
2913 instantiated with the types in the following table.
2914 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2916 </td></tr><tr><td align=
"left">
2917 <code class=
"classname">std::priority_queue
</code> adapting
<code class=
"classname">std::vector
</code>
2918 </td><td align=
"left">
2919 <code class=
"classname">Sequence
</code>
2920 </td><td align=
"left">
2921 <code class=
"classname">std::vector
</code>
2922 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2924 </td></tr><tr><td align=
"left">
2925 <code class=
"classname">std::priority_queue
</code>
2926 </td><td align=
"left">
2927 <code class=
"classname">Sequence
</code>
2928 </td><td align=
"left">
2929 <code class=
"classname">std::deque
</code>
2930 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2932 </td></tr><tr><td align=
"left">
2933 <code class=
"classname">priority_queue
</code>
2934 </td><td align=
"left">
2935 <code class=
"classname">Tag
</code>
2936 </td><td align=
"left">
2937 <code class=
"classname">binary_heap_tag
</code>
2938 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.int_push.observations"></a>
2940 </h6></div></div></div><p>Binary heaps are the most suited for sequences of
2941 <code class=
"function">push
</code> and
<code class=
"function">pop
</code> operations of primitive types
2942 (e.g.
<span class=
"type">int
</span>s). They are less constrained
2943 than any other type, and since it is very efficient to store
2944 such types in arrays, they outperform even pairing heaps. (See
2946 Queue Text
<code class=
"function">push
</code> Timing Test for the case of
2947 non-primitive types.)
</p></div></div><div class=
"section" title=
"Integer push"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.priority_queue.int_push_pop"></a>
2948 Integer
<code class=
"function">push
</code>
2949 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.int_push_pop.info"></a>
2951 </h6></div></div></div><p>This test inserts a number of values with integer keys
2952 into a container using
<code class=
"function">push
</code> , then removes them
2953 using
<code class=
"function">pop
</code> . It measures the average time for
2954 <code class=
"function">push
</code> and
<code class=
"function">pop
</code> as a function
2955 of the number of values.
</p><p>
2956 It uses the test file:
2957 <code class=
"filename">
2958 performance/ext/pb_ds/priority_queue_random_int_push_pop_timing.cc
2960 </p><p>The test checks the effect of different underlying data
2962 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.int_push_pop.results"></a>
2964 </h6></div></div></div><p>The graphic immediately below shows the results for the
2965 native priority_queue type instantiated with different underlying
2966 container types versus several different versions of library's
2968 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_priority_queue_int_push_pop.png" align=
"middle"></div></div><p>
2969 The abbreviated names in the legend of the graphic above are
2970 instantiated with the types in the following table.
2971 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2973 </td></tr><tr><td align=
"left">
2974 <code class=
"classname">std::priority_queue
</code>
2975 </td><td align=
"left">
2976 <code class=
"classname">Sequence
</code>
2977 </td><td align=
"left">
2978 <code class=
"classname">std::vector
</code>
2979 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2981 </td></tr><tr><td align=
"left">
2982 <code class=
"classname">std::priority_queue
</code>
2983 </td><td align=
"left">
2984 <code class=
"classname">Sequence
</code>
2985 </td><td align=
"left">
2986 <code class=
"classname">std::deque
</code>
2987 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2989 </td></tr><tr><td align=
"left">
2990 <code class=
"classname">priority_queue
</code>
2991 </td><td align=
"left">
2992 <code class=
"classname">Tag
</code>
2993 </td><td align=
"left">
2994 <code class=
"classname">binary_heap_tag
</code>
2995 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
2997 </td></tr><tr><td align=
"left">
2998 <code class=
"classname">priority_queue
</code>
2999 </td><td align=
"left">
3000 <code class=
"classname">Tag
</code>
3001 </td><td align=
"left">
3002 <code class=
"classname">binomial_heap_tag
</code>
3003 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3005 </td></tr><tr><td align=
"left">
3006 <code class=
"classname">priority_queue
</code>
3007 </td><td align=
"left">
3008 <code class=
"classname">Tag
</code>
3009 </td><td align=
"left">
3010 <code class=
"classname">rc_binomial_heap_tag
</code>
3011 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3013 </td></tr><tr><td align=
"left">
3014 <code class=
"classname">priority_queue
</code>
3015 </td><td align=
"left">
3016 <code class=
"classname">Tag
</code>
3017 </td><td align=
"left">
3018 <code class=
"classname">thin_heap_tag
</code>
3019 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3021 </td></tr><tr><td align=
"left">
3022 <code class=
"classname">priority_queue
</code>
3023 </td><td align=
"left">
3024 <code class=
"classname">Tag
</code>
3025 </td><td align=
"left">
3026 <code class=
"classname">pairing_heap_tag
</code>
3027 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.int_push_pop.observations"></a>
3029 </h6></div></div></div><p>Binary heaps are the most suited for sequences of
3030 <code class=
"function">push
</code> and
<code class=
"function">pop
</code> operations of primitive types
3031 (e.g.
<span class=
"type">int
</span>s). This is explained in
3033 Queue Random Int
<code class=
"function">push
</code> Timing Test. (See Priority Queue
3034 Text
<code class=
"function">push
</code> Timing Test for the case of primitive
3035 types.)
</p><p>At first glance it seems that the standard's vector-based
3036 priority queue is approximately on par with this
3037 library's corresponding priority queue. There are two
3038 differences however:
</p><div class=
"orderedlist"><ol class=
"orderedlist" type=
"1"><li class=
"listitem"><p>The standard's priority queue does not downsize the underlying
3039 vector (or deque) as the priority queue becomes smaller
3041 Text
<code class=
"function">pop
</code> Memory Use Test). It is therefore
3042 gaining some speed at the expense of space.
</p></li><li class=
"listitem"><p>From Priority Queue Random
3043 Integer
<code class=
"function">push
</code> and
<code class=
"function">pop
</code>
3044 Timing Test, it seems that the standard's priority queue is
3045 slower in terms of
<code class=
"function">push
</code> operations. Since
3047 <code class=
"function">pop
</code> operations is at most that of
<code class=
"function">push
</code>
3048 operations, the test here is the
"best" for the standard's
3049 priority queue.
</p></li></ol></div></div></div><div class=
"section" title=
"Text pop Memory Use"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.priority_queue.text_pop"></a>
3050 Text
<code class=
"function">pop
</code> Memory Use
3051 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_pop.info"></a>
3053 </h6></div></div></div><p>This test inserts a number of values with keys from an
3054 arbitrary text ([ wickland96thirty ]) into
3055 a container, then pops them until only one is left in the
3056 container. It measures the memory use as a function of the
3057 number of values pushed to the container.
</p><p>
3058 It uses the test file:
3059 <code class=
"filename">
3060 performance/ext/pb_ds/priority_queue_text_pop_mem_usage.cc
3062 </p><p>The test checks the effect of different underlying data
3064 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_pop.results"></a>
3066 </h6></div></div></div><p>The graphic immediately below shows the results for the
3067 native priority_queue type instantiated with different underlying
3068 container types versus several different versions of library's
3070 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_priority_queue_text_pop_mem.png" align=
"middle"></div></div><p>
3071 The abbreviated names in the legend of the graphic above are
3072 instantiated with the types in the following table.
3073 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3075 </td></tr><tr><td align=
"left">
3076 <code class=
"classname">std::priority_queue
</code>
3077 </td><td align=
"left">
3078 <code class=
"classname">Sequence
</code>
3079 </td><td align=
"left">
3080 <code class=
"classname">std::vector
</code>
3081 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3083 </td></tr><tr><td align=
"left">
3084 <code class=
"classname">std::priority_queue
</code>
3085 </td><td align=
"left">
3086 <code class=
"classname">Sequence
</code>
3087 </td><td align=
"left">
3088 <code class=
"classname">std::deque
</code>
3089 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3091 </td></tr><tr><td align=
"left">
3092 <code class=
"classname">priority_queue
</code>
3093 </td><td align=
"left">
3094 <code class=
"classname">Tag
</code>
3095 </td><td align=
"left">
3096 <code class=
"classname">binary_heap_tag
</code>
3097 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3099 </td></tr><tr><td align=
"left">
3100 <code class=
"classname">priority_queue
</code>
3101 </td><td align=
"left">
3102 <code class=
"classname">Tag
</code>
3103 </td><td align=
"left">
3104 <code class=
"classname">binomial_heap_tag
</code>
3105 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3107 </td></tr><tr><td align=
"left">
3108 <code class=
"classname">priority_queue
</code>
3109 </td><td align=
"left">
3110 <code class=
"classname">Tag
</code>
3111 </td><td align=
"left">
3112 <code class=
"classname">rc_binomial_heap_tag
</code>
3113 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3115 </td></tr><tr><td align=
"left">
3116 <code class=
"classname">priority_queue
</code>
3117 </td><td align=
"left">
3118 <code class=
"classname">Tag
</code>
3119 </td><td align=
"left">
3120 <code class=
"classname">thin_heap_tag
</code>
3121 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3123 </td></tr><tr><td align=
"left">
3124 <code class=
"classname">priority_queue
</code>
3125 </td><td align=
"left">
3126 <code class=
"classname">Tag
</code>
3127 </td><td align=
"left">
3128 <code class=
"classname">pairing_heap_tag
</code>
3129 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_pop.observations"></a>
3131 </h6></div></div></div><p>The priority queue implementations (excluding the standard's) use
3132 memory proportionally to the number of values they hold:
3133 node-based implementations (e.g., a pairing heap) do so
3134 naturally; this library's binary heap de-allocates memory when
3135 a certain lower threshold is exceeded.
</p><p>Note from Priority Queue Text
<code class=
"function">push
</code>
3136 and
<code class=
"function">pop
</code> Timing Test and Priority Queue
3137 Random Integer
<code class=
"function">push
</code>
3138 and
<code class=
"function">pop
</code> Timing Test that this does not
3139 impede performance compared to the standard's priority
3140 queues.
</p><p>See Hash-Based Erase
3141 Memory Use Test for a similar phenomenon regarding priority
3142 queues.
</p></div></div><div class=
"section" title=
"Text join"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.priority_queue.text_join"></a>
3143 Text
<code class=
"function">join
</code>
3144 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_join.info"></a>
3146 </h6></div></div></div><p>This test inserts a number of values with keys from an
3147 arbitrary text ([ wickland96thirty ]) into
3148 two containers, then merges the containers. It uses
3149 <code class=
"function">join
</code> for this library's priority queues; for
3150 the standard's priority queues, it successively pops values from
3151 one container and pushes them into the other. The test measures
3152 the average time as a function of the number of values.
</p><p>
3153 It uses the test file:
3154 <code class=
"filename">
3155 performance/ext/pb_ds/priority_queue_text_join_timing.cc
3157 </p><p>The test checks the effect of different underlying data
3159 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_join.results"></a>
3161 </h6></div></div></div><p>The graphic immediately below shows the results for the
3162 native priority_queue type instantiated with different underlying
3163 container types versus several different versions of library's
3165 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_priority_queue_text_join.png" align=
"middle"></div></div><p>
3166 The abbreviated names in the legend of the graphic above are
3167 instantiated with the types in the following table.
3168 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3170 </td></tr><tr><td align=
"left">
3171 <code class=
"classname">std::priority_queue
</code>
3172 </td><td align=
"left">
3173 <code class=
"classname">Sequence
</code>
3174 </td><td align=
"left">
3175 <code class=
"classname">std::vector
</code>
3176 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3178 </td></tr><tr><td align=
"left">
3179 <code class=
"classname">std::priority_queue
</code>
3180 </td><td align=
"left">
3181 <code class=
"classname">Sequence
</code>
3182 </td><td align=
"left">
3183 <code class=
"classname">std::deque
</code>
3184 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3186 </td></tr><tr><td align=
"left">
3187 <code class=
"classname">priority_queue
</code>
3188 </td><td align=
"left">
3189 <code class=
"classname">Tag
</code>
3190 </td><td align=
"left">
3191 <code class=
"classname">binary_heap_tag
</code>
3192 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3194 </td></tr><tr><td align=
"left">
3195 <code class=
"classname">priority_queue
</code>
3196 </td><td align=
"left">
3197 <code class=
"classname">Tag
</code>
3198 </td><td align=
"left">
3199 <code class=
"classname">binomial_heap_tag
</code>
3200 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3202 </td></tr><tr><td align=
"left">
3203 <code class=
"classname">priority_queue
</code>
3204 </td><td align=
"left">
3205 <code class=
"classname">Tag
</code>
3206 </td><td align=
"left">
3207 <code class=
"classname">rc_binomial_heap_tag
</code>
3208 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3210 </td></tr><tr><td align=
"left">
3211 <code class=
"classname">priority_queue
</code>
3212 </td><td align=
"left">
3213 <code class=
"classname">Tag
</code>
3214 </td><td align=
"left">
3215 <code class=
"classname">thin_heap_tag
</code>
3216 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3218 </td></tr><tr><td align=
"left">
3219 <code class=
"classname">priority_queue
</code>
3220 </td><td align=
"left">
3221 <code class=
"classname">Tag
</code>
3222 </td><td align=
"left">
3223 <code class=
"classname">pairing_heap_tag
</code>
3224 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_join.observations"></a>
3226 </h6></div></div></div><p>In this test the node-based heaps perform
<code class=
"function">join
</code> in
3227 either logarithmic or constant time. The binary heap requires
3228 linear time, since the well-known heapify algorithm [clrs2001] is linear.
</p><p>It would be possible to apply the heapify algorithm to the
3229 standard containers, if they would support iteration (which they
3230 don't). Barring iterators, it is still somehow possible to perform
3231 linear-time merge on a
<code class=
"classname">std::vector
</code>-based
3232 standard priority queue, using
<code class=
"function">top()
</code>
3233 and
<code class=
"function">size()
</code> (since they are enough to expose
3234 the underlying array), but this is impossible for
3235 a
<code class=
"classname">std::deque
</code>-based standard priority queue.
3236 Without heapify, the cost is super-linear.
</p></div></div><div class=
"section" title=
"Text modify Up"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.priority_queue.text_modify_up"></a>
3237 Text
<code class=
"function">modify
</code> Up
3238 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_modify_up.info"></a>
3240 </h6></div></div></div><p>This test inserts a number of values with keys from an
3241 arbitrary text ([ wickland96thirty ]) into
3242 into a container then modifies each one
"up" (i.e., it
3243 makes it larger). It uses
<code class=
"function">modify
</code> for this library's
3244 priority queues; for the standard's priority queues, it pops values
3245 from a container until it reaches the value that should be
3246 modified, then pushes values back in. It measures the average
3247 time for
<code class=
"function">modify
</code> as a function of the number of
3249 It uses the test file:
3250 <code class=
"filename">
3251 performance/ext/pb_ds/priority_queue_text_modify_up_timing.cc
3253 </p><p>The test checks the effect of different underlying data
3254 structures for graph algorithms settings. Note that making an
3255 arbitrary value larger (in the sense of the priority queue's
3256 comparison functor) corresponds to decrease-key in standard graph
3257 algorithms [clrs2001].
3258 </p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_modify_up.results"></a>
3260 </h6></div></div></div><p>The two graphics below show the results for the native
3261 priority_queues and this library's priority_queues.
3262 </p><p>The graphic immediately below shows the results for the
3263 native priority_queue type instantiated with different underlying
3264 container types versus several different versions of library's
3266 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_priority_queue_text_modify_up.png" align=
"middle"></div></div><p>
3267 The abbreviated names in the legend of the graphic above are
3268 instantiated with the types in the following table.
3269 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3271 </td></tr><tr><td align=
"left">
3272 <code class=
"classname">std::priority_queue
</code>
3273 </td><td align=
"left">
3274 <code class=
"classname">Sequence
</code>
3275 </td><td align=
"left">
3276 <code class=
"classname">std::vector
</code>
3277 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3279 </td></tr><tr><td align=
"left">
3280 <code class=
"classname">std::priority_queue
</code>
3281 </td><td align=
"left">
3282 <code class=
"classname">Sequence
</code>
3283 </td><td align=
"left">
3284 <code class=
"classname">std::deque
</code>
3285 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3287 </td></tr><tr><td align=
"left">
3288 <code class=
"classname">priority_queue
</code>
3289 </td><td align=
"left">
3290 <code class=
"classname">Tag
</code>
3291 </td><td align=
"left">
3292 <code class=
"classname">binary_heap_tag
</code>
3293 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3295 </td></tr><tr><td align=
"left">
3296 <code class=
"classname">priority_queue
</code>
3297 </td><td align=
"left">
3298 <code class=
"classname">Tag
</code>
3299 </td><td align=
"left">
3300 <code class=
"classname">binomial_heap_tag
</code>
3301 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3303 </td></tr><tr><td align=
"left">
3304 <code class=
"classname">priority_queue
</code>
3305 </td><td align=
"left">
3306 <code class=
"classname">Tag
</code>
3307 </td><td align=
"left">
3308 <code class=
"classname">rc_binomial_heap_tag
</code>
3309 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3311 </td></tr><tr><td align=
"left">
3312 <code class=
"classname">priority_queue
</code>
3313 </td><td align=
"left">
3314 <code class=
"classname">Tag
</code>
3315 </td><td align=
"left">
3316 <code class=
"classname">thin_heap_tag
</code>
3317 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3319 </td></tr><tr><td align=
"left">
3320 <code class=
"classname">priority_queue
</code>
3321 </td><td align=
"left">
3322 <code class=
"classname">Tag
</code>
3323 </td><td align=
"left">
3324 <code class=
"classname">pairing_heap_tag
</code>
3325 </td></tr></tbody></table></div><p>The graphic below shows the results for the
3326 native priority queues and this library's pairing and thin heap
3327 priority_queue data structures.
3328 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_pairing_priority_queue_text_modify_up_thin.png" align=
"middle"></div></div><p>
3329 The abbreviated names in the legend of the graphic above are
3330 instantiated with the types in the following table.
3331 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3333 </td></tr><tr><td align=
"left">
3334 <code class=
"classname">priority_queue
</code>
3335 </td><td align=
"left">
3336 <code class=
"classname">Tag
</code>
3337 </td><td align=
"left">
3338 <code class=
"classname">thin_heap_tag
</code>
3339 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3341 </td></tr><tr><td align=
"left">
3342 <code class=
"classname">priority_queue
</code>
3343 </td><td align=
"left">
3344 <code class=
"classname">Tag
</code>
3345 </td><td align=
"left">
3346 <code class=
"classname">pairing_heap_tag
</code>
3347 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_modify_up.observations"></a>
3349 </h6></div></div></div><p>As noted above, increasing an arbitrary value (in the sense of
3350 the priority queue's comparison functor) is very common in
3351 graph-related algorithms. In this case, a thin heap
3352 (
<code class=
"classname">priority_queue
</code> with
3353 <code class=
"classname">Tag
</code> =
<code class=
"classname">thin_heap_tag
</code>)
3354 outperforms a pairing heap (
<code class=
"classname">priority_queue
</code> with
3355 <code class=
"classname">Tag
</code> =
<code class=
"classname">pairing_heap_tag
</code>).
3356 Conversely, Priority Queue Text
3357 <code class=
"function">push
</code> Timing Test, Priority Queue
3358 Text
<code class=
"function">push
</code> and
<code class=
"function">pop
</code> Timing Test, Priority
3359 Queue Random Integer
<code class=
"function">push
</code> Timing Test, and
3361 Queue Random Integer
<code class=
"function">push
</code> and
<code class=
"function">pop
</code> Timing
3362 Test show that the situation is reversed for other
3363 operations. It is not clear when to prefer one of these two
3364 different types.
</p><p>In this test this library's binary heaps
3365 effectively perform modify in linear time. As explained in
3366 Priority Queue Design::Traits, given a valid point-type iterator,
3367 a binary heap can perform
3368 <code class=
"function">modify
</code> logarithmically. The problem is that binary
3369 heaps invalidate their find iterators with each modifying
3370 operation, and so the only way to obtain a valid point-type
3371 iterator is to iterate using a range-type iterator until
3372 finding the appropriate value, then use the range-type iterator
3373 for the
<code class=
"function">modify
</code> operation.
</p><p>The explanation for the standard's priority queues' performance
3374 is similar to that in Priority Queue Text
3375 <code class=
"function">join
</code> Timing Test.
</p></div></div><div class=
"section" title=
"Text modify Down"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"performance.priority_queue.text_modify_down"></a>
3376 Text
<code class=
"function">modify
</code> Down
3377 </h5></div></div></div><p></p><div class=
"section" title=
"Description"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_modify_down.info"></a>
3379 </h6></div></div></div><p>This test inserts a number of values with keys from an
3380 arbitrary text ([ wickland96thirty ]) into
3381 into a container then modifies each one
"down" (i.e., it
3382 makes it smaller). It uses
<code class=
"function">modify
</code> for this library's
3383 priority queues; for the standard's priority queues, it pops values
3384 from a container until it reaches the value that should be
3385 modified, then pushes values back in. It measures the average
3386 time for
<code class=
"function">modify
</code> as a function of the number of
3388 It uses the test file:
3389 <code class=
"filename">
3390 performance/ext/pb_ds/priority_queue_text_modify_down_timing.cc
3392 </p><p>The main purpose of this test is to contrast Priority Queue
3393 Text
<code class=
"classname">modify
</code> Up Timing Test.
</p></div><div class=
"section" title=
"Results"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_modify_down.results"></a>
3395 </h6></div></div></div><p>The two graphics below show the results for the native
3396 priority_queues and this library's priority_queues.
3397 </p><p>The graphic immediately below shows the results for the
3398 native priority_queue type instantiated with different underlying
3399 container types versus several different versions of library's
3401 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_priority_queue_text_modify_down.png" align=
"middle"></div></div><p>
3402 The abbreviated names in the legend of the graphic above are
3403 instantiated with the types in the following table.
3404 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3406 </td></tr><tr><td align=
"left">
3407 <code class=
"classname">std::priority_queue
</code>
3408 </td><td align=
"left">
3409 <code class=
"classname">Sequence
</code>
3410 </td><td align=
"left">
3411 <code class=
"classname">std::vector
</code>
3412 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3414 </td></tr><tr><td align=
"left">
3415 <code class=
"classname">std::priority_queue
</code>
3416 </td><td align=
"left">
3417 <code class=
"classname">Sequence
</code>
3418 </td><td align=
"left">
3419 <code class=
"classname">std::deque
</code>
3420 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3422 </td></tr><tr><td align=
"left">
3423 <code class=
"classname">priority_queue
</code>
3424 </td><td align=
"left">
3425 <code class=
"classname">Tag
</code>
3426 </td><td align=
"left">
3427 <code class=
"classname">binary_heap_tag
</code>
3428 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3430 </td></tr><tr><td align=
"left">
3431 <code class=
"classname">priority_queue
</code>
3432 </td><td align=
"left">
3433 <code class=
"classname">Tag
</code>
3434 </td><td align=
"left">
3435 <code class=
"classname">binomial_heap_tag
</code>
3436 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3438 </td></tr><tr><td align=
"left">
3439 <code class=
"classname">priority_queue
</code>
3440 </td><td align=
"left">
3441 <code class=
"classname">Tag
</code>
3442 </td><td align=
"left">
3443 <code class=
"classname">rc_binomial_heap_tag
</code>
3444 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3446 </td></tr><tr><td align=
"left">
3447 <code class=
"classname">priority_queue
</code>
3448 </td><td align=
"left">
3449 <code class=
"classname">Tag
</code>
3450 </td><td align=
"left">
3451 <code class=
"classname">thin_heap_tag
</code>
3452 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3454 </td></tr><tr><td align=
"left">
3455 <code class=
"classname">priority_queue
</code>
3456 </td><td align=
"left">
3457 <code class=
"classname">Tag
</code>
3458 </td><td align=
"left">
3459 <code class=
"classname">pairing_heap_tag
</code>
3460 </td></tr></tbody></table></div><p>The graphic below shows the results for the
3461 native priority queues and this library's pairing and thin heap
3462 priority_queue data structures.
3463 </p><div class=
"informalfigure"><div class=
"mediaobject" align=
"center"><img src=
"../images/pbds_pairing_priority_queue_text_modify_down_thin.png" align=
"middle"></div></div><p>
3464 The abbreviated names in the legend of the graphic above are
3465 instantiated with the types in the following table.
3466 </p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"></colgroup><thead><tr><th align=
"left"><span class=
"emphasis"><em>Name/Instantiating Type
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Parameter
</em></span></th><th align=
"left"><span class=
"emphasis"><em>Details
</em></span></th></tr></thead><tbody><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3468 </td></tr><tr><td align=
"left">
3469 <code class=
"classname">priority_queue
</code>
3470 </td><td align=
"left">
3471 <code class=
"classname">Tag
</code>
3472 </td><td align=
"left">
3473 <code class=
"classname">thin_heap_tag
</code>
3474 </td></tr><tr bgcolor=
"#B0B0B0"><td colspan=
"3" align=
"left">
3476 </td></tr><tr><td align=
"left">
3477 <code class=
"classname">priority_queue
</code>
3478 </td><td align=
"left">
3479 <code class=
"classname">Tag
</code>
3480 </td><td align=
"left">
3481 <code class=
"classname">pairing_heap_tag
</code>
3482 </td></tr></tbody></table></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"priority_queue.text_modify_down.observations"></a>
3484 </h6></div></div></div><p>Most points in these results are similar to Priority Queue
3485 Text
<code class=
"function">modify
</code> Up Timing Test.
</p><p>It is interesting to note, however, that as opposed to that
3486 test, a thin heap (
<code class=
"classname">priority_queue
</code> with
3487 <code class=
"classname">Tag
</code> =
<code class=
"classname">thin_heap_tag
</code>) is
3488 outperformed by a pairing heap (
<code class=
"classname">priority_queue
</code> with
3489 <code class=
"classname">Tag
</code> =
<code class=
"classname">pairing_heap_tag
</code>).
3490 In this case, both heaps essentially perform an
<code class=
"function">erase
</code>
3491 operation followed by a
<code class=
"function">push
</code> operation. As the other
3492 tests show, a pairing heap is usually far more efficient than a
3493 thin heap, so this is not surprising.
</p><p>Most algorithms that involve priority queues increase values
3494 (in the sense of the priority queue's comparison functor), and
3496 Text
<code class=
"classname">modify
</code> Up Timing Test - is more interesting
3497 than this test.
</p></div></div></div><div class=
"section" title=
"Observations"><div class=
"titlepage"><div><div><h4 class=
"title"><a name=
"pbds.test.performance.observations"></a>Observations
</h4></div></div></div><div class=
"section" title=
"Associative"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"observations.associative"></a>Associative
</h5></div></div></div><div class=
"section" title=
"Underlying Data-Structure Families"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"observations.associative.underlying"></a>
3498 Underlying Data-Structure Families
3499 </h6></div></div></div><p>In general, hash-based containers have better timing performance
3500 than containers based on different underlying-data structures. The
3501 main reason to choose a tree-based or trie-based container is if a
3502 byproduct of the tree-like structure is required: either
3503 order-preservation, or the ability to utilize node invariants. If
3504 memory-use is the major factor, an ordered-vector tree gives
3505 optimal results (albeit with high modificiation costs), and a
3506 list-based container gives reasonable results.
</p></div><div class=
"section" title=
"Hash-Based Containers"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"observations.associative.hash"></a>
3507 Hash-Based Containers
3508 </h6></div></div></div><p>Hash-based containers are typically either collision
3509 chaining or probing. Collision-chaining
3510 containers are more flexible internally, and so offer better
3511 timing performance. Probing containers, if used for simple
3512 value-types, manage memory more efficiently (they perform far
3513 fewer allocation-related calls). In general, therefore, a
3514 collision-chaining table should be used. A probing container,
3515 conversely, might be used efficiently for operations such as
3516 eliminating duplicates in a sequence, or counting the number of
3517 occurrences within a sequence. Probing containers might be more
3518 useful also in multithreaded applications where each thread
3519 manipulates a hash-based container: in the standard, allocators have
3520 class-wise semantics (see [meyers96more] - Item
10); a
3521 probing container might incur less contention in this case.
</p></div><div class=
"section" title=
"Hash Policies"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"observations.associative.hash_policies"></a>
3523 </h6></div></div></div><p>In hash-based containers, the range-hashing scheme seems to
3524 affect performance more than other considerations. In most
3525 settings, a mask-based scheme works well (or can be made to
3526 work well). If the key-distribution can be estimated a-priori,
3527 a simple hash function can produce nearly uniform hash-value
3528 distribution. In many other cases (e.g., text hashing,
3529 floating-point hashing), the hash function is powerful enough
3530 to generate hash values with good uniformity properties
3532 a modulo-based scheme, taking into account all bits of the hash
3533 value, appears to overlap the hash function in its effort.
</p><p>The range-hashing scheme determines many of the other
3534 policies. A mask-based scheme works
3535 well with an exponential-size policy; for
3536 probing-based containers, it goes well with a linear-probe
3537 function.
</p><p>An orthogonal consideration is the trigger policy. This
3538 presents difficult tradeoffs. E.g., different load
3539 factors in a load-check trigger policy yield a
3540 space/amortized-cost tradeoff.
</p></div><div class=
"section" title=
"Branch-Based Containers"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"observations.associative.branch"></a>
3541 Branch-Based Containers
3542 </h6></div></div></div><p>In general, there are several families of tree-based
3543 underlying data structures: balanced node-based trees
3544 (e.g., red-black or AVL trees), high-probability
3545 balanced node-based trees (e.g., random treaps or
3546 skip-lists), competitive node-based trees (e.g., splay
3547 trees), vector-based
"trees", and tries. (Additionally, there
3548 are disk-residing or network-residing trees, such as B-Trees
3549 and their numerous variants. An interface for this would have
3550 to deal with the execution model and ACID guarantees; this is
3551 out of the scope of this library.) Following are some
3552 observations on their application to different settings.
</p><p>Of the balanced node-based trees, this library includes a
3553 red-black tree, as does standard (in
3554 practice). This type of tree is the
"workhorse" of tree-based
3555 containers: it offers both reasonable modification and
3556 reasonable lookup time. Unfortunately, this data structure
3557 stores a huge amount of metadata. Each node must contain,
3558 besides a value, three pointers and a boolean. This type might
3559 be avoided if space is at a premium [austern00noset].
</p><p>High-probability balanced node-based trees suffer the
3560 drawbacks of deterministic balanced trees. Although they are
3561 fascinating data structures, preliminary tests with them showed
3562 their performance was worse than red-black trees. The library
3563 does not contain any such trees, therefore.
</p><p>Competitive node-based trees have two drawbacks. They are
3564 usually somewhat unbalanced, and they perform a large number of
3565 comparisons. Balanced trees perform one comparison per each
3566 node they encounter on a search path; a splay tree performs two
3567 comparisons. If the keys are complex objects, e.g.,
3568 <code class=
"classname">std::string
</code>, this can increase the running time.
3569 Conversely, such trees do well when there is much locality of
3570 reference. It is difficult to determine in which case to prefer
3571 such trees over balanced trees. This library includes a splay
3572 tree.
</p><p>Ordered-vector trees use very little space
3574 They do not have any other advantages (at least in this
3575 implementation).
</p><p>Large-fan-out PATRICIA tries have excellent lookup
3576 performance, but they do so through maintaining, for each node,
3577 a miniature
"hash-table". Their space efficiency is low, and
3578 their modification performance is bad. These tries might be
3579 used for semi-static settings, where order preservation is
3580 important. Alternatively, red-black trees cross-referenced with
3581 hash tables can be used. [okasaki98mereable]
3582 discusses small-fan-out PATRICIA tries for integers, but the
3583 cited results seem to indicate that the amortized cost of
3584 maintaining such trees is higher than that of balanced trees.
3585 Moderate-fan-out trees might be useful for sequences where each
3586 element has a limited number of choices, e.g., DNA
3587 strings.
</p></div><div class=
"section" title=
"Mapping-Semantics"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"observations.associative.mapping_semantics"></a>
3589 </h6></div></div></div><p>Different mapping semantics were discussed in the introduction and design sections.Here
3590 the focus will be on the case where a keys can be composed into
3591 primary keys and secondary keys. (In the case where some keys
3592 are completely identical, it is trivial that one should use an
3593 associative container mapping values to size types.) In this
3594 case there are (at least) five possibilities:
</p><div class=
"orderedlist"><ol class=
"orderedlist" type=
"1"><li class=
"listitem"><p>Use an associative container that allows equivalent-key
3595 values (such as
<code class=
"classname">std::multimap
</code>)
</p></li><li class=
"listitem"><p>Use a unique-key value associative container that maps
3596 each primary key to some complex associative container of
3597 secondary keys, say a tree-based or hash-based container.
3598 </p></li><li class=
"listitem"><p>Use a unique-key value associative container that maps
3599 each primary key to some simple associative container of
3600 secondary keys, say a list-based container.
</p></li><li class=
"listitem"><p>Use a unique-key value associative container that maps
3601 each primary key to some non-associative container
3602 (e.g.,
<code class=
"classname">std::vector
</code>)
</p></li><li class=
"listitem"><p>Use a unique-key value associative container that takes
3603 into account both primary and secondary keys.
</p></li></ol></div><p>Stated simply: there is a simple answer for this. (Excluding
3604 option
1, which should be avoided in all cases).
</p><p>If the expected ratio of secondary keys to primary keys is
3605 small, then
3 and
4 seem reasonable. Both types of secondary
3606 containers are relatively lightweight (in terms of memory use
3607 and construction time), and so creating an entire container
3608 object for each primary key is not too expensive. Option
4
3609 might be preferable to option
3 if changing the secondary key
3610 of some primary key is frequent - one cannot modify an
3611 associative container's key, and the only possibility,
3612 therefore, is erasing the secondary key and inserting another
3613 one instead; a non-associative container, conversely, can
3614 support in-place modification. The actual cost of erasing a
3615 secondary key and inserting another one depends also on the
3616 allocator used for secondary associative-containers (The tests
3617 above used the standard allocator, but in practice one might
3618 choose to use, e.g., [boost_pool]). Option
2 is
3619 definitely an overkill in this case. Option
1 loses out either
3620 immediately (when there is one secondary key per primary key)
3621 or almost immediately after that. Option
5 has the same
3622 drawbacks as option
2, but it has the additional drawback that
3623 finding all values whose primary key is equivalent to some key,
3624 might be linear in the total number of values stored (for
3625 example, if using a hash-based container).
</p><p>If the expected ratio of secondary keys to primary keys is
3626 large, then the answer is more complicated. It depends on the
3627 distribution of secondary keys to primary keys, the
3628 distribution of accesses according to primary keys, and the
3629 types of operations most frequent.
</p><p>To be more precise, assume there are m primary keys,
3630 primary key i is mapped to n
<sub>i
</sub>
3631 secondary keys, and each primary key is mapped, on average, to
3632 n secondary keys (i.e.,
3633 E(n
<sub>i
</sub>) = n).
</p><p>Suppose one wants to find a specific pair of primary and
3634 secondary keys. Using
1 with a tree based container
3635 (
<code class=
"classname">std::multimap
</code>), the expected cost is
3636 E(Θ(log(m) + n
<sub>i
</sub>)) = Θ(log(m) +
3637 n); using
1 with a hash-based container
3638 (
<code class=
"classname">std::tr1::unordered_multimap
</code>), the expected cost is
3639 Θ(n). Using
2 with a primary hash-based container
3640 and secondary hash-based containers, the expected cost is
3641 O(
1); using
2 with a primary tree-based container and
3642 secondary tree-based containers, the expected cost is (using
3643 the Jensen inequality [motwani95random])
3644 E(O(log(m) + log(n
<sub>i
</sub>)) = O(log(m)) +
3645 E(O(log(n
<sub>i
</sub>)) = O(log(m)) + O(log(n)),
3646 assuming that primary keys are accessed equiprobably.
3 and
4
3647 are similar to
1, but with lower constants. Using
5 with a
3648 hash-based container, the expected cost is O(
1); using
5
3649 with a tree based container, the cost is
3650 E(Θ(log(mn))) = Θ(log(m) +
3651 log(n)).
</p><p>Suppose one needs the values whose primary key matches some
3652 given key. Using
1 with a hash-based container, the expected
3653 cost is Θ(n), but the values will not be ordered
3654 by secondary keys (which may or may not be required); using
1
3655 with a tree-based container, the expected cost is
3656 Θ(log(m) + n), but with high constants; again the
3657 values will not be ordered by secondary keys.
2,
3, and
4 are
3658 similar to
1, but typically with lower constants (and,
3659 additionally, if one uses a tree-based container for secondary
3660 keys, they will be ordered). Using
5 with a hash-based
3661 container, the cost is Θ(mn).
</p><p>Suppose one wants to assign to a primary key all secondary
3662 keys assigned to a different primary key. Using
1 with a
3663 hash-based container, the expected cost is Θ(n),
3664 but with very high constants; using
1 with a tree-based
3665 container, the cost is Θ(nlog(mn)). Using
2,
3,
3666 and
4, the expected cost is Θ(n), but typically
3667 with far lower costs than
1.
5 is similar to
1.
</p></div></div><div class=
"section" title=
"Priority_Queue"><div class=
"titlepage"><div><div><h5 class=
"title"><a name=
"observations.priority_queue"></a>Priority_Queue
</h5></div></div></div><div class=
"section" title=
"Complexity"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"observations.priority_queue.complexity"></a>Complexity
</h6></div></div></div><p>The following table shows the complexities of the different
3668 underlying data structures in terms of orders of growth. It is
3669 interesting to note that this table implies something about the
3670 constants of the operations as well (see Amortized
<code class=
"function">push
</code>
3671 and
<code class=
"function">pop
</code> operations).
</p><div class=
"informaltable"><table border=
"1"><colgroup><col align=
"left" class=
"c1"><col align=
"left" class=
"c2"><col align=
"left" class=
"c3"><col align=
"left" class=
"c4"><col align=
"left" class=
"c5"><col align=
"left" class=
"c6"></colgroup><thead><tr><th align=
"left"> </th><th align=
"left"><span class=
"emphasis"><em><code class=
"function">push
</code></em></span></th><th align=
"left"><span class=
"emphasis"><em><code class=
"function">pop
</code></em></span></th><th align=
"left"><span class=
"emphasis"><em><code class=
"function">modify
</code></em></span></th><th align=
"left"><span class=
"emphasis"><em><code class=
"function">erase
</code></em></span></th><th align=
"left"><span class=
"emphasis"><em><code class=
"function">join
</code></em></span></th></tr></thead><tbody><tr><td align=
"left">
3672 <code class=
"classname">std::priority_queue
</code>
3673 </td><td align=
"left">
3676 </td><td align=
"left">
3678 </td><td align=
"left">
3680 <sub>[std note
1]
</sub>
3681 </td><td align=
"left">
3683 <sub>[std note
2]
</sub>
3684 </td><td align=
"left">
3686 <sub>[std note
1]
</sub>
3687 </td></tr><tr><td align=
"left">
3688 <code class=
"classname">priority_queue
</code>
3689 <<code class=
"classname">Tag
</code> =
3690 <code class=
"classname">pairing_heap_tag
</code>>
3691 </td><td align=
"left">
3693 </td><td align=
"left">
3696 </td><td align=
"left">
3699 </td><td align=
"left">
3702 </td><td align=
"left">
3704 </td></tr><tr><td align=
"left">
3705 <code class=
"classname">priority_queue
</code>
3706 <<code class=
"classname">Tag
</code> =
3707 <code class=
"classname">binary_heap_tag
</code>>
3708 </td><td align=
"left">
3711 </td><td align=
"left">
3714 </td><td align=
"left">
3716 </td><td align=
"left">
3718 </td><td align=
"left">
3720 </td></tr><tr><td align=
"left">
3721 <code class=
"classname">priority_queue
</code>
3722 <<code class=
"classname">Tag
</code> =
3723 <code class=
"classname">binomial_heap_tag
</code>>
3724 </td><td align=
"left">
3727 </td><td align=
"left">
3729 </td><td align=
"left">
3731 </td><td align=
"left">
3733 </td><td align=
"left">
3735 </td></tr><tr><td align=
"left">
3736 <code class=
"classname">priority_queue
</code>
3737 <<code class=
"classname">Tag
</code> =
3738 <code class=
"classname">rc_binomial_heap_tag
</code>>
3739 </td><td align=
"left">
3741 </td><td align=
"left">
3743 </td><td align=
"left">
3745 </td><td align=
"left">
3747 </td><td align=
"left">
3749 </td></tr><tr><td align=
"left">
3750 <code class=
"classname">priority_queue
</code><<code class=
"classname">Tag
</code> =
3751 <code class=
"classname">thin_heap_tag
</code>>
3752 </td><td align=
"left">
3754 </td><td align=
"left">
3757 </td><td align=
"left">
3760 or Θ(log(n)) amortized
3761 <sub>[thin_heap_note]
</sub>
3762 </td><td align=
"left">
3765 </td><td align=
"left">
3767 </td></tr></tbody></table></div><p>[std note
1] This
3768 is not a property of the algorithm, but rather due to the fact
3769 that the standard's priority queue implementation does not support
3770 iterators (and consequently the ability to access a specific
3771 value inside it). If the priority queue is adapting an
3772 <code class=
"classname">std::vector
</code>, then it is still possible to reduce this
3773 to Θ(n) by adapting over the standard's adapter and
3774 using the fact that
<code class=
"function">top
</code> returns a reference to the
3775 first value; if, however, it is adapting an
3776 <code class=
"classname">std::deque
</code>, then this is impossible.
</p><p>[std note
2] As
3777 with [std note
1], this is not a
3778 property of the algorithm, but rather the standard's implementation.
3779 Again, if the priority queue is adapting an
3780 <code class=
"classname">std::vector
</code> then it is possible to reduce this to
3781 Θ(n), but with a very high constant (one must call
3782 <code class=
"function">std::make_heap
</code> which is an expensive linear
3783 operation); if the priority queue is adapting an
3784 <code class=
"classname">std::deque
</code>, then this is impossible.
</p><p>[thin_heap_note] A thin heap has
3785 Θ(log(n)) worst case
<code class=
"function">modify
</code> time
3786 always, but the amortized time depends on the nature of the
3787 operation: I) if the operation increases the key (in the sense
3788 of the priority queue's comparison functor), then the amortized
3789 time is O(
1), but if II) it decreases it, then the
3790 amortized time is the same as the worst case time. Note that
3791 for most algorithms, I) is important and II) is not.
</p></div><div class=
"section" title=
"Amortized push and pop operations"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"observations.priority_queue.amortized_ops"></a>
3792 Amortized
<code class=
"function">push
</code>
3793 and
<code class=
"function">pop
</code> operations
3794 </h6></div></div></div><p>In many cases, a priority queue is needed primarily for
3795 sequences of
<code class=
"function">push
</code> and
<code class=
"function">pop
</code> operations. All of
3796 the underlying data structures have the same amortized
3797 logarithmic complexity, but they differ in terms of
3798 constants.
</p><p>The table above shows that the different data structures are
3799 "constrained" in some respects. In general, if a data structure
3800 has lower worst-case complexity than another, then it will
3801 perform slower in the amortized sense. Thus, for example a
3802 redundant-counter binomial heap (
<code class=
"classname">priority_queue
</code> with
3803 <code class=
"classname">Tag
</code> =
<code class=
"classname">rc_binomial_heap_tag
</code>)
3804 has lower worst-case
<code class=
"function">push
</code> performance than a binomial
3805 heap (
<code class=
"classname">priority_queue
</code>
3806 with
<code class=
"classname">Tag
</code> =
<code class=
"classname">binomial_heap_tag
</code>),
3807 and so its amortized
<code class=
"function">push
</code> performance is slower in
3808 terms of constants.
</p><p>As the table shows, the
"least constrained" underlying
3809 data structures are binary heaps and pairing heaps.
3810 Consequently, it is not surprising that they perform best in
3811 terms of amortized constants.
</p><div class=
"orderedlist"><ol class=
"orderedlist" type=
"1"><li class=
"listitem"><p>Pairing heaps seem to perform best for non-primitive
3812 types (e.g.,
<code class=
"classname">std::string
</code>s), as shown by
3814 Queue Text
<code class=
"function">push
</code> Timing Test and Priority
3815 Queue Text
<code class=
"function">push
</code> and
<code class=
"function">pop
</code> Timing
3816 Test
</p></li><li class=
"listitem"><p>binary heaps seem to perform best for primitive types
3817 (e.g.,
<span class=
"type">int
</span>s), as shown by Priority
3818 Queue Random Integer
<code class=
"function">push
</code> Timing Test and
3820 Queue Random Integer
<code class=
"function">push
</code> and
<code class=
"function">pop
</code> Timing
3821 Test.
</p></li></ol></div></div><div class=
"section" title=
"Graph Algorithms"><div class=
"titlepage"><div><div><h6 class=
"title"><a name=
"observations.priority_queue.graphs"></a>
3823 </h6></div></div></div><p>In some graph algorithms, a decrease-key operation is
3824 required [clrs2001];
3825 this operation is identical to
<code class=
"function">modify
</code> if a value is
3826 increased (in the sense of the priority queue's comparison
3827 functor). The table above and Priority Queue
3828 Text
<code class=
"function">modify
</code> Up Timing Test show that a thin heap
3829 (
<code class=
"classname">priority_queue
</code> with
3830 <code class=
"classname">Tag
</code> =
<code class=
"classname">thin_heap_tag
</code>)
3831 outperforms a pairing heap (
<code class=
"classname">priority_queue
</code> with
3832 <code class=
"classname">Tag
</code> =
<code class=
"classname">Tag
</code> =
<code class=
"classname">pairing_heap_tag
</code>),
3833 but the rest of the tests show otherwise.
</p><p>This makes it difficult to decide which implementation to use in
3834 this case. Dijkstra's shortest-path algorithm, for example, requires
3835 Θ(n)
<code class=
"function">push
</code> and
<code class=
"function">pop
</code> operations
3836 (in the number of vertices), but O(n
<sup>2</sup>)
3837 <code class=
"function">modify
</code> operations, which can be in practice Θ(n)
3838 as well. It is difficult to find an a-priori characterization of
3839 graphs in which the actual number of
<code class=
"function">modify
</code>
3840 operations will dwarf the number of
<code class=
"function">push
</code> and
3841 <code class=
"function">pop
</code> operations.
</p></div></div></div></div></div><div class=
"navfooter"><hr><table width=
"100%" summary=
"Navigation footer"><tr><td width=
"40%" align=
"left"><a accesskey=
"p" href=
"policy_data_structures_design.html">Prev
</a> </td><td width=
"20%" align=
"center"><a accesskey=
"u" href=
"policy_data_structures.html">Up
</a></td><td width=
"40%" align=
"right"> <a accesskey=
"n" href=
"policy_data_structures_biblio.html">Next
</a></td></tr><tr><td width=
"40%" align=
"left" valign=
"top">Design
</td><td width=
"20%" align=
"center"><a accesskey=
"h" href=
"../index.html">Home
</a></td><td width=
"40%" align=
"right" valign=
"top"> Acknowledgments
</td></tr></table></div></body></html>
projects / gcc.git / blob