source: GTP/trunk/Lib/Vis/Preprocessing/src/sparsehash/doc/performance.html @ 2162

Revision 2162, 3.4 KB checked in by mattausch, 17 years ago (diff)

improved hash performance with google hashmap
Line 
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,
12taken from a version of time_hash_map that was instrumented to also
13report memory allocation information (this modification is not
14included by default because it required a big hack to do, including
15modifying 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
18machine to machine and compiler to compiler, and they only test a very
19particular usage pattern that may not match how you use hashtables --
20for instance, they test hashtables with very small keys.  However,
21they're still useful for a baseline comparison of the various
22hashtable 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
26included with <tt>gcc2</tt>.  Compiled with <tt>gcc2.95.3 -g
27-O2</tt></p>
28
29<pre>
30======
31Average over 10000000 iterations
32Wed Dec  8 14:56:38 PST 2004
33
34SPARSE_HASH_MAP:
35map_grow                  665 ns
36map_predict/grow          303 ns
37map_replace               177 ns
38map_fetch                 117 ns
39map_remove                192 ns
40memory used in map_grow    84.3956 Mbytes
41
42DENSE_HASH_MAP:
43map_grow                   84 ns
44map_predict/grow           22 ns
45map_replace                18 ns
46map_fetch                  13 ns
47map_remove                 23 ns
48memory used in map_grow   256.0000 Mbytes
49
50STANDARD HASH_MAP:
51map_grow                  162 ns
52map_predict/grow          107 ns
53map_replace                44 ns
54map_fetch                  22 ns
55map_remove                124 ns
56memory used in map_grow   204.1643 Mbytes
57
58STANDARD MAP:
59map_grow                  297 ns
60map_predict/grow          282 ns
61map_replace               113 ns
62map_fetch                 113 ns
63map_remove                238 ns
64memory 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
71hash function: one that distributes data evenly.  Many hashtable
72implementations come with sub-optimal hash functions that can degrade
73performance.  For instance, the hash function given in Knuth's _Art of
74Computer Programming_, and the default string hash function in SGI's
75STL implementation, both distribute certain data sets unevenly,
76leading to poor performance.</p>
77
78<p>As an example, in one test of the default SGI STL string hash
79function against the Hsieh hash function (see below), for a particular
80set of string keys, the Hsieh function resulted in hashtable lookups
81that were 20 times as fast as the STLPort hash function.  The string
82keys were chosen to be "hard" to hash well, so these results may not
83be typical, but they are suggestive.</p>
84
85<p>There has been much research over the years into good hash
86functions.  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>
Note: See TracBrowser for help on using the repository browser.