1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 4<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 5<head> 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" /> 9</head> 10<body> 11<div id="page"> 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"> 19<div class="c1"> 20<h3><a name="gcc" id="gcc"><u>g++</u></a></h3> 21<ul> 22<li>CPU speed - cpu MHz : 2660.644</li> 23<li>Memory - MemTotal: 484412 kB</li> 24<li>Platform - 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 31 PURPOSE.</li> 32</ul> 33</div> 34<div class="c2"></div> 35</div> 36<div id="msvc_settings_div"> 37<div class="c1"> 38<h3><a name="msvc" id="msvc"><u>msvc++</u></a></h3> 39<ul> 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 46 reserved.</li> 47</ul> 48</div> 49<div class="c2"></div> 50</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) 56Copyright (C) 2006 Free Software Foundation, Inc. 57This is free software; see the source for copying conditions. There is NO 58warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 59</li> 60</ul> 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 64 Containers</a></h3> 65<ol> 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 76 Test</a></li> 77<li><a href="hash_random_int_erase_mem_usage_test.html">Hash-Based Erase 78 Memory Use Test</a></li> 79</ol> 80<h3><a name="tree_like_based" id="tree_like_based">Tree-Like-Based Containers</a></h3> 81<ol> 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 88 Test</a></li> 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> 95</ol> 96<h3><a name="multimaps" id="multimaps">Multimaps</a></h3> 97<ol> 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> 116</ol> 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 138 results.</p> 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 185 Types</a></h3> 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 226 implementation).</p> 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> 253<ol> 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> 271</ol> 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) + 324 log(n))</i>.</p> 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> 343</div> 344</body> 345</html> 346