🚀 go-pugleaf

preston@Tera.COM (Preston Briggs) writes:

> Joe Keane <jgk@netcom.com> writes:
> > Whenever I find some important hash table, one of the changes that 
> > I make is:
> > Take out that stupid `%' operator!
> >
> > People that don't have low-level knowledge of machines don't
> > realize how slow that remainder operation is.  Of course, it
> > depends on the machine, so it can range from rather slow to 
> > extremely slow.  With no exaggeration, a good hash table can do
> > several lookups in the time it takes to compute one remainder.
>
> _I_ think you're exaggerating.  I don't think you can handle a
> single successful lookup (or collision) in the amount of time it
> takes to do a remainder.  If we're hashing strings, there's a string
> compare implied in either case, not to mention the possibility of 2
> or more cache (tlb, ...) misses along the way.
> 
> > In many applications, various hash tables are just critical to
> > performance.  The most important thing for a hash table like this
> > is for it to *go fast*;
> 
> Hash tables offer constant (expected) time access.  Thus, they're
> almost always helpful asymptotically.  Getting a bad distribution of
> keys can provoke O(n) time per lookup, where n is the number of keys
> in the table.  I'm glad to spend a little constant factor to help
> avoid that possibility.

I have to agree with Joe Keane here.  It's easy to tune a hash
function for power-of-2 size tables.  I've been using one for years
that I use for strings (id lookup during parsing).  I've tested it on
datasets up to 100,000 identifiers, and gotten good spread for
power-of-2 size tables from 16 to 65536.  I tried the same dataset on
all these sizes.  "Good spread" means ~5% of the slots in the 64K
case were empty, most had 2 entries, very few had 4, maybe 1 had 5
entries.

In summary: it's not hard to tune a hash function for power-of-2, and
it buys a little speed.  (The other moral here is that you should 
_always_ tune your hash function at least once, 'cause many naive-but-
looks-good functions (with or without mod) are really lousy and you
can't tell from a correctness viewpoint.)


> Preston Briggs

Cliff

Cliff Click                  Compiler Researcher & Designer
RISC Software, Motorola      PowerPC Compilers
cliffc@risc.sps.mot.com      (512) 891-7240
--
Cliff Click                  Compiler Researcher & Designer
RISC Software, Motorola      PowerPC Compilers
cliffc@risc.sps.mot.com      (512) 891-7240