OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libstdc++-v3/] [doc/] [html/] [manual/] [policy_based_data_structures_test.html] - Blame information for rev 742

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 742 jeremybenn
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
3
<html xmlns="http://www.w3.org/1999/xhtml"><head><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 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 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"><a id="pbds.test"/>Testing</h2></div></div></div><div class="section" title="Regression"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.regression"/>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"/>Performance</h3></div></div></div><div class="section" title="Hash-Based"><div class="titlepage"><div><div><h4 class="title"><a id="performance.hash"/>Hash-Based</h4></div></div></div><p/><div class="section" title="Text find"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.text_find"/>
26
          Text <code class="function">find</code>
27
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_hash_text_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
57
                    n_hash_map_ncah
58
                  </td></tr><tr><td style="text-align: left">
59
                    <code class="classname">std::tr1::unordered_map</code>
60
                  </td><td style="text-align: left">
61
                    <code class="classname">cache_hash_code</code>
62
                  </td><td style="text-align: left">
63
                    <code class="constant">false</code>
64
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
65
                    cc_hash_mod_prime_1div1_nsth_map
66
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
67
                    <code class="classname">cc_hash_table</code>
68
                  </td><td style="text-align: left">
69
                    <code class="classname">Comb_Hash_Fn</code>
70
                  </td><td style="text-align: left">
71
                    <code class="classname">direct_mod_range_hashing</code>
72
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
73
                    <code class="classname">Resize_Policy</code>
74
                  </td><td rowspan="2" style="text-align: left" valign="top">
75
                    <code class="classname">hash_standard_resize_policy</code>
76
                  </td><td style="text-align: left">
77
                    <code class="classname">Size_Policy</code>
78
                  </td><td style="text-align: left">
79
                    <code class="classname">hash_prime_size_policy</code>
80
                  </td></tr><tr><td style="text-align: left" valign="top">
81
                    <code class="classname">Trigger_Policy</code>
82
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
86
                    cc_hash_mask_exp_1div2_sth_map
87
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
88
                    <code class="classname">
89
                      cc_hash_table
90
                    </code>
91
                  </td><td style="text-align: left">
92
                    <code class="classname">Comb_Hash_Fn</code>
93
                  </td><td style="text-align: left">
94
                    <code class="classname">direct_mask_range_hashing</code>
95
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
96
                    <code class="classname">Resize_Policy</code>
97
                  </td><td rowspan="2" style="text-align: left" valign="top">
98
                    <code class="classname">hash_standard_resize_policy</code>
99
                  </td><td style="text-align: left">
100
                    <code class="classname">Size_Policy</code>
101
                  </td><td style="text-align: left">
102
                    <code class="classname">hash_exponential_size_policy</code>
103
                  </td></tr><tr><td style="text-align: left" valign="top">
104
                    <code class="classname">Trigger_Policy</code>
105
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
109
                    cc_hash_mask_exp_1div1_nsth_map
110
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
111
                    <code class="classname">cc_hash_table</code>
112
                  </td><td style="text-align: left">
113
                    <code class="classname">Comb_Hash_Fn</code>
114
                  </td><td style="text-align: left">
115
                    <code class="classname">direct_mask_range_hashing</code>
116
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
117
                    <code class="classname">Resize_Policy</code>
118
                  </td><td rowspan="2" style="text-align: left" valign="top">
119
                    <code class="classname">hash_standard_resize_policy</code>
120
                  </td><td style="text-align: left">
121
                    <code class="classname">Size_Policy</code>
122
                  </td><td style="text-align: left">
123
                    <code class="classname">hash_exponential_size_policy</code>
124
                  </td></tr><tr><td style="text-align: left" valign="top">
125
                    <code class="classname">Trigger_Policy</code>
126
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
130
                    cc_hash_mask_exp_1div2_nsth_map
131
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
132
                    <code class="classname">cc_hash_table</code>
133
                  </td><td style="text-align: left">
134
                    <code class="classname">Comb_Hash_Fn</code>
135
                  </td><td style="text-align: left">
136
                    <code class="classname">direct_mask_range_hashing</code>
137
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
138
                    <code class="classname">Resize_Policy</code>
139
                  </td><td rowspan="2" style="text-align: left" valign="top">
140
                    <code class="classname">hash_standard_resize_policy</code>
141
                  </td><td style="text-align: left">
142
                    <code class="classname">Size_Policy</code>
143
                  </td><td style="text-align: left">
144
                    <code class="classname">hash_exponential_size_policy</code>
145
                  </td></tr><tr><td style="text-align: left" valign="top">
146
                    <code class="classname">Trigger_Policy</code>
147
                  </td><td style="text-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"/>
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"/>
166
          Integer <code class="function">find</code>
167
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_cc_hash_int_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
192
                    n_hash_map_ncah
193
                  </td></tr><tr><td style="text-align: left">
194
                    <code class="classname">std::tr1::unordered_map</code>
195
                  </td><td style="text-align: left">
196
                    <code class="classname">cache_hash_code</code>
197
                  </td><td style="text-align: left">
198
                    <code class="constant">false</code>
199
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
200
                    cc_hash_mod_prime_1div1_nsth_map
201
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
202
                    <code class="classname">cc_hash_table</code>
203
                  </td><td style="text-align: left">
204
                    <code class="classname">Comb_Hash_Fn</code>
205
                  </td><td style="text-align: left">
206
                    <code class="classname">direct_mod_range_hashing</code>
207
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
208
                    <code class="classname">Resize_Policy</code>
209
                  </td><td rowspan="2" style="text-align: left" valign="top">
210
                    <code class="classname">hash_standard_resize_policy</code>
211
                  </td><td style="text-align: left">
212
                    <code class="classname">Size_Policy</code>
213
                  </td><td style="text-align: left">
214
                    <code class="classname">hash_prime_size_policy</code>
215
                  </td></tr><tr><td style="text-align: left" valign="top">
216
                    <code class="classname">Trigger_Policy</code>
217
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
221
                    cc_hash_mod_prime_1div2_nsth_map
222
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
223
                    <code class="classname">
224
                      cc_hash_table
225
                    </code>
226
                  </td><td style="text-align: left">
227
                    <code class="classname">Comb_Hash_Fn</code>
228
                  </td><td style="text-align: left">
229
                    <code class="classname">direct_mod_range_hashing</code>
230
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
231
                    <code class="classname">Resize_Policy</code>
232
                  </td><td rowspan="2" style="text-align: left" valign="top">
233
                    <code class="classname">hash_standard_resize_policy</code>
234
                  </td><td style="text-align: left">
235
                    <code class="classname">Size_Policy</code>
236
                  </td><td style="text-align: left">
237
                    <code class="classname">hash_prime_size_policy</code>
238
                  </td></tr><tr><td style="text-align: left" valign="top">
239
                    <code class="classname">Trigger_Policy</code>
240
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
244
                    cc_hash_mask_exp_1div1_nsth_map
245
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
246
                    <code class="classname">cc_hash_table</code>
247
                  </td><td style="text-align: left">
248
                    <code class="classname">Comb_Hash_Fn</code>
249
                  </td><td style="text-align: left">
250
                    <code class="classname">direct_mask_range_hashing</code>
251
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
252
                    <code class="classname">Resize_Policy</code>
253
                  </td><td rowspan="2" style="text-align: left" valign="top">
254
                    <code class="classname">hash_standard_resize_policy</code>
255
                  </td><td style="text-align: left">
256
                    <code class="classname">Size_Policy</code>
257
                  </td><td style="text-align: left">
258
                    <code class="classname">hash_exponential_size_policy</code>
259
                  </td></tr><tr><td style="text-align: left" valign="top">
260
                    <code class="classname">Trigger_Policy</code>
261
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
265
                    cc_hash_mask_exp_1div2_nsth_map
266
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
267
                    <code class="classname">cc_hash_table</code>
268
                  </td><td style="text-align: left">
269
                    <code class="classname">Comb_Hash_Fn</code>
270
                  </td><td style="text-align: left">
271
                    <code class="classname">direct_mask_range_hashing</code>
272
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
273
                    <code class="classname">Resize_Policy</code>
274
                  </td><td rowspan="2" style="text-align: left" valign="top">
275
                    <code class="classname">hash_standard_resize_policy</code>
276
                  </td><td style="text-align: left">
277
                    <code class="classname">Size_Policy</code>
278
                  </td><td style="text-align: left">
279
                    <code class="classname">hash_exponential_size_policy</code>
280
                  </td></tr><tr><td style="text-align: left" valign="top">
281
                    <code class="classname">Trigger_Policy</code>
282
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_gp_hash_int_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
294
                    n_hash_map_ncah
295
                  </td></tr><tr><td style="text-align: left">
296
                    <code class="classname">std::tr1::unordered_map</code>
297
                  </td><td style="text-align: left">
298
                    <code class="classname">cache_hash_code</code>
299
                  </td><td style="text-align: left">
300
                    <code class="constant">false</code>
301
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
302
                    gp_hash_mod_quadp_prime_1div2_nsth_map
303
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
304
                    <code class="classname">gp_hash_table</code>
305
                  </td><td style="text-align: left">
306
                    <code class="classname">Comb_Hash_Fn</code>
307
                  </td><td style="text-align: left">
308
                    <code class="classname">direct_mod_range_hashing</code>
309
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
310
                    <code class="classname">Probe_Fn</code>
311
                  </td><td style="text-align: left">
312
                    <code class="classname">quadratic_probe_fn</code>
313
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
314
                    <code class="classname">Resize_Policy</code>
315
                  </td><td rowspan="2" style="text-align: left" valign="top">
316
                    <code class="classname">hash_standard_resize_policy</code>
317
                  </td><td style="text-align: left">
318
                    <code class="classname">Size_Policy</code>
319
                  </td><td style="text-align: left">
320
                    <code class="classname">hash_prime_size_policy</code>
321
                  </td></tr><tr><td style="text-align: left" valign="top">
322
                    <code class="classname">Trigger_Policy</code>
323
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
327
                    gp_hash_mask_linp_exp_1div2_nsth_map
328
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
329
                    <code class="classname">
330
                      gp_hash_table
331
                    </code>
332
                  </td><td style="text-align: left">
333
                    <code class="classname">Comb_Hash_Fn</code>
334
                  </td><td style="text-align: left">
335
                    <code class="classname">direct_mask_range_hashing</code>
336
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
337
                    <code class="classname">Probe_Fn</code>
338
                  </td><td style="text-align: left">
339
                    <code class="classname">linear_probe_fn</code>
340
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
341
                    <code class="classname">Resize_Policy</code>
342
                  </td><td rowspan="2" style="text-align: left" valign="top">
343
                    <code class="classname">hash_standard_resize_policy</code>
344
                  </td><td style="text-align: left">
345
                    <code class="classname">Size_Policy</code>
346
                  </td><td style="text-align: left">
347
                    <code class="classname">hash_exponential_size_policy</code>
348
                  </td></tr><tr><td style="text-align: left" valign="top">
349
                    <code class="classname">Trigger_Policy</code>
350
                  </td><td style="text-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"/>
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"/>
370
          Integer Subscript <code class="function">find</code>
371
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_cc_hash_int_subscript_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
396
                    n_hash_map_ncah
397
                  </td></tr><tr><td style="text-align: left">
398
                    <code class="classname">std::tr1::unordered_map</code>
399
                  </td><td style="text-align: left">
400
                    <code class="classname">cache_hash_code</code>
401
                  </td><td style="text-align: left">
402
                    <code class="constant">false</code>
403
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
404
                    cc_hash_mod_prime_1div1_nsth_map
405
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
406
                    <code class="classname">cc_hash_table</code>
407
                  </td><td style="text-align: left">
408
                    <code class="classname">Comb_Hash_Fn</code>
409
                  </td><td style="text-align: left">
410
                    <code class="classname">direct_mod_range_hashing</code>
411
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
412
                    <code class="classname">Resize_Policy</code>
413
                  </td><td rowspan="2" style="text-align: left" valign="top">
414
                    <code class="classname">hash_standard_resize_policy</code>
415
                  </td><td style="text-align: left">
416
                    <code class="classname">Size_Policy</code>
417
                  </td><td style="text-align: left">
418
                    <code class="classname">hash_prime_size_policy</code>
419
                  </td></tr><tr><td style="text-align: left" valign="top">
420
                    <code class="classname">Trigger_Policy</code>
421
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
425
                    cc_hash_mod_prime_1div2_nsth_map
426
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
427
                    <code class="classname">cc_hash_table</code>
428
                  </td><td style="text-align: left">
429
                    <code class="classname">Comb_Hash_Fn</code>
430
                  </td><td style="text-align: left">
431
                    <code class="classname">direct_mod_range_hashing</code>
432
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
433
                    <code class="classname">Resize_Policy</code>
434
                  </td><td rowspan="2" style="text-align: left" valign="top">
435
                    <code class="classname">hash_standard_resize_policy</code>
436
                  </td><td style="text-align: left">
437
                    <code class="classname">Size_Policy</code>
438
                  </td><td style="text-align: left">
439
                    <code class="classname">hash_prime_size_policy</code>
440
                  </td></tr><tr><td style="text-align: left" valign="top">
441
                    <code class="classname">Trigger_Policy</code>
442
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
446
                    cc_hash_mask_exp_1div1_nsth_map
447
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
448
                    <code class="classname">cc_hash_table</code>
449
                  </td><td style="text-align: left">
450
                    <code class="classname">Comb_Hash_Fn</code>
451
                  </td><td style="text-align: left">
452
                    <code class="classname">direct_mask_range_hashing</code>
453
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
454
                    <code class="classname">Resize_Policy</code>
455
                  </td><td rowspan="2" style="text-align: left" valign="top">
456
                    <code class="classname">hash_standard_resize_policy</code>
457
                  </td><td style="text-align: left">
458
                    <code class="classname">Size_Policy</code>
459
                  </td><td style="text-align: left">
460
                    <code class="classname">hash_exponential_size_policy</code>
461
                  </td></tr><tr><td style="text-align: left" valign="top">
462
                    <code class="classname">Trigger_Policy</code>
463
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
467
                    cc_hash_mask_exp_1div2_nsth_map
468
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
469
                    <code class="classname">cc_hash_table</code>
470
                  </td><td style="text-align: left">
471
                    <code class="classname">Comb_Hash_Fn</code>
472
                  </td><td style="text-align: left">
473
                    <code class="classname">direct_mask_range_hashing</code>
474
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
475
                    <code class="classname">Resize_Policy</code>
476
                  </td><td rowspan="2" style="text-align: left" valign="top">
477
                    <code class="classname">hash_standard_resize_policy</code>
478
                  </td><td style="text-align: left">
479
                    <code class="classname">Size_Policy</code>
480
                  </td><td style="text-align: left">
481
                    <code class="classname">hash_exponential_size_policy</code>
482
                  </td></tr><tr><td style="text-align: left" valign="top">
483
                    <code class="classname">Trigger_Policy</code>
484
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_gp_hash_int_subscript_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
496
                    n_hash_map_ncah
497
                  </td></tr><tr><td style="text-align: left">
498
                    <code class="classname">std::tr1::unordered_map</code>
499
                  </td><td style="text-align: left">
500
                    <code class="classname">cache_hash_code</code>
501
                  </td><td style="text-align: left">
502
                    <code class="constant">false</code>
503
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
504
                    gp_hash_mod_quadp_prime_1div2_nsth_map
505
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
506
                    <code class="classname">gp_hash_table</code>
507
                  </td><td style="text-align: left">
508
                    <code class="classname">Comb_Hash_Fn</code>
509
                  </td><td style="text-align: left">
510
                    <code class="classname">direct_mod_range_hashing</code>
511
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
512
                    <code class="classname">Probe_Fn</code>
513
                  </td><td style="text-align: left">
514
                    <code class="classname">quadratic_probe_fn</code>
515
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
516
                    <code class="classname">Resize_Policy</code>
517
                  </td><td rowspan="2" style="text-align: left" valign="top">
518
                    <code class="classname">hash_standard_resize_policy</code>
519
                  </td><td style="text-align: left">
520
                    <code class="classname">Size_Policy</code>
521
                  </td><td style="text-align: left">
522
                    <code class="classname">hash_prime_size_policy</code>
523
                  </td></tr><tr><td style="text-align: left" valign="top">
524
                    <code class="classname">Trigger_Policy</code>
525
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
529
                    gp_hash_mask_linp_exp_1div2_nsth_map
530
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
531
                    <code class="classname">
532
                      gp_hash_table
533
                    </code>
534
                  </td><td style="text-align: left">
535
                    <code class="classname">Comb_Hash_Fn</code>
536
                  </td><td style="text-align: left">
537
                    <code class="classname">direct_mask_range_hashing</code>
538
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
539
                    <code class="classname">Probe_Fn</code>
540
                  </td><td style="text-align: left">
541
                    <code class="classname">linear_probe_fn</code>
542
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
543
                    <code class="classname">Resize_Policy</code>
544
                  </td><td rowspan="2" style="text-align: left" valign="top">
545
                    <code class="classname">hash_standard_resize_policy</code>
546
                  </td><td style="text-align: left">
547
                    <code class="classname">Size_Policy</code>
548
                  </td><td style="text-align: left">
549
                    <code class="classname">hash_exponential_size_policy</code>
550
                  </td></tr><tr><td style="text-align: left" valign="top">
551
                    <code class="classname">Trigger_Policy</code>
552
                  </td><td style="text-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"/>
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"/>
559
          Integer Subscript <code class="function">insert</code>
560
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_cc_hash_int_subscript_insert.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
585
                    n_hash_map_ncah
586
                  </td></tr><tr><td style="text-align: left">
587
                    <code class="classname">std::tr1::unordered_map</code>
588
                  </td><td style="text-align: left">
589
                    <code class="classname">cache_hash_code</code>
590
                  </td><td style="text-align: left">
591
                    <code class="constant">false</code>
592
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
593
                    cc_hash_mod_prime_1div1_nsth_map
594
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
595
                    <code class="classname">cc_hash_table</code>
596
                  </td><td style="text-align: left">
597
                    <code class="classname">Comb_Hash_Fn</code>
598
                  </td><td style="text-align: left">
599
                    <code class="classname">direct_mod_range_hashing</code>
600
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
601
                    <code class="classname">Resize_Policy</code>
602
                  </td><td rowspan="2" style="text-align: left" valign="top">
603
                    <code class="classname">hash_standard_resize_policy</code>
604
                  </td><td style="text-align: left">
605
                    <code class="classname">Size_Policy</code>
606
                  </td><td style="text-align: left">
607
                    <code class="classname">hash_prime_size_policy</code>
608
                  </td></tr><tr><td style="text-align: left" valign="top">
609
                    <code class="classname">Trigger_Policy</code>
610
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
614
                    cc_hash_mod_prime_1div2_nsth_map
615
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
616
                    <code class="classname">cc_hash_table</code>
617
                  </td><td style="text-align: left">
618
                    <code class="classname">Comb_Hash_Fn</code>
619
                  </td><td style="text-align: left">
620
                    <code class="classname">direct_mod_range_hashing</code>
621
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
622
                    <code class="classname">Resize_Policy</code>
623
                  </td><td rowspan="2" style="text-align: left" valign="top">
624
                    <code class="classname">hash_standard_resize_policy</code>
625
                  </td><td style="text-align: left">
626
                    <code class="classname">Size_Policy</code>
627
                  </td><td style="text-align: left">
628
                    <code class="classname">hash_prime_size_policy</code>
629
                  </td></tr><tr><td style="text-align: left" valign="top">
630
                    <code class="classname">Trigger_Policy</code>
631
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
635
                    cc_hash_mask_exp_1div1_nsth_map
636
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
637
                    <code class="classname">cc_hash_table</code>
638
                  </td><td style="text-align: left">
639
                    <code class="classname">Comb_Hash_Fn</code>
640
                  </td><td style="text-align: left">
641
                    <code class="classname">direct_mask_range_hashing</code>
642
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
643
                    <code class="classname">Resize_Policy</code>
644
                  </td><td rowspan="2" style="text-align: left" valign="top">
645
                    <code class="classname">hash_standard_resize_policy</code>
646
                  </td><td style="text-align: left">
647
                    <code class="classname">Size_Policy</code>
648
                  </td><td style="text-align: left">
649
                    <code class="classname">hash_exponential_size_policy</code>
650
                  </td></tr><tr><td style="text-align: left" valign="top">
651
                    <code class="classname">Trigger_Policy</code>
652
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
656
                    cc_hash_mask_exp_1div2_nsth_map
657
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
658
                    <code class="classname">cc_hash_table</code>
659
                  </td><td style="text-align: left">
660
                    <code class="classname">Comb_Hash_Fn</code>
661
                  </td><td style="text-align: left">
662
                    <code class="classname">direct_mask_range_hashing</code>
663
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
664
                    <code class="classname">Resize_Policy</code>
665
                  </td><td rowspan="2" style="text-align: left" valign="top">
666
                    <code class="classname">hash_standard_resize_policy</code>
667
                  </td><td style="text-align: left">
668
                    <code class="classname">Size_Policy</code>
669
                  </td><td style="text-align: left">
670
                    <code class="classname">hash_exponential_size_policy</code>
671
                  </td></tr><tr><td style="text-align: left" valign="top">
672
                    <code class="classname">Trigger_Policy</code>
673
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_gp_hash_int_subscript_insert.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
685
                    n_hash_map_ncah
686
                  </td></tr><tr><td style="text-align: left">
687
                    <code class="classname">std::tr1::unordered_map</code>
688
                  </td><td style="text-align: left">
689
                    <code class="classname">cache_hash_code</code>
690
                  </td><td style="text-align: left">
691
                    <code class="constant">false</code>
692
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
693
                    gp_hash_mod_quadp_prime_1div2_nsth_map
694
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
695
                    <code class="classname">gp_hash_table</code>
696
                  </td><td style="text-align: left">
697
                    <code class="classname">Comb_Hash_Fn</code>
698
                  </td><td style="text-align: left">
699
                    <code class="classname">direct_mod_range_hashing</code>
700
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
701
                    <code class="classname">Probe_Fn</code>
702
                  </td><td style="text-align: left">
703
                    <code class="classname">quadratic_probe_fn</code>
704
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
705
                    <code class="classname">Resize_Policy</code>
706
                  </td><td rowspan="2" style="text-align: left" valign="top">
707
                    <code class="classname">hash_standard_resize_policy</code>
708
                  </td><td style="text-align: left">
709
                    <code class="classname">Size_Policy</code>
710
                  </td><td style="text-align: left">
711
                    <code class="classname">hash_prime_size_policy</code>
712
                  </td></tr><tr><td style="text-align: left" valign="top">
713
                    <code class="classname">Trigger_Policy</code>
714
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
718
                    gp_hash_mask_linp_exp_1div2_nsth_map
719
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
720
                    <code class="classname">
721
                      gp_hash_table
722
                    </code>
723
                  </td><td style="text-align: left">
724
                    <code class="classname">Comb_Hash_Fn</code>
725
                  </td><td style="text-align: left">
726
                    <code class="classname">direct_mask_range_hashing</code>
727
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
728
                    <code class="classname">Probe_Fn</code>
729
                  </td><td style="text-align: left">
730
                    <code class="classname">linear_probe_fn</code>
731
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
732
                    <code class="classname">Resize_Policy</code>
733
                  </td><td rowspan="2" style="text-align: left" valign="top">
734
                    <code class="classname">hash_standard_resize_policy</code>
735
                  </td><td style="text-align: left">
736
                    <code class="classname">Size_Policy</code>
737
                  </td><td style="text-align: left">
738
                    <code class="classname">hash_exponential_size_policy</code>
739
                  </td></tr><tr><td style="text-align: left" valign="top">
740
                    <code class="classname">Trigger_Policy</code>
741
                  </td><td style="text-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"/>
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"><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"/>
774
          Integer <code class="function">find</code> with Skewed-Distribution
775
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_hash_zlob_int_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
795
                    n_hash_map_ncah
796
                  </td></tr><tr><td style="text-align: left">
797
                    <code class="classname">std::tr1::unordered_map</code>
798
                  </td><td style="text-align: left">
799
                    <code class="classname">cache_hash_code</code>
800
                  </td><td style="text-align: left">
801
                    <code class="constant">false</code>
802
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
803
                    cc_hash_mod_prime_1div1_nsth_map
804
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
805
                    <code class="classname">cc_hash_table</code>
806
                  </td><td style="text-align: left">
807
                    <code class="classname">Comb_Hash_Fn</code>
808
                  </td><td style="text-align: left">
809
                    <code class="classname">direct_mod_range_hashing</code>
810
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
811
                    <code class="classname">Resize_Policy</code>
812
                  </td><td rowspan="2" style="text-align: left" valign="top">
813
                    <code class="classname">hash_standard_resize_policy</code>
814
                  </td><td style="text-align: left">
815
                    <code class="classname">Size_Policy</code>
816
                  </td><td style="text-align: left">
817
                    <code class="classname">hash_prime_size_policy</code>
818
                  </td></tr><tr><td style="text-align: left" valign="top">
819
                    <code class="classname">Trigger_Policy</code>
820
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
824
                    cc_hash_mask_exp_1div1_nsth_map
825
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
826
                    <code class="classname">
827
                      cc_hash_table
828
                    </code>
829
                  </td><td style="text-align: left">
830
                    <code class="classname">Comb_Hash_Fn</code>
831
                  </td><td style="text-align: left">
832
                    <code class="classname">direct_mask_range_hashing</code>
833
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
834
                    <code class="classname">Resize_Policy</code>
835
                  </td><td rowspan="2" style="text-align: left" valign="top">
836
                    <code class="classname">hash_standard_resize_policy</code>
837
                  </td><td style="text-align: left">
838
                    <code class="classname">Size_Policy</code>
839
                  </td><td style="text-align: left">
840
                    <code class="classname">hash_exponential_size_policy</code>
841
                  </td></tr><tr><td style="text-align: left" valign="top">
842
                    <code class="classname">Trigger_Policy</code>
843
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
847
                    gp_hash_mod_quadp_prime_1div2_nsth_map
848
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
849
                    <code class="classname">gp_hash_table</code>
850
                  </td><td style="text-align: left">
851
                    <code class="classname">Comb_Hash_Fn</code>
852
                  </td><td style="text-align: left">
853
                    <code class="classname">direct_mod_range_hashing</code>
854
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
855
                    <code class="classname">Probe_Fn</code>
856
                  </td><td style="text-align: left">
857
                    <code class="classname">quadratic_probe_fn</code>
858
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
859
                    <code class="classname">Resize_Policy</code>
860
                  </td><td rowspan="2" style="text-align: left" valign="top">
861
                    <code class="classname">hash_standard_resize_policy</code>
862
                  </td><td style="text-align: left">
863
                    <code class="classname">Size_Policy</code>
864
                  </td><td style="text-align: left">
865
                    <code class="classname">hash_prime_size_policy</code>
866
                  </td></tr><tr><td style="text-align: left" valign="top">
867
                    <code class="classname">Trigger_Policy</code>
868
                  </td><td style="text-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"/>
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"/>
899
          Erase Memory Use
900
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_hash_int_erase_mem.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
917
                    n_hash_map_ncah
918
                  </td></tr><tr><td style="text-align: left">
919
                    <code class="classname">std::tr1::unordered_map</code>
920
                  </td><td style="text-align: left">
921
                    <code class="classname">cache_hash_code</code>
922
                  </td><td style="text-align: left">
923
                    <code class="constant">false</code>
924
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
925
                    cc_hash_mod_prime_1div1_nsth_map
926
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
927
                    <code class="classname">cc_hash_table</code>
928
                  </td><td style="text-align: left">
929
                    <code class="classname">Comb_Hash_Fn</code>
930
                  </td><td style="text-align: left">
931
                    <code class="classname">direct_mod_range_hashing</code>
932
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
933
                    <code class="classname">Resize_Policy</code>
934
                  </td><td rowspan="2" style="text-align: left" valign="top">
935
                    <code class="classname">hash_standard_resize_policy</code>
936
                  </td><td style="text-align: left">
937
                    <code class="classname">Size_Policy</code>
938
                  </td><td style="text-align: left">
939
                    <code class="classname">hash_prime_size_policy</code>
940
                  </td></tr><tr><td style="text-align: left" valign="top">
941
                    <code class="classname">Trigger_Policy</code>
942
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
946
                    cc_hash_mask_exp_1div2_nsth_map
947
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
948
                    <code class="classname">
949
                      cc_hash_table
950
                    </code>
951
                  </td><td style="text-align: left">
952
                    <code class="classname">Comb_Hash_Fn</code>
953
                  </td><td style="text-align: left">
954
                    <code class="classname">direct_mask_range_hashing</code>
955
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
956
                    <code class="classname">Resize_Policy</code>
957
                  </td><td rowspan="2" style="text-align: left" valign="top">
958
                    <code class="classname">hash_standard_resize_policy</code>
959
                  </td><td style="text-align: left">
960
                    <code class="classname">Size_Policy</code>
961
                  </td><td style="text-align: left">
962
                    <code class="classname">hash_exponential_size_policy</code>
963
                  </td></tr><tr><td style="text-align: left" valign="top">
964
                    <code class="classname">Trigger_Policy</code>
965
                  </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left">
969
                    gp_hash_mask_linp_exp_1div2_nsth_set
970
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
971
                    <code class="classname">gp_hash_table</code>
972
                  </td><td style="text-align: left">
973
                    <code class="classname">Comb_Hash_Fn</code>
974
                  </td><td style="text-align: left">
975
                    <code class="classname">direct_mask_range_hashing</code>
976
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
977
                    <code class="classname">Probe_Fn</code>
978
                  </td><td style="text-align: left">
979
                    <code class="classname">linear_probe_fn</code>
980
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
981
                    <code class="classname">Resize_Policy</code>
982
                  </td><td rowspan="2" style="text-align: left" valign="top">
983
                    <code class="classname">hash_standard_resize_policy</code>
984
                  </td><td style="text-align: left">
985
                    <code class="classname">Size_Policy</code>
986
                  </td><td style="text-align: left">
987
                    <code class="classname">hash_exponential_size_policy</code>
988
                  </td></tr><tr><td style="text-align: left" valign="top">
989
                    <code class="classname">Trigger_Policy</code>
990
                  </td><td style="text-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"/>
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"/>Branch-Based</h4></div></div></div><p/><div class="section" title="Text insert"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_insert"/>
1002
          Text <code class="function">insert</code>
1003
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_tree_text_insert_node.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1027
                    n_map
1028
                  </td></tr><tr><td style="text-align: left">
1029
                    <code class="classname">std::map</code>
1030
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1031
                    splay_tree_map
1032
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1033
                    <code class="classname">tree</code>
1034
                  </td><td style="text-align: left">
1035
                    <code class="classname">Tag</code>
1036
                  </td><td style="text-align: left">
1037
                    <code class="classname">splay_tree_tag</code>
1038
                  </td></tr><tr><td style="text-align: left">
1039
                    <code class="classname">Node_update</code>
1040
                  </td><td style="text-align: left">
1041
                    <code class="classname">null_node_update</code>
1042
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1043
                    rb_tree_map
1044
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1045
                    <code class="classname">tree</code>
1046
                  </td><td style="text-align: left">
1047
                    <code class="classname">Tag</code>
1048
                  </td><td style="text-align: left">
1049
                    <code class="classname">rb_tree_tag</code>
1050
                  </td></tr><tr><td style="text-align: left">
1051
                    <code class="classname">Node_update</code>
1052
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_tree_text_insert_vector.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1060
                    n_map
1061
                  </td></tr><tr><td style="text-align: left">
1062
                    <code class="classname">std::map</code>
1063
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1064
                    ov_tree_map
1065
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1066
                    <code class="classname">tree</code>
1067
                  </td><td style="text-align: left">
1068
                    <code class="classname">Tag</code>
1069
                  </td><td style="text-align: left">
1070
                    <code class="classname">ov_tree_tag</code>
1071
                  </td></tr><tr><td style="text-align: left">
1072
                    <code class="classname">Node_update</code>
1073
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_tree_text_insert_trie.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1081
                    n_map
1082
                  </td></tr><tr><td style="text-align: left">
1083
                    <code class="classname">std::map</code>
1084
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1085
                    pat_trie_map
1086
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1087
                    <code class="classname">tree</code>
1088
                  </td><td style="text-align: left">
1089
                    <code class="classname">Tag</code>
1090
                  </td><td style="text-align: left">
1091
                    <code class="classname">pat_trie_tag</code>
1092
                  </td></tr><tr><td style="text-align: left">
1093
                    <code class="classname">Node_update</code>
1094
                  </td><td style="text-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"/>
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"/>
1117
          Text <code class="function">find</code>
1118
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_tree_text_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1139
                    n_map
1140
                  </td></tr><tr><td style="text-align: left">
1141
                    <code class="classname">std::map</code>
1142
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1143
                    splay_tree_map
1144
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1145
                    <code class="classname">tree</code>
1146
                  </td><td style="text-align: left">
1147
                    <code class="classname">Tag</code>
1148
                  </td><td style="text-align: left">
1149
                    <code class="classname">splay_tree_tag</code>
1150
                  </td></tr><tr><td style="text-align: left">
1151
                    <code class="classname">Node_Update</code>
1152
                  </td><td style="text-align: left">
1153
                    <code class="classname">null_node_update</code>
1154
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1155
                    rb_tree_map
1156
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1157
                    <code class="classname">tree</code>
1158
                  </td><td style="text-align: left">
1159
                    <code class="classname">Tag</code>
1160
                  </td><td style="text-align: left">
1161
                    <code class="classname">rb_tree_tag</code>
1162
                  </td></tr><tr><td style="text-align: left">
1163
                    <code class="classname">Node_Update</code>
1164
                  </td><td style="text-align: left">
1165
                    <code class="classname">null_node_update</code>
1166
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1167
                    ov_tree_map
1168
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1169
                    <code class="classname">tree</code>
1170
                  </td><td style="text-align: left">
1171
                    <code class="classname">Tag</code>
1172
                  </td><td style="text-align: left">
1173
                    <code class="classname">ov_tree_tag</code>
1174
                  </td></tr><tr><td style="text-align: left">
1175
                    <code class="classname">Node_Update</code>
1176
                  </td><td style="text-align: left">
1177
                    <code class="classname">null_node_update</code>
1178
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1179
                    pat_trie_map
1180
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1181
                    <code class="classname">tree</code>
1182
                  </td><td style="text-align: left">
1183
                    <code class="classname">Tag</code>
1184
                  </td><td style="text-align: left">
1185
                    <code class="classname">pat_trie_tag</code>
1186
                  </td></tr><tr><td style="text-align: left">
1187
                    <code class="classname">Node_Update</code>
1188
                  </td><td style="text-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"/>
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"><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"/>
1224
          Text <code class="function">find</code> with Locality-of-Reference
1225
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_tree_text_lor_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1249
                    n_map
1250
                  </td></tr><tr><td style="text-align: left">
1251
                    <code class="classname">std::map</code>
1252
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1253
                    splay_tree_map
1254
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1255
                    <code class="classname">tree</code>
1256
                  </td><td style="text-align: left">
1257
                    <code class="classname">Tag</code>
1258
                  </td><td style="text-align: left">
1259
                    <code class="classname">splay_tree_tag</code>
1260
                  </td></tr><tr><td style="text-align: left">
1261
                    <code class="classname">Node_Update</code>
1262
                  </td><td style="text-align: left">
1263
                    <code class="classname">null_node_update</code>
1264
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1265
                    rb_tree_map
1266
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1267
                    <code class="classname">tree</code>
1268
                  </td><td style="text-align: left">
1269
                    <code class="classname">Tag</code>
1270
                  </td><td style="text-align: left">
1271
                    <code class="classname">rb_tree_tag</code>
1272
                  </td></tr><tr><td style="text-align: left">
1273
                    <code class="classname">Node_Update</code>
1274
                  </td><td style="text-align: left">
1275
                    <code class="classname">null_node_update</code>
1276
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1277
                    ov_tree_map
1278
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1279
                    <code class="classname">tree</code>
1280
                  </td><td style="text-align: left">
1281
                    <code class="classname">Tag</code>
1282
                  </td><td style="text-align: left">
1283
                    <code class="classname">ov_tree_tag</code>
1284
                  </td></tr><tr><td style="text-align: left">
1285
                    <code class="classname">Node_Update</code>
1286
                  </td><td style="text-align: left">
1287
                    <code class="classname">null_node_update</code>
1288
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1289
                    pat_trie_map
1290
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1291
                    <code class="classname">tree</code>
1292
                  </td><td style="text-align: left">
1293
                    <code class="classname">Tag</code>
1294
                  </td><td style="text-align: left">
1295
                    <code class="classname">pat_trie_tag</code>
1296
                  </td></tr><tr><td style="text-align: left">
1297
                    <code class="classname">Node_Update</code>
1298
                  </td><td style="text-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"/>
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"/>
1311
          <code class="function">split</code> and <code class="function">join</code>
1312
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_tree_split_join.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1339
                    n_set
1340
                  </td></tr><tr><td style="text-align: left">
1341
                    <code class="classname">std::set</code>
1342
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1343
                    splay_tree_set
1344
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1345
                    <code class="classname">tree</code>
1346
                  </td><td style="text-align: left">
1347
                    <code class="classname">Tag</code>
1348
                  </td><td style="text-align: left">
1349
                    <code class="classname">splay_tree_tag</code>
1350
                  </td></tr><tr><td style="text-align: left">
1351
                    <code class="classname">Node_Update</code>
1352
                  </td><td style="text-align: left">
1353
                    <code class="classname">null_node_update</code>
1354
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1355
                    rb_tree_set
1356
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1357
                    <code class="classname">tree</code>
1358
                  </td><td style="text-align: left">
1359
                    <code class="classname">Tag</code>
1360
                  </td><td style="text-align: left">
1361
                    <code class="classname">rb_tree_tag</code>
1362
                  </td></tr><tr><td style="text-align: left">
1363
                    <code class="classname">Node_Update</code>
1364
                  </td><td style="text-align: left">
1365
                    <code class="classname">null_node_update</code>
1366
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1367
                    ov_tree_set
1368
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1369
                    <code class="classname">tree</code>
1370
                  </td><td style="text-align: left">
1371
                    <code class="classname">Tag</code>
1372
                  </td><td style="text-align: left">
1373
                    <code class="classname">ov_tree_tag</code>
1374
                  </td></tr><tr><td style="text-align: left">
1375
                    <code class="classname">Node_Update</code>
1376
                  </td><td style="text-align: left">
1377
                    <code class="classname">null_node_update</code>
1378
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1379
                    pat_trie_map
1380
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1381
                    <code class="classname">tree</code>
1382
                  </td><td style="text-align: left">
1383
                    <code class="classname">Tag</code>
1384
                  </td><td style="text-align: left">
1385
                    <code class="classname">pat_trie_tag</code>
1386
                  </td></tr><tr><td style="text-align: left">
1387
                    <code class="classname">Node_Update</code>
1388
                  </td><td style="text-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"/>
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"/>
1418
          Order-Statistics
1419
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_tree_order_statistics.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1444
                    n_set
1445
                  </td></tr><tr><td style="text-align: left">
1446
                    <code class="classname">std::set</code>
1447
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1448
                    splay_tree_ost_set
1449
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1450
                    <code class="classname">tree</code>
1451
                  </td><td style="text-align: left">
1452
                    <code class="classname">Tag</code>
1453
                  </td><td style="text-align: left">
1454
                    <code class="classname">splay_tree_tag</code>
1455
                  </td></tr><tr><td style="text-align: left">
1456
                    <code class="classname">Node_Update</code>
1457
                  </td><td style="text-align: left">
1458
                    <code class="classname">tree_order_statistics_node_update</code>
1459
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
1460
                    rb_tree_ost_set
1461
                  </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1462
                    <code class="classname">tree</code>
1463
                  </td><td style="text-align: left">
1464
                    <code class="classname">Tag</code>
1465
                  </td><td style="text-align: left">
1466
                    <code class="classname">rb_tree_tag</code>
1467
                  </td></tr><tr><td style="text-align: left">
1468
                    <code class="classname">Node_Update</code>
1469
                  </td><td style="text-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"/>
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"/>Multimap</h4></div></div></div><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"/>
1489
          Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios
1490
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_multimap_text_find_small_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1519
                    n_mmap
1520
                  </td></tr><tr><td style="text-align: left">
1521
                    <code class="classname">std::multimap</code>
1522
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1523
                    rb_tree_mmap_lu_mtf_set
1524
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1525
                    <code class="classname">tree</code>
1526
                  </td><td style="text-align: left">
1527
                    <code class="classname">Tag</code>
1528
                  </td><td style="text-align: left">
1529
                    <code class="classname">rb_tree_tag</code>
1530
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1531
                    <code class="classname">Node_Update</code>
1532
                  </td><td style="text-align: left">
1533
                    <code class="classname">null_node_update</code>
1534
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1535
                    <code class="classname">Mapped</code>
1536
                  </td><td style="text-align: left">
1537
                    <code class="classname">list_update</code>
1538
                  </td><td style="text-align: left">
1539
                    <code class="classname">Update_Policy</code>
1540
                  </td><td style="text-align: left">
1541
                    <code class="classname">lu_move_to_front_policy</code>
1542
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1543
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1544
                  </td></tr><tr><td rowspan="5" style="text-align: left" valign="top">
1545
                    <code class="classname">tree</code>
1546
                  </td><td style="text-align: left">
1547
                    <code class="classname">Tag</code>
1548
                  </td><td style="text-align: left">
1549
                    <code class="classname">rb_tree_tag</code>
1550
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1551
                    <code class="classname">Node_Update</code>
1552
                  </td><td style="text-align: left">
1553
                    <code class="classname">null_node_update</code>
1554
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1555
                    <code class="classname">Mapped</code>
1556
                  </td><td rowspan="3" style="text-align: left" valign="top">
1557
                    <code class="classname">cc_hash_table</code>
1558
                  </td><td style="text-align: left">
1559
                    <code class="classname">Comb_Hash_Fn</code>
1560
                  </td><td style="text-align: left">
1561
                    <code class="classname">direct_mask_range_hashing</code>
1562
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1563
                    <code class="classname">Resize_Policy</code>
1564
                  </td><td rowspan="2" style="text-align: left" valign="top">
1565
                    <code class="classname">hash_standard_resize_policy</code>
1566
                  </td><td style="text-align: left">
1567
                    <code class="classname">Size_Policy</code>
1568
                  </td><td style="text-align: left">
1569
                    <code class="classname">hash_exponential_size_policy</code>
1570
                  </td></tr><tr><td style="text-align: left" valign="top">
1571
                    <code class="classname">Trigger_Policy</code>
1572
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1581
                    n_hash_mmap
1582
                  </td></tr><tr><td style="text-align: left">
1583
                    <code class="classname">std::tr1::unordered_multimap</code>
1584
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1585
                    rb_tree_mmap_lu_mtf_set
1586
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
1587
                    <code class="classname">
1588
                      cc_hash_table
1589
                    </code>
1590
                  </td><td style="text-align: left">
1591
                    <code class="classname">Comb_Hash_Fn</code>
1592
                  </td><td style="text-align: left">
1593
                    <code class="classname">direct_mask_range_hashing</code>
1594
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1595
                    <code class="classname">Resize_Policy</code>
1596
                  </td><td rowspan="2" style="text-align: left" valign="top">
1597
                    <code class="classname">hash_standard_resize_policy</code>
1598
                  </td><td style="text-align: left">
1599
                    <code class="classname">Size_Policy</code>
1600
                  </td><td style="text-align: left">
1601
                    <code class="classname">hash_exponential_size_policy</code>
1602
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
1603
                    <code class="classname">Trigger_Policy</code>
1604
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1608
                    <code class="classname">Mapped</code>
1609
                  </td><td style="text-align: left">
1610
                    <code class="classname">list_update</code>
1611
                  </td><td style="text-align: left">
1612
                    <code class="classname">Update_Policy</code>
1613
                  </td><td style="text-align: left">
1614
                    <code class="classname">lu_move_to_front_policy</code>
1615
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1616
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1617
                  </td></tr><tr><td rowspan="6" style="text-align: left" valign="top">
1618
                    <code class="classname">
1619
                      cc_hash_table
1620
                    </code>
1621
                  </td><td style="text-align: left">
1622
                    <code class="classname">Comb_Hash_Fn</code>
1623
                  </td><td style="text-align: left">
1624
                    <code class="classname">direct_mask_range_hashing</code>
1625
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1626
                    <code class="classname">Resize_Policy</code>
1627
                  </td><td rowspan="2" style="text-align: left" valign="top">
1628
                    <code class="classname">hash_standard_resize_policy</code>
1629
                  </td><td style="text-align: left">
1630
                    <code class="classname">Size_Policy</code>
1631
                  </td><td style="text-align: left">
1632
                    <code class="classname">hash_exponential_size_policy</code>
1633
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
1634
                    <code class="classname">Trigger_Policy</code>
1635
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1639
                    <code class="classname">Mapped</code>
1640
                  </td><td rowspan="3" style="text-align: left" valign="top">
1641
                    <code class="classname">cc_hash_table</code>
1642
                  </td><td style="text-align: left">
1643
                    <code class="classname">Comb_Hash_Fn</code>
1644
                  </td><td style="text-align: left">
1645
                    <code class="classname">direct_mask_range_hashing</code>
1646
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1647
                    <code class="classname">Resize_Policy</code>
1648
                  </td><td rowspan="2" style="text-align: left" valign="top">
1649
                    <code class="classname">hash_standard_resize_policy</code>
1650
                  </td><td style="text-align: left">
1651
                    <code class="classname">Size_Policy</code>
1652
                  </td><td style="text-align: left">
1653
                    <code class="classname">hash_exponential_size_policy</code>
1654
                  </td></tr><tr><td style="text-align: left" valign="top">
1655
                    <code class="classname">Trigger_Policy</code>
1656
                  </td><td style="text-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"/>
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"/>
1663
          Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios
1664
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1692
                    n_mmap
1693
                  </td></tr><tr><td style="text-align: left">
1694
                    <code class="classname">std::multimap</code>
1695
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1696
                    rb_tree_mmap_lu_mtf_set
1697
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1698
                    <code class="classname">tree</code>
1699
                  </td><td style="text-align: left">
1700
                    <code class="classname">Tag</code>
1701
                  </td><td style="text-align: left">
1702
                    <code class="classname">rb_tree_tag</code>
1703
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1704
                    <code class="classname">Node_Update</code>
1705
                  </td><td style="text-align: left">
1706
                    <code class="classname">null_node_update</code>
1707
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1708
                    <code class="classname">Mapped</code>
1709
                  </td><td style="text-align: left">
1710
                    <code class="classname">list_update</code>
1711
                  </td><td style="text-align: left">
1712
                    <code class="classname">Update_Policy</code>
1713
                  </td><td style="text-align: left">
1714
                    <code class="classname">lu_move_to_front_policy</code>
1715
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1716
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1717
                  </td></tr><tr><td rowspan="5" style="text-align: left" valign="top">
1718
                    <code class="classname">tree</code>
1719
                  </td><td style="text-align: left">
1720
                    <code class="classname">Tag</code>
1721
                  </td><td style="text-align: left">
1722
                    <code class="classname">rb_tree_tag</code>
1723
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1724
                    <code class="classname">Node_Update</code>
1725
                  </td><td style="text-align: left">
1726
                    <code class="classname">null_node_update</code>
1727
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1728
                    <code class="classname">Mapped</code>
1729
                  </td><td rowspan="3" style="text-align: left" valign="top">
1730
                    <code class="classname">cc_hash_table</code>
1731
                  </td><td style="text-align: left">
1732
                    <code class="classname">Comb_Hash_Fn</code>
1733
                  </td><td style="text-align: left">
1734
                    <code class="classname">direct_mask_range_hashing</code>
1735
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1736
                    <code class="classname">Resize_Policy</code>
1737
                  </td><td rowspan="2" style="text-align: left" valign="top">
1738
                    <code class="classname">hash_standard_resize_policy</code>
1739
                  </td><td style="text-align: left">
1740
                    <code class="classname">Size_Policy</code>
1741
                  </td><td style="text-align: left">
1742
                    <code class="classname">hash_exponential_size_policy</code>
1743
                  </td></tr><tr><td style="text-align: left" valign="top">
1744
                    <code class="classname">Trigger_Policy</code>
1745
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1754
                    n_hash_mmap
1755
                  </td></tr><tr><td style="text-align: left">
1756
                    <code class="classname">std::tr1::unordered_multimap</code>
1757
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1758
                    rb_tree_mmap_lu_mtf_set
1759
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
1760
                    <code class="classname">
1761
                      cc_hash_table
1762
                    </code>
1763
                  </td><td style="text-align: left">
1764
                    <code class="classname">Comb_Hash_Fn</code>
1765
                  </td><td style="text-align: left">
1766
                    <code class="classname">direct_mask_range_hashing</code>
1767
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1768
                    <code class="classname">Resize_Policy</code>
1769
                  </td><td rowspan="2" style="text-align: left" valign="top">
1770
                    <code class="classname">hash_standard_resize_policy</code>
1771
                  </td><td style="text-align: left">
1772
                    <code class="classname">Size_Policy</code>
1773
                  </td><td style="text-align: left">
1774
                    <code class="classname">hash_exponential_size_policy</code>
1775
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
1776
                    <code class="classname">Trigger_Policy</code>
1777
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1781
                    <code class="classname">Mapped</code>
1782
                  </td><td style="text-align: left">
1783
                    <code class="classname">list_update</code>
1784
                  </td><td style="text-align: left">
1785
                    <code class="classname">Update_Policy</code>
1786
                  </td><td style="text-align: left">
1787
                    <code class="classname">lu_move_to_front_policy</code>
1788
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1789
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1790
                  </td></tr><tr><td rowspan="6" style="text-align: left" valign="top">
1791
                    <code class="classname">
1792
                      cc_hash_table
1793
                    </code>
1794
                  </td><td style="text-align: left">
1795
                    <code class="classname">Comb_Hash_Fn</code>
1796
                  </td><td style="text-align: left">
1797
                    <code class="classname">direct_mask_range_hashing</code>
1798
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1799
                    <code class="classname">Resize_Policy</code>
1800
                  </td><td rowspan="2" style="text-align: left" valign="top">
1801
                    <code class="classname">hash_standard_resize_policy</code>
1802
                  </td><td style="text-align: left">
1803
                    <code class="classname">Size_Policy</code>
1804
                  </td><td style="text-align: left">
1805
                    <code class="classname">hash_exponential_size_policy</code>
1806
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
1807
                    <code class="classname">Trigger_Policy</code>
1808
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1812
                    <code class="classname">Mapped</code>
1813
                  </td><td rowspan="3" style="text-align: left" valign="top">
1814
                    <code class="classname">cc_hash_table</code>
1815
                  </td><td style="text-align: left">
1816
                    <code class="classname">Comb_Hash_Fn</code>
1817
                  </td><td style="text-align: left">
1818
                    <code class="classname">direct_mask_range_hashing</code>
1819
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1820
                    <code class="classname">Resize_Policy</code>
1821
                  </td><td rowspan="2" style="text-align: left" valign="top">
1822
                    <code class="classname">hash_standard_resize_policy</code>
1823
                  </td><td style="text-align: left">
1824
                    <code class="classname">Size_Policy</code>
1825
                  </td><td style="text-align: left">
1826
                    <code class="classname">hash_exponential_size_policy</code>
1827
                  </td></tr><tr><td style="text-align: left" valign="top">
1828
                    <code class="classname">Trigger_Policy</code>
1829
                  </td><td style="text-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"/>
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"/>
1836
          Text <code class="function">insert</code> with Small
1837
          Secondary-to-Primary Key Ratios
1838
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_multimap_text_insert_small_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1868
                    n_mmap
1869
                  </td></tr><tr><td style="text-align: left">
1870
                    <code class="classname">std::multimap</code>
1871
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1872
                    rb_tree_mmap_lu_mtf_set
1873
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1874
                    <code class="classname">tree</code>
1875
                  </td><td style="text-align: left">
1876
                    <code class="classname">Tag</code>
1877
                  </td><td style="text-align: left">
1878
                    <code class="classname">rb_tree_tag</code>
1879
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1880
                    <code class="classname">Node_Update</code>
1881
                  </td><td style="text-align: left">
1882
                    <code class="classname">null_node_update</code>
1883
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1884
                    <code class="classname">Mapped</code>
1885
                  </td><td style="text-align: left">
1886
                    <code class="classname">list_update</code>
1887
                  </td><td style="text-align: left">
1888
                    <code class="classname">Update_Policy</code>
1889
                  </td><td style="text-align: left">
1890
                    <code class="classname">lu_move_to_front_policy</code>
1891
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1892
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1893
                  </td></tr><tr><td rowspan="5" style="text-align: left" valign="top">
1894
                    <code class="classname">tree</code>
1895
                  </td><td style="text-align: left">
1896
                    <code class="classname">Tag</code>
1897
                  </td><td style="text-align: left">
1898
                    <code class="classname">rb_tree_tag</code>
1899
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1900
                    <code class="classname">Node_Update</code>
1901
                  </td><td style="text-align: left">
1902
                    <code class="classname">null_node_update</code>
1903
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1904
                    <code class="classname">Mapped</code>
1905
                  </td><td rowspan="3" style="text-align: left" valign="top">
1906
                    <code class="classname">cc_hash_table</code>
1907
                  </td><td style="text-align: left">
1908
                    <code class="classname">Comb_Hash_Fn</code>
1909
                  </td><td style="text-align: left">
1910
                    <code class="classname">direct_mask_range_hashing</code>
1911
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1912
                    <code class="classname">Resize_Policy</code>
1913
                  </td><td rowspan="2" style="text-align: left" valign="top">
1914
                    <code class="classname">hash_standard_resize_policy</code>
1915
                  </td><td style="text-align: left">
1916
                    <code class="classname">Size_Policy</code>
1917
                  </td><td style="text-align: left">
1918
                    <code class="classname">hash_exponential_size_policy</code>
1919
                  </td></tr><tr><td style="text-align: left" valign="top">
1920
                    <code class="classname">Trigger_Policy</code>
1921
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1930
                    n_hash_mmap
1931
                  </td></tr><tr><td style="text-align: left">
1932
                    <code class="classname">std::tr1::unordered_multimap</code>
1933
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1934
                    rb_tree_mmap_lu_mtf_set
1935
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
1936
                    <code class="classname">
1937
                      cc_hash_table
1938
                    </code>
1939
                  </td><td style="text-align: left">
1940
                    <code class="classname">Comb_Hash_Fn</code>
1941
                  </td><td style="text-align: left">
1942
                    <code class="classname">direct_mask_range_hashing</code>
1943
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1944
                    <code class="classname">Resize_Policy</code>
1945
                  </td><td rowspan="2" style="text-align: left" valign="top">
1946
                    <code class="classname">hash_standard_resize_policy</code>
1947
                  </td><td style="text-align: left">
1948
                    <code class="classname">Size_Policy</code>
1949
                  </td><td style="text-align: left">
1950
                    <code class="classname">hash_exponential_size_policy</code>
1951
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
1952
                    <code class="classname">Trigger_Policy</code>
1953
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left">
1957
                    <code class="classname">Mapped</code>
1958
                  </td><td style="text-align: left">
1959
                    <code class="classname">list_update</code>
1960
                  </td><td style="text-align: left">
1961
                    <code class="classname">Update_Policy</code>
1962
                  </td><td style="text-align: left">
1963
                    <code class="classname">lu_move_to_front_policy</code>
1964
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
1965
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1966
                  </td></tr><tr><td rowspan="6" style="text-align: left" valign="top">
1967
                    <code class="classname">
1968
                      cc_hash_table
1969
                    </code>
1970
                  </td><td style="text-align: left">
1971
                    <code class="classname">Comb_Hash_Fn</code>
1972
                  </td><td style="text-align: left">
1973
                    <code class="classname">direct_mask_range_hashing</code>
1974
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1975
                    <code class="classname">Resize_Policy</code>
1976
                  </td><td rowspan="2" style="text-align: left" valign="top">
1977
                    <code class="classname">hash_standard_resize_policy</code>
1978
                  </td><td style="text-align: left">
1979
                    <code class="classname">Size_Policy</code>
1980
                  </td><td style="text-align: left">
1981
                    <code class="classname">hash_exponential_size_policy</code>
1982
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
1983
                    <code class="classname">Trigger_Policy</code>
1984
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
1988
                    <code class="classname">Mapped</code>
1989
                  </td><td rowspan="3" style="text-align: left" valign="top">
1990
                    <code class="classname">cc_hash_table</code>
1991
                  </td><td style="text-align: left">
1992
                    <code class="classname">Comb_Hash_Fn</code>
1993
                  </td><td style="text-align: left">
1994
                    <code class="classname">direct_mask_range_hashing</code>
1995
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
1996
                    <code class="classname">Resize_Policy</code>
1997
                  </td><td rowspan="2" style="text-align: left" valign="top">
1998
                    <code class="classname">hash_standard_resize_policy</code>
1999
                  </td><td style="text-align: left">
2000
                    <code class="classname">Size_Policy</code>
2001
                  </td><td style="text-align: left">
2002
                    <code class="classname">hash_exponential_size_policy</code>
2003
                  </td></tr><tr><td style="text-align: left" valign="top">
2004
                    <code class="classname">Trigger_Policy</code>
2005
                  </td><td style="text-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"/>
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"/>
2012
          Text <code class="function">insert</code> with Small
2013
          Secondary-to-Primary Key Ratios
2014
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_multimap_text_insert_large_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2044
                    n_mmap
2045
                  </td></tr><tr><td style="text-align: left">
2046
                    <code class="classname">std::multimap</code>
2047
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2048
                    rb_tree_mmap_lu_mtf_set
2049
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2050
                    <code class="classname">tree</code>
2051
                  </td><td style="text-align: left">
2052
                    <code class="classname">Tag</code>
2053
                  </td><td style="text-align: left">
2054
                    <code class="classname">rb_tree_tag</code>
2055
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2056
                    <code class="classname">Node_Update</code>
2057
                  </td><td style="text-align: left">
2058
                    <code class="classname">null_node_update</code>
2059
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2060
                    <code class="classname">Mapped</code>
2061
                  </td><td style="text-align: left">
2062
                    <code class="classname">list_update</code>
2063
                  </td><td style="text-align: left">
2064
                    <code class="classname">Update_Policy</code>
2065
                  </td><td style="text-align: left">
2066
                    <code class="classname">lu_move_to_front_policy</code>
2067
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2068
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2069
                  </td></tr><tr><td rowspan="5" style="text-align: left" valign="top">
2070
                    <code class="classname">tree</code>
2071
                  </td><td style="text-align: left">
2072
                    <code class="classname">Tag</code>
2073
                  </td><td style="text-align: left">
2074
                    <code class="classname">rb_tree_tag</code>
2075
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2076
                    <code class="classname">Node_Update</code>
2077
                  </td><td style="text-align: left">
2078
                    <code class="classname">null_node_update</code>
2079
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2080
                    <code class="classname">Mapped</code>
2081
                  </td><td rowspan="3" style="text-align: left" valign="top">
2082
                    <code class="classname">cc_hash_table</code>
2083
                  </td><td style="text-align: left">
2084
                    <code class="classname">Comb_Hash_Fn</code>
2085
                  </td><td style="text-align: left">
2086
                    <code class="classname">direct_mask_range_hashing</code>
2087
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2088
                    <code class="classname">Resize_Policy</code>
2089
                  </td><td rowspan="2" style="text-align: left" valign="top">
2090
                    <code class="classname">hash_standard_resize_policy</code>
2091
                  </td><td style="text-align: left">
2092
                    <code class="classname">Size_Policy</code>
2093
                  </td><td style="text-align: left">
2094
                    <code class="classname">hash_exponential_size_policy</code>
2095
                  </td></tr><tr><td style="text-align: left" valign="top">
2096
                    <code class="classname">Trigger_Policy</code>
2097
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2106
                    n_hash_mmap
2107
                  </td></tr><tr><td style="text-align: left">
2108
                    <code class="classname">std::tr1::unordered_multimap</code>
2109
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2110
                    rb_tree_mmap_lu_mtf_set
2111
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
2112
                    <code class="classname">
2113
                      cc_hash_table
2114
                    </code>
2115
                  </td><td style="text-align: left">
2116
                    <code class="classname">Comb_Hash_Fn</code>
2117
                  </td><td style="text-align: left">
2118
                    <code class="classname">direct_mask_range_hashing</code>
2119
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2120
                    <code class="classname">Resize_Policy</code>
2121
                  </td><td rowspan="2" style="text-align: left" valign="top">
2122
                    <code class="classname">hash_standard_resize_policy</code>
2123
                  </td><td style="text-align: left">
2124
                    <code class="classname">Size_Policy</code>
2125
                  </td><td style="text-align: left">
2126
                    <code class="classname">hash_exponential_size_policy</code>
2127
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
2128
                    <code class="classname">Trigger_Policy</code>
2129
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2133
                    <code class="classname">Mapped</code>
2134
                  </td><td style="text-align: left">
2135
                    <code class="classname">list_update</code>
2136
                  </td><td style="text-align: left">
2137
                    <code class="classname">Update_Policy</code>
2138
                  </td><td style="text-align: left">
2139
                    <code class="classname">lu_move_to_front_policy</code>
2140
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2141
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2142
                  </td></tr><tr><td rowspan="6" style="text-align: left" valign="top">
2143
                    <code class="classname">
2144
                      cc_hash_table
2145
                    </code>
2146
                  </td><td style="text-align: left">
2147
                    <code class="classname">Comb_Hash_Fn</code>
2148
                  </td><td style="text-align: left">
2149
                    <code class="classname">direct_mask_range_hashing</code>
2150
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2151
                    <code class="classname">Resize_Policy</code>
2152
                  </td><td rowspan="2" style="text-align: left" valign="top">
2153
                    <code class="classname">hash_standard_resize_policy</code>
2154
                  </td><td style="text-align: left">
2155
                    <code class="classname">Size_Policy</code>
2156
                  </td><td style="text-align: left">
2157
                    <code class="classname">hash_exponential_size_policy</code>
2158
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
2159
                    <code class="classname">Trigger_Policy</code>
2160
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2164
                    <code class="classname">Mapped</code>
2165
                  </td><td rowspan="3" style="text-align: left" valign="top">
2166
                    <code class="classname">cc_hash_table</code>
2167
                  </td><td style="text-align: left">
2168
                    <code class="classname">Comb_Hash_Fn</code>
2169
                  </td><td style="text-align: left">
2170
                    <code class="classname">direct_mask_range_hashing</code>
2171
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2172
                    <code class="classname">Resize_Policy</code>
2173
                  </td><td rowspan="2" style="text-align: left" valign="top">
2174
                    <code class="classname">hash_standard_resize_policy</code>
2175
                  </td><td style="text-align: left">
2176
                    <code class="classname">Size_Policy</code>
2177
                  </td><td style="text-align: left">
2178
                    <code class="classname">hash_exponential_size_policy</code>
2179
                  </td></tr><tr><td style="text-align: left" valign="top">
2180
                    <code class="classname">Trigger_Policy</code>
2181
                  </td><td style="text-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"/>
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"/>
2188
          Text <code class="function">insert</code> with Small
2189
          Secondary-to-Primary Key Ratios Memory Use
2190
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.info"/>
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"/>
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" style="text-align: center"><img src="../images/pbds_multimap_text_insert_mem_small_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2215
                    n_mmap
2216
                  </td></tr><tr><td style="text-align: left">
2217
                    <code class="classname">std::multimap</code>
2218
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2219
                    rb_tree_mmap_lu_mtf_set
2220
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2221
                    <code class="classname">tree</code>
2222
                  </td><td style="text-align: left">
2223
                    <code class="classname">Tag</code>
2224
                  </td><td style="text-align: left">
2225
                    <code class="classname">rb_tree_tag</code>
2226
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2227
                    <code class="classname">Node_Update</code>
2228
                  </td><td style="text-align: left">
2229
                    <code class="classname">null_node_update</code>
2230
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2231
                    <code class="classname">Mapped</code>
2232
                  </td><td style="text-align: left">
2233
                    <code class="classname">list_update</code>
2234
                  </td><td style="text-align: left">
2235
                    <code class="classname">Update_Policy</code>
2236
                  </td><td style="text-align: left">
2237
                    <code class="classname">lu_move_to_front_policy</code>
2238
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2239
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2240
                  </td></tr><tr><td rowspan="5" style="text-align: left" valign="top">
2241
                    <code class="classname">tree</code>
2242
                  </td><td style="text-align: left">
2243
                    <code class="classname">Tag</code>
2244
                  </td><td style="text-align: left">
2245
                    <code class="classname">rb_tree_tag</code>
2246
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2247
                    <code class="classname">Node_Update</code>
2248
                  </td><td style="text-align: left">
2249
                    <code class="classname">null_node_update</code>
2250
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2251
                    <code class="classname">Mapped</code>
2252
                  </td><td rowspan="3" style="text-align: left" valign="top">
2253
                    <code class="classname">cc_hash_table</code>
2254
                  </td><td style="text-align: left">
2255
                    <code class="classname">Comb_Hash_Fn</code>
2256
                  </td><td style="text-align: left">
2257
                    <code class="classname">direct_mask_range_hashing</code>
2258
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2259
                    <code class="classname">Resize_Policy</code>
2260
                  </td><td rowspan="2" style="text-align: left" valign="top">
2261
                    <code class="classname">hash_standard_resize_policy</code>
2262
                  </td><td style="text-align: left">
2263
                    <code class="classname">Size_Policy</code>
2264
                  </td><td style="text-align: left">
2265
                    <code class="classname">hash_exponential_size_policy</code>
2266
                  </td></tr><tr><td style="text-align: left" valign="top">
2267
                    <code class="classname">Trigger_Policy</code>
2268
                  </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2277
                    n_hash_mmap
2278
                  </td></tr><tr><td style="text-align: left">
2279
                    <code class="classname">std::tr1::unordered_multimap</code>
2280
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2281
                    rb_tree_mmap_lu_mtf_set
2282
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
2283
                    <code class="classname">
2284
                      cc_hash_table
2285
                    </code>
2286
                  </td><td style="text-align: left">
2287
                    <code class="classname">Comb_Hash_Fn</code>
2288
                  </td><td style="text-align: left">
2289
                    <code class="classname">direct_mask_range_hashing</code>
2290
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2291
                    <code class="classname">Resize_Policy</code>
2292
                  </td><td rowspan="2" style="text-align: left" valign="top">
2293
                    <code class="classname">hash_standard_resize_policy</code>
2294
                  </td><td style="text-align: left">
2295
                    <code class="classname">Size_Policy</code>
2296
                  </td><td style="text-align: left">
2297
                    <code class="classname">hash_exponential_size_policy</code>
2298
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
2299
                    <code class="classname">Trigger_Policy</code>
2300
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2304
                    <code class="classname">Mapped</code>
2305
                  </td><td style="text-align: left">
2306
                    <code class="classname">list_update</code>
2307
                  </td><td style="text-align: left">
2308
                    <code class="classname">Update_Policy</code>
2309
                  </td><td style="text-align: left">
2310
                    <code class="classname">lu_move_to_front_policy</code>
2311
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2312
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2313
                  </td></tr><tr><td rowspan="6" style="text-align: left" valign="top">
2314
                    <code class="classname">
2315
                      cc_hash_table
2316
                    </code>
2317
                  </td><td style="text-align: left">
2318
                    <code class="classname">Comb_Hash_Fn</code>
2319
                  </td><td style="text-align: left">
2320
                    <code class="classname">direct_mask_range_hashing</code>
2321
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2322
                    <code class="classname">Resize_Policy</code>
2323
                  </td><td rowspan="2" style="text-align: left" valign="top">
2324
                    <code class="classname">hash_standard_resize_policy</code>
2325
                  </td><td style="text-align: left">
2326
                    <code class="classname">Size_Policy</code>
2327
                  </td><td style="text-align: left">
2328
                    <code class="classname">hash_exponential_size_policy</code>
2329
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
2330
                    <code class="classname">Trigger_Policy</code>
2331
                  </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2335
                    <code class="classname">Mapped</code>
2336
                  </td><td rowspan="3" style="text-align: left" valign="top">
2337
                    <code class="classname">cc_hash_table</code>
2338
                  </td><td style="text-align: left">
2339
                    <code class="classname">Comb_Hash_Fn</code>
2340
                  </td><td style="text-align: left">
2341
                    <code class="classname">direct_mask_range_hashing</code>
2342
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2343
                    <code class="classname">Resize_Policy</code>
2344
                  </td><td rowspan="2" style="text-align: left" valign="top">
2345
                    <code class="classname">hash_standard_resize_policy</code>
2346
                  </td><td style="text-align: left">
2347
                    <code class="classname">Size_Policy</code>
2348
                  </td><td style="text-align: left">
2349
                    <code class="classname">hash_exponential_size_policy</code>
2350
                  </td></tr><tr><td style="text-align: left" valign="top">
2351
                    <code class="classname">Trigger_Policy</code>
2352
                  </td><td style="text-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"/>
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"/>
2359
          Text <code class="function">insert</code> with Small
2360
          Secondary-to-Primary Key Ratios Memory Use
2361
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.info"/>
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
          </p><p>The test checks the memory scalability of different
2378
          "multimap" designs.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.results"/>
2379
            Results
2380
          </h6></div></div></div><p>The graphic below show the results for "multimaps" which
2381
          use a tree-based container for primary keys.
2382
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_multimap_text_insert_mem_large_s2p_tree.png" style="text-align: middle"/></div></div><p>
2383
            The abbreviated names in the legend of the graphic above are
2384
            instantiated with the types in the following table.
2385
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2386
                    n_mmap
2387
                  </td></tr><tr><td style="text-align: left">
2388
                    <code class="classname">std::multimap</code>
2389
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2390
                    rb_tree_mmap_lu_mtf_set
2391
                  </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2392
                    <code class="classname">tree</code>
2393
                  </td><td style="text-align: left">
2394
                    <code class="classname">Tag</code>
2395
                  </td><td style="text-align: left">
2396
                    <code class="classname">rb_tree_tag</code>
2397
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2398
                    <code class="classname">Node_Update</code>
2399
                  </td><td style="text-align: left">
2400
                    <code class="classname">null_node_update</code>
2401
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2402
                    <code class="classname">Mapped</code>
2403
                  </td><td style="text-align: left">
2404
                    <code class="classname">list_update</code>
2405
                  </td><td style="text-align: left">
2406
                    <code class="classname">Update_Policy</code>
2407
                  </td><td style="text-align: left">
2408
                    <code class="classname">lu_move_to_front_policy</code>
2409
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2410
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2411
                  </td></tr><tr><td rowspan="5" style="text-align: left" valign="top">
2412
                    <code class="classname">tree</code>
2413
                  </td><td style="text-align: left">
2414
                    <code class="classname">Tag</code>
2415
                  </td><td style="text-align: left">
2416
                    <code class="classname">rb_tree_tag</code>
2417
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2418
                    <code class="classname">Node_Update</code>
2419
                  </td><td style="text-align: left">
2420
                    <code class="classname">null_node_update</code>
2421
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2422
                    <code class="classname">Mapped</code>
2423
                  </td><td rowspan="3" style="text-align: left" valign="top">
2424
                    <code class="classname">cc_hash_table</code>
2425
                  </td><td style="text-align: left">
2426
                    <code class="classname">Comb_Hash_Fn</code>
2427
                  </td><td style="text-align: left">
2428
                    <code class="classname">direct_mask_range_hashing</code>
2429
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2430
                    <code class="classname">Resize_Policy</code>
2431
                  </td><td rowspan="2" style="text-align: left" valign="top">
2432
                    <code class="classname">hash_standard_resize_policy</code>
2433
                  </td><td style="text-align: left">
2434
                    <code class="classname">Size_Policy</code>
2435
                  </td><td style="text-align: left">
2436
                    <code class="classname">hash_exponential_size_policy</code>
2437
                  </td></tr><tr><td style="text-align: left" valign="top">
2438
                    <code class="classname">Trigger_Policy</code>
2439
                  </td><td style="text-align: left">
2440
                    <code class="classname">hash_load_check_resize_trigger</code> with
2441
                    α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2442
                  </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
2443
          use a hash-based container for primary keys.
2444
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" style="text-align: middle"/></div></div><p>
2445
            The abbreviated names in the legend of the graphic above are
2446
            instantiated with the types in the following table.
2447
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2448
                    n_hash_mmap
2449
                  </td></tr><tr><td style="text-align: left">
2450
                    <code class="classname">std::tr1::unordered_multimap</code>
2451
                  </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2452
                    rb_tree_mmap_lu_mtf_set
2453
                  </td></tr><tr><td rowspan="4" style="text-align: left" valign="top">
2454
                    <code class="classname">
2455
                      cc_hash_table
2456
                    </code>
2457
                  </td><td style="text-align: left">
2458
                    <code class="classname">Comb_Hash_Fn</code>
2459
                  </td><td style="text-align: left">
2460
                    <code class="classname">direct_mask_range_hashing</code>
2461
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2462
                    <code class="classname">Resize_Policy</code>
2463
                  </td><td rowspan="2" style="text-align: left" valign="top">
2464
                    <code class="classname">hash_standard_resize_policy</code>
2465
                  </td><td style="text-align: left">
2466
                    <code class="classname">Size_Policy</code>
2467
                  </td><td style="text-align: left">
2468
                    <code class="classname">hash_exponential_size_policy</code>
2469
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
2470
                    <code class="classname">Trigger_Policy</code>
2471
                  </td><td style="text-align: left">
2472
                    <code class="classname">hash_load_check_resize_trigger</code> with
2473
                    α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2474
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left">
2475
                    <code class="classname">Mapped</code>
2476
                  </td><td style="text-align: left">
2477
                    <code class="classname">list_update</code>
2478
                  </td><td style="text-align: left">
2479
                    <code class="classname">Update_Policy</code>
2480
                  </td><td style="text-align: left">
2481
                    <code class="classname">lu_move_to_front_policy</code>
2482
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left">
2483
                    rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2484
                  </td></tr><tr><td rowspan="6" style="text-align: left" valign="top">
2485
                    <code class="classname">
2486
                      cc_hash_table
2487
                    </code>
2488
                  </td><td style="text-align: left">
2489
                    <code class="classname">Comb_Hash_Fn</code>
2490
                  </td><td style="text-align: left">
2491
                    <code class="classname">direct_mask_range_hashing</code>
2492
                  </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2493
                    <code class="classname">Resize_Policy</code>
2494
                  </td><td rowspan="2" style="text-align: left" valign="top">
2495
                    <code class="classname">hash_standard_resize_policy</code>
2496
                  </td><td style="text-align: left">
2497
                    <code class="classname">Size_Policy</code>
2498
                  </td><td style="text-align: left">
2499
                    <code class="classname">hash_exponential_size_policy</code>
2500
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top">
2501
                    <code class="classname">Trigger_Policy</code>
2502
                  </td><td style="text-align: left">
2503
                    <code class="classname">hash_load_check_resize_trigger</code> with
2504
                    α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2505
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top">
2506
                    <code class="classname">Mapped</code>
2507
                  </td><td rowspan="3" style="text-align: left" valign="top">
2508
                    <code class="classname">cc_hash_table</code>
2509
                  </td><td style="text-align: left">
2510
                    <code class="classname">Comb_Hash_Fn</code>
2511
                  </td><td style="text-align: left">
2512
                    <code class="classname">direct_mask_range_hashing</code>
2513
                  </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top">
2514
                    <code class="classname">Resize_Policy</code>
2515
                  </td><td rowspan="2" style="text-align: left" valign="top">
2516
                    <code class="classname">hash_standard_resize_policy</code>
2517
                  </td><td style="text-align: left">
2518
                    <code class="classname">Size_Policy</code>
2519
                  </td><td style="text-align: left">
2520
                    <code class="classname">hash_exponential_size_policy</code>
2521
                  </td></tr><tr><td style="text-align: left" valign="top">
2522
                    <code class="classname">Trigger_Policy</code>
2523
                  </td><td style="text-align: left">
2524
                    <code class="classname">hash_load_check_resize_trigger</code> with
2525
                    α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2526
                  </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_large.observations"/>
2527
            Observations
2528
          </h6></div></div></div><p>See Observations::Mapping-Semantics
2529
          Considerations.</p></div></div></div><div class="section" title="Priority Queue"><div class="titlepage"><div><div><h4 class="title"><a id="performance.priority_queue"/>Priority Queue</h4></div></div></div><div class="section" title="Text push"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_push"/>
2530
          Text <code class="function">push</code>
2531
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.info"/>
2532
            Description
2533
          </h6></div></div></div><p>This test inserts a number of values with keys from an
2534
          arbitrary text ([ wickland96thirty ]) into
2535
          a container using <code class="function">push</code>. It measures the average time
2536
          for <code class="function">push</code> as a function of the number of values
2537
          pushed.</p><p>
2538
            It uses the test file:
2539
            <code class="filename">
2540
              performance/ext/pb_ds/priority_queue_text_push_timing.cc
2541
            </code>
2542
          </p><p>The test checks the effect of different underlying data
2543
          structures.
2544
          </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.results"/>
2545
            Results
2546
          </h6></div></div></div><p>The two graphics below show the results for the native
2547
          priority_queues and this library's priority_queues.
2548
          </p><p>The graphic immediately below shows the results for the
2549
          native priority_queue type instantiated with different underlying
2550
          container types versus several different versions of library's
2551
          priority_queues.
2552
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_priority_queue_text_push.png" style="text-align: middle"/></div></div><p>
2553
            The abbreviated names in the legend of the graphic above are
2554
            instantiated with the types in the following table.
2555
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2556
                    n_pq_vector
2557
                  </td></tr><tr><td style="text-align: left">
2558
                    <code class="classname">std::priority_queue</code>
2559
                  </td><td style="text-align: left">
2560
                    <code class="classname">Sequence</code>
2561
                  </td><td style="text-align: left">
2562
                    <code class="classname">std::vector</code>
2563
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2564
                    n_pq_deque
2565
                  </td></tr><tr><td style="text-align: left">
2566
                    <code class="classname">std::priority_queue</code>
2567
                  </td><td style="text-align: left">
2568
                    <code class="classname">Sequence</code>
2569
                  </td><td style="text-align: left">
2570
                    <code class="classname">std::deque</code>
2571
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2572
                    binary_heap
2573
                  </td></tr><tr><td style="text-align: left">
2574
                    <code class="classname">priority_queue</code>
2575
                  </td><td style="text-align: left">
2576
                    <code class="classname">Tag</code>
2577
                  </td><td style="text-align: left">
2578
                    <code class="classname">binary_heap_tag</code>
2579
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2580
                    binomial_heap
2581
                  </td></tr><tr><td style="text-align: left">
2582
                    <code class="classname">priority_queue</code>
2583
                  </td><td style="text-align: left">
2584
                    <code class="classname">Tag</code>
2585
                  </td><td style="text-align: left">
2586
                    <code class="classname">binomial_heap_tag</code>
2587
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2588
                    rc_binomial_heap
2589
                  </td></tr><tr><td style="text-align: left">
2590
                    <code class="classname">priority_queue</code>
2591
                  </td><td style="text-align: left">
2592
                    <code class="classname">Tag</code>
2593
                  </td><td style="text-align: left">
2594
                    <code class="classname">rc_binomial_heap_tag</code>
2595
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2596
                    thin_heap
2597
                  </td></tr><tr><td style="text-align: left">
2598
                    <code class="classname">priority_queue</code>
2599
                  </td><td style="text-align: left">
2600
                    <code class="classname">Tag</code>
2601
                  </td><td style="text-align: left">
2602
                    <code class="classname">thin_heap_tag</code>
2603
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2604
                    pairing_heap
2605
                  </td></tr><tr><td style="text-align: left">
2606
                    <code class="classname">priority_queue</code>
2607
                  </td><td style="text-align: left">
2608
                    <code class="classname">Tag</code>
2609
                  </td><td style="text-align: left">
2610
                    <code class="classname">pairing_heap_tag</code>
2611
                  </td></tr></tbody></table></div><p>The graphic below shows the results for the binary-heap
2612
          based native priority queues and this library's pairing-heap
2613
          priority_queue data structures.
2614
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_pairing_priority_queue_text_push.png" style="text-align: middle"/></div></div><p>
2615
            The abbreviated names in the legend of the graphic above are
2616
            instantiated with the types in the following table.
2617
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2618
                    n_pq_vector
2619
                  </td></tr><tr><td style="text-align: left">
2620
                    <code class="classname">std::priority_queue</code>
2621
                  </td><td style="text-align: left">
2622
                    <code class="classname">Sequence</code>
2623
                  </td><td style="text-align: left">
2624
                    <code class="classname">std::vector</code>
2625
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2626
                    n_pq_deque
2627
                  </td></tr><tr><td style="text-align: left">
2628
                    <code class="classname">std::priority_queue</code>
2629
                  </td><td style="text-align: left">
2630
                    <code class="classname">Sequence</code>
2631
                  </td><td style="text-align: left">
2632
                    <code class="classname">std::deque</code>
2633
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2634
                    thin_heap
2635
                  </td></tr><tr><td style="text-align: left">
2636
                    <code class="classname">priority_queue</code>
2637
                  </td><td style="text-align: left">
2638
                    <code class="classname">Tag</code>
2639
                  </td><td style="text-align: left">
2640
                    <code class="classname">thin_heap_tag</code>
2641
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2642
                    pairing_heap
2643
                  </td></tr><tr><td style="text-align: left">
2644
                    <code class="classname">priority_queue</code>
2645
                  </td><td style="text-align: left">
2646
                    <code class="classname">Tag</code>
2647
                  </td><td style="text-align: left">
2648
                    <code class="classname">pairing_heap_tag</code>
2649
                  </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.observations"/>
2650
            Observations
2651
          </h6></div></div></div><p>Pairing heaps (<code class="classname">priority_queue</code> with
2652
          <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>)
2653
          are the most suited for sequences of <code class="function">push</code> and
2654
          <code class="function">pop</code> operations of non-primitive types (e.g.
2655
          <code class="classname">std::string</code>s). (See Priority Queue
2656
          Text <code class="function">push</code> and <code class="function">pop</code> Timing Test.) They are
2657
          less constrained than binomial heaps, e.g., and since
2658
          they are node-based, they outperform binary heaps. (See
2659
          Priority
2660
          Queue Random Integer <code class="function">push</code> Timing Test for the case
2661
          of primitive types.)</p><p>The standard's priority queues do not seem to perform well in
2662
          this case: the <code class="classname">std::vector</code> implementation needs to
2663
          perform a logarithmic sequence of string operations for each
2664
          operation, and the deque implementation is possibly hampered by
2665
          its need to manipulate a relatively-complex type (deques
2666
          support a O(1) <code class="function">push_front</code>, even though it is
2667
          not used by <code class="classname">std::priority_queue</code>.)</p></div></div><div class="section" title="Text push and pop"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_push_pop"/>
2668
          Text <code class="function">push</code> and <code class="function">pop</code>
2669
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.info"/>
2670
            Description
2671
          </h6></div></div></div><p>This test inserts a number of values with keys from an
2672
          arbitrary text ([ wickland96thirty ]) into
2673
          a container using <code class="classname">push</code> , then removes them using
2674
          <code class="classname">pop</code> . It measures the average time for <code class="classname">push</code>
2675
          as a function of the number of values.</p><p>
2676
            It uses the test file:
2677
            <code class="filename">
2678
              performance/ext/pb_ds/priority_queue_text_push_pop_timing.cc
2679
            </code>
2680
          </p><p>The test checks the effect of different underlying data
2681
          structures.
2682
          </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.results"/>
2683
            Results
2684
          </h6></div></div></div><p>The two graphics below show the results for the native
2685
          priority_queues and this library's priority_queues.
2686
          </p><p>The graphic immediately below shows the results for the
2687
          native priority_queue type instantiated with different underlying
2688
          container types versus several different versions of library's
2689
          priority_queues.
2690
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_priority_queue_text_push_pop.png" style="text-align: middle"/></div></div><p>
2691
            The abbreviated names in the legend of the graphic above are
2692
            instantiated with the types in the following table.
2693
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2694
                    n_pq_vector
2695
                  </td></tr><tr><td style="text-align: left">
2696
                    <code class="classname">std::priority_queue</code>
2697
                  </td><td style="text-align: left">
2698
                    <code class="classname">Sequence</code>
2699
                  </td><td style="text-align: left">
2700
                    <code class="classname">std::vector</code>
2701
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2702
                    n_pq_deque
2703
                  </td></tr><tr><td style="text-align: left">
2704
                    <code class="classname">std::priority_queue</code>
2705
                  </td><td style="text-align: left">
2706
                    <code class="classname">Sequence</code>
2707
                  </td><td style="text-align: left">
2708
                    <code class="classname">std::deque</code>
2709
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2710
                    binary_heap
2711
                  </td></tr><tr><td style="text-align: left">
2712
                    <code class="classname">priority_queue</code>
2713
                  </td><td style="text-align: left">
2714
                    <code class="classname">Tag</code>
2715
                  </td><td style="text-align: left">
2716
                    <code class="classname">binary_heap_tag</code>
2717
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2718
                    binomial_heap
2719
                  </td></tr><tr><td style="text-align: left">
2720
                    <code class="classname">priority_queue</code>
2721
                  </td><td style="text-align: left">
2722
                    <code class="classname">Tag</code>
2723
                  </td><td style="text-align: left">
2724
                    <code class="classname">binomial_heap_tag</code>
2725
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2726
                    rc_binomial_heap
2727
                  </td></tr><tr><td style="text-align: left">
2728
                    <code class="classname">priority_queue</code>
2729
                  </td><td style="text-align: left">
2730
                    <code class="classname">Tag</code>
2731
                  </td><td style="text-align: left">
2732
                    <code class="classname">rc_binomial_heap_tag</code>
2733
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2734
                    thin_heap
2735
                  </td></tr><tr><td style="text-align: left">
2736
                    <code class="classname">priority_queue</code>
2737
                  </td><td style="text-align: left">
2738
                    <code class="classname">Tag</code>
2739
                  </td><td style="text-align: left">
2740
                    <code class="classname">thin_heap_tag</code>
2741
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2742
                    pairing_heap
2743
                  </td></tr><tr><td style="text-align: left">
2744
                    <code class="classname">priority_queue</code>
2745
                  </td><td style="text-align: left">
2746
                    <code class="classname">Tag</code>
2747
                  </td><td style="text-align: left">
2748
                    <code class="classname">pairing_heap_tag</code>
2749
                  </td></tr></tbody></table></div><p>The graphic below shows the results for the native priority
2750
          queues and this library's pairing-heap priority_queue data
2751
          structures.
2752
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_pairing_priority_queue_text_push_pop.png" style="text-align: middle"/></div></div><p>
2753
            The abbreviated names in the legend of the graphic above are
2754
            instantiated with the types in the following table.
2755
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2756
                    n_pq_vector
2757
                  </td></tr><tr><td style="text-align: left">
2758
                    <code class="classname">std::priority_queue</code> adapting <code class="classname">std::vector</code>
2759
                  </td><td style="text-align: left">
2760
                    <code class="classname">Sequence</code>
2761
                  </td><td style="text-align: left">
2762
                    <code class="classname">std::vector</code>
2763
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2764
                    n_pq_deque
2765
                  </td></tr><tr><td style="text-align: left">
2766
                    <code class="classname">std::priority_queue</code>
2767
                  </td><td style="text-align: left">
2768
                    <code class="classname">Sequence</code>
2769
                  </td><td style="text-align: left">
2770
                    <code class="classname">std::deque</code>
2771
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2772
                    pairing_heap
2773
                  </td></tr><tr><td style="text-align: left">
2774
                    <code class="classname">priority_queue</code>
2775
                  </td><td style="text-align: left">
2776
                    <code class="classname">Tag</code>
2777
                  </td><td style="text-align: left">
2778
                    <code class="classname">pairing_heap_tag</code>
2779
                  </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.observations"/>
2780
            Observations
2781
          </h6></div></div></div><p>These results are very similar to Priority Queue Text
2782
          <code class="function">push</code> Timing Test. As stated there, pairing heaps
2783
          (<code class="classname">priority_queue</code> with
2784
          <code class="classname">Tag</code>
2785
          = <code class="classname">pairing_heap_tag</code>) are most suited
2786
          for <code class="function">push</code> and <code class="function">pop</code>
2787
          sequences of non-primitive types such as strings. Observing these
2788
          two tests, one can note that a pairing heap outperforms the others
2789
          in terms of <code class="function">push</code> operations, but equals
2790
          binary heaps (<code class="classname">priority_queue</code> with
2791
          <code class="classname">Tag</code>
2792
          = <code class="classname">binary_heap_tag</code>) if the number
2793
          of <code class="function">push</code> and <code class="function">pop</code>
2794
          operations is equal. As the number of <code class="function">pop</code>
2795
          operations is at most equal to the number
2796
          of <code class="function">push</code> operations, pairing heaps are better
2797
          in this case. See Priority Queue Random
2798
          Integer <code class="function">push</code> and <code class="function">pop</code>
2799
          Timing Test for a case which is different.</p></div></div><div class="section" title="Integer push"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.int_push"/>
2800
          Integer <code class="function">push</code>
2801
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.info"/>
2802
            Description
2803
          </h6></div></div></div><p>This test inserts a number of values with integer keys
2804
          into a container using <code class="function">push</code>. It
2805
          measures the average time for <code class="function">push</code> as a
2806
          function of the number of values.</p><p>
2807
            It uses the test file:
2808
            <code class="filename">
2809
              performance/ext/pb_ds/priority_queue_random_int_push_timing.cc
2810
            </code>
2811
          </p><p>The test checks the effect of different underlying data
2812
          structures.
2813
          </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.results"/>
2814
            Results
2815
          </h6></div></div></div><p>The two graphics below show the results for the native
2816
          priority_queues and this library's priority_queues.
2817
          </p><p>The graphic immediately below shows the results for the
2818
          native priority_queue type instantiated with different underlying
2819
          container types versus several different versions of library's
2820
          priority_queues.
2821
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_priority_queue_int_push.png" style="text-align: middle"/></div></div><p>
2822
            The abbreviated names in the legend of the graphic above are
2823
            instantiated with the types in the following table.
2824
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2825
                    n_pq_vector
2826
                  </td></tr><tr><td style="text-align: left">
2827
                    <code class="classname">std::priority_queue</code>
2828
                  </td><td style="text-align: left">
2829
                    <code class="classname">Sequence</code>
2830
                  </td><td style="text-align: left">
2831
                    <code class="classname">std::vector</code>
2832
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2833
                    n_pq_deque
2834
                  </td></tr><tr><td style="text-align: left">
2835
                    <code class="classname">std::priority_queue</code>
2836
                  </td><td style="text-align: left">
2837
                    <code class="classname">Sequence</code>
2838
                  </td><td style="text-align: left">
2839
                    <code class="classname">std::deque</code>
2840
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2841
                    binary_heap
2842
                  </td></tr><tr><td style="text-align: left">
2843
                    <code class="classname">priority_queue</code>
2844
                  </td><td style="text-align: left">
2845
                    <code class="classname">Tag</code>
2846
                  </td><td style="text-align: left">
2847
                    <code class="classname">binary_heap_tag</code>
2848
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2849
                    binomial_heap
2850
                  </td></tr><tr><td style="text-align: left">
2851
                    <code class="classname">priority_queue</code>
2852
                  </td><td style="text-align: left">
2853
                    <code class="classname">Tag</code>
2854
                  </td><td style="text-align: left">
2855
                    <code class="classname">binomial_heap_tag</code>
2856
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2857
                    rc_binomial_heap
2858
                  </td></tr><tr><td style="text-align: left">
2859
                    <code class="classname">priority_queue</code>
2860
                  </td><td style="text-align: left">
2861
                    <code class="classname">Tag</code>
2862
                  </td><td style="text-align: left">
2863
                    <code class="classname">rc_binomial_heap_tag</code>
2864
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2865
                    thin_heap
2866
                  </td></tr><tr><td style="text-align: left">
2867
                    <code class="classname">priority_queue</code>
2868
                  </td><td style="text-align: left">
2869
                    <code class="classname">Tag</code>
2870
                  </td><td style="text-align: left">
2871
                    <code class="classname">thin_heap_tag</code>
2872
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2873
                    pairing_heap
2874
                  </td></tr><tr><td style="text-align: left">
2875
                    <code class="classname">priority_queue</code>
2876
                  </td><td style="text-align: left">
2877
                    <code class="classname">Tag</code>
2878
                  </td><td style="text-align: left">
2879
                    <code class="classname">pairing_heap_tag</code>
2880
                  </td></tr></tbody></table></div><p>The graphic below shows the results for the binary-heap
2881
          based native priority queues and this library's
2882
          priority_queue data structures.
2883
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_binary_priority_queue_int_push.png" style="text-align: middle"/></div></div><p>
2884
            The abbreviated names in the legend of the graphic above are
2885
            instantiated with the types in the following table.
2886
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2887
                    n_pq_vector
2888
                  </td></tr><tr><td style="text-align: left">
2889
                    <code class="classname">std::priority_queue</code> adapting <code class="classname">std::vector</code>
2890
                  </td><td style="text-align: left">
2891
                    <code class="classname">Sequence</code>
2892
                  </td><td style="text-align: left">
2893
                    <code class="classname">std::vector</code>
2894
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2895
                    n_pq_deque
2896
                  </td></tr><tr><td style="text-align: left">
2897
                    <code class="classname">std::priority_queue</code>
2898
                  </td><td style="text-align: left">
2899
                    <code class="classname">Sequence</code>
2900
                  </td><td style="text-align: left">
2901
                    <code class="classname">std::deque</code>
2902
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2903
                    binary_heap
2904
                  </td></tr><tr><td style="text-align: left">
2905
                    <code class="classname">priority_queue</code>
2906
                  </td><td style="text-align: left">
2907
                    <code class="classname">Tag</code>
2908
                  </td><td style="text-align: left">
2909
                    <code class="classname">binary_heap_tag</code>
2910
                  </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.observations"/>
2911
            Observations
2912
          </h6></div></div></div><p>Binary heaps are the most suited for sequences of
2913
          <code class="function">push</code> and <code class="function">pop</code> operations of primitive types
2914
          (e.g. <span class="type">int</span>s). They are less constrained
2915
          than any other type, and since it is very efficient to store
2916
          such types in arrays, they outperform even pairing heaps. (See
2917
          Priority
2918
          Queue Text <code class="function">push</code> Timing Test for the case of
2919
          non-primitive types.)</p></div></div><div class="section" title="Integer push"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.int_push_pop"/>
2920
          Integer <code class="function">push</code>
2921
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.info"/>
2922
            Description
2923
          </h6></div></div></div><p>This test inserts a number of values with integer keys
2924
          into a container using <code class="function">push</code> , then removes them
2925
          using <code class="function">pop</code> . It measures the average time for
2926
          <code class="function">push</code> and <code class="function">pop</code> as a function
2927
          of the number of values.</p><p>
2928
            It uses the test file:
2929
            <code class="filename">
2930
              performance/ext/pb_ds/priority_queue_random_int_push_pop_timing.cc
2931
            </code>
2932
          </p><p>The test checks the effect of different underlying data
2933
          structures.
2934
          </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.results"/>
2935
            Results
2936
          </h6></div></div></div><p>The graphic immediately below shows the results for the
2937
          native priority_queue type instantiated with different underlying
2938
          container types versus several different versions of library's
2939
          priority_queues.
2940
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_priority_queue_int_push_pop.png" style="text-align: middle"/></div></div><p>
2941
            The abbreviated names in the legend of the graphic above are
2942
            instantiated with the types in the following table.
2943
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2944
                    n_pq_vector
2945
                  </td></tr><tr><td style="text-align: left">
2946
                    <code class="classname">std::priority_queue</code>
2947
                  </td><td style="text-align: left">
2948
                    <code class="classname">Sequence</code>
2949
                  </td><td style="text-align: left">
2950
                    <code class="classname">std::vector</code>
2951
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2952
                    n_pq_deque
2953
                  </td></tr><tr><td style="text-align: left">
2954
                    <code class="classname">std::priority_queue</code>
2955
                  </td><td style="text-align: left">
2956
                    <code class="classname">Sequence</code>
2957
                  </td><td style="text-align: left">
2958
                    <code class="classname">std::deque</code>
2959
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2960
                    binary_heap
2961
                  </td></tr><tr><td style="text-align: left">
2962
                    <code class="classname">priority_queue</code>
2963
                  </td><td style="text-align: left">
2964
                    <code class="classname">Tag</code>
2965
                  </td><td style="text-align: left">
2966
                    <code class="classname">binary_heap_tag</code>
2967
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2968
                    binomial_heap
2969
                  </td></tr><tr><td style="text-align: left">
2970
                    <code class="classname">priority_queue</code>
2971
                  </td><td style="text-align: left">
2972
                    <code class="classname">Tag</code>
2973
                  </td><td style="text-align: left">
2974
                    <code class="classname">binomial_heap_tag</code>
2975
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2976
                    rc_binomial_heap
2977
                  </td></tr><tr><td style="text-align: left">
2978
                    <code class="classname">priority_queue</code>
2979
                  </td><td style="text-align: left">
2980
                    <code class="classname">Tag</code>
2981
                  </td><td style="text-align: left">
2982
                    <code class="classname">rc_binomial_heap_tag</code>
2983
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2984
                    thin_heap
2985
                  </td></tr><tr><td style="text-align: left">
2986
                    <code class="classname">priority_queue</code>
2987
                  </td><td style="text-align: left">
2988
                    <code class="classname">Tag</code>
2989
                  </td><td style="text-align: left">
2990
                    <code class="classname">thin_heap_tag</code>
2991
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
2992
                    pairing_heap
2993
                  </td></tr><tr><td style="text-align: left">
2994
                    <code class="classname">priority_queue</code>
2995
                  </td><td style="text-align: left">
2996
                    <code class="classname">Tag</code>
2997
                  </td><td style="text-align: left">
2998
                    <code class="classname">pairing_heap_tag</code>
2999
                  </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.observations"/>
3000
            Observations
3001
          </h6></div></div></div><p>Binary heaps are the most suited for sequences of
3002
          <code class="function">push</code> and <code class="function">pop</code> operations of primitive types
3003
          (e.g. <span class="type">int</span>s). This is explained in
3004
          Priority
3005
          Queue Random Int <code class="function">push</code> Timing Test. (See Priority Queue
3006
          Text <code class="function">push</code> Timing Test for the case of primitive
3007
          types.)</p><p>At first glance it seems that the standard's vector-based
3008
          priority queue is approximately on par with this
3009
          library's corresponding priority queue. There are two
3010
          differences however:</p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>The standard's priority queue does not downsize the underlying
3011
            vector (or deque) as the priority queue becomes smaller
3012
            (see Priority Queue
3013
            Text <code class="function">pop</code> Memory Use Test). It is therefore
3014
            gaining some speed at the expense of space.</p></li><li class="listitem"><p>From Priority Queue Random
3015
            Integer <code class="function">push</code> and <code class="function">pop</code>
3016
            Timing Test, it seems that the standard's priority queue is
3017
            slower in terms of <code class="function">push</code> operations. Since
3018
            the number of
3019
            <code class="function">pop</code> operations is at most that of <code class="function">push</code>
3020
            operations, the test here is the "best" for the standard's
3021
            priority queue.</p></li></ol></div></div></div><div class="section" title="Text pop Memory Use"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_pop"/>
3022
          Text <code class="function">pop</code> Memory Use
3023
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.info"/>
3024
            Description
3025
          </h6></div></div></div><p>This test inserts a number of values with keys from an
3026
          arbitrary text ([ wickland96thirty ]) into
3027
          a container, then pops them until only one is left in the
3028
          container. It measures the memory use as a function of the
3029
          number of values pushed to the container.</p><p>
3030
            It uses the test file:
3031
            <code class="filename">
3032
              performance/ext/pb_ds/priority_queue_text_pop_mem_usage.cc
3033
            </code>
3034
          </p><p>The test checks the effect of different underlying data
3035
          structures.
3036
          </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.results"/>
3037
            Results
3038
          </h6></div></div></div><p>The graphic immediately below shows the results for the
3039
          native priority_queue type instantiated with different underlying
3040
          container types versus several different versions of library's
3041
          priority_queues.
3042
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_priority_queue_text_pop_mem.png" style="text-align: middle"/></div></div><p>
3043
            The abbreviated names in the legend of the graphic above are
3044
            instantiated with the types in the following table.
3045
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3046
                    n_pq_vector
3047
                  </td></tr><tr><td style="text-align: left">
3048
                    <code class="classname">std::priority_queue</code>
3049
                  </td><td style="text-align: left">
3050
                    <code class="classname">Sequence</code>
3051
                  </td><td style="text-align: left">
3052
                    <code class="classname">std::vector</code>
3053
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3054
                    n_pq_deque
3055
                  </td></tr><tr><td style="text-align: left">
3056
                    <code class="classname">std::priority_queue</code>
3057
                  </td><td style="text-align: left">
3058
                    <code class="classname">Sequence</code>
3059
                  </td><td style="text-align: left">
3060
                    <code class="classname">std::deque</code>
3061
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3062
                    binary_heap
3063
                  </td></tr><tr><td style="text-align: left">
3064
                    <code class="classname">priority_queue</code>
3065
                  </td><td style="text-align: left">
3066
                    <code class="classname">Tag</code>
3067
                  </td><td style="text-align: left">
3068
                    <code class="classname">binary_heap_tag</code>
3069
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3070
                    binomial_heap
3071
                  </td></tr><tr><td style="text-align: left">
3072
                    <code class="classname">priority_queue</code>
3073
                  </td><td style="text-align: left">
3074
                    <code class="classname">Tag</code>
3075
                  </td><td style="text-align: left">
3076
                    <code class="classname">binomial_heap_tag</code>
3077
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3078
                    rc_binomial_heap
3079
                  </td></tr><tr><td style="text-align: left">
3080
                    <code class="classname">priority_queue</code>
3081
                  </td><td style="text-align: left">
3082
                    <code class="classname">Tag</code>
3083
                  </td><td style="text-align: left">
3084
                    <code class="classname">rc_binomial_heap_tag</code>
3085
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3086
                    thin_heap
3087
                  </td></tr><tr><td style="text-align: left">
3088
                    <code class="classname">priority_queue</code>
3089
                  </td><td style="text-align: left">
3090
                    <code class="classname">Tag</code>
3091
                  </td><td style="text-align: left">
3092
                    <code class="classname">thin_heap_tag</code>
3093
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3094
                    pairing_heap
3095
                  </td></tr><tr><td style="text-align: left">
3096
                    <code class="classname">priority_queue</code>
3097
                  </td><td style="text-align: left">
3098
                    <code class="classname">Tag</code>
3099
                  </td><td style="text-align: left">
3100
                    <code class="classname">pairing_heap_tag</code>
3101
                  </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.observations"/>
3102
            Observations
3103
          </h6></div></div></div><p>The priority queue implementations (excluding the standard's) use
3104
          memory proportionally to the number of values they hold:
3105
          node-based implementations (e.g., a pairing heap) do so
3106
          naturally; this library's binary heap de-allocates memory when
3107
          a certain lower threshold is exceeded.</p><p>Note from Priority Queue Text <code class="function">push</code>
3108
          and <code class="function">pop</code> Timing Test and Priority Queue
3109
          Random Integer <code class="function">push</code>
3110
          and <code class="function">pop</code> Timing Test that this does not
3111
          impede performance compared to the standard's priority
3112
          queues.</p><p>See Hash-Based Erase
3113
          Memory Use Test for a similar phenomenon regarding priority
3114
          queues.</p></div></div><div class="section" title="Text join"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_join"/>
3115
          Text <code class="function">join</code>
3116
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.info"/>
3117
            Description
3118
          </h6></div></div></div><p>This test inserts a number of values with keys from an
3119
          arbitrary text ([ wickland96thirty ]) into
3120
          two containers, then merges the containers. It uses
3121
          <code class="function">join</code> for this library's priority queues; for
3122
          the standard's priority queues, it successively pops values from
3123
          one container and pushes them into the other. The test measures
3124
          the average time as a function of the number of values.</p><p>
3125
            It uses the test file:
3126
            <code class="filename">
3127
              performance/ext/pb_ds/priority_queue_text_join_timing.cc
3128
            </code>
3129
          </p><p>The test checks the effect of different underlying data
3130
          structures.
3131
          </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.results"/>
3132
            Results
3133
          </h6></div></div></div><p>The graphic immediately below shows the results for the
3134
          native priority_queue type instantiated with different underlying
3135
          container types versus several different versions of library's
3136
          priority_queues.
3137
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_priority_queue_text_join.png" style="text-align: middle"/></div></div><p>
3138
            The abbreviated names in the legend of the graphic above are
3139
            instantiated with the types in the following table.
3140
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3141
                    n_pq_vector
3142
                  </td></tr><tr><td style="text-align: left">
3143
                    <code class="classname">std::priority_queue</code>
3144
                  </td><td style="text-align: left">
3145
                    <code class="classname">Sequence</code>
3146
                  </td><td style="text-align: left">
3147
                    <code class="classname">std::vector</code>
3148
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3149
                    n_pq_deque
3150
                  </td></tr><tr><td style="text-align: left">
3151
                    <code class="classname">std::priority_queue</code>
3152
                  </td><td style="text-align: left">
3153
                    <code class="classname">Sequence</code>
3154
                  </td><td style="text-align: left">
3155
                    <code class="classname">std::deque</code>
3156
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3157
                    binary_heap
3158
                  </td></tr><tr><td style="text-align: left">
3159
                    <code class="classname">priority_queue</code>
3160
                  </td><td style="text-align: left">
3161
                    <code class="classname">Tag</code>
3162
                  </td><td style="text-align: left">
3163
                    <code class="classname">binary_heap_tag</code>
3164
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3165
                    binomial_heap
3166
                  </td></tr><tr><td style="text-align: left">
3167
                    <code class="classname">priority_queue</code>
3168
                  </td><td style="text-align: left">
3169
                    <code class="classname">Tag</code>
3170
                  </td><td style="text-align: left">
3171
                    <code class="classname">binomial_heap_tag</code>
3172
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3173
                    rc_binomial_heap
3174
                  </td></tr><tr><td style="text-align: left">
3175
                    <code class="classname">priority_queue</code>
3176
                  </td><td style="text-align: left">
3177
                    <code class="classname">Tag</code>
3178
                  </td><td style="text-align: left">
3179
                    <code class="classname">rc_binomial_heap_tag</code>
3180
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3181
                    thin_heap
3182
                  </td></tr><tr><td style="text-align: left">
3183
                    <code class="classname">priority_queue</code>
3184
                  </td><td style="text-align: left">
3185
                    <code class="classname">Tag</code>
3186
                  </td><td style="text-align: left">
3187
                    <code class="classname">thin_heap_tag</code>
3188
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3189
                    pairing_heap
3190
                  </td></tr><tr><td style="text-align: left">
3191
                    <code class="classname">priority_queue</code>
3192
                  </td><td style="text-align: left">
3193
                    <code class="classname">Tag</code>
3194
                  </td><td style="text-align: left">
3195
                    <code class="classname">pairing_heap_tag</code>
3196
                  </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.observations"/>
3197
            Observations
3198
          </h6></div></div></div><p>In this test the node-based heaps perform <code class="function">join</code> in
3199
          either logarithmic or constant time. The binary heap requires
3200
          linear time, since the well-known heapify algorithm [clrs2001] is linear.</p><p>It would be possible to apply the heapify algorithm to the
3201
          standard containers, if they would support iteration (which they
3202
          don't). Barring iterators, it is still somehow possible to perform
3203
          linear-time merge on a <code class="classname">std::vector</code>-based
3204
          standard priority queue, using <code class="function">top()</code>
3205
          and <code class="function">size()</code> (since they are enough to expose
3206
          the underlying array), but this is impossible for
3207
          a <code class="classname">std::deque</code>-based standard priority queue.
3208
          Without heapify, the cost is super-linear.</p></div></div><div class="section" title="Text modify Up"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_modify_up"/>
3209
          Text <code class="function">modify</code> Up
3210
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.info"/>
3211
            Description
3212
          </h6></div></div></div><p>This test inserts a number of values with keys from an
3213
          arbitrary text ([ wickland96thirty ]) into
3214
          into a container then modifies each one "up" (i.e., it
3215
          makes it larger). It uses <code class="function">modify</code> for this library's
3216
          priority queues; for the standard's priority queues, it pops values
3217
          from a container until it reaches the value that should be
3218
          modified, then pushes values back in. It measures the average
3219
          time for <code class="function">modify</code> as a function of the number of
3220
          values.</p><p>
3221
            It uses the test file:
3222
            <code class="filename">
3223
              performance/ext/pb_ds/priority_queue_text_modify_up_timing.cc
3224
            </code>
3225
          </p><p>The test checks the effect of different underlying data
3226
          structures for graph algorithms settings.  Note that making an
3227
          arbitrary value larger (in the sense of the priority queue's
3228
          comparison functor) corresponds to decrease-key in standard graph
3229
          algorithms [clrs2001].
3230
          </p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.results"/>
3231
            Results
3232
          </h6></div></div></div><p>The two graphics below show the results for the native
3233
          priority_queues and this library's priority_queues.
3234
          </p><p>The graphic immediately below shows the results for the
3235
          native priority_queue type instantiated with different underlying
3236
          container types versus several different versions of library's
3237
          priority_queues.
3238
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_priority_queue_text_modify_up.png" style="text-align: middle"/></div></div><p>
3239
            The abbreviated names in the legend of the graphic above are
3240
            instantiated with the types in the following table.
3241
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3242
                    n_pq_vector
3243
                  </td></tr><tr><td style="text-align: left">
3244
                    <code class="classname">std::priority_queue</code>
3245
                  </td><td style="text-align: left">
3246
                    <code class="classname">Sequence</code>
3247
                  </td><td style="text-align: left">
3248
                    <code class="classname">std::vector</code>
3249
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3250
                    n_pq_deque
3251
                  </td></tr><tr><td style="text-align: left">
3252
                    <code class="classname">std::priority_queue</code>
3253
                  </td><td style="text-align: left">
3254
                    <code class="classname">Sequence</code>
3255
                  </td><td style="text-align: left">
3256
                    <code class="classname">std::deque</code>
3257
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3258
                    binary_heap
3259
                  </td></tr><tr><td style="text-align: left">
3260
                    <code class="classname">priority_queue</code>
3261
                  </td><td style="text-align: left">
3262
                    <code class="classname">Tag</code>
3263
                  </td><td style="text-align: left">
3264
                    <code class="classname">binary_heap_tag</code>
3265
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3266
                    binomial_heap
3267
                  </td></tr><tr><td style="text-align: left">
3268
                    <code class="classname">priority_queue</code>
3269
                  </td><td style="text-align: left">
3270
                    <code class="classname">Tag</code>
3271
                  </td><td style="text-align: left">
3272
                    <code class="classname">binomial_heap_tag</code>
3273
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3274
                    rc_binomial_heap
3275
                  </td></tr><tr><td style="text-align: left">
3276
                    <code class="classname">priority_queue</code>
3277
                  </td><td style="text-align: left">
3278
                    <code class="classname">Tag</code>
3279
                  </td><td style="text-align: left">
3280
                    <code class="classname">rc_binomial_heap_tag</code>
3281
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3282
                    thin_heap
3283
                  </td></tr><tr><td style="text-align: left">
3284
                    <code class="classname">priority_queue</code>
3285
                  </td><td style="text-align: left">
3286
                    <code class="classname">Tag</code>
3287
                  </td><td style="text-align: left">
3288
                    <code class="classname">thin_heap_tag</code>
3289
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3290
                    pairing_heap
3291
                  </td></tr><tr><td style="text-align: left">
3292
                    <code class="classname">priority_queue</code>
3293
                  </td><td style="text-align: left">
3294
                    <code class="classname">Tag</code>
3295
                  </td><td style="text-align: left">
3296
                    <code class="classname">pairing_heap_tag</code>
3297
                  </td></tr></tbody></table></div><p>The graphic below shows the results for the
3298
          native priority queues and this library's pairing and thin heap
3299
          priority_queue data structures.
3300
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_pairing_priority_queue_text_modify_up_thin.png" style="text-align: middle"/></div></div><p>
3301
            The abbreviated names in the legend of the graphic above are
3302
            instantiated with the types in the following table.
3303
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3304
                    thin_heap
3305
                  </td></tr><tr><td style="text-align: left">
3306
                    <code class="classname">priority_queue</code>
3307
                  </td><td style="text-align: left">
3308
                    <code class="classname">Tag</code>
3309
                  </td><td style="text-align: left">
3310
                    <code class="classname">thin_heap_tag</code>
3311
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3312
                    pairing_heap
3313
                  </td></tr><tr><td style="text-align: left">
3314
                    <code class="classname">priority_queue</code>
3315
                  </td><td style="text-align: left">
3316
                    <code class="classname">Tag</code>
3317
                  </td><td style="text-align: left">
3318
                    <code class="classname">pairing_heap_tag</code>
3319
                  </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.observations"/>
3320
            Observations
3321
          </h6></div></div></div><p>As noted above, increasing an arbitrary value (in the sense of
3322
          the priority queue's comparison functor) is very common in
3323
          graph-related algorithms. In this case, a thin heap
3324
          (<code class="classname">priority_queue</code> with
3325
          <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>)
3326
          outperforms a pairing heap (<code class="classname">priority_queue</code> with
3327
          <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>).
3328
          Conversely, Priority Queue Text
3329
          <code class="function">push</code> Timing Test, Priority Queue
3330
          Text <code class="function">push</code> and <code class="function">pop</code> Timing Test, Priority
3331
          Queue Random Integer <code class="function">push</code> Timing Test, and
3332
          Priority
3333
          Queue Random Integer <code class="function">push</code> and <code class="function">pop</code> Timing
3334
          Test show that the situation is reversed for other
3335
          operations. It is not clear when to prefer one of these two
3336
          different types.</p><p>In this test this library's binary heaps
3337
          effectively perform modify in linear time. As explained in
3338
          Priority Queue Design::Traits, given a valid point-type iterator,
3339
          a binary heap can perform
3340
          <code class="function">modify</code> logarithmically. The problem is that binary
3341
          heaps invalidate their find iterators with each modifying
3342
          operation, and so the only way to obtain a valid point-type
3343
          iterator is to iterate using a range-type iterator until
3344
          finding the appropriate value, then use the range-type iterator
3345
          for the <code class="function">modify</code> operation.</p><p>The explanation for the standard's priority queues' performance
3346
          is similar to that in Priority Queue Text
3347
          <code class="function">join</code> Timing Test.</p></div></div><div class="section" title="Text modify Down"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_modify_down"/>
3348
          Text <code class="function">modify</code> Down
3349
        </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.info"/>
3350
            Description
3351
          </h6></div></div></div><p>This test inserts a number of values with keys from an
3352
          arbitrary text ([ wickland96thirty ]) into
3353
          into a container then modifies each one "down" (i.e., it
3354
          makes it smaller). It uses <code class="function">modify</code> for this library's
3355
          priority queues; for the standard's priority queues, it pops values
3356
          from a container until it reaches the value that should be
3357
          modified, then pushes values back in. It measures the average
3358
          time for <code class="function">modify</code> as a function of the number of
3359
          values.</p><p>
3360
            It uses the test file:
3361
            <code class="filename">
3362
              performance/ext/pb_ds/priority_queue_text_modify_down_timing.cc
3363
            </code>
3364
          </p><p>The main purpose of this test is to contrast Priority Queue
3365
          Text <code class="classname">modify</code> Up Timing Test.</p></div><div class="section" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.results"/>
3366
            Results
3367
          </h6></div></div></div><p>The two graphics below show the results for the native
3368
          priority_queues and this library's priority_queues.
3369
          </p><p>The graphic immediately below shows the results for the
3370
          native priority_queue type instantiated with different underlying
3371
          container types versus several different versions of library's
3372
          priority_queues.
3373
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_priority_queue_text_modify_down.png" style="text-align: middle"/></div></div><p>
3374
            The abbreviated names in the legend of the graphic above are
3375
            instantiated with the types in the following table.
3376
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3377
                    n_pq_vector
3378
                  </td></tr><tr><td style="text-align: left">
3379
                    <code class="classname">std::priority_queue</code>
3380
                  </td><td style="text-align: left">
3381
                    <code class="classname">Sequence</code>
3382
                  </td><td style="text-align: left">
3383
                    <code class="classname">std::vector</code>
3384
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3385
                    n_pq_deque
3386
                  </td></tr><tr><td style="text-align: left">
3387
                    <code class="classname">std::priority_queue</code>
3388
                  </td><td style="text-align: left">
3389
                    <code class="classname">Sequence</code>
3390
                  </td><td style="text-align: left">
3391
                    <code class="classname">std::deque</code>
3392
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3393
                    binary_heap
3394
                  </td></tr><tr><td style="text-align: left">
3395
                    <code class="classname">priority_queue</code>
3396
                  </td><td style="text-align: left">
3397
                    <code class="classname">Tag</code>
3398
                  </td><td style="text-align: left">
3399
                    <code class="classname">binary_heap_tag</code>
3400
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3401
                    binomial_heap
3402
                  </td></tr><tr><td style="text-align: left">
3403
                    <code class="classname">priority_queue</code>
3404
                  </td><td style="text-align: left">
3405
                    <code class="classname">Tag</code>
3406
                  </td><td style="text-align: left">
3407
                    <code class="classname">binomial_heap_tag</code>
3408
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3409
                    rc_binomial_heap
3410
                  </td></tr><tr><td style="text-align: left">
3411
                    <code class="classname">priority_queue</code>
3412
                  </td><td style="text-align: left">
3413
                    <code class="classname">Tag</code>
3414
                  </td><td style="text-align: left">
3415
                    <code class="classname">rc_binomial_heap_tag</code>
3416
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3417
                    thin_heap
3418
                  </td></tr><tr><td style="text-align: left">
3419
                    <code class="classname">priority_queue</code>
3420
                  </td><td style="text-align: left">
3421
                    <code class="classname">Tag</code>
3422
                  </td><td style="text-align: left">
3423
                    <code class="classname">thin_heap_tag</code>
3424
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3425
                    pairing_heap
3426
                  </td></tr><tr><td style="text-align: left">
3427
                    <code class="classname">priority_queue</code>
3428
                  </td><td style="text-align: left">
3429
                    <code class="classname">Tag</code>
3430
                  </td><td style="text-align: left">
3431
                    <code class="classname">pairing_heap_tag</code>
3432
                  </td></tr></tbody></table></div><p>The graphic below shows the results for the
3433
          native priority queues and this library's pairing and thin heap
3434
          priority_queue data structures.
3435
          </p><div class="informalfigure"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_pairing_priority_queue_text_modify_down_thin.png" style="text-align: middle"/></div></div><p>
3436
            The abbreviated names in the legend of the graphic above are
3437
            instantiated with the types in the following table.
3438
          </p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3439
                    thin_heap
3440
                  </td></tr><tr><td style="text-align: left">
3441
                    <code class="classname">priority_queue</code>
3442
                  </td><td style="text-align: left">
3443
                    <code class="classname">Tag</code>
3444
                  </td><td style="text-align: left">
3445
                    <code class="classname">thin_heap_tag</code>
3446
                  </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left">
3447
                    pairing_heap
3448
                  </td></tr><tr><td style="text-align: left">
3449
                    <code class="classname">priority_queue</code>
3450
                  </td><td style="text-align: left">
3451
                    <code class="classname">Tag</code>
3452
                  </td><td style="text-align: left">
3453
                    <code class="classname">pairing_heap_tag</code>
3454
                  </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.observations"/>
3455
            Observations
3456
          </h6></div></div></div><p>Most points in these results are similar to Priority Queue
3457
          Text <code class="function">modify</code> Up Timing Test.</p><p>It is interesting to note, however, that as opposed to that
3458
          test, a thin heap (<code class="classname">priority_queue</code> with
3459
          <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>) is
3460
          outperformed by a pairing heap (<code class="classname">priority_queue</code> with
3461
          <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>).
3462
          In this case, both heaps essentially perform an <code class="function">erase</code>
3463
          operation followed by a <code class="function">push</code> operation. As the other
3464
          tests show, a pairing heap is usually far more efficient than a
3465
          thin heap, so this is not surprising.</p><p>Most algorithms that involve priority queues increase values
3466
          (in the sense of the priority queue's comparison functor), and
3467
          so Priority Queue
3468
          Text <code class="classname">modify</code> Up Timing Test - is more interesting
3469
          than this test.</p></div></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.test.performance.observations"/>Observations</h4></div></div></div><div class="section" title="Associative"><div class="titlepage"><div><div><h5 class="title"><a id="observations.associative"/>Associative</h5></div></div></div><div class="section" title="Underlying Data-Structure Families"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.underlying"/>
3470
            Underlying Data-Structure Families
3471
          </h6></div></div></div><p>In general, hash-based containers have better timing performance
3472
          than containers based on different underlying-data structures. The
3473
          main reason to choose a tree-based or trie-based container is if a
3474
          byproduct of the tree-like structure is required: either
3475
          order-preservation, or the ability to utilize node invariants. If
3476
          memory-use is the major factor, an ordered-vector tree gives
3477
          optimal results (albeit with high modificiation costs), and a
3478
          list-based container gives reasonable results.</p></div><div class="section" title="Hash-Based Containers"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash"/>
3479
            Hash-Based Containers
3480
          </h6></div></div></div><p>Hash-based containers are typically either collision
3481
          chaining or probing. Collision-chaining
3482
          containers are more flexible internally, and so offer better
3483
          timing performance. Probing containers, if used for simple
3484
          value-types, manage memory more efficiently (they perform far
3485
          fewer allocation-related calls). In general, therefore, a
3486
          collision-chaining table should be used. A probing container,
3487
          conversely, might be used efficiently for operations such as
3488
          eliminating duplicates in a sequence, or counting the number of
3489
          occurrences within a sequence. Probing containers might be more
3490
          useful also in multithreaded applications where each thread
3491
          manipulates a hash-based container: in the standard, allocators have
3492
          class-wise semantics (see [meyers96more] - Item 10); a
3493
          probing container might incur less contention in this case.</p></div><div class="section" title="Hash Policies"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash_policies"/>
3494
            Hash Policies
3495
          </h6></div></div></div><p>In hash-based containers, the range-hashing scheme seems to
3496
          affect performance more than other considerations. In most
3497
          settings, a mask-based scheme works well (or can be made to
3498
          work well). If the key-distribution can be estimated a-priori,
3499
          a simple hash function can produce nearly uniform hash-value
3500
          distribution. In many other cases (e.g., text hashing,
3501
          floating-point hashing), the hash function is powerful enough
3502
          to generate hash values with good uniformity properties
3503
          [knuth98sorting];
3504
          a modulo-based scheme, taking into account all bits of the hash
3505
          value, appears to overlap the hash function in its effort.</p><p>The range-hashing scheme determines many of the other
3506
          policies. A mask-based scheme works
3507
          well with an exponential-size policy; for
3508
          probing-based containers, it goes well with a linear-probe
3509
          function.</p><p>An orthogonal consideration is the trigger policy. This
3510
          presents difficult tradeoffs. E.g., different load
3511
          factors in a load-check trigger policy yield a
3512
          space/amortized-cost tradeoff.</p></div><div class="section" title="Branch-Based Containers"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.branch"/>
3513
            Branch-Based Containers
3514
          </h6></div></div></div><p>In general, there are several families of tree-based
3515
          underlying data structures: balanced node-based trees
3516
          (e.g., red-black or AVL trees), high-probability
3517
          balanced node-based trees (e.g., random treaps or
3518
          skip-lists), competitive node-based trees (e.g., splay
3519
          trees), vector-based "trees", and tries. (Additionally, there
3520
          are disk-residing or network-residing trees, such as B-Trees
3521
          and their numerous variants. An interface for this would have
3522
          to deal with the execution model and ACID guarantees; this is
3523
          out of the scope of this library.) Following are some
3524
          observations on their application to different settings.</p><p>Of the balanced node-based trees, this library includes a
3525
          red-black tree, as does standard (in
3526
          practice). This type of tree is the "workhorse" of tree-based
3527
          containers: it offers both reasonable modification and
3528
          reasonable lookup time. Unfortunately, this data structure
3529
          stores a huge amount of metadata. Each node must contain,
3530
          besides a value, three pointers and a boolean. This type might
3531
          be avoided if space is at a premium [austern00noset].</p><p>High-probability balanced node-based trees suffer the
3532
          drawbacks of deterministic balanced trees. Although they are
3533
          fascinating data structures, preliminary tests with them showed
3534
          their performance was worse than red-black trees. The library
3535
          does not contain any such trees, therefore.</p><p>Competitive node-based trees have two drawbacks. They are
3536
          usually somewhat unbalanced, and they perform a large number of
3537
          comparisons. Balanced trees perform one comparison per each
3538
          node they encounter on a search path; a splay tree performs two
3539
          comparisons. If the keys are complex objects, e.g.,
3540
          <code class="classname">std::string</code>, this can increase the running time.
3541
          Conversely, such trees do well when there is much locality of
3542
          reference. It is difficult to determine in which case to prefer
3543
          such trees over balanced trees. This library includes a splay
3544
          tree.</p><p>Ordered-vector trees use very little space
3545
          [austern00noset].
3546
          They do not have any other advantages (at least in this
3547
          implementation).</p><p>Large-fan-out PATRICIA tries have excellent lookup
3548
          performance, but they do so through maintaining, for each node,
3549
          a miniature "hash-table". Their space efficiency is low, and
3550
          their modification performance is bad. These tries might be
3551
          used for semi-static settings, where order preservation is
3552
          important. Alternatively, red-black trees cross-referenced with
3553
          hash tables can be used. [okasaki98mereable]
3554
          discusses small-fan-out PATRICIA tries for integers, but the
3555
          cited results seem to indicate that the amortized cost of
3556
          maintaining such trees is higher than that of balanced trees.
3557
          Moderate-fan-out trees might be useful for sequences where each
3558
          element has a limited number of choices, e.g., DNA
3559
          strings.</p></div><div class="section" title="Mapping-Semantics"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.mapping_semantics"/>
3560
            Mapping-Semantics
3561
          </h6></div></div></div><p>Different mapping semantics were discussed in the introduction and design sections.Here
3562
          the focus will be on the case where a keys can be composed into
3563
          primary keys and secondary keys. (In the case where some keys
3564
          are completely identical, it is trivial that one should use an
3565
          associative container mapping values to size types.) In this
3566
          case there are (at least) five possibilities:</p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>Use an associative container that allows equivalent-key
3567
            values (such as <code class="classname">std::multimap</code>)</p></li><li class="listitem"><p>Use a unique-key value associative container that maps
3568
            each primary key to some complex associative container of
3569
            secondary keys, say a tree-based or hash-based container.
3570
            </p></li><li class="listitem"><p>Use a unique-key value associative container that maps
3571
            each primary key to some simple associative container of
3572
            secondary keys, say a list-based container.</p></li><li class="listitem"><p>Use a unique-key value associative container that maps
3573
            each primary key to some non-associative container
3574
            (e.g., <code class="classname">std::vector</code>)</p></li><li class="listitem"><p>Use a unique-key value associative container that takes
3575
            into account both primary and secondary keys.</p></li></ol></div><p>Stated simply: there is a simple answer for this. (Excluding
3576
          option 1, which should be avoided in all cases).</p><p>If the expected ratio of secondary keys to primary keys is
3577
          small, then 3 and 4 seem reasonable. Both types of secondary
3578
          containers are relatively lightweight (in terms of memory use
3579
          and construction time), and so creating an entire container
3580
          object for each primary key is not too expensive. Option 4
3581
          might be preferable to option 3 if changing the secondary key
3582
          of some primary key is frequent - one cannot modify an
3583
          associative container's key, and the only possibility,
3584
          therefore, is erasing the secondary key and inserting another
3585
          one instead; a non-associative container, conversely, can
3586
          support in-place modification. The actual cost of erasing a
3587
          secondary key and inserting another one depends also on the
3588
          allocator used for secondary associative-containers (The tests
3589
          above used the standard allocator, but in practice one might
3590
          choose to use, e.g., [boost_pool]). Option 2 is
3591
          definitely an overkill in this case. Option 1 loses out either
3592
          immediately (when there is one secondary key per primary key)
3593
          or almost immediately after that. Option 5 has the same
3594
          drawbacks as option 2, but it has the additional drawback that
3595
          finding all values whose primary key is equivalent to some key,
3596
          might be linear in the total number of values stored (for
3597
          example, if using a hash-based container).</p><p>If the expected ratio of secondary keys to primary keys is
3598
          large, then the answer is more complicated. It depends on the
3599
          distribution of secondary keys to primary keys, the
3600
          distribution of accesses according to primary keys, and the
3601
          types of operations most frequent.</p><p>To be more precise, assume there are m primary keys,
3602
          primary key i is mapped to n<sub>i</sub>
3603
          secondary keys, and each primary key is mapped, on average, to
3604
          n secondary keys (i.e.,
3605
          E(n<sub>i</sub>) = n).</p><p>Suppose one wants to find a specific pair of primary and
3606
          secondary keys. Using 1 with a tree based container
3607
          (<code class="classname">std::multimap</code>), the expected cost is
3608
          E(Θ(log(m) + n<sub>i</sub>)) = Θ(log(m) +
3609
          n); using 1 with a hash-based container
3610
          (<code class="classname">std::tr1::unordered_multimap</code>), the expected cost is
3611
          Θ(n). Using 2 with a primary hash-based container
3612
          and secondary hash-based containers, the expected cost is
3613
          O(1); using 2 with a primary tree-based container and
3614
          secondary tree-based containers, the expected cost is (using
3615
          the Jensen inequality [motwani95random])
3616
          E(O(log(m) + log(n<sub>i</sub>)) = O(log(m)) +
3617
          E(O(log(n<sub>i</sub>)) = O(log(m)) + O(log(n)),
3618
          assuming that primary keys are accessed equiprobably. 3 and 4
3619
          are similar to 1, but with lower constants. Using 5 with a
3620
          hash-based container, the expected cost is O(1); using 5
3621
          with a tree based container, the cost is
3622
          E(Θ(log(mn))) = Θ(log(m) +
3623
          log(n)).</p><p>Suppose one needs the values whose primary key matches some
3624
          given key. Using 1 with a hash-based container, the expected
3625
          cost is Θ(n), but the values will not be ordered
3626
          by secondary keys (which may or may not be required); using 1
3627
          with a tree-based container, the expected cost is
3628
          Θ(log(m) + n), but with high constants; again the
3629
          values will not be ordered by secondary keys. 2, 3, and 4 are
3630
          similar to 1, but typically with lower constants (and,
3631
          additionally, if one uses a tree-based container for secondary
3632
          keys, they will be ordered). Using 5 with a hash-based
3633
          container, the cost is Θ(mn).</p><p>Suppose one wants to assign to a primary key all secondary
3634
          keys assigned to a different primary key. Using 1 with a
3635
          hash-based container, the expected cost is Θ(n),
3636
          but with very high constants; using 1 with a tree-based
3637
          container, the cost is Θ(nlog(mn)). Using 2, 3,
3638
          and 4, the expected cost is Θ(n), but typically
3639
          with far lower costs than 1. 5 is similar to 1.</p></div></div><div class="section" title="Priority_Queue"><div class="titlepage"><div><div><h5 class="title"><a id="observations.priority_queue"/>Priority_Queue</h5></div></div></div><div class="section" title="Complexity"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.complexity"/>Complexity</h6></div></div></div><p>The following table shows the complexities of the different
3640
          underlying data structures in terms of orders of growth. It is
3641
          interesting to note that this table implies something about the
3642
          constants of the operations as well (see Amortized <code class="function">push</code>
3643
          and <code class="function">pop</code> operations).</p><div class="informaltable"><table border="1"><colgroup><col style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/></colgroup><thead><tr><th style="text-align: left"> </th><th style="text-align: left"><span class="emphasis"><em><code class="function">push</code></em></span></th><th style="text-align: left"><span class="emphasis"><em><code class="function">pop</code></em></span></th><th style="text-align: left"><span class="emphasis"><em><code class="function">modify</code></em></span></th><th style="text-align: left"><span class="emphasis"><em><code class="function">erase</code></em></span></th><th style="text-align: left"><span class="emphasis"><em><code class="function">join</code></em></span></th></tr></thead><tbody><tr><td style="text-align: left">
3644
                    <code class="classname">std::priority_queue</code>
3645
                  </td><td style="text-align: left">
3646
                    Θ(n) worst
3647
                    Θ(log(n)) amortized
3648
                  </td><td style="text-align: left">
3649
                    Θ(log(n)) Worst
3650
                  </td><td style="text-align: left">
3651
                    Θ(n log(n)) Worst
3652
                    <sub>[std note 1]</sub>
3653
                  </td><td style="text-align: left">
3654
                    Θ(n log(n))
3655
                    <sub>[std note 2]</sub>
3656
                  </td><td style="text-align: left">
3657
                    Θ(n log(n))
3658
                    <sub>[std note 1]</sub>
3659
                  </td></tr><tr><td style="text-align: left">
3660
                    <code class="classname">priority_queue</code>
3661
                    &lt;<code class="classname">Tag</code> =
3662
                    <code class="classname">pairing_heap_tag</code>&gt;
3663
                  </td><td style="text-align: left">
3664
                    O(1)
3665
                  </td><td style="text-align: left">
3666
                    Θ(n) worst
3667
                    Θ(log(n)) amortized
3668
                  </td><td style="text-align: left">
3669
                    Θ(n) worst
3670
                    Θ(log(n)) amortized
3671
                  </td><td style="text-align: left">
3672
                    Θ(n) worst
3673
                    Θ(log(n)) amortized
3674
                  </td><td style="text-align: left">
3675
                    O(1)
3676
                  </td></tr><tr><td style="text-align: left">
3677
                    <code class="classname">priority_queue</code>
3678
                    &lt;<code class="classname">Tag</code> =
3679
                    <code class="classname">binary_heap_tag</code>&gt;
3680
                  </td><td style="text-align: left">
3681
                    Θ(n) worst
3682
                    Θ(log(n)) amortized
3683
                  </td><td style="text-align: left">
3684
                    Θ(n) worst
3685
                    Θ(log(n)) amortized
3686
                  </td><td style="text-align: left">
3687
                    Θ(n)
3688
                  </td><td style="text-align: left">
3689
                    Θ(n)
3690
                  </td><td style="text-align: left">
3691
                    Θ(n)
3692
                  </td></tr><tr><td style="text-align: left">
3693
                    <code class="classname">priority_queue</code>
3694
                    &lt;<code class="classname">Tag</code> =
3695
                    <code class="classname">binomial_heap_tag</code>&gt;
3696
                  </td><td style="text-align: left">
3697
                    Θ(log(n)) worst
3698
                    O(1) amortized
3699
                  </td><td style="text-align: left">
3700
                    Θ(log(n))
3701
                  </td><td style="text-align: left">
3702
                    Θ(log(n))
3703
                  </td><td style="text-align: left">
3704
                    Θ(log(n))
3705
                  </td><td style="text-align: left">
3706
                    Θ(log(n))
3707
                  </td></tr><tr><td style="text-align: left">
3708
                    <code class="classname">priority_queue</code>
3709
                    &lt;<code class="classname">Tag</code> =
3710
                    <code class="classname">rc_binomial_heap_tag</code>&gt;
3711
                  </td><td style="text-align: left">
3712
                    O(1)
3713
                  </td><td style="text-align: left">
3714
                    Θ(log(n))
3715
                  </td><td style="text-align: left">
3716
                    Θ(log(n))
3717
                  </td><td style="text-align: left">
3718
                    Θ(log(n))
3719
                  </td><td style="text-align: left">
3720
                    Θ(log(n))
3721
                  </td></tr><tr><td style="text-align: left">
3722
                    <code class="classname">priority_queue</code>&lt;<code class="classname">Tag</code> =
3723
                    <code class="classname">thin_heap_tag</code>&gt;
3724
                  </td><td style="text-align: left">
3725
                    O(1)
3726
                  </td><td style="text-align: left">
3727
                    Θ(n) worst
3728
                    Θ(log(n)) amortized
3729
                  </td><td style="text-align: left">
3730
                    Θ(log(n)) worst
3731
                    O(1) amortized,
3732
                    or Θ(log(n)) amortized
3733
                    <sub>[thin_heap_note]</sub>
3734
                  </td><td style="text-align: left">
3735
                    Θ(n) worst
3736
                    Θ(log(n)) amortized
3737
                  </td><td style="text-align: left">
3738
                    Θ(n)
3739
                  </td></tr></tbody></table></div><p>[std note 1] This
3740
          is not a property of the algorithm, but rather due to the fact
3741
          that the standard's priority queue implementation does not support
3742
          iterators (and consequently the ability to access a specific
3743
          value inside it). If the priority queue is adapting an
3744
          <code class="classname">std::vector</code>, then it is still possible to reduce this
3745
          to Θ(n) by adapting over the standard's adapter and
3746
          using the fact that <code class="function">top</code> returns a reference to the
3747
          first value; if, however, it is adapting an
3748
          <code class="classname">std::deque</code>, then this is impossible.</p><p>[std note 2] As
3749
          with [std note 1], this is not a
3750
          property of the algorithm, but rather the standard's implementation.
3751
          Again, if the priority queue is adapting an
3752
          <code class="classname">std::vector</code> then it is possible to reduce this to
3753
          Θ(n), but with a very high constant (one must call
3754
          <code class="function">std::make_heap</code> which is an expensive linear
3755
          operation); if the priority queue is adapting an
3756
          <code class="classname">std::deque</code>, then this is impossible.</p><p>[thin_heap_note] A thin heap has
3757
          Θ(log(n)) worst case <code class="function">modify</code> time
3758
          always, but the amortized time depends on the nature of the
3759
          operation: I) if the operation increases the key (in the sense
3760
          of the priority queue's comparison functor), then the amortized
3761
          time is O(1), but if II) it decreases it, then the
3762
          amortized time is the same as the worst case time. Note that
3763
          for most algorithms, I) is important and II) is not.</p></div><div class="section" title="Amortized push and pop operations"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.amortized_ops"/>
3764
            Amortized <code class="function">push</code>
3765
            and <code class="function">pop</code> operations
3766
          </h6></div></div></div><p>In many cases, a priority queue is needed primarily for
3767
          sequences of <code class="function">push</code> and <code class="function">pop</code> operations. All of
3768
          the underlying data structures have the same amortized
3769
          logarithmic complexity, but they differ in terms of
3770
          constants.</p><p>The table above shows that the different data structures are
3771
          "constrained" in some respects. In general, if a data structure
3772
          has lower worst-case complexity than another, then it will
3773
          perform slower in the amortized sense. Thus, for example a
3774
          redundant-counter binomial heap (<code class="classname">priority_queue</code> with
3775
          <code class="classname">Tag</code> = <code class="classname">rc_binomial_heap_tag</code>)
3776
          has lower worst-case <code class="function">push</code> performance than a binomial
3777
          heap (<code class="classname">priority_queue</code>
3778
          with <code class="classname">Tag</code> = <code class="classname">binomial_heap_tag</code>),
3779
          and so its amortized <code class="function">push</code> performance is slower in
3780
          terms of constants.</p><p>As the table shows, the "least constrained" underlying
3781
          data structures are binary heaps and pairing heaps.
3782
          Consequently, it is not surprising that they perform best in
3783
          terms of amortized constants.</p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>Pairing heaps seem to perform best for non-primitive
3784
            types (e.g., <code class="classname">std::string</code>s), as shown by
3785
            Priority
3786
            Queue Text <code class="function">push</code> Timing Test and Priority
3787
            Queue Text <code class="function">push</code> and <code class="function">pop</code> Timing
3788
            Test</p></li><li class="listitem"><p>binary heaps seem to perform best for primitive types
3789
            (e.g., <span class="type">int</span>s), as shown by Priority
3790
            Queue Random Integer <code class="function">push</code> Timing Test and
3791
            Priority
3792
            Queue Random Integer <code class="function">push</code> and <code class="function">pop</code> Timing
3793
            Test.</p></li></ol></div></div><div class="section" title="Graph Algorithms"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.graphs"/>
3794
            Graph Algorithms
3795
          </h6></div></div></div><p>In some graph algorithms, a decrease-key operation is
3796
          required [clrs2001];
3797
          this operation is identical to <code class="function">modify</code> if a value is
3798
          increased (in the sense of the priority queue's comparison
3799
          functor). The table above and Priority Queue
3800
          Text <code class="function">modify</code> Up Timing Test show that a thin heap
3801
          (<code class="classname">priority_queue</code> with
3802
          <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>)
3803
          outperforms a pairing heap (<code class="classname">priority_queue</code> with
3804
          <code class="classname">Tag</code> = <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>),
3805
          but the rest of the tests show otherwise.</p><p>This makes it difficult to decide which implementation to use in
3806
          this case. Dijkstra's shortest-path algorithm, for example, requires
3807
          Θ(n) <code class="function">push</code> and <code class="function">pop</code> operations
3808
          (in the number of vertices), but O(n<sup>2</sup>)
3809
          <code class="function">modify</code> operations, which can be in practice Θ(n)
3810
          as well. It is difficult to find an a-priori characterization of
3811
          graphs in which the actual number of <code class="function">modify</code>
3812
          operations will dwarf the number of <code class="function">push</code> and
3813
          <code class="function">pop</code> operations.</p></div></div></div></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td align="left"><a accesskey="p" href="policy_data_structures_design.html">Prev</a> </td><td align="center"><a accesskey="u" href="policy_data_structures.html">Up</a></td><td align="right"> <a accesskey="n" href="policy_data_structures_biblio.html">Next</a></td></tr><tr><td align="left" valign="top">Design </td><td align="center"><a accesskey="h" href="../index.html">Home</a></td><td align="right" valign="top"> Acknowledgments</td></tr></table></div></body></html>

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.