Re: [PATCH] Improve PR12245 compile-time by 50%

[Daniel Berlin <dberlin at dberlin dot org>]

On Tue, 4 Oct 2005, Paolo Carlini wrote:

> Daniel Berlin wrote:
>
> > > How about the hash_combine function from Boost:
> > >
> > > http://www.boost.org/doc/html/hash_combine.html
> >
> > Out of curiosity, Do you know if there is some reference for the magic
> > boost seems to have chosen?
>
> Out of (further) curiosity, do you all have strong opinions about FNV
> hashing, which we adopted a few months ago for the new tr1 bits of the
> library after some literature search? E.g.:
>
>    http://www.isthe.com/chongo/tech/comp/fnv/

I replaced GDB's symbol table hash with FNV-1 a while ago, after trying a 
lot of hash functions out on some large debug info (IE > 100 meg of debug 
info in the executable) and looking at chain length.

However, since then, i've discovered
http://burtleburtle.net/bob/hash/doobs.html

I agree with his criticisms of FNV, but i'm not sure it matters in 
practice.

BTW, i'm a big fan of using power of 2 hash table sizes (as most people 
who implement real hash tables are).
While prime sizes are theoretically nice, the price you pay in terms 
of % table size (which your collision resolution, etc, should be using. 
Not that ours doesn't do it more than once, and it looks like it was done 
specifically to avoid this repeated cost) isn't worth it.  On a power of 2 
hash table, % table size is just masking some bits, of course.

You can also use nicer collision resolution anyway, because of some nice 
mathematical properties of powers of 2 (python does this, for example).

--Dan