1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
6 <meta name="generator" content="HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
7 <title>Associative-Container Performance Tests</title>
8 <meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
12 <h1><a name="assoc" id="assoc">Associative-Container
13 Performance Tests</a></h1>
14 <h2><a name="settings" id="settings">Settings</a></h2>
15 <p>This section describes performance tests and their results.
16 In the following, <a href="#gcc"><u>g++</u></a>, <a href="#msvc"><u>msvc++</u></a>, and <a href="#local"><u>local</u></a> (the build used for generating this
17 documentation) stand for three different builds:</p>
18 <div id="gcc_settings_div">
20 <h3><a name="gcc" id="gcc"><u>g++</u></a></h3>
22 <li>CPU speed - cpu MHz : 2660.644</li>
23 <li>Memory - MemTotal: 484412 kB</li>
25 Linux-2.6.12-9-386-i686-with-debian-testing-unstable</li>
26 <li>Compiler - g++ (GCC) 4.0.2 20050808 (prerelease)
27 (Ubuntu 4.0.1-4ubuntu9) Copyright (C) 2005 Free Software
28 Foundation, Inc. This is free software; see the source
29 for copying conditions. There is NO warranty; not even
30 for MERCHANTABILITY or FITNESS FOR A PARTICULAR
34 <div class="c2"></div>
36 <div id="msvc_settings_div">
38 <h3><a name="msvc" id="msvc"><u>msvc++</u></a></h3>
40 <li>CPU speed - cpu MHz : 2660.554</li>
41 <li>Memory - MemTotal: 484412 kB</li>
42 <li>Platform - Windows XP Pro</li>
43 <li>Compiler - Microsoft (R) 32-bit C/C++ Optimizing
44 Compiler Version 13.10.3077 for 80x86 Copyright (C)
45 Microsoft Corporation 1984-2002. All rights
49 <div class="c2"></div>
51 <div id="local_settings_div"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h3><a name = "local"><u>local</u></a></h3><ul>
52 <li>CPU speed - cpu MHz : 2250.000</li>
53 <li>Memory - MemTotal: 2076248 kB</li>
54 <li>Platform - Linux-2.6.16-1.2133_FC5-i686-with-redhat-5-Bordeaux</li>
55 <li>Compiler - g++ (GCC) 4.1.1 20060525 (Red Hat 4.1.1-1)
56 Copyright (C) 2006 Free Software Foundation, Inc.
57 This is free software; see the source for copying conditions. There is NO
58 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
61 </div><div style = "width: 100%; height: 20px"></div></div>
62 <h2><a name="assoc_tests" id="assoc_tests">Tests</a></h2>
63 <h3><a name="hash_based" id="hash_based">Hash-Based
66 <li><a href="hash_text_find_find_timing_test.html">Hash-Based
67 Text <tt>find</tt> Find Timing Test</a></li>
68 <li><a href="hash_random_int_find_find_timing_test.html">Hash-Based
69 Random-Integer <tt>find</tt> Find Timing Test</a></li>
70 <li><a href="hash_random_int_subscript_find_timing_test.html">Hash-Based
71 Random-Integer Subscript Find Timing Test</a></li>
72 <li><a href="hash_random_int_subscript_insert_timing_test.html">Hash-Based
73 Random-Integer Subscript Insert Timing Test</a></li>
74 <li><a href="hash_zlob_random_int_find_find_timing_test.html">Hash-Based
75 Skewed-Distribution Random-Integer <tt>find</tt> Find Timing
77 <li><a href="hash_random_int_erase_mem_usage_test.html">Hash-Based Erase
78 Memory Use Test</a></li>
80 <h3><a name="tree_like_based" id="tree_like_based">Tree-Like-Based Containers</a></h3>
82 <li><a href="tree_text_insert_timing_test.html">Tree-Based
83 and Trie-Based Text Insert Timing Test</a></li>
84 <li><a href="tree_text_find_find_timing_test.html">Tree-Based
85 and Trie-Based Text <tt>find</tt> Find Timing Test</a></li>
86 <li><a href="tree_text_lor_find_find_timing_test.html">Tree-Based
87 Locality-of-Reference Text <tt>find</tt> Find Timing
89 <li><a href="tree_random_int_find_find_timing_test.html">Tree-Based
90 Random-Integer <tt>find</tt> Find Timing Test</a></li>
91 <li><a href="tree_split_join_timing_test.html">Tree Split and
92 Join Timing Test</a></li>
93 <li><a href="tree_order_statistics_timing_test.html">Tree
94 Order-Statistics Timing Test</a></li>
96 <h3><a name="multimaps" id="multimaps">Multimaps</a></h3>
98 <li><a href="multimap_text_find_timing_test_small.html">"Multimap"
99 Text Find Timing Test with <u>Small</u> Average Secondary-Key
100 to Primary-Key Ratio</a></li>
101 <li><a href="multimap_text_find_timing_test_large.html">"Multimap"
102 Text Find Timing Test with <u>Large</u> Average Secondary-Key
103 to Primary-Key Ratio</a></li>
104 <li><a href="multimap_text_insert_timing_test_small.html">"Multimap"
105 Text Insert Timing Test with <u>Small</u> Average
106 Secondary-Key to Primary-Key Ratio</a></li>
107 <li><a href="multimap_text_insert_timing_test_large.html">"Multimap"
108 Text Insert Timing Test with <u>Large</u> Average
109 Secondary-Key to Primary-Key Ratio</a></li>
110 <li><a href="multimap_text_insert_mem_usage_test_small.html">"Multimap"
111 Text Insert Memory-Use Test with <u>Small</u> Average
112 Secondary-Key to Primary-Key Ratio</a></li>
113 <li><a href="multimap_text_insert_mem_usage_test_large.html">"Multimap"
114 Text Insert Memory-Use Test with <u>Large</u> Average
115 Secondary-Key to Primary-Key Ratio</a></li>
117 <h2><a name="assoc_observations" id="assoc_observations">Observations</a></h2>
118 <h3><a name="dss_family_choice" id="dss_family_choice">Underlying Data-Structure Families</a></h3>
119 <p>In general, hash-based containers (see <a href="hash_based_containers.html">Design::Associative
120 Containers::Hash-Based Containers</a>) have better timing
121 performance than containers based on different underlying-data
122 structures. The main reason to choose a tree-based (see
123 <a href="tree_based_containers.html">Design::Associative
124 Containers::Tree-Based Containers</a>) or trie-based container
125 (see <a href="trie_based_containers.html">Design::Associative
126 Containers::Trie-Based Containers</a>) is if a byproduct of the
127 tree-like structure is required: either order-preservation, or
128 the ability to utilize node invariants (see <a href="tree_based_containers.html#invariants">Design::Associative
129 Containers::Tree-Based Containers::Node Invariants</a> and
130 <a href="trie_based_containers.html#invariants">Design::Associative
131 Containers::Trie-Based Containers::Node Invariants</a>). If
132 memory-use is the major factor, an ordered-vector tree (see
133 <a href="tree_based_containers.html">Design::Associative
134 Containers::Tree-Based Containers</a>) gives optimal results
135 (albeit with high modificiation costs), and a list-based
136 container (see <a href="lu_based_containers.html">Design::Associative
137 Containers::List-Based Containers</a>) gives reasonable
139 <h3><a name="hash_based_types" id="hash_based_types">Hash-Based
140 Container Types</a></h3>
141 <p>Hash-based containers are typically either collision
142 chaining or probing (see <a href="hash_based_containers.html">Design::Associative
143 Containers::Hash-Based Containers</a>). Collision-chaining
144 containers are more flexible internally, and so offer better
145 timing performance. Probing containers, if used for simple
146 value-types, manage memory more efficiently (they perform far
147 fewer allocation-related calls). In general, therefore, a
148 collision-chaining table should be used. A probing container,
149 conversely, might be used efficiently for operations such as
150 eliminating duplicates in a sequence, or counting the number of
151 occurrences within a sequence. Probing containers might be more
152 useful also in multithreaded applications where each thread
153 manipulates a hash-based container: in the STL, allocators have
154 class-wise semantics (see [<a href="references.html#meyers96more">meyers96more</a>] - Item 10); a
155 probing container might incur less contention in this case.</p>
156 <h3><a name="hash_based_policies" id="hash_based_policies">Hash-Based Containers' Policies</a></h3>
157 <p>In hash-based containers, the range-hashing scheme (see
158 <a href="hash_based_containers.html#hash_policies">Design::Associative
159 Containers::Hash-Based Containers::Hash Policies</a>) seems to
160 affect performance more than other considerations. In most
161 settings, a mask-based scheme works well (or can be made to
162 work well). If the key-distribution can be estimated a-priori,
163 a simple hash function can produce nearly uniform hash-value
164 distribution. In many other cases (<i>e.g.</i>, text hashing,
165 floating-point hashing), the hash function is powerful enough
166 to generate hash values with good uniformity properties
167 [<a href="references.html#knuth98sorting">knuth98sorting</a>];
168 a modulo-based scheme, taking into account all bits of the hash
169 value, appears to overlap the hash function in its effort.</p>
170 <p>The range-hashing scheme determines many of the other
171 policies (see <a href="hash_based_containers.html#policy_interaction">Design::Hash-Based
172 Containers::Policy Interaction</a>). A mask-based scheme works
173 well with an exponential-size policy (see <a href="hash_based_containers.html#resize_policies">Design::Associative
174 Containers::Hash-Based Containers::Resize Policies</a>) ; for
175 probing-based containers, it goes well with a linear-probe
176 function (see <a href="hash_based_containers.html#hash_policies">Design::Associative
177 Containers::Hash-Based Containers::Hash Policies</a>).</p>
178 <p>An orthogonal consideration is the trigger policy (see
179 <a href="hash_based_containers.html#resize_policies">Design::Associative
180 Containers::Hash-Based Containers::Resize Policies</a>). This
181 presents difficult tradeoffs. <i>E.g.</i>, different load
182 factors in a load-check trigger policy yield a
183 space/amortized-cost tradeoff.</p>
184 <h3><a name="tree_like_based_types" id="tree_like_based_types">Tree-Like-Based Container
186 <p>In general, there are several families of tree-based
187 underlying data structures: balanced node-based trees
188 (<i>e.g.</i>, red-black or AVL trees), high-probability
189 balanced node-based trees (<i>e.g.</i>, random treaps or
190 skip-lists), competitive node-based trees (<i>e.g.</i>, splay
191 trees), vector-based "trees", and tries. (Additionally, there
192 are disk-residing or network-residing trees, such as B-Trees
193 and their numerous variants. An interface for this would have
194 to deal with the execution model and ACID guarantees; this is
195 out of the scope of this library.) Following are some
196 observations on their application to different settings.</p>
197 <p>Of the balanced node-based trees, this library includes a
198 red-black tree (see <a href="tree_based_containers.html">Design::Associative
199 Containers::Tree-Based Containers</a>), as does STL (in
200 practice). This type of tree is the "workhorse" of tree-based
201 containers: it offers both reasonable modification and
202 reasonable lookup time. Unfortunately, this data structure
203 stores a huge amount of metadata. Each node must contain,
204 besides a value, three pointers and a boolean. This type might
205 be avoided if space is at a premium [<a href="references.html#austern00noset">austern00noset</a>].</p>
206 <p>High-probability balanced node-based trees suffer the
207 drawbacks of deterministic balanced trees. Although they are
208 fascinating data structures, preliminary tests with them showed
209 their performance was worse than red-black trees. The library
210 does not contain any such trees, therefore.</p>
211 <p>Competitive node-based trees have two drawbacks. They are
212 usually somewhat unbalanced, and they perform a large number of
213 comparisons. Balanced trees perform one comparison per each
214 node they encounter on a search path; a splay tree performs two
215 comparisons. If the keys are complex objects, <i>e.g.</i>,
216 <tt>std::string</tt>, this can increase the running time.
217 Conversely, such trees do well when there is much locality of
218 reference. It is difficult to determine in which case to prefer
219 such trees over balanced trees. This library includes a splay
220 tree (see <a href="tree_based_containers.html">Design::Associative
221 Containers::Tree-Based Containers</a>).</p>
222 <p>Ordered-vector trees (see <a href="tree_based_containers.html">Design::Associative
223 Containers::Tree-Based Containers</a>) use very little space
224 [<a href="references.html#austern00noset">austern00noset</a>].
225 They do not have any other advantages (at least in this
227 <p>Large-fan-out PATRICIA tries (see <a href="trie_based_containers.html">Design::Associative
228 Containers::Trie-Based Containers</a>) have excellent lookup
229 performance, but they do so through maintaining, for each node,
230 a miniature "hash-table". Their space efficiency is low, and
231 their modification performance is bad. These tries might be
232 used for semi-static settings, where order preservation is
233 important. Alternatively, red-black trees cross-referenced with
234 hash tables can be used. [<a href="references.html#okasaki98mereable">okasaki98mereable</a>]
235 discusses small-fan-out PATRICIA tries for integers, but the
236 cited results seem to indicate that the amortized cost of
237 maintaining such trees is higher than that of balanced trees.
238 Moderate-fan-out trees might be useful for sequences where each
239 element has a limited number of choices, <i>e.g.</i>, DNA
240 strings (see <a href="assoc_examples.html#trie_based">Examples::Associative
241 Containers::Trie-Based Containers</a>).</p>
242 <h3><a name="msc" id="msc">Mapping-Semantics
243 Considerations</a></h3>
244 <p>Different mapping semantics were discussed in <a href="motivation.html#assoc_mapping_semantics">Motivation::Associative
245 Containers::Alternative to Multiple Equivalent Keys</a> and
246 <a href="tutorial.html#assoc_ms">Tutorial::Associative
247 Containers::Associative Containers Others than Maps</a>. We
248 will focus here on the case where a keys can be composed into
249 primary keys and secondary keys. (In the case where some keys
250 are completely identical, it is trivial that one should use an
251 associative container mapping values to size types.) In this
252 case there are (at least) five possibilities:</p>
254 <li>Use an associative container that allows equivalent-key
255 values (such as <tt>std::multimap</tt>)</li>
256 <li>Use a unique-key value associative container that maps
257 each primary key to some complex associative container of
258 secondary keys, say a tree-based or hash-based container (see
259 <a href="tree_based_containers.html">Design::Associative
260 Containers::Tree-Based Containers</a> and <a href="hash_based_containers.html">Design::Associative
261 Containers::Hash-Based Containers</a>)</li>
262 <li>Use a unique-key value associative container that maps
263 each primary key to some simple associative container of
264 secondary keys, say a list-based container (see <a href="lu_based_containers.html">Design::Associative
265 Containers::List-Based Containers</a>)</li>
266 <li>Use a unique-key value associative container that maps
267 each primary key to some non-associative container
268 (<i>e.g.</i>, <tt>std::vector</tt>)</li>
269 <li>Use a unique-key value associative container that takes
270 into account both primary and secondary keys.</li>
272 <p>We do not think there is a simple answer for this (excluding
273 option 1, which we think should be avoided in all cases).</p>
274 <p>If the expected ratio of secondary keys to primary keys is
275 small, then 3 and 4 seem reasonable. Both types of secondary
276 containers are relatively lightweight (in terms of memory use
277 and construction time), and so creating an entire container
278 object for each primary key is not too expensive. Option 4
279 might be preferable to option 3 if changing the secondary key
280 of some primary key is frequent - one cannot modify an
281 associative container's key, and the only possibility,
282 therefore, is erasing the secondary key and inserting another
283 one instead; a non-associative container, conversely, can
284 support in-place modification. The actual cost of erasing a
285 secondary key and inserting another one depends also on the
286 allocator used for secondary associative-containers (The tests
287 above used the standard allocator, but in practice one might
288 choose to use, <i>e.g.</i>, [<a href="references.html#boost_pool">boost_pool</a>]). Option 2 is
289 definitely an overkill in this case. Option 1 loses out either
290 immediately (when there is one secondary key per primary key)
291 or almost immediately after that. Option 5 has the same
292 drawbacks as option 2, but it has the additional drawback that
293 finding all values whose primary key is equivalent to some key,
294 might be linear in the total number of values stored (for
295 example, if using a hash-based container).</p>
296 <p>If the expected ratio of secondary keys to primary keys is
297 large, then the answer is more complicated. It depends on the
298 distribution of secondary keys to primary keys, the
299 distribution of accesses according to primary keys, and the
300 types of operations most frequent.</p>
301 <p>To be more precise, assume there are <i>m</i> primary keys,
302 primary key <i>i</i> is mapped to <i>n<sub>i</sub></i>
303 secondary keys, and each primary key is mapped, on average, to
304 <i>n</i> secondary keys (<i>i.e.</i>,
305 <i><b>E</b>(n<sub>i</sub>) = n</i>).</p>
306 <p>Suppose one wants to find a specific pair of primary and
307 secondary keys. Using 1 with a tree based container
308 (<tt>std::multimap</tt>), the expected cost is
309 <i><b>E</b>(Θ(log(m) + n<sub>i</sub>)) = Θ(log(m) +
310 n)</i>; using 1 with a hash-based container
311 (<tt>std::tr1::unordered_multimap</tt>), the expected cost is
312 <i>Θ(n)</i>. Using 2 with a primary hash-based container
313 and secondary hash-based containers, the expected cost is
314 <i>O(1)</i>; using 2 with a primary tree-based container and
315 secondary tree-based containers, the expected cost is (using
316 the Jensen inequality [<a href="references.html#motwani95random">motwani95random</a>])
317 <i><b>E</b>(O(log(m) + log(n<sub>i</sub>)) = O(log(m)) +
318 <b>E</b>(O(log(n<sub>i</sub>)) = O(log(m)) + O(log(n))</i>,
319 assuming that primary keys are accessed equiprobably. 3 and 4
320 are similar to 1, but with lower constants. Using 5 with a
321 hash-based container, the expected cost is <i>O(1)</i>; using 5
322 with a tree based container, the cost is
323 <i><b>E</b>(Θ(log(mn))) = Θ(log(m) +
325 <p>Suppose one needs the values whose primary key matches some
326 given key. Using 1 with a hash-based container, the expected
327 cost is <i>Θ(n)</i>, but the values will not be ordered
328 by secondary keys (which may or may not be required); using 1
329 with a tree-based container, the expected cost is
330 <i>Θ(log(m) + n)</i>, but with high constants; again the
331 values will not be ordered by secondary keys. 2, 3, and 4 are
332 similar to 1, but typically with lower constants (and,
333 additionally, if one uses a tree-based container for secondary
334 keys, they will be ordered). Using 5 with a hash-based
335 container, the cost is <i>Θ(mn)</i>.</p>
336 <p>Suppose one wants to assign to a primary key all secondary
337 keys assigned to a different primary key. Using 1 with a
338 hash-based container, the expected cost is <i>Θ(n)</i>,
339 but with very high constants; using 1 with a tree-based
340 container, the cost is <i>Θ(nlog(mn))</i>. Using 2, 3,
341 and 4, the expected cost is <i>Θ(n)</i>, but typically
342 with far lower costs than 1. 5 is similar to 1.</p>
OSDN Git Service
