[2162] | 1 | <HTML>
|
---|
| 2 |
|
---|
| 3 | <HEAD>
|
---|
| 4 | <title>Performance notes: sparse_hash, dense_hash, sparsetable</title>
|
---|
| 5 | </HEAD>
|
---|
| 6 |
|
---|
| 7 | <BODY>
|
---|
| 8 |
|
---|
| 9 | <H2>Performance Numbers</H2>
|
---|
| 10 |
|
---|
| 11 | <p>Here are some performance numbers from an example desktop machine,
|
---|
| 12 | taken from a version of time_hash_map that was instrumented to also
|
---|
| 13 | report memory allocation information (this modification is not
|
---|
| 14 | included by default because it required a big hack to do, including
|
---|
| 15 | modifying the STL code to not try to do its own freelist management).</p>
|
---|
| 16 |
|
---|
| 17 | <p>Note there are lots of caveats on these numbers: they may differ from
|
---|
| 18 | machine to machine and compiler to compiler, and they only test a very
|
---|
| 19 | particular usage pattern that may not match how you use hashtables --
|
---|
| 20 | for instance, they test hashtables with very small keys. However,
|
---|
| 21 | they're still useful for a baseline comparison of the various
|
---|
| 22 | hashtable implementations.</p>
|
---|
| 23 |
|
---|
| 24 | <p>These figures are from a 2.80GHz Pentium 4 with 2G of memory. The
|
---|
| 25 | 'standard' hash_map and map implementations are the SGI STL code
|
---|
| 26 | included with <tt>gcc2</tt>. Compiled with <tt>gcc2.95.3 -g
|
---|
| 27 | -O2</tt></p>
|
---|
| 28 |
|
---|
| 29 | <pre>
|
---|
| 30 | ======
|
---|
| 31 | Average over 10000000 iterations
|
---|
| 32 | Wed Dec 8 14:56:38 PST 2004
|
---|
| 33 |
|
---|
| 34 | SPARSE_HASH_MAP:
|
---|
| 35 | map_grow 665 ns
|
---|
| 36 | map_predict/grow 303 ns
|
---|
| 37 | map_replace 177 ns
|
---|
| 38 | map_fetch 117 ns
|
---|
| 39 | map_remove 192 ns
|
---|
| 40 | memory used in map_grow 84.3956 Mbytes
|
---|
| 41 |
|
---|
| 42 | DENSE_HASH_MAP:
|
---|
| 43 | map_grow 84 ns
|
---|
| 44 | map_predict/grow 22 ns
|
---|
| 45 | map_replace 18 ns
|
---|
| 46 | map_fetch 13 ns
|
---|
| 47 | map_remove 23 ns
|
---|
| 48 | memory used in map_grow 256.0000 Mbytes
|
---|
| 49 |
|
---|
| 50 | STANDARD HASH_MAP:
|
---|
| 51 | map_grow 162 ns
|
---|
| 52 | map_predict/grow 107 ns
|
---|
| 53 | map_replace 44 ns
|
---|
| 54 | map_fetch 22 ns
|
---|
| 55 | map_remove 124 ns
|
---|
| 56 | memory used in map_grow 204.1643 Mbytes
|
---|
| 57 |
|
---|
| 58 | STANDARD MAP:
|
---|
| 59 | map_grow 297 ns
|
---|
| 60 | map_predict/grow 282 ns
|
---|
| 61 | map_replace 113 ns
|
---|
| 62 | map_fetch 113 ns
|
---|
| 63 | map_remove 238 ns
|
---|
| 64 | memory used in map_grow 236.8081 Mbytes
|
---|
| 65 | </pre>
|
---|
| 66 |
|
---|
| 67 |
|
---|
| 68 | <H2><A name="hashfn">A Note on Hash Functions</A></H2>
|
---|
| 69 |
|
---|
| 70 | <p>For good performance, the Google hash routines depend on a good
|
---|
| 71 | hash function: one that distributes data evenly. Many hashtable
|
---|
| 72 | implementations come with sub-optimal hash functions that can degrade
|
---|
| 73 | performance. For instance, the hash function given in Knuth's _Art of
|
---|
| 74 | Computer Programming_, and the default string hash function in SGI's
|
---|
| 75 | STL implementation, both distribute certain data sets unevenly,
|
---|
| 76 | leading to poor performance.</p>
|
---|
| 77 |
|
---|
| 78 | <p>As an example, in one test of the default SGI STL string hash
|
---|
| 79 | function against the Hsieh hash function (see below), for a particular
|
---|
| 80 | set of string keys, the Hsieh function resulted in hashtable lookups
|
---|
| 81 | that were 20 times as fast as the STLPort hash function. The string
|
---|
| 82 | keys were chosen to be "hard" to hash well, so these results may not
|
---|
| 83 | be typical, but they are suggestive.</p>
|
---|
| 84 |
|
---|
| 85 | <p>There has been much research over the years into good hash
|
---|
| 86 | functions. Here are some hash functions of note.</p>
|
---|
| 87 |
|
---|
| 88 | <ul>
|
---|
| 89 | <li> Bob Jenkins: <A HREF="http://burtleburtle.net/bob/hash/">http://burtleburtle.net/bob/hash/</A>
|
---|
| 90 | <li> Paul Hsieh: <A HREF="http://www.azillionmonkeys.com/qed/hash.html">http://www.azillionmonkeys.com/qed/hash.html</A>
|
---|
| 91 | <li> Fowler/Noll/Vo (FNV): <A HREF="http://www.isthe.com/chongo/tech/comp/fnv/">http://www.isthe.com/chongo/tech/comp/fnv/</A>
|
---|
| 92 | </ul>
|
---|
| 93 |
|
---|
| 94 | </body>
|
---|
| 95 | </html>
|
---|