OSDN Git Service

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