libstdc++-v3/doc/html/ext/pb_ds/assoc_performance_tests.html

   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)
  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.
  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>(&Theta;(log(m) + n<sub>i</sub>)) = &Theta;(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>&Theta;(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>(&Theta;(log(mn))) = &Theta;(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>&Theta;(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>&Theta;(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>&Theta;(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>&Theta;(n)</i>,
 339     but with very high constants; using 1 with a tree-based
 340     container, the cost is <i>&Theta;(nlog(mn))</i>. Using 2, 3,
 341     and 4, the expected cost is <i>&Theta;(n)</i>, but typically
 342     with far lower costs than 1. 5 is similar to 1.</p>
 343 </div>
 344 </body>
 345 </html>