OSDN Git Service

* doc/xml/manual/abi.xml: Update URLs for C++ ABI.
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / doc / html / manual / policy_based_data_structures_test.html
1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3 <html xmlns="http://www.w3.org/1999/xhtml"><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="&#10;&#9;ISO C++&#10;      , &#10;&#9;policy&#10;      , &#10;&#9;container&#10;      , &#10;&#9;data&#10;      , &#10;&#9;structure&#10;      , &#10;&#9;associated&#10;      , &#10;&#9;tree&#10;      , &#10;&#9;trie&#10;      , &#10;&#9;hash&#10;      , &#10;&#9;metaprogramming&#10;      " /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    " /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      runtime&#10;    , &#10;      library&#10;    " /><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_ack.html" title="Acknowledgments" /></head><body><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_ack.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 id="pbds.test"></a>Testing</h2></div></div></div><div class="section" title="Regression"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.regression"></a>Regression</h3></div></div></div><p>The library contains a single comprehensive regression test.
4     For a given container type in this library, the test creates
5     an object of the container type and an object of the
6     corresponding standard type (e.g., <code class="classname">std::set</code>). It
7     then performs a random sequence of methods with random
8     arguments (e.g., inserts, erases, and so forth) on both
9     objects. At each operation, the test checks the return value of
10     the method, and optionally both compares this library's
11     object with the standard's object as well as performing other
12     consistency checks on this library's object (e.g.,
13     order preservation, when applicable, or node invariants, when
14     applicable).</p><p>Additionally, the test integrally checks exception safety
15     and resource leaks. This is done as follows. A special
16     allocator type, written for the purpose of the test, both
17     randomly throws an exceptions when allocations are performed,
18     and tracks allocations and de-allocations. The exceptions thrown
19     at allocations simulate memory-allocation failures; the
20     tracking mechanism checks for memory-related bugs (e.g.,
21     resource leaks and multiple de-allocations). Both
22     this library's containers and the containers' value-types are
23     configured to use this allocator.</p><p>For granularity, the test is split into the
24     several sources, each checking only some containers.</p><p>For more details, consult the files in
25     <code class="filename">testsuite/ext/pb_ds/regression</code>.
26     </p></div><div class="section" title="Performance"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.performance"></a>Performance</h3></div></div></div><div class="section" title="Hash-Based"><div class="titlepage"><div><div><h4 class="title"><a id="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 id="performance.hash.text_find"></a>
27           Text <code class="function">find</code>
28         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.info"></a>
29             Description
30           </h6></div></div></div><p>
31             This test inserts a number of values with keys from an
32             arbitrary text (<a class="xref" href="policy_data_structures.html#biblio.wickland96thirty" title="Thirty Years Among the Dead">[biblio.wickland96thirty]</a>) into a container,
33             then performs a series of finds using
34             <code class="function">find</code> . It measures the average
35             time for <code class="function">find</code> as a function of
36           the number of values inserted.</p><p>
37             It uses the test file:
38             <code class="filename">performance/ext/pb_ds/text_find_timing_test.cc</code>
39           </p><p>
40             And uses the data file:
41             <code class="filename">filethirty_years_among_the_dead_preproc.txt</code>
42           </p><p>The test checks the effect of different range-hashing
43           functions, trigger policies, and cache-hashing policies.
44           </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.results"></a>
45             Results
46           </h6></div></div></div><p>The graphic below show the results for the native
47           and collision-chaining hash types the the function
48           applied being a text find timing test using
49           <code class="function">find</code>.
50           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_text_find.png" align="middle" /></div></div><p>
51             The abbreviated names in the legend of the graphic above are
52             instantiated with the types in the following table.
53           </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">
54                     n_hash_map_ncah
55                   </td></tr><tr><td align="left">
56                     <code class="classname">std::tr1::unordered_map</code>
57                   </td><td align="left">
58                     <code class="classname">cache_hash_code</code>
59                   </td><td align="left">
60                     <code class="constant">false</code>
61                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
62                     cc_hash_mod_prime_1div1_nsth_map
63                   </td></tr><tr><td rowspan="3" align="left" valign="top">
64                     <code class="classname">cc_hash_table</code>
65                   </td><td align="left">
66                     <code class="classname">Comb_Hash_Fn</code>
67                   </td><td align="left">
68                     <code class="classname">direct_mod_range_hashing</code>
69                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
70                     <code class="classname">Resize_Policy</code>
71                   </td><td rowspan="2" align="left" valign="top">
72                     <code class="classname">hash_standard_resize_policy</code>
73                   </td><td align="left">
74                     <code class="classname">Size_Policy</code>
75                   </td><td align="left">
76                     <code class="classname">hash_prime_size_policy</code>
77                   </td></tr><tr><td align="left" valign="top">
78                     <code class="classname">Trigger_Policy</code>
79                   </td><td align="left">
80                     <code class="classname">hash_load_check_resize_trigger</code> with
81                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
82                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
83                     cc_hash_mask_exp_1div2_sth_map
84                   </td></tr><tr><td rowspan="3" align="left" valign="top">
85                     <code class="classname">
86                       cc_hash_table
87                     </code>
88                   </td><td align="left">
89                     <code class="classname">Comb_Hash_Fn</code>
90                   </td><td align="left">
91                     <code class="classname">direct_mask_range_hashing</code>
92                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
93                     <code class="classname">Resize_Policy</code>
94                   </td><td rowspan="2" align="left" valign="top">
95                     <code class="classname">hash_standard_resize_policy</code>
96                   </td><td align="left">
97                     <code class="classname">Size_Policy</code>
98                   </td><td align="left">
99                     <code class="classname">hash_exponential_size_policy</code>
100                   </td></tr><tr><td align="left" valign="top">
101                     <code class="classname">Trigger_Policy</code>
102                   </td><td align="left">
103                     <code class="classname">hash_load_check_resize_trigger</code> with
104                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
105                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
106                     cc_hash_mask_exp_1div1_nsth_map
107                   </td></tr><tr><td rowspan="3" align="left" valign="top">
108                     <code class="classname">cc_hash_table</code>
109                   </td><td align="left">
110                     <code class="classname">Comb_Hash_Fn</code>
111                   </td><td align="left">
112                     <code class="classname">direct_mask_range_hashing</code>
113                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
114                     <code class="classname">Resize_Policy</code>
115                   </td><td rowspan="2" align="left" valign="top">
116                     <code class="classname">hash_standard_resize_policy</code>
117                   </td><td align="left">
118                     <code class="classname">Size_Policy</code>
119                   </td><td align="left">
120                     <code class="classname">hash_exponential_size_policy</code>
121                   </td></tr><tr><td align="left" valign="top">
122                     <code class="classname">Trigger_Policy</code>
123                   </td><td align="left">
124                     <code class="classname">hash_load_check_resize_trigger</code> with
125                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
126                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
127                     cc_hash_mask_exp_1div2_nsth_map
128                   </td></tr><tr><td rowspan="3" align="left" valign="top">
129                     <code class="classname">cc_hash_table</code>
130                   </td><td align="left">
131                     <code class="classname">Comb_Hash_Fn</code>
132                   </td><td align="left">
133                     <code class="classname">direct_mask_range_hashing</code>
134                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
135                     <code class="classname">Resize_Policy</code>
136                   </td><td rowspan="2" align="left" valign="top">
137                     <code class="classname">hash_standard_resize_policy</code>
138                   </td><td align="left">
139                     <code class="classname">Size_Policy</code>
140                   </td><td align="left">
141                     <code class="classname">hash_exponential_size_policy</code>
142                   </td></tr><tr><td align="left" valign="top">
143                     <code class="classname">Trigger_Policy</code>
144                   </td><td align="left">
145                     <code class="classname">hash_load_check_resize_trigger</code> with
146                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
147                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.observations"></a>
148             Observations
149           </h6></div></div></div><p>In this setting, the range-hashing scheme affects performance
150           more than other policies. As the results show, containers using
151           mod-based range-hashing (including the native hash-based container,
152           which is currently hard-wired to this scheme) have lower performance
153           than those using mask-based range-hashing. A modulo-based
154           range-hashing scheme's main benefit is that it takes into account
155           all hash-value bits. Standard string hash-functions are designed to
156           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
157           performance to a lesser extent.</p><p>Perhaps surprisingly, storing the hash value alongside each
158           entry affects performance only marginally, at least in this
159           library's implementation. (Unfortunately, it was not possible to run
160           the tests with <code class="classname">std::tr1::unordered_map</code> 's
161           <code class="classname">cache_hash_code = true</code> , as it appeared to
162           malfuntion.)</p></div></div><div class="section" title="Integer find"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_find"></a>
163           Integer <code class="function">find</code>
164         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.info"></a>
165             Description
166           </h6></div></div></div><p>This test inserts a number of values with uniform
167           integer keys into a container, then performs a series of finds
168           using <code class="function">find</code>. It measures the average time
169           for <code class="function">find</code> as a function of the number of values
170           inserted.</p><p>
171             It uses the test file:
172             <code class="filename">performance/ext/pb_ds/random_int_find_timing.cc</code>
173           </p><p>The test checks the effect of different underlying
174           hash-tables,
175           range-hashing functions, and trigger policies.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.results"></a>
176             Results
177           </h6></div></div></div><p>
178             There are two sets of results for this type, one for
179             collision-chaining hashes, and one for general-probe hashes.
180           </p><p>The first graphic below shows the results for the native and
181           collision-chaining hash types. The function applied being a random
182           integer timing test using <code class="function">find</code>.
183           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_find.png" align="middle" /></div></div><p>
184             The abbreviated names in the legend of the graphic above are
185             instantiated with the types in the following table.
186           </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">
187                     n_hash_map_ncah
188                   </td></tr><tr><td align="left">
189                     <code class="classname">std::tr1::unordered_map</code>
190                   </td><td align="left">
191                     <code class="classname">cache_hash_code</code>
192                   </td><td align="left">
193                     <code class="constant">false</code>
194                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
195                     cc_hash_mod_prime_1div1_nsth_map
196                   </td></tr><tr><td rowspan="3" align="left" valign="top">
197                     <code class="classname">cc_hash_table</code>
198                   </td><td align="left">
199                     <code class="classname">Comb_Hash_Fn</code>
200                   </td><td align="left">
201                     <code class="classname">direct_mod_range_hashing</code>
202                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
203                     <code class="classname">Resize_Policy</code>
204                   </td><td rowspan="2" align="left" valign="top">
205                     <code class="classname">hash_standard_resize_policy</code>
206                   </td><td align="left">
207                     <code class="classname">Size_Policy</code>
208                   </td><td align="left">
209                     <code class="classname">hash_prime_size_policy</code>
210                   </td></tr><tr><td align="left" valign="top">
211                     <code class="classname">Trigger_Policy</code>
212                   </td><td align="left">
213                     <code class="classname">hash_load_check_resize_trigger</code> with
214                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
215                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
216                     cc_hash_mod_prime_1div2_nsth_map
217                   </td></tr><tr><td rowspan="3" align="left" valign="top">
218                     <code class="classname">
219                       cc_hash_table
220                     </code>
221                   </td><td align="left">
222                     <code class="classname">Comb_Hash_Fn</code>
223                   </td><td align="left">
224                     <code class="classname">direct_mod_range_hashing</code>
225                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
226                     <code class="classname">Resize_Policy</code>
227                   </td><td rowspan="2" align="left" valign="top">
228                     <code class="classname">hash_standard_resize_policy</code>
229                   </td><td align="left">
230                     <code class="classname">Size_Policy</code>
231                   </td><td align="left">
232                     <code class="classname">hash_prime_size_policy</code>
233                   </td></tr><tr><td align="left" valign="top">
234                     <code class="classname">Trigger_Policy</code>
235                   </td><td align="left">
236                     <code class="classname">hash_load_check_resize_trigger</code> with
237                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
238                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
239                     cc_hash_mask_exp_1div1_nsth_map
240                   </td></tr><tr><td rowspan="3" align="left" valign="top">
241                     <code class="classname">cc_hash_table</code>
242                   </td><td align="left">
243                     <code class="classname">Comb_Hash_Fn</code>
244                   </td><td align="left">
245                     <code class="classname">direct_mask_range_hashing</code>
246                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
247                     <code class="classname">Resize_Policy</code>
248                   </td><td rowspan="2" align="left" valign="top">
249                     <code class="classname">hash_standard_resize_policy</code>
250                   </td><td align="left">
251                     <code class="classname">Size_Policy</code>
252                   </td><td align="left">
253                     <code class="classname">hash_exponential_size_policy</code>
254                   </td></tr><tr><td align="left" valign="top">
255                     <code class="classname">Trigger_Policy</code>
256                   </td><td align="left">
257                     <code class="classname">hash_load_check_resize_trigger</code> with
258                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
259                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
260                     cc_hash_mask_exp_1div2_nsth_map
261                   </td></tr><tr><td rowspan="3" align="left" valign="top">
262                     <code class="classname">cc_hash_table</code>
263                   </td><td align="left">
264                     <code class="classname">Comb_Hash_Fn</code>
265                   </td><td align="left">
266                     <code class="classname">direct_mask_range_hashing</code>
267                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
268                     <code class="classname">Resize_Policy</code>
269                   </td><td rowspan="2" align="left" valign="top">
270                     <code class="classname">hash_standard_resize_policy</code>
271                   </td><td align="left">
272                     <code class="classname">Size_Policy</code>
273                   </td><td align="left">
274                     <code class="classname">hash_exponential_size_policy</code>
275                   </td></tr><tr><td align="left" valign="top">
276                     <code class="classname">Trigger_Policy</code>
277                   </td><td align="left">
278                     <code class="classname">hash_load_check_resize_trigger</code> with
279                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
280                   </td></tr></tbody></table></div><p>
281           </p><p>
282           </p><p>And the second graphic shows the results for the native and
283           general-probe hash types. The function applied being a random
284           integer timing test using <code class="function">find</code>.
285           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_find.png" align="middle" /></div></div><p>
286             The abbreviated names in the legend of the graphic above are
287             instantiated with the types in the following table.
288           </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">
289                     n_hash_map_ncah
290                   </td></tr><tr><td align="left">
291                     <code class="classname">std::tr1::unordered_map</code>
292                   </td><td align="left">
293                     <code class="classname">cache_hash_code</code>
294                   </td><td align="left">
295                     <code class="constant">false</code>
296                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
297                     gp_hash_mod_quadp_prime_1div2_nsth_map
298                   </td></tr><tr><td rowspan="4" align="left" valign="top">
299                     <code class="classname">gp_hash_table</code>
300                   </td><td align="left">
301                     <code class="classname">Comb_Hash_Fn</code>
302                   </td><td align="left">
303                     <code class="classname">direct_mod_range_hashing</code>
304                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
305                     <code class="classname">Probe_Fn</code>
306                   </td><td align="left">
307                     <code class="classname">quadratic_probe_fn</code>
308                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
309                     <code class="classname">Resize_Policy</code>
310                   </td><td rowspan="2" align="left" valign="top">
311                     <code class="classname">hash_standard_resize_policy</code>
312                   </td><td align="left">
313                     <code class="classname">Size_Policy</code>
314                   </td><td align="left">
315                     <code class="classname">hash_prime_size_policy</code>
316                   </td></tr><tr><td align="left" valign="top">
317                     <code class="classname">Trigger_Policy</code>
318                   </td><td align="left">
319                     <code class="classname">hash_load_check_resize_trigger</code> with
320                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
321                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
322                     gp_hash_mask_linp_exp_1div2_nsth_map
323                   </td></tr><tr><td rowspan="4" align="left" valign="top">
324                     <code class="classname">
325                       gp_hash_table
326                     </code>
327                   </td><td align="left">
328                     <code class="classname">Comb_Hash_Fn</code>
329                   </td><td align="left">
330                     <code class="classname">direct_mask_range_hashing</code>
331                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
332                     <code class="classname">Probe_Fn</code>
333                   </td><td align="left">
334                     <code class="classname">linear_probe_fn</code>
335                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
336                     <code class="classname">Resize_Policy</code>
337                   </td><td rowspan="2" align="left" valign="top">
338                     <code class="classname">hash_standard_resize_policy</code>
339                   </td><td align="left">
340                     <code class="classname">Size_Policy</code>
341                   </td><td align="left">
342                     <code class="classname">hash_exponential_size_policy</code>
343                   </td></tr><tr><td align="left" valign="top">
344                     <code class="classname">Trigger_Policy</code>
345                   </td><td align="left">
346                     <code class="classname">hash_load_check_resize_trigger</code> with
347                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
348                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.observations"></a>
349             Observations
350           </h6></div></div></div><p>In this setting, the choice of underlying hash-table affects
351           performance most, then the range-hashing scheme and, only finally,
352           other policies.</p><p>When comparing probing and chaining containers, it is
353           apparent that the probing containers are less efficient than the
354           collision-chaining containers (
355           <code class="classname">std::tr1::unordered_map</code> uses
356           collision-chaining) in this case.</p><p>Hash-Based Integer Subscript Insert Timing Test shows
357           a different case, where the situation is reversed;
358           </p><p>Within each type of hash-table, the range-hashing scheme
359           affects performance more than other policies; Hash-Based Text
360           <code class="function">find</code> Find Timing Test also shows this. In the
361           above graphics should be noted that
362           <code class="classname">std::tr1::unordered_map</code> are hard-wired
363           currently to mod-based schemes.
364           </p></div></div><div class="section" title="Integer Subscript find"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_subscript_find"></a>
365           Integer Subscript <code class="function">find</code>
366         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.info"></a>
367             Description
368           </h6></div></div></div><p>This test inserts a number of values with uniform
369           integer keys into a container, then performs a series of finds
370           using <code class="function">operator[]</code>. It measures the average time
371           for <code class="function">operator[]</code> as a function of the number of
372           values inserted.</p><p>
373             It uses the test file:
374             <code class="filename">performance/ext/pb_ds/random_int_subscript_find_timing.cc</code>
375           </p><p>The test checks the effect of different underlying
376           hash-tables, range-hashing functions, and trigger policies.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.results"></a>
377             Results
378           </h6></div></div></div><p>
379             There are two sets of results for this type, one for
380             collision-chaining hashes, and one for general-probe hashes.
381           </p><p>The first graphic below shows the results for the native
382           and collision-chaining hash types, using as the function
383           applied an integer subscript timing test with
384           <code class="function">find</code>.
385           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_subscript_find.png" align="middle" /></div></div><p>
386             The abbreviated names in the legend of the graphic above are
387             instantiated with the types in the following table.
388           </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">
389                     n_hash_map_ncah
390                   </td></tr><tr><td align="left">
391                     <code class="classname">std::tr1::unordered_map</code>
392                   </td><td align="left">
393                     <code class="classname">cache_hash_code</code>
394                   </td><td align="left">
395                     <code class="constant">false</code>
396                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
397                     cc_hash_mod_prime_1div1_nsth_map
398                   </td></tr><tr><td rowspan="3" align="left" valign="top">
399                     <code class="classname">cc_hash_table</code>
400                   </td><td align="left">
401                     <code class="classname">Comb_Hash_Fn</code>
402                   </td><td align="left">
403                     <code class="classname">direct_mod_range_hashing</code>
404                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
405                     <code class="classname">Resize_Policy</code>
406                   </td><td rowspan="2" align="left" valign="top">
407                     <code class="classname">hash_standard_resize_policy</code>
408                   </td><td align="left">
409                     <code class="classname">Size_Policy</code>
410                   </td><td align="left">
411                     <code class="classname">hash_prime_size_policy</code>
412                   </td></tr><tr><td align="left" valign="top">
413                     <code class="classname">Trigger_Policy</code>
414                   </td><td align="left">
415                     <code class="classname">hash_load_check_resize_trigger</code> with
416                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
417                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
418                     cc_hash_mod_prime_1div2_nsth_map
419                   </td></tr><tr><td rowspan="3" align="left" valign="top">
420                     <code class="classname">cc_hash_table</code>
421                   </td><td align="left">
422                     <code class="classname">Comb_Hash_Fn</code>
423                   </td><td align="left">
424                     <code class="classname">direct_mod_range_hashing</code>
425                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
426                     <code class="classname">Resize_Policy</code>
427                   </td><td rowspan="2" align="left" valign="top">
428                     <code class="classname">hash_standard_resize_policy</code>
429                   </td><td align="left">
430                     <code class="classname">Size_Policy</code>
431                   </td><td align="left">
432                     <code class="classname">hash_prime_size_policy</code>
433                   </td></tr><tr><td align="left" valign="top">
434                     <code class="classname">Trigger_Policy</code>
435                   </td><td align="left">
436                     <code class="classname">hash_load_check_resize_trigger</code> with
437                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
438                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
439                     cc_hash_mask_exp_1div1_nsth_map
440                   </td></tr><tr><td rowspan="3" align="left" valign="top">
441                     <code class="classname">cc_hash_table</code>
442                   </td><td align="left">
443                     <code class="classname">Comb_Hash_Fn</code>
444                   </td><td align="left">
445                     <code class="classname">direct_mask_range_hashing</code>
446                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
447                     <code class="classname">Resize_Policy</code>
448                   </td><td rowspan="2" align="left" valign="top">
449                     <code class="classname">hash_standard_resize_policy</code>
450                   </td><td align="left">
451                     <code class="classname">Size_Policy</code>
452                   </td><td align="left">
453                     <code class="classname">hash_exponential_size_policy</code>
454                   </td></tr><tr><td align="left" valign="top">
455                     <code class="classname">Trigger_Policy</code>
456                   </td><td align="left">
457                     <code class="classname">hash_load_check_resize_trigger</code> with
458                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
459                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
460                     cc_hash_mask_exp_1div2_nsth_map
461                   </td></tr><tr><td rowspan="3" align="left" valign="top">
462                     <code class="classname">cc_hash_table</code>
463                   </td><td align="left">
464                     <code class="classname">Comb_Hash_Fn</code>
465                   </td><td align="left">
466                     <code class="classname">direct_mask_range_hashing</code>
467                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
468                     <code class="classname">Resize_Policy</code>
469                   </td><td rowspan="2" align="left" valign="top">
470                     <code class="classname">hash_standard_resize_policy</code>
471                   </td><td align="left">
472                     <code class="classname">Size_Policy</code>
473                   </td><td align="left">
474                     <code class="classname">hash_exponential_size_policy</code>
475                   </td></tr><tr><td align="left" valign="top">
476                     <code class="classname">Trigger_Policy</code>
477                   </td><td align="left">
478                     <code class="classname">hash_load_check_resize_trigger</code> with
479                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
480                   </td></tr></tbody></table></div><p>
481           </p><p>
482           </p><p>And the second graphic shows the results for the native and
483           general-probe hash types. The function applied being a random
484           integer timing test using <code class="function">find</code>.
485           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_subscript_find.png" align="middle" /></div></div><p>
486             The abbreviated names in the legend of the graphic above are
487             instantiated with the types in the following table.
488           </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">
489                     n_hash_map_ncah
490                   </td></tr><tr><td align="left">
491                     <code class="classname">std::tr1::unordered_map</code>
492                   </td><td align="left">
493                     <code class="classname">cache_hash_code</code>
494                   </td><td align="left">
495                     <code class="constant">false</code>
496                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
497                     gp_hash_mod_quadp_prime_1div2_nsth_map
498                   </td></tr><tr><td rowspan="4" align="left" valign="top">
499                     <code class="classname">gp_hash_table</code>
500                   </td><td align="left">
501                     <code class="classname">Comb_Hash_Fn</code>
502                   </td><td align="left">
503                     <code class="classname">direct_mod_range_hashing</code>
504                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
505                     <code class="classname">Probe_Fn</code>
506                   </td><td align="left">
507                     <code class="classname">quadratic_probe_fn</code>
508                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
509                     <code class="classname">Resize_Policy</code>
510                   </td><td rowspan="2" align="left" valign="top">
511                     <code class="classname">hash_standard_resize_policy</code>
512                   </td><td align="left">
513                     <code class="classname">Size_Policy</code>
514                   </td><td align="left">
515                     <code class="classname">hash_prime_size_policy</code>
516                   </td></tr><tr><td align="left" valign="top">
517                     <code class="classname">Trigger_Policy</code>
518                   </td><td align="left">
519                     <code class="classname">hash_load_check_resize_trigger</code> with
520                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
521                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
522                     gp_hash_mask_linp_exp_1div2_nsth_map
523                   </td></tr><tr><td rowspan="4" align="left" valign="top">
524                     <code class="classname">
525                       gp_hash_table
526                     </code>
527                   </td><td align="left">
528                     <code class="classname">Comb_Hash_Fn</code>
529                   </td><td align="left">
530                     <code class="classname">direct_mask_range_hashing</code>
531                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
532                     <code class="classname">Probe_Fn</code>
533                   </td><td align="left">
534                     <code class="classname">linear_probe_fn</code>
535                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
536                     <code class="classname">Resize_Policy</code>
537                   </td><td rowspan="2" align="left" valign="top">
538                     <code class="classname">hash_standard_resize_policy</code>
539                   </td><td align="left">
540                     <code class="classname">Size_Policy</code>
541                   </td><td align="left">
542                     <code class="classname">hash_exponential_size_policy</code>
543                   </td></tr><tr><td align="left" valign="top">
544                     <code class="classname">Trigger_Policy</code>
545                   </td><td align="left">
546                     <code class="classname">hash_load_check_resize_trigger</code> with
547                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
548                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.observations"></a>
549             Observations
550           </h6></div></div></div><p>This test shows similar results to Hash-Based
551           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 id="performance.hash.int_subscript_insert"></a>
552           Integer Subscript <code class="function">insert</code>
553         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.info"></a>
554             Description
555           </h6></div></div></div><p>This test inserts a number of values with uniform i.i.d.
556           integer keys into a container, using
557           <code class="function">operator[]</code>. It measures the average time for
558           <code class="function">operator[]</code> as a function of the number of
559           values inserted.</p><p>
560             It uses the test file:
561             <code class="filename">performance/ext/pb_ds/random_int_subscript_insert_timing.cc</code>
562           </p><p>The test checks the effect of different underlying
563           hash-tables.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.results"></a>
564             Results
565           </h6></div></div></div><p>
566             There are two sets of results for this type, one for
567             collision-chaining hashes, and one for general-probe hashes.
568           </p><p>The first graphic below shows the results for the native
569           and collision-chaining hash types, using as the function
570           applied an integer subscript timing test with
571           <code class="function">insert</code>.
572           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_subscript_insert.png" align="middle" /></div></div><p>
573             The abbreviated names in the legend of the graphic above are
574             instantiated with the types in the following table.
575           </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">
576                     n_hash_map_ncah
577                   </td></tr><tr><td align="left">
578                     <code class="classname">std::tr1::unordered_map</code>
579                   </td><td align="left">
580                     <code class="classname">cache_hash_code</code>
581                   </td><td align="left">
582                     <code class="constant">false</code>
583                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
584                     cc_hash_mod_prime_1div1_nsth_map
585                   </td></tr><tr><td rowspan="3" align="left" valign="top">
586                     <code class="classname">cc_hash_table</code>
587                   </td><td align="left">
588                     <code class="classname">Comb_Hash_Fn</code>
589                   </td><td align="left">
590                     <code class="classname">direct_mod_range_hashing</code>
591                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
592                     <code class="classname">Resize_Policy</code>
593                   </td><td rowspan="2" align="left" valign="top">
594                     <code class="classname">hash_standard_resize_policy</code>
595                   </td><td align="left">
596                     <code class="classname">Size_Policy</code>
597                   </td><td align="left">
598                     <code class="classname">hash_prime_size_policy</code>
599                   </td></tr><tr><td align="left" valign="top">
600                     <code class="classname">Trigger_Policy</code>
601                   </td><td align="left">
602                     <code class="classname">hash_load_check_resize_trigger</code> with
603                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
604                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
605                     cc_hash_mod_prime_1div2_nsth_map
606                   </td></tr><tr><td rowspan="3" align="left" valign="top">
607                     <code class="classname">cc_hash_table</code>
608                   </td><td align="left">
609                     <code class="classname">Comb_Hash_Fn</code>
610                   </td><td align="left">
611                     <code class="classname">direct_mod_range_hashing</code>
612                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
613                     <code class="classname">Resize_Policy</code>
614                   </td><td rowspan="2" align="left" valign="top">
615                     <code class="classname">hash_standard_resize_policy</code>
616                   </td><td align="left">
617                     <code class="classname">Size_Policy</code>
618                   </td><td align="left">
619                     <code class="classname">hash_prime_size_policy</code>
620                   </td></tr><tr><td align="left" valign="top">
621                     <code class="classname">Trigger_Policy</code>
622                   </td><td align="left">
623                     <code class="classname">hash_load_check_resize_trigger</code> with
624                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
625                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
626                     cc_hash_mask_exp_1div1_nsth_map
627                   </td></tr><tr><td rowspan="3" align="left" valign="top">
628                     <code class="classname">cc_hash_table</code>
629                   </td><td align="left">
630                     <code class="classname">Comb_Hash_Fn</code>
631                   </td><td align="left">
632                     <code class="classname">direct_mask_range_hashing</code>
633                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
634                     <code class="classname">Resize_Policy</code>
635                   </td><td rowspan="2" align="left" valign="top">
636                     <code class="classname">hash_standard_resize_policy</code>
637                   </td><td align="left">
638                     <code class="classname">Size_Policy</code>
639                   </td><td align="left">
640                     <code class="classname">hash_exponential_size_policy</code>
641                   </td></tr><tr><td align="left" valign="top">
642                     <code class="classname">Trigger_Policy</code>
643                   </td><td align="left">
644                     <code class="classname">hash_load_check_resize_trigger</code> with
645                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
646                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
647                     cc_hash_mask_exp_1div2_nsth_map
648                   </td></tr><tr><td rowspan="3" align="left" valign="top">
649                     <code class="classname">cc_hash_table</code>
650                   </td><td align="left">
651                     <code class="classname">Comb_Hash_Fn</code>
652                   </td><td align="left">
653                     <code class="classname">direct_mask_range_hashing</code>
654                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
655                     <code class="classname">Resize_Policy</code>
656                   </td><td rowspan="2" align="left" valign="top">
657                     <code class="classname">hash_standard_resize_policy</code>
658                   </td><td align="left">
659                     <code class="classname">Size_Policy</code>
660                   </td><td align="left">
661                     <code class="classname">hash_exponential_size_policy</code>
662                   </td></tr><tr><td align="left" valign="top">
663                     <code class="classname">Trigger_Policy</code>
664                   </td><td align="left">
665                     <code class="classname">hash_load_check_resize_trigger</code> with
666                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
667                   </td></tr></tbody></table></div><p>
668           </p><p>
669           </p><p>And the second graphic shows the results for the native and
670           general-probe hash types. The function applied being a random
671           integer timing test using <code class="function">find</code>.
672           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_subscript_insert.png" align="middle" /></div></div><p>
673             The abbreviated names in the legend of the graphic above are
674             instantiated with the types in the following table.
675           </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">
676                     n_hash_map_ncah
677                   </td></tr><tr><td align="left">
678                     <code class="classname">std::tr1::unordered_map</code>
679                   </td><td align="left">
680                     <code class="classname">cache_hash_code</code>
681                   </td><td align="left">
682                     <code class="constant">false</code>
683                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
684                     gp_hash_mod_quadp_prime_1div2_nsth_map
685                   </td></tr><tr><td rowspan="4" align="left" valign="top">
686                     <code class="classname">gp_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_mod_range_hashing</code>
691                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
692                     <code class="classname">Probe_Fn</code>
693                   </td><td align="left">
694                     <code class="classname">quadratic_probe_fn</code>
695                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
696                     <code class="classname">Resize_Policy</code>
697                   </td><td rowspan="2" align="left" valign="top">
698                     <code class="classname">hash_standard_resize_policy</code>
699                   </td><td align="left">
700                     <code class="classname">Size_Policy</code>
701                   </td><td align="left">
702                     <code class="classname">hash_prime_size_policy</code>
703                   </td></tr><tr><td align="left" valign="top">
704                     <code class="classname">Trigger_Policy</code>
705                   </td><td align="left">
706                     <code class="classname">hash_load_check_resize_trigger</code> with
707                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
708                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
709                     gp_hash_mask_linp_exp_1div2_nsth_map
710                   </td></tr><tr><td rowspan="4" align="left" valign="top">
711                     <code class="classname">
712                       gp_hash_table
713                     </code>
714                   </td><td align="left">
715                     <code class="classname">Comb_Hash_Fn</code>
716                   </td><td align="left">
717                     <code class="classname">direct_mask_range_hashing</code>
718                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
719                     <code class="classname">Probe_Fn</code>
720                   </td><td align="left">
721                     <code class="classname">linear_probe_fn</code>
722                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
723                     <code class="classname">Resize_Policy</code>
724                   </td><td rowspan="2" align="left" valign="top">
725                     <code class="classname">hash_standard_resize_policy</code>
726                   </td><td align="left">
727                     <code class="classname">Size_Policy</code>
728                   </td><td align="left">
729                     <code class="classname">hash_exponential_size_policy</code>
730                   </td></tr><tr><td align="left" valign="top">
731                     <code class="classname">Trigger_Policy</code>
732                   </td><td align="left">
733                     <code class="classname">hash_load_check_resize_trigger</code> with
734                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
735                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.observations"></a>
736             Observations
737           </h6></div></div></div><p>In this setting, as in Hash-Based Text
738           <code class="function">find</code> Find Timing test and Hash-Based
739           Integer <code class="function">find</code> Find Timing test , the choice
740           of underlying hash-table underlying hash-table affects performance
741           most, then the range-hashing scheme, and
742           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
743             efficiently than collision-chaining tables.
744             This is explained shortly.</p></li><li class="listitem"><p>The performance graphs have a "saw-tooth" shape. The
745             average insert time rises and falls. As values are inserted
746             into the container, the load factor grows larger. Eventually,
747             a resize occurs. The reallocations and rehashing are
748             relatively expensive. After this, the load factor is smaller
749             than before.</p></li></ol></div><p>Collision-chaining containers use indirection for greater
750           flexibility; probing containers store values contiguously, in
751           an array (see Figure Motivation::Different
752           underlying data structures A and B, respectively). It
753           follows that for simple data types, probing containers access
754           their allocator less frequently than collision-chaining
755           containers, (although they still have less efficient probing
756           sequences). This explains why some probing containers fare
757           better than collision-chaining containers in this case.</p><p>
758             Within each type of hash-table, the range-hashing scheme affects
759             performance more than other policies. This is similar to the
760             situation in Hash-Based Text
761             <code class="function">find</code> Find Timing Test and Hash-Based
762             Integer <code class="function">find</code> Find Timing Test.
763             Unsurprisingly, however, containers with lower α<sub>max</sub> perform worse in this case,
764           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 id="performance.hash.zlob_int_find"></a>
765           Integer <code class="function">find</code> with Skewed-Distribution
766         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.info"></a>
767             Description
768           </h6></div></div></div><p>This test inserts a number of values with a markedly
769           non-uniform integer keys into a container, then performs
770           a series of finds using <code class="function">find</code>. It measures the average
771           time for <code class="function">find</code> as a function of the number of values in
772           the containers. The keys are generated as follows. First, a
773           uniform integer is created. Then it is then shifted left 8 bits.</p><p>
774             It uses the test file:
775             <code class="filename">performance/ext/pb_ds/hash_zlob_random_int_find_timing.cc</code>
776           </p><p>The test checks the effect of different range-hashing
777           functions and trigger policies.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.results"></a>
778             Results
779           </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
780           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_zlob_int_find.png" align="middle" /></div></div><p>
781             The abbreviated names in the legend of the graphic above are
782             instantiated with the types in the following table.
783           </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">
784                     n_hash_map_ncah
785                   </td></tr><tr><td align="left">
786                     <code class="classname">std::tr1::unordered_map</code>
787                   </td><td align="left">
788                     <code class="classname">cache_hash_code</code>
789                   </td><td align="left">
790                     <code class="constant">false</code>
791                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
792                     cc_hash_mod_prime_1div1_nsth_map
793                   </td></tr><tr><td rowspan="3" align="left" valign="top">
794                     <code class="classname">cc_hash_table</code>
795                   </td><td align="left">
796                     <code class="classname">Comb_Hash_Fn</code>
797                   </td><td align="left">
798                     <code class="classname">direct_mod_range_hashing</code>
799                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
800                     <code class="classname">Resize_Policy</code>
801                   </td><td rowspan="2" align="left" valign="top">
802                     <code class="classname">hash_standard_resize_policy</code>
803                   </td><td align="left">
804                     <code class="classname">Size_Policy</code>
805                   </td><td align="left">
806                     <code class="classname">hash_prime_size_policy</code>
807                   </td></tr><tr><td align="left" valign="top">
808                     <code class="classname">Trigger_Policy</code>
809                   </td><td align="left">
810                     <code class="classname">hash_load_check_resize_trigger</code> with
811                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
812                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
813                     cc_hash_mask_exp_1div1_nsth_map
814                   </td></tr><tr><td rowspan="3" align="left" valign="top">
815                     <code class="classname">
816                       cc_hash_table
817                     </code>
818                   </td><td align="left">
819                     <code class="classname">Comb_Hash_Fn</code>
820                   </td><td align="left">
821                     <code class="classname">direct_mask_range_hashing</code>
822                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
823                     <code class="classname">Resize_Policy</code>
824                   </td><td rowspan="2" align="left" valign="top">
825                     <code class="classname">hash_standard_resize_policy</code>
826                   </td><td align="left">
827                     <code class="classname">Size_Policy</code>
828                   </td><td align="left">
829                     <code class="classname">hash_exponential_size_policy</code>
830                   </td></tr><tr><td align="left" valign="top">
831                     <code class="classname">Trigger_Policy</code>
832                   </td><td align="left">
833                     <code class="classname">hash_load_check_resize_trigger</code> with
834                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
835                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
836                     gp_hash_mod_quadp_prime_1div2_nsth_map
837                   </td></tr><tr><td rowspan="4" align="left" valign="top">
838                     <code class="classname">gp_hash_table</code>
839                   </td><td align="left">
840                     <code class="classname">Comb_Hash_Fn</code>
841                   </td><td align="left">
842                     <code class="classname">direct_mod_range_hashing</code>
843                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
844                     <code class="classname">Probe_Fn</code>
845                   </td><td align="left">
846                     <code class="classname">quadratic_probe_fn</code>
847                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
848                     <code class="classname">Resize_Policy</code>
849                   </td><td rowspan="2" align="left" valign="top">
850                     <code class="classname">hash_standard_resize_policy</code>
851                   </td><td align="left">
852                     <code class="classname">Size_Policy</code>
853                   </td><td align="left">
854                     <code class="classname">hash_prime_size_policy</code>
855                   </td></tr><tr><td align="left" valign="top">
856                     <code class="classname">Trigger_Policy</code>
857                   </td><td align="left">
858                     <code class="classname">hash_load_check_resize_trigger</code> with
859                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
860                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.observations"></a>
861             Observations
862           </h6></div></div></div><p>In this setting, the distribution of keys is so skewed that
863           the underlying hash-table type affects performance marginally.
864           (This is in contrast with Hash-Based Text
865           <code class="function">find</code> Find Timing Test, Hash-Based
866           Integer <code class="function">find</code> Find Timing Test, Hash-Based
867           Integer Subscript Find Timing Test and Hash-Based
868           Integer Subscript Insert Timing Test.)</p><p>The range-hashing scheme affects performance dramatically. A
869           mask-based range-hashing scheme effectively maps all values
870           into the same bucket. Access degenerates into a search within
871           an unordered linked-list. In the graphic above, it should be noted that
872           <code class="classname">std::tr1::unordered_map</code> is hard-wired currently to mod-based and mask-based schemes,
873           respectively.</p><p>When observing the settings of this test, it is apparent
874           that the keys' distribution is far from natural. One might ask
875           if the test is not contrived to show that, in some cases,
876           mod-based range hashing does better than mask-based range
877           hashing. This is, in fact just the case. A
878           more natural case in which mod-based range hashing is better was not encountered.
879           Thus the inescapable conclusion: real-life key distributions are handled better
880           with an appropriate hash function and a mask-based
881           range-hashing function. (<code class="filename">pb_ds/example/hash_shift_mask.cc</code>
882           shows an example of handling this a-priori known skewed
883           distribution with a mask-based range-hashing function). If hash
884           performance is bad, a χ<sup>2</sup> test can be used
885           to check how to transform it into a more uniform
886           distribution.</p><p>For this reason, this library's default range-hashing
887           function is mask-based.</p></div></div><div class="section" title="Erase Memory Use"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.erase_mem"></a>
888           Erase Memory Use
889         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.info"></a>
890             Description
891           </h6></div></div></div><p>This test inserts a number of uniform integer keys
892           into a container, then erases all keys except one. It measures
893           the final size of the container.</p><p>
894             It uses the test file:
895             <code class="filename">performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc</code>
896           </p><p>The test checks how containers adjust internally as their
897           logical size decreases.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.results"></a>
898             Results
899           </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
900           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_int_erase_mem.png" align="middle" /></div></div><p>
901             The abbreviated names in the legend of the graphic above are
902             instantiated with the types in the following table.
903           </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">
904                     n_hash_map_ncah
905                   </td></tr><tr><td align="left">
906                     <code class="classname">std::tr1::unordered_map</code>
907                   </td><td align="left">
908                     <code class="classname">cache_hash_code</code>
909                   </td><td align="left">
910                     <code class="constant">false</code>
911                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
912                     cc_hash_mod_prime_1div1_nsth_map
913                   </td></tr><tr><td rowspan="3" align="left" valign="top">
914                     <code class="classname">cc_hash_table</code>
915                   </td><td align="left">
916                     <code class="classname">Comb_Hash_Fn</code>
917                   </td><td align="left">
918                     <code class="classname">direct_mod_range_hashing</code>
919                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
920                     <code class="classname">Resize_Policy</code>
921                   </td><td rowspan="2" align="left" valign="top">
922                     <code class="classname">hash_standard_resize_policy</code>
923                   </td><td align="left">
924                     <code class="classname">Size_Policy</code>
925                   </td><td align="left">
926                     <code class="classname">hash_prime_size_policy</code>
927                   </td></tr><tr><td align="left" valign="top">
928                     <code class="classname">Trigger_Policy</code>
929                   </td><td align="left">
930                     <code class="classname">hash_load_check_resize_trigger</code> with
931                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
932                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
933                     cc_hash_mask_exp_1div2_nsth_map
934                   </td></tr><tr><td rowspan="3" align="left" valign="top">
935                     <code class="classname">
936                       cc_hash_table
937                     </code>
938                   </td><td align="left">
939                     <code class="classname">Comb_Hash_Fn</code>
940                   </td><td align="left">
941                     <code class="classname">direct_mask_range_hashing</code>
942                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
943                     <code class="classname">Resize_Policy</code>
944                   </td><td rowspan="2" align="left" valign="top">
945                     <code class="classname">hash_standard_resize_policy</code>
946                   </td><td align="left">
947                     <code class="classname">Size_Policy</code>
948                   </td><td align="left">
949                     <code class="classname">hash_exponential_size_policy</code>
950                   </td></tr><tr><td align="left" valign="top">
951                     <code class="classname">Trigger_Policy</code>
952                   </td><td align="left">
953                     <code class="classname">hash_load_check_resize_trigger</code> with
954                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
955                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
956                     gp_hash_mask_linp_exp_1div2_nsth_set
957                   </td></tr><tr><td rowspan="4" align="left" valign="top">
958                     <code class="classname">gp_hash_table</code>
959                   </td><td align="left">
960                     <code class="classname">Comb_Hash_Fn</code>
961                   </td><td align="left">
962                     <code class="classname">direct_mask_range_hashing</code>
963                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
964                     <code class="classname">Probe_Fn</code>
965                   </td><td align="left">
966                     <code class="classname">linear_probe_fn</code>
967                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
968                     <code class="classname">Resize_Policy</code>
969                   </td><td rowspan="2" align="left" valign="top">
970                     <code class="classname">hash_standard_resize_policy</code>
971                   </td><td align="left">
972                     <code class="classname">Size_Policy</code>
973                   </td><td align="left">
974                     <code class="classname">hash_exponential_size_policy</code>
975                   </td></tr><tr><td align="left" valign="top">
976                     <code class="classname">Trigger_Policy</code>
977                   </td><td align="left">
978                     <code class="classname">hash_load_check_resize_trigger</code> with
979                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
980                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.observations"></a>
981             Observations
982           </h6></div></div></div><p>The standard's hash-based containers act very differently than trees in
983           this respect. When erasing numerous keys from an standard
984           associative-container, the resulting memory user varies greatly
985           depending on whether the container is tree-based or hash-based.
986           This is a fundamental consequence of the standard's interface for
987           associative containers, and it is not due to a specific
988           implementation.</p></div></div></div><div class="section" title="Branch-Based"><div class="titlepage"><div><div><h4 class="title"><a id="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 id="performance.branch.text_insert"></a>
989           Text <code class="function">insert</code>
990         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.info"></a>
991             Description
992           </h6></div></div></div><p>This test inserts a number of values with keys from an arbitrary
993           text ([ wickland96thirty ]) into a container
994           using <code class="function">insert</code> . It measures the average time
995           for <code class="function">insert</code> as a function of the number of
996           values inserted.</p><p>The test checks the effect of different underlying
997           data structures.</p><p>
998             It uses the test file:
999             <code class="filename">performance/ext/pb_ds/tree_text_insert_timing.cc</code>
1000           </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.results"></a>
1001             Results
1002           </h6></div></div></div><p>The three graphics below show the results for the native
1003           tree and this library's node-based trees, the native tree and
1004           this library's vector-based trees, and the native tree
1005           and this library's PATRICIA-trie, respectively.
1006           </p><p>The graphic immediately below shows the results for the
1007           native tree type and several node-based tree types.
1008           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_node.png" align="middle" /></div><p>
1009               The abbreviated names in the legend of the graphic above are
1010               instantiated with the types in the following table.
1011             </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">
1012                     n_map
1013                   </td></tr><tr><td align="left">
1014                     <code class="classname">std::map</code>
1015                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1016                     splay_tree_map
1017                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1018                     <code class="classname">tree</code>
1019                   </td><td align="left">
1020                     <code class="classname">Tag</code>
1021                   </td><td align="left">
1022                     <code class="classname">splay_tree_tag</code>
1023                   </td></tr><tr><td align="left">
1024                     <code class="classname">Node_update</code>
1025                   </td><td align="left">
1026                     <code class="classname">null_node_update</code>
1027                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1028                     rb_tree_map
1029                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1030                     <code class="classname">tree</code>
1031                   </td><td align="left">
1032                     <code class="classname">Tag</code>
1033                   </td><td align="left">
1034                     <code class="classname">rb_tree_tag</code>
1035                   </td></tr><tr><td align="left">
1036                     <code class="classname">Node_update</code>
1037                   </td><td align="left">
1038                     <code class="classname">null_node_update</code>
1039                   </td></tr></tbody></table></div><p>The graphic below shows the results for the
1040           native tree type and a vector-based tree type.
1041           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_vector.png" align="middle" /></div></div><p>
1042             The abbreviated names in the legend of the graphic above are
1043             instantiated with the types in the following table.
1044           </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">
1045                     n_map
1046                   </td></tr><tr><td align="left">
1047                     <code class="classname">std::map</code>
1048                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1049                     ov_tree_map
1050                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1051                     <code class="classname">tree</code>
1052                   </td><td align="left">
1053                     <code class="classname">Tag</code>
1054                   </td><td align="left">
1055                     <code class="classname">ov_tree_tag</code>
1056                   </td></tr><tr><td align="left">
1057                     <code class="classname">Node_update</code>
1058                   </td><td align="left">
1059                     <code class="classname">null_node_update</code>
1060                   </td></tr></tbody></table></div><p>The graphic below shows the results for the
1061           native tree type and a PATRICIA trie type.
1062           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_trie.png" align="middle" /></div></div><p>
1063             The abbreviated names in the legend of the graphic above are
1064             instantiated with the types in the following table.
1065           </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">
1066                     n_map
1067                   </td></tr><tr><td align="left">
1068                     <code class="classname">std::map</code>
1069                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1070                     pat_trie_map
1071                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1072                     <code class="classname">tree</code>
1073                   </td><td align="left">
1074                     <code class="classname">Tag</code>
1075                   </td><td align="left">
1076                     <code class="classname">pat_trie_tag</code>
1077                   </td></tr><tr><td align="left">
1078                     <code class="classname">Node_update</code>
1079                   </td><td align="left">
1080                     <code class="classname">null_node_update</code>
1081                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.observations"></a>
1082             Observations
1083           </h6></div></div></div><p>Observing the first graphic implies that for this setting, a splay tree
1084           (<code class="classname">tree</code> with <code class="classname">Tag
1085           </code> = <code class="classname">splay_tree_tag</code>) does not do
1086           well. See also the Branch-Based
1087           Text <code class="function">find</code> Find Timing Test. The two
1088           red-black trees perform better.</p><p>Observing the second graphic, an ordered-vector tree
1089           (<code class="classname">tree</code> with <code class="classname">Tag
1090           </code> = <code class="classname">ov_tree_tag</code>) performs
1091           abysmally. Inserting into this type of tree has linear complexity
1092           [ austern00noset].</p><p>Observing the third and last graphic, A PATRICIA trie
1093           (<code class="classname">trie</code> with <code class="classname">Tag
1094           </code> = <code class="classname">pat_trie_tag</code>) has abysmal
1095           performance, as well. This is not that surprising, since a
1096           large-fan-out PATRICIA trie works like a hash table with
1097           collisions resolved by a sub-trie. Each time a collision is
1098           encountered, a new "hash-table" is built A large fan-out PATRICIA
1099           trie, however, doe does well in look-ups (see Branch-Based
1100           Text <code class="function">find</code> Find Timing Test). It may be
1101           beneficial in semi-static settings.</p></div></div><div class="section" title="Text find"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_find"></a>
1102           Text <code class="function">find</code>
1103         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.info"></a>
1104             Description
1105           </h6></div></div></div><p>This test inserts a number of values with keys from an
1106           arbitrary text ([wickland96thirty]) into
1107           a container, then performs a series of finds using
1108           <code class="function">find</code>. It measures the average time
1109           for <code class="function">find</code> as a function of the number of
1110           values inserted.</p><p>
1111             It uses the test file:
1112             <code class="filename">performance/ext/pb_ds/text_find_timing.cc</code>
1113           </p><p>The test checks the effect of different underlying
1114           data structures.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.results"></a>
1115             Results
1116           </h6></div></div></div><p>The graphic immediately below shows the results for the
1117           native tree type and several other tree types.
1118           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_find.png" align="middle" /></div></div><p>
1119             The abbreviated names in the legend of the graphic above are
1120             instantiated with the types in the following table.
1121           </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">
1122                     n_map
1123                   </td></tr><tr><td align="left">
1124                     <code class="classname">std::map</code>
1125                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1126                     splay_tree_map
1127                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1128                     <code class="classname">tree</code>
1129                   </td><td align="left">
1130                     <code class="classname">Tag</code>
1131                   </td><td align="left">
1132                     <code class="classname">splay_tree_tag</code>
1133                   </td></tr><tr><td align="left">
1134                     <code class="classname">Node_Update</code>
1135                   </td><td align="left">
1136                     <code class="classname">null_node_update</code>
1137                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1138                     rb_tree_map
1139                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1140                     <code class="classname">tree</code>
1141                   </td><td align="left">
1142                     <code class="classname">Tag</code>
1143                   </td><td align="left">
1144                     <code class="classname">rb_tree_tag</code>
1145                   </td></tr><tr><td align="left">
1146                     <code class="classname">Node_Update</code>
1147                   </td><td align="left">
1148                     <code class="classname">null_node_update</code>
1149                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1150                     ov_tree_map
1151                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1152                     <code class="classname">tree</code>
1153                   </td><td align="left">
1154                     <code class="classname">Tag</code>
1155                   </td><td align="left">
1156                     <code class="classname">ov_tree_tag</code>
1157                   </td></tr><tr><td align="left">
1158                     <code class="classname">Node_Update</code>
1159                   </td><td align="left">
1160                     <code class="classname">null_node_update</code>
1161                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1162                     pat_trie_map
1163                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1164                     <code class="classname">tree</code>
1165                   </td><td align="left">
1166                     <code class="classname">Tag</code>
1167                   </td><td align="left">
1168                     <code class="classname">pat_trie_tag</code>
1169                   </td></tr><tr><td align="left">
1170                     <code class="classname">Node_Update</code>
1171                   </td><td align="left">
1172                     <code class="classname">null_node_update</code>
1173                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.observations"></a>
1174             Observations
1175           </h6></div></div></div><p>For this setting, a splay tree (<code class="classname">tree</code>
1176           with <code class="classname">Tag
1177           </code> = <code class="classname">splay_tree_tag</code>) does not do
1178           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
1179             splay tree contains n nodes, its average root-leaf
1180             path can be m &gt;&gt; log(n).</p></li><li class="listitem"><p>Assume a specific root-leaf search path has length
1181             m, and the search-target node has distance m'
1182             from the root. A red-black tree will require m + 1
1183             comparisons to find the required node; a splay tree will
1184             require 2 m' comparisons. A splay tree, consequently,
1185             can perform many more comparisons than a red-black tree.</p></li></ol></div><p>An ordered-vector tree (<code class="classname">tree</code>
1186           with <code class="classname">Tag</code> =  <code class="classname">ov_tree_tag</code>), a red-black
1187           tree (<code class="classname">tree</code>
1188           with <code class="classname">Tag</code>  = <code class="classname">rb_tree_tag</code>), and the
1189           native red-black tree all share approximately the same
1190           performance.</p><p>An ordered-vector tree is slightly slower than red-black
1191           trees, since it requires, in order to find a key, more math
1192           operations than they do. Conversely, an ordered-vector tree
1193           requires far lower space than the others. ([austern00noset], however,
1194           seems to have an implementation that is also faster than a
1195           red-black tree).</p><p>A PATRICIA trie (<code class="classname">trie</code>
1196           with <code class="classname">Tag</code> = <code class="classname">pat_trie_tag</code>) has good
1197           look-up performance, due to its large fan-out in this case. In
1198           this setting, a PATRICIA trie has look-up performance comparable
1199           to a hash table (see Hash-Based Text
1200           <code class="classname">find</code> Timing Test), but it is order
1201           preserving. This is not that surprising, since a large-fan-out
1202           PATRICIA trie works like a hash table with collisions resolved
1203           by a sub-trie. A large-fan-out PATRICIA trie does not do well on
1204           modifications (see Tree-Based and Trie-Based
1205           Text Insert Timing Test). Therefore, it is possibly beneficial in
1206           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 id="performance.branch.text_lor_find"></a>
1207           Text <code class="function">find</code> with Locality-of-Reference
1208         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.info"></a>
1209             Description
1210           </h6></div></div></div><p>This test inserts a number of values with keys from an
1211           arbitrary text ([ wickland96thirty ]) into
1212           a container, then performs a series of finds using
1213           <code class="function">find</code>. It is different than Tree-Based and
1214           Trie-Based Text <code class="function">find</code> Find Timing Test in the
1215           sequence of finds it performs: this test performs multiple
1216           <code class="function">find</code>s on the same key before moving on to the next
1217           key. It measures the average time for <code class="function">find</code> as a
1218           function of the number of values inserted.</p><p>
1219             It uses the test file:
1220             <code class="filename">performance/ext/pb_ds/tree_text_lor_find_timing.cc</code>
1221           </p><p>The test checks the effect of different underlying
1222           data structures in a locality-of-reference setting.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.results"></a>
1223             Results
1224           </h6></div></div></div><p>The graphic immediately below shows the results for the
1225           native tree type and several other tree types.
1226           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_lor_find.png" align="middle" /></div></div><p>
1227             The abbreviated names in the legend of the graphic above are
1228             instantiated with the types in the following table.
1229           </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">
1230                     n_map
1231                   </td></tr><tr><td align="left">
1232                     <code class="classname">std::map</code>
1233                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1234                     splay_tree_map
1235                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1236                     <code class="classname">tree</code>
1237                   </td><td align="left">
1238                     <code class="classname">Tag</code>
1239                   </td><td align="left">
1240                     <code class="classname">splay_tree_tag</code>
1241                   </td></tr><tr><td align="left">
1242                     <code class="classname">Node_Update</code>
1243                   </td><td align="left">
1244                     <code class="classname">null_node_update</code>
1245                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1246                     rb_tree_map
1247                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1248                     <code class="classname">tree</code>
1249                   </td><td align="left">
1250                     <code class="classname">Tag</code>
1251                   </td><td align="left">
1252                     <code class="classname">rb_tree_tag</code>
1253                   </td></tr><tr><td align="left">
1254                     <code class="classname">Node_Update</code>
1255                   </td><td align="left">
1256                     <code class="classname">null_node_update</code>
1257                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1258                     ov_tree_map
1259                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1260                     <code class="classname">tree</code>
1261                   </td><td align="left">
1262                     <code class="classname">Tag</code>
1263                   </td><td align="left">
1264                     <code class="classname">ov_tree_tag</code>
1265                   </td></tr><tr><td align="left">
1266                     <code class="classname">Node_Update</code>
1267                   </td><td align="left">
1268                     <code class="classname">null_node_update</code>
1269                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1270                     pat_trie_map
1271                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1272                     <code class="classname">tree</code>
1273                   </td><td align="left">
1274                     <code class="classname">Tag</code>
1275                   </td><td align="left">
1276                     <code class="classname">pat_trie_tag</code>
1277                   </td></tr><tr><td align="left">
1278                     <code class="classname">Node_Update</code>
1279                   </td><td align="left">
1280                     <code class="classname">null_node_update</code>
1281                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.observations"></a>
1282             Observations
1283           </h6></div></div></div><p>For this setting, an ordered-vector tree
1284           (<code class="classname">tree</code> with <code class="classname">Tag</code>
1285           = <code class="classname">ov_tree_tag</code>), a red-black tree
1286           (<code class="classname">tree</code> with <code class="classname">Tag</code>
1287           = <code class="classname">rb_tree_tag</code>), and the native red-black
1288           tree all share approximately the same performance.</p><p>A splay tree (<code class="classname">tree</code>
1289           with <code class="classname">Tag</code> = <code class="classname">splay_tree_tag</code>) does
1290           much better, since each (successful) find "bubbles" the
1291           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 id="performance.branch.split_join"></a>
1292           <code class="function">split</code> and <code class="function">join</code>
1293         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.info"></a>
1294             Description
1295           </h6></div></div></div><p>This test a container, inserts into a number of values, splits
1296           the container at the median, and joins the two containers. (If the
1297           containers are one of this library's trees,
1298           it splits and joins with the <code class="function">split</code> and
1299           <code class="function">join</code> method; otherwise, it uses the <code class="function">erase</code> and
1300           <code class="function">insert</code> methods.) It measures the time for splitting
1301           and joining the containers as a function of the number of
1302           values inserted.</p><p>
1303             It uses the test file:
1304             <code class="filename">performance/ext/pb_ds/tree_split_join_timing.cc</code>
1305           </p><p>The test checks the performance difference of <code class="function">join</code>
1306           as opposed to a sequence of <code class="function">insert</code> operations; by
1307           implication, this test checks the most efficient way to erase a
1308           sub-sequence from a tree-like-based container, since this can
1309           always be performed by a small sequence of splits and joins.
1310           </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.results"></a>
1311             Results
1312           </h6></div></div></div><p>The graphic immediately below shows the results for the
1313           native tree type and several other tree types.
1314           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_split_join.png" align="middle" /></div></div><p>
1315             The abbreviated names in the legend of the graphic above are
1316             instantiated with the types in the following table.
1317           </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">
1318                     n_set
1319                   </td></tr><tr><td align="left">
1320                     <code class="classname">std::set</code>
1321                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1322                     splay_tree_set
1323                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1324                     <code class="classname">tree</code>
1325                   </td><td align="left">
1326                     <code class="classname">Tag</code>
1327                   </td><td align="left">
1328                     <code class="classname">splay_tree_tag</code>
1329                   </td></tr><tr><td align="left">
1330                     <code class="classname">Node_Update</code>
1331                   </td><td align="left">
1332                     <code class="classname">null_node_update</code>
1333                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1334                     rb_tree_set
1335                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1336                     <code class="classname">tree</code>
1337                   </td><td align="left">
1338                     <code class="classname">Tag</code>
1339                   </td><td align="left">
1340                     <code class="classname">rb_tree_tag</code>
1341                   </td></tr><tr><td align="left">
1342                     <code class="classname">Node_Update</code>
1343                   </td><td align="left">
1344                     <code class="classname">null_node_update</code>
1345                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1346                     ov_tree_set
1347                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1348                     <code class="classname">tree</code>
1349                   </td><td align="left">
1350                     <code class="classname">Tag</code>
1351                   </td><td align="left">
1352                     <code class="classname">ov_tree_tag</code>
1353                   </td></tr><tr><td align="left">
1354                     <code class="classname">Node_Update</code>
1355                   </td><td align="left">
1356                     <code class="classname">null_node_update</code>
1357                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1358                     pat_trie_map
1359                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1360                     <code class="classname">tree</code>
1361                   </td><td align="left">
1362                     <code class="classname">Tag</code>
1363                   </td><td align="left">
1364                     <code class="classname">pat_trie_tag</code>
1365                   </td></tr><tr><td align="left">
1366                     <code class="classname">Node_Update</code>
1367                   </td><td align="left">
1368                     <code class="classname">null_node_update</code>
1369                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.observations"></a>
1370             Observations
1371           </h6></div></div></div><p>In this test, the native red-black trees must be split and
1372           joined externally, through a sequence of <code class="function">erase</code> and
1373           <code class="function">insert</code> operations. This is clearly
1374           super-linear, and it is not that surprising that the cost is
1375           high.</p><p>This library's tree-based containers use in this test the
1376           <code class="function">split</code> and <code class="function">join</code> methods,
1377           which have lower complexity: the <code class="function">join</code> method
1378           of a splay tree (<code class="classname">tree</code>
1379           with <code class="classname">Tag </code>
1380           = <code class="classname">splay_tree_tag</code>) is quadratic in the
1381           length of the longest root-leaf path, and linear in the total
1382           number of elements; the <code class="function">join</code> method of a
1383           red-black tree (<code class="classname">tree</code>
1384           with <code class="classname">Tag </code>
1385           = <code class="classname">rb_tree_tag</code>) or an ordered-vector tree
1386           (<code class="classname">tree</code> with <code class="classname">Tag </code>
1387           = <code class="classname">ov_tree_tag</code>) is linear in the number of
1388           elements.</p><p>Asides from orders of growth, this library's trees access their
1389           allocator very little in these operations, and some of them do not
1390           access it at all. This leads to lower constants in their
1391           complexity, and, for some containers, to exception-free splits and
1392           joins (which can be determined
1393           via <code class="classname">container_traits</code>).</p><p>It is important to note that <code class="function">split</code> and
1394           <code class="function">join</code> are not esoteric methods - they are the most
1395           efficient means of erasing a contiguous range of values from a
1396           tree based container.</p></div></div><div class="section" title="Order-Statistics"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.order_statistics"></a>
1397           Order-Statistics
1398         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.info"></a>
1399             Description
1400           </h6></div></div></div><p>This test creates a container, inserts random integers into the
1401           the container, and then checks the order-statistics of the
1402           container's values. (If the container is one of this
1403           library's trees, it does this with
1404           the <code class="function">order_of_key</code> method of
1405           <code class="classname">tree_order_statistics_node_update</code>
1406           ; otherwise, it uses the <code class="function">find</code> method and
1407           <code class="function">std::distance</code>.) It measures the average
1408           time for such queries as a function of the number of values
1409           inserted.</p><p>
1410             It uses the test file:
1411             <code class="filename">performance/ext/pb_ds/tree_order_statistics_timing.cc</code>
1412           </p><p>The test checks the performance difference of policies based
1413           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 id="branch.order_statistics.results"></a>
1414             Results
1415           </h6></div></div></div><p>The graphic immediately below shows the results for the
1416           native tree type and several other tree types.
1417           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_order_statistics.png" align="middle" /></div></div><p>
1418             The abbreviated names in the legend of the graphic above are
1419             instantiated with the types in the following table.
1420           </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">
1421                     n_set
1422                   </td></tr><tr><td align="left">
1423                     <code class="classname">std::set</code>
1424                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1425                     splay_tree_ost_set
1426                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1427                     <code class="classname">tree</code>
1428                   </td><td align="left">
1429                     <code class="classname">Tag</code>
1430                   </td><td align="left">
1431                     <code class="classname">splay_tree_tag</code>
1432                   </td></tr><tr><td align="left">
1433                     <code class="classname">Node_Update</code>
1434                   </td><td align="left">
1435                     <code class="classname">tree_order_statistics_node_update</code>
1436                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1437                     rb_tree_ost_set
1438                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1439                     <code class="classname">tree</code>
1440                   </td><td align="left">
1441                     <code class="classname">Tag</code>
1442                   </td><td align="left">
1443                     <code class="classname">rb_tree_tag</code>
1444                   </td></tr><tr><td align="left">
1445                     <code class="classname">Node_Update</code>
1446                   </td><td align="left">
1447                     <code class="classname">tree_order_statistics_node_update</code>
1448                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.observations"></a>
1449             Observations
1450           </h6></div></div></div><p>In this test, the native red-black tree can support
1451           order-statistics queries only externally, by performing a
1452           <code class="classname">find</code> (alternatively, <code class="classname">lower_bound</code> or
1453           <code class="classname">upper_bound</code> ) and then using <code class="classname">std::distance</code> .
1454           This is clearly linear, and it is not that surprising that the
1455           cost is high.</p><p>This library's tree-based containers use in this test the
1456           <code class="classname">order_of_key</code> method of <code class="classname">tree_order_statistics_node_update</code>.
1457           This method has only linear complexity in the length of the
1458           root-node path. Unfortunately, the average path of a splay tree
1459           (<code class="classname">tree</code>
1460           with <code class="classname">Tag =</code> <code class="classname">splay_tree_tag</code> ) can
1461           be higher than logarithmic; the longest path of a red-black
1462           tree (<code class="classname">tree</code>
1463           with <code class="classname">Tag =</code> <code class="classname">rb_tree_tag</code> ) is
1464           logarithmic in the number of elements. Consequently, the splay
1465           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 id="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 id="performance.multimap.text_find_small"></a>
1466           Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios 
1467         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.info"></a>
1468             Description
1469           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1470           first item of each pair is a string from an arbitrary text
1471           [wickland96thirty], and
1472           the second is a uniform i.i.d.integer. The container is a
1473           "multimap" - it considers the first member of each pair as a
1474           primary key, and the second member of each pair as a secondary
1475           key (see Motivation::Associative
1476           Containers::Alternative to Multiple Equivalent Keys). There
1477           are 400 distinct primary keys, and the ratio of secondary keys
1478           to primary keys ranges from 1 to 5.</p><p>The test measures the average find-time as a function of the
1479           number of values inserted. For this library's containers, it
1480           finds the secondary key from a container obtained from finding
1481           a primary key. For the native multimaps, it searches a range
1482           obtained using <code class="classname">std::equal_range</code> on a primary key.</p><p>
1483             It uses the test file:
1484             <code class="filename">performance/ext/pb_ds/multimap_text_find_timing_small.cc</code>
1485           </p><p>The test checks the find-time scalability of different
1486           "multimap" designs.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.results"></a>
1487             Results
1488           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
1489           use a tree-based container for primary keys.
1490           </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>
1491             The abbreviated names in the legend of the graphic above are
1492             instantiated with the types in the following table.
1493           </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">
1494                     n_mmap
1495                   </td></tr><tr><td align="left">
1496                     <code class="classname">std::multimap</code>
1497                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1498                     rb_tree_mmap_lu_mtf_set
1499                   </td></tr><tr><td rowspan="3" align="left" valign="top">
1500                     <code class="classname">tree</code>
1501                   </td><td align="left">
1502                     <code class="classname">Tag</code>
1503                   </td><td align="left">
1504                     <code class="classname">rb_tree_tag</code>
1505                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1506                     <code class="classname">Node_Update</code>
1507                   </td><td align="left">
1508                     <code class="classname">null_node_update</code>
1509                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1510                     <code class="classname">Mapped</code>
1511                   </td><td align="left">
1512                     <code class="classname">list_update</code>
1513                   </td><td align="left">
1514                     <code class="classname">Update_Policy</code>
1515                   </td><td align="left">
1516                     <code class="classname">lu_move_to_front_policy</code>
1517                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1518                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1519                   </td></tr><tr><td rowspan="5" align="left" valign="top">
1520                     <code class="classname">tree</code>
1521                   </td><td align="left">
1522                     <code class="classname">Tag</code>
1523                   </td><td align="left">
1524                     <code class="classname">rb_tree_tag</code>
1525                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1526                     <code class="classname">Node_Update</code>
1527                   </td><td align="left">
1528                     <code class="classname">null_node_update</code>
1529                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1530                     <code class="classname">Mapped</code>
1531                   </td><td rowspan="3" align="left" valign="top">
1532                     <code class="classname">cc_hash_table</code>
1533                   </td><td align="left">
1534                     <code class="classname">Comb_Hash_Fn</code>
1535                   </td><td align="left">
1536                     <code class="classname">direct_mask_range_hashing</code>
1537                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1538                     <code class="classname">Resize_Policy</code>
1539                   </td><td rowspan="2" align="left" valign="top">
1540                     <code class="classname">hash_standard_resize_policy</code>
1541                   </td><td align="left">
1542                     <code class="classname">Size_Policy</code>
1543                   </td><td align="left">
1544                     <code class="classname">hash_exponential_size_policy</code>
1545                   </td></tr><tr><td align="left" valign="top">
1546                     <code class="classname">Trigger_Policy</code>
1547                   </td><td align="left">
1548                     <code class="classname">hash_load_check_resize_trigger</code> with
1549                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1550                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
1551           use a hash-based container for primary keys.
1552           </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>
1553             The abbreviated names in the legend of the graphic above are
1554             instantiated with the types in the following table.
1555           </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">
1556                     n_hash_mmap
1557                   </td></tr><tr><td align="left">
1558                     <code class="classname">std::tr1::unordered_multimap</code>
1559                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1560                     rb_tree_mmap_lu_mtf_set
1561                   </td></tr><tr><td rowspan="4" align="left" valign="top">
1562                     <code class="classname">
1563                       cc_hash_table
1564                     </code>
1565                   </td><td align="left">
1566                     <code class="classname">Comb_Hash_Fn</code>
1567                   </td><td align="left">
1568                     <code class="classname">direct_mask_range_hashing</code>
1569                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1570                     <code class="classname">Resize_Policy</code>
1571                   </td><td rowspan="2" align="left" valign="top">
1572                     <code class="classname">hash_standard_resize_policy</code>
1573                   </td><td align="left">
1574                     <code class="classname">Size_Policy</code>
1575                   </td><td align="left">
1576                     <code class="classname">hash_exponential_size_policy</code>
1577                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1578                     <code class="classname">Trigger_Policy</code>
1579                   </td><td align="left">
1580                     <code class="classname">hash_load_check_resize_trigger</code> with
1581                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1582                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
1583                     <code class="classname">Mapped</code>
1584                   </td><td align="left">
1585                     <code class="classname">list_update</code>
1586                   </td><td align="left">
1587                     <code class="classname">Update_Policy</code>
1588                   </td><td align="left">
1589                     <code class="classname">lu_move_to_front_policy</code>
1590                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1591                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1592                   </td></tr><tr><td rowspan="6" align="left" valign="top">
1593                     <code class="classname">
1594                       cc_hash_table
1595                     </code>
1596                   </td><td align="left">
1597                     <code class="classname">Comb_Hash_Fn</code>
1598                   </td><td align="left">
1599                     <code class="classname">direct_mask_range_hashing</code>
1600                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1601                     <code class="classname">Resize_Policy</code>
1602                   </td><td rowspan="2" align="left" valign="top">
1603                     <code class="classname">hash_standard_resize_policy</code>
1604                   </td><td align="left">
1605                     <code class="classname">Size_Policy</code>
1606                   </td><td align="left">
1607                     <code class="classname">hash_exponential_size_policy</code>
1608                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1609                     <code class="classname">Trigger_Policy</code>
1610                   </td><td align="left">
1611                     <code class="classname">hash_load_check_resize_trigger</code> with
1612                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1613                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1614                     <code class="classname">Mapped</code>
1615                   </td><td rowspan="3" align="left" valign="top">
1616                     <code class="classname">cc_hash_table</code>
1617                   </td><td align="left">
1618                     <code class="classname">Comb_Hash_Fn</code>
1619                   </td><td align="left">
1620                     <code class="classname">direct_mask_range_hashing</code>
1621                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1622                     <code class="classname">Resize_Policy</code>
1623                   </td><td rowspan="2" align="left" valign="top">
1624                     <code class="classname">hash_standard_resize_policy</code>
1625                   </td><td align="left">
1626                     <code class="classname">Size_Policy</code>
1627                   </td><td align="left">
1628                     <code class="classname">hash_exponential_size_policy</code>
1629                   </td></tr><tr><td align="left" valign="top">
1630                     <code class="classname">Trigger_Policy</code>
1631                   </td><td align="left">
1632                     <code class="classname">hash_load_check_resize_trigger</code> with
1633                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1634                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.observations"></a>
1635             Observations
1636           </h6></div></div></div><p>See Observations::Mapping-Semantics
1637           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 id="performance.multimap.text_find_large"></a>
1638           Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios 
1639         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.info"></a>
1640             Description
1641           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1642           first item of each pair is a string from an arbitrary text
1643           [wickland96thirty], and
1644           the second is a uniform integer. The container is a
1645           "multimap" - it considers the first member of each pair as a
1646           primary key, and the second member of each pair as a secondary
1647           key. There
1648           are 400 distinct primary keys, and the ratio of secondary keys
1649           to primary keys ranges from 1 to 5.</p><p>The test measures the average find-time as a function of the
1650           number of values inserted. For this library's containers, it
1651           finds the secondary key from a container obtained from finding
1652           a primary key. For the native multimaps, it searches a range
1653           obtained using <code class="classname">std::equal_range</code> on a primary key.</p><p>
1654             It uses the test file:
1655             <code class="filename">performance/ext/pb_ds/multimap_text_find_timing_large.cc</code>
1656           </p><p>The test checks the find-time scalability of different
1657           "multimap" designs.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.results"></a>
1658             Results
1659           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
1660           use a tree-based container for primary keys.
1661           </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>
1662             The abbreviated names in the legend of the graphic above are
1663             instantiated with the types in the following table.
1664           </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">
1665                     n_mmap
1666                   </td></tr><tr><td align="left">
1667                     <code class="classname">std::multimap</code>
1668                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1669                     rb_tree_mmap_lu_mtf_set
1670                   </td></tr><tr><td rowspan="3" align="left" valign="top">
1671                     <code class="classname">tree</code>
1672                   </td><td align="left">
1673                     <code class="classname">Tag</code>
1674                   </td><td align="left">
1675                     <code class="classname">rb_tree_tag</code>
1676                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1677                     <code class="classname">Node_Update</code>
1678                   </td><td align="left">
1679                     <code class="classname">null_node_update</code>
1680                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1681                     <code class="classname">Mapped</code>
1682                   </td><td align="left">
1683                     <code class="classname">list_update</code>
1684                   </td><td align="left">
1685                     <code class="classname">Update_Policy</code>
1686                   </td><td align="left">
1687                     <code class="classname">lu_move_to_front_policy</code>
1688                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1689                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1690                   </td></tr><tr><td rowspan="5" align="left" valign="top">
1691                     <code class="classname">tree</code>
1692                   </td><td align="left">
1693                     <code class="classname">Tag</code>
1694                   </td><td align="left">
1695                     <code class="classname">rb_tree_tag</code>
1696                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1697                     <code class="classname">Node_Update</code>
1698                   </td><td align="left">
1699                     <code class="classname">null_node_update</code>
1700                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1701                     <code class="classname">Mapped</code>
1702                   </td><td rowspan="3" align="left" valign="top">
1703                     <code class="classname">cc_hash_table</code>
1704                   </td><td align="left">
1705                     <code class="classname">Comb_Hash_Fn</code>
1706                   </td><td align="left">
1707                     <code class="classname">direct_mask_range_hashing</code>
1708                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1709                     <code class="classname">Resize_Policy</code>
1710                   </td><td rowspan="2" align="left" valign="top">
1711                     <code class="classname">hash_standard_resize_policy</code>
1712                   </td><td align="left">
1713                     <code class="classname">Size_Policy</code>
1714                   </td><td align="left">
1715                     <code class="classname">hash_exponential_size_policy</code>
1716                   </td></tr><tr><td align="left" valign="top">
1717                     <code class="classname">Trigger_Policy</code>
1718                   </td><td align="left">
1719                     <code class="classname">hash_load_check_resize_trigger</code> with
1720                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1721                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
1722           use a hash-based container for primary keys.
1723           </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>
1724             The abbreviated names in the legend of the graphic above are
1725             instantiated with the types in the following table.
1726           </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">
1727                     n_hash_mmap
1728                   </td></tr><tr><td align="left">
1729                     <code class="classname">std::tr1::unordered_multimap</code>
1730                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1731                     rb_tree_mmap_lu_mtf_set
1732                   </td></tr><tr><td rowspan="4" align="left" valign="top">
1733                     <code class="classname">
1734                       cc_hash_table
1735                     </code>
1736                   </td><td align="left">
1737                     <code class="classname">Comb_Hash_Fn</code>
1738                   </td><td align="left">
1739                     <code class="classname">direct_mask_range_hashing</code>
1740                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1741                     <code class="classname">Resize_Policy</code>
1742                   </td><td rowspan="2" align="left" valign="top">
1743                     <code class="classname">hash_standard_resize_policy</code>
1744                   </td><td align="left">
1745                     <code class="classname">Size_Policy</code>
1746                   </td><td align="left">
1747                     <code class="classname">hash_exponential_size_policy</code>
1748                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1749                     <code class="classname">Trigger_Policy</code>
1750                   </td><td align="left">
1751                     <code class="classname">hash_load_check_resize_trigger</code> with
1752                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1753                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
1754                     <code class="classname">Mapped</code>
1755                   </td><td align="left">
1756                     <code class="classname">list_update</code>
1757                   </td><td align="left">
1758                     <code class="classname">Update_Policy</code>
1759                   </td><td align="left">
1760                     <code class="classname">lu_move_to_front_policy</code>
1761                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1762                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1763                   </td></tr><tr><td rowspan="6" align="left" valign="top">
1764                     <code class="classname">
1765                       cc_hash_table
1766                     </code>
1767                   </td><td align="left">
1768                     <code class="classname">Comb_Hash_Fn</code>
1769                   </td><td align="left">
1770                     <code class="classname">direct_mask_range_hashing</code>
1771                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1772                     <code class="classname">Resize_Policy</code>
1773                   </td><td rowspan="2" align="left" valign="top">
1774                     <code class="classname">hash_standard_resize_policy</code>
1775                   </td><td align="left">
1776                     <code class="classname">Size_Policy</code>
1777                   </td><td align="left">
1778                     <code class="classname">hash_exponential_size_policy</code>
1779                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1780                     <code class="classname">Trigger_Policy</code>
1781                   </td><td align="left">
1782                     <code class="classname">hash_load_check_resize_trigger</code> with
1783                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1784                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1785                     <code class="classname">Mapped</code>
1786                   </td><td rowspan="3" align="left" valign="top">
1787                     <code class="classname">cc_hash_table</code>
1788                   </td><td align="left">
1789                     <code class="classname">Comb_Hash_Fn</code>
1790                   </td><td align="left">
1791                     <code class="classname">direct_mask_range_hashing</code>
1792                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1793                     <code class="classname">Resize_Policy</code>
1794                   </td><td rowspan="2" align="left" valign="top">
1795                     <code class="classname">hash_standard_resize_policy</code>
1796                   </td><td align="left">
1797                     <code class="classname">Size_Policy</code>
1798                   </td><td align="left">
1799                     <code class="classname">hash_exponential_size_policy</code>
1800                   </td></tr><tr><td align="left" valign="top">
1801                     <code class="classname">Trigger_Policy</code>
1802                   </td><td align="left">
1803                     <code class="classname">hash_load_check_resize_trigger</code> with
1804                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1805                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.observations"></a>
1806             Observations
1807           </h6></div></div></div><p>See Observations::Mapping-Semantics
1808           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 id="performance.multimap.text_insert_small"></a>
1809           Text <code class="function">insert</code> with Small
1810           Secondary-to-Primary Key Ratios
1811         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.info"></a>
1812             Description
1813           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1814           first item of each pair is a string from an arbitrary text
1815           [wickland96thirty], and
1816           the second is a uniform integer. The container is a
1817           "multimap" - it considers the first member of each pair as a
1818           primary key, and the second member of each pair as a secondary
1819           key. There
1820           are 400 distinct primary keys, and the ratio of secondary keys
1821           to primary keys ranges from 1 to 5.</p><p>The test measures the average insert-time as a function of
1822           the number of values inserted. For this library's containers,
1823           it inserts a primary key into the primary associative
1824           container, then a secondary key into the secondary associative
1825           container. For the native multimaps, it obtains a range using
1826           <code class="classname">std::equal_range</code>, and inserts a value only if it was
1827           not contained already.</p><p>
1828             It uses the test file:
1829             <code class="filename">performance/ext/pb_ds/multimap_text_insert_timing_small.cc</code>
1830           </p><p>The test checks the insert-time scalability of different
1831           "multimap" designs.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.results"></a>
1832             Results
1833           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
1834           use a tree-based container for primary keys.
1835           </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>
1836             The abbreviated names in the legend of the graphic above are
1837             instantiated with the types in the following table.
1838           </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">
1839                     n_mmap
1840                   </td></tr><tr><td align="left">
1841                     <code class="classname">std::multimap</code>
1842                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1843                     rb_tree_mmap_lu_mtf_set
1844                   </td></tr><tr><td rowspan="3" align="left" valign="top">
1845                     <code class="classname">tree</code>
1846                   </td><td align="left">
1847                     <code class="classname">Tag</code>
1848                   </td><td align="left">
1849                     <code class="classname">rb_tree_tag</code>
1850                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1851                     <code class="classname">Node_Update</code>
1852                   </td><td align="left">
1853                     <code class="classname">null_node_update</code>
1854                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1855                     <code class="classname">Mapped</code>
1856                   </td><td align="left">
1857                     <code class="classname">list_update</code>
1858                   </td><td align="left">
1859                     <code class="classname">Update_Policy</code>
1860                   </td><td align="left">
1861                     <code class="classname">lu_move_to_front_policy</code>
1862                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1863                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1864                   </td></tr><tr><td rowspan="5" align="left" valign="top">
1865                     <code class="classname">tree</code>
1866                   </td><td align="left">
1867                     <code class="classname">Tag</code>
1868                   </td><td align="left">
1869                     <code class="classname">rb_tree_tag</code>
1870                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1871                     <code class="classname">Node_Update</code>
1872                   </td><td align="left">
1873                     <code class="classname">null_node_update</code>
1874                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1875                     <code class="classname">Mapped</code>
1876                   </td><td rowspan="3" align="left" valign="top">
1877                     <code class="classname">cc_hash_table</code>
1878                   </td><td align="left">
1879                     <code class="classname">Comb_Hash_Fn</code>
1880                   </td><td align="left">
1881                     <code class="classname">direct_mask_range_hashing</code>
1882                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1883                     <code class="classname">Resize_Policy</code>
1884                   </td><td rowspan="2" align="left" valign="top">
1885                     <code class="classname">hash_standard_resize_policy</code>
1886                   </td><td align="left">
1887                     <code class="classname">Size_Policy</code>
1888                   </td><td align="left">
1889                     <code class="classname">hash_exponential_size_policy</code>
1890                   </td></tr><tr><td align="left" valign="top">
1891                     <code class="classname">Trigger_Policy</code>
1892                   </td><td align="left">
1893                     <code class="classname">hash_load_check_resize_trigger</code> with
1894                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1895                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
1896           use a hash-based container for primary keys.
1897           </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>
1898             The abbreviated names in the legend of the graphic above are
1899             instantiated with the types in the following table.
1900           </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">
1901                     n_hash_mmap
1902                   </td></tr><tr><td align="left">
1903                     <code class="classname">std::tr1::unordered_multimap</code>
1904                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1905                     rb_tree_mmap_lu_mtf_set
1906                   </td></tr><tr><td rowspan="4" align="left" valign="top">
1907                     <code class="classname">
1908                       cc_hash_table
1909                     </code>
1910                   </td><td align="left">
1911                     <code class="classname">Comb_Hash_Fn</code>
1912                   </td><td align="left">
1913                     <code class="classname">direct_mask_range_hashing</code>
1914                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1915                     <code class="classname">Resize_Policy</code>
1916                   </td><td rowspan="2" align="left" valign="top">
1917                     <code class="classname">hash_standard_resize_policy</code>
1918                   </td><td align="left">
1919                     <code class="classname">Size_Policy</code>
1920                   </td><td align="left">
1921                     <code class="classname">hash_exponential_size_policy</code>
1922                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1923                     <code class="classname">Trigger_Policy</code>
1924                   </td><td align="left">
1925                     <code class="classname">hash_load_check_resize_trigger</code> with
1926                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1927                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
1928                     <code class="classname">Mapped</code>
1929                   </td><td align="left">
1930                     <code class="classname">list_update</code>
1931                   </td><td align="left">
1932                     <code class="classname">Update_Policy</code>
1933                   </td><td align="left">
1934                     <code class="classname">lu_move_to_front_policy</code>
1935                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1936                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1937                   </td></tr><tr><td rowspan="6" align="left" valign="top">
1938                     <code class="classname">
1939                       cc_hash_table
1940                     </code>
1941                   </td><td align="left">
1942                     <code class="classname">Comb_Hash_Fn</code>
1943                   </td><td align="left">
1944                     <code class="classname">direct_mask_range_hashing</code>
1945                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1946                     <code class="classname">Resize_Policy</code>
1947                   </td><td rowspan="2" align="left" valign="top">
1948                     <code class="classname">hash_standard_resize_policy</code>
1949                   </td><td align="left">
1950                     <code class="classname">Size_Policy</code>
1951                   </td><td align="left">
1952                     <code class="classname">hash_exponential_size_policy</code>
1953                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1954                     <code class="classname">Trigger_Policy</code>
1955                   </td><td align="left">
1956                     <code class="classname">hash_load_check_resize_trigger</code> with
1957                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1958                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1959                     <code class="classname">Mapped</code>
1960                   </td><td rowspan="3" align="left" valign="top">
1961                     <code class="classname">cc_hash_table</code>
1962                   </td><td align="left">
1963                     <code class="classname">Comb_Hash_Fn</code>
1964                   </td><td align="left">
1965                     <code class="classname">direct_mask_range_hashing</code>
1966                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1967                     <code class="classname">Resize_Policy</code>
1968                   </td><td rowspan="2" align="left" valign="top">
1969                     <code class="classname">hash_standard_resize_policy</code>
1970                   </td><td align="left">
1971                     <code class="classname">Size_Policy</code>
1972                   </td><td align="left">
1973                     <code class="classname">hash_exponential_size_policy</code>
1974                   </td></tr><tr><td align="left" valign="top">
1975                     <code class="classname">Trigger_Policy</code>
1976                   </td><td align="left">
1977                     <code class="classname">hash_load_check_resize_trigger</code> with
1978                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1979                   </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.observations"></a>
1980             Observations
1981           </h6></div></div></div><p>See Observations::Mapping-Semantics
1982           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 id="performance.multimap.text_insert_large"></a>
1983           Text <code class="function">insert</code> with Small
1984           Secondary-to-Primary Key Ratios
1985         </h5></div></div></div><p></p><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.info"></a>
1986             Description
1987           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1988           first item of each pair is a string from an arbitrary text
1989           [wickland96thirty], and
1990           the second is a uniform integer. The container is a
1991           "multimap" - it considers the first member of each pair as a
1992           primary key, and the second member of each pair as a secondary
1993           key. There
1994           are 400 distinct primary keys, and the ratio of secondary keys
1995           to primary keys ranges from 1 to 5.</p><p>The test measures the average insert-time as a function of
1996           the number of values inserted. For this library's containers,
1997           it inserts a primary key into the primary associative
1998           container, then a secondary key into the secondary associative
1999           container. For the native multimaps, it obtains a range using
2000           <code class="classname">std::equal_range</code>, and inserts a value only if it was
2001           not contained already.</p><p>
2002             It uses the test file:
2003             <code class="filename">performance/ext/pb_ds/multimap_text_insert_timing_large.cc</code>
2004           </p><p>The test checks the insert-time scalability of different
2005           "multimap" designs.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.results"></a>
2006             Results
2007           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
2008           use a tree-based container for primary keys.
2009           </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>
2010             The abbreviated names in the legend of the graphic above are
2011             instantiated with the types in the following table.
2012           </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">
2013                     n_mmap
2014                   </td></tr><tr><td align="left">
2015                     <code class="classname">std::multimap</code>
2016                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2017                     rb_tree_mmap_lu_mtf_set
2018                   </td></tr><tr><td rowspan="3" align="left" valign="top">
2019                     <code class="classname">tree</code>
2020                   </td><td align="left">
2021                     <code class="classname">Tag</code>
2022                   </td><td align="left">
2023                     <code class="classname">rb_tree_tag</code>
2024                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2025                     <code class="classname">Node_Update</code>
2026                   </td><td align="left">
2027                     <code class="classname">null_node_update</code>
2028                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2029                     <code class="classname">Mapped</code>
2030                   </td><td align="left">
2031                     <code class="classname">list_update</code>
2032                   </td><td align="left">
2033                     <code class="classname">Update_Policy</code>
2034                   </td><td align="left">
2035                     <code class="classname">lu_move_to_front_policy</code>
2036                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2037                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2038                   </td></tr><tr><td rowspan="5" align="left" valign="top">
2039                     <code class="classname">tree</code>
2040                   </td><td align="left">
2041                     <code class="classname">Tag</code>
2042                   </td><td align="left">
2043                     <code class="classname">rb_tree_tag</code>
2044                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2045                     <code class="classname">Node_Update</code>
2046                   </td><td align="left">
2047                     <code class="classname">null_node_update</code>
2048                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
2049                     <code class="classname">Mapped</code>
2050                   </td><td rowspan="3" align="left" valign="top">
2051                     <code class="classname">cc_hash_table</code>
2052                   </td><td align="left">
2053                     <code class="classname">Comb_Hash_Fn</code>
2054                   </td><td align="left">
2055                     <code class="classname">direct_mask_range_hashing</code>
2056                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2057                     <code class="classname">Resize_Policy</code>
2058                   </td><td rowspan="2" align="left" valign="top">
2059                     <code class="classname">hash_standard_resize_policy</code>
2060                   </td><td align="left">
2061                     <code class="classname">Size_Policy</code>
2062                   </td><td align="left">
2063                     <code class="classname">hash_exponential_size_policy</code>
2064                   </td></tr><tr><td align="left" valign="top">
2065                     <code class="classname">Trigger_Policy</code>
2066                   </td><td align="left">
2067                     <code class="classname">hash_load_check_resize_trigger</code> with
2068                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2069                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
2070           use a hash-based container for primary keys.
2071           </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>
2072             The abbreviated names in the legend of the graphic above are
2073             instantiated with the types in the following table.
2074           </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">
2075                     n_hash_mmap
2076                   </td></tr><tr><td align="left">
2077                     <code class="classname">std::tr1::unordered_multimap</code>
2078                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2079                     rb_tree_mmap_lu_mtf_set
2080                   </td></tr><tr><td rowspan="4" align="left" valign="top">
2081                     <code class="classname">
2082                       cc_hash_table
2083                     </code>
2084                   </td><td align="left">
2085                     <code class="classname">Comb_Hash_Fn</code>
2086                   </td><td align="left">
2087                     <code class="classname">direct_mask_range_hashing</code>
2088                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2089                     <code class="classname">Resize_Policy</code>
2090                   </td><td rowspan="2" align="left" valign="top">
2091                     <code class="classname">hash_standard_resize_policy</code>
2092                   </td><td align="left">
2093                     <code class="classname">Size_Policy</code>
2094                   </td><td align="left">
2095                     <code class="classname">hash_exponential_size_policy</code>
2096                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
2097                     <code class="classname">Trigger_Policy</code>
2098                   </td><td align="left">
2099                     <code class="classname">hash_load_check_resize_trigger</code> with
2100                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2101                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
2102                     <code class="classname">Mapped</code>
2103                   </td><td align="left">
2104                     <code class="classname">list_update</code>
2105                   </td><td align="left">
2106                     <code class="classname">Update_Policy</code>
2107                   </td><td align="left">
2108                     <code class="classname">lu_move_to_front_policy</code>
2109                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2110                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2111                   </td></tr><tr><td rowspan="6" align="left" valign="top">
2112                     <code class="classname">
2113                       cc_hash_table
2114                     </code>
2115                   </td><td align="left">
2116                     <code class="classname">Comb_Hash_Fn</code>
2117                   </td><td align="left">
2118                     <code class="classname">direct_mask_range_hashing</code>
2119                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2120                     <code class="classname">Resize_Policy</code>
2121                   </td><td rowspan="2" align="left" valign="top">
2122                     <code class="classname">hash_standard_resize_policy</code>
2123                   </td><td align="left">
2124                     <code class="classname">Size_Policy</code>
2125                   </td><td align="left">
2126                     <code class="classname">hash_exponential_size_policy</code>
2127                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
2128                     <code class="classname">Trigger_Policy</code>
2129                   </td><td align="left">
2130                     <code class="classname">hash_load_check_resize_trigger</code> with
2131                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2132                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
2133                     <code class="classname">Mapped</code>
2134                   </td><td rowspan="3" align="left" valign="top">
2135                     <code class="classname">cc_hash_table</code>
2136                   </td><td align="left">
2137                     <code class="classname">Comb_Hash_Fn</code>
2138                   </td><td align="left">
2139                     <code class="classname">direct_mask_range_hashing</code>
2140                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2141                     <code class="classname">Resize_Policy</code>
2142                   </td><td rowspan="2" align="left" valign="top">
2143                     <code class="classname">hash_standard_resize_policy</code>
2144                   </td><td align="left">
2145                     <code class="classname">Size_Policy</code>
2146                   </td><td align="left">
2147                     <code class="classname">hash_exponential_size_policy</code>
2148                   </td></tr><tr><td align="left" valign="top">
2149                     <code class="classname">Trigger_Policy</code>
2150                   </td><td align="left">
2151           &nb