hashinit versus phashinit

[Johan Bucht]

On Tue, May 6, 2008 at 5:08 AM, Adrian Chadd <adrian at freebsd.org> wrote:
> 2008/5/6 Roman Divacky <rdivacky at freebsd.org>:
>
>
>
>  >  > Most general-purpose hash implementations I've used (e.g., GNU
>  >  > libstdc++, Sun JDK, Microsoft .NET) use prime table sizes,
>  >  > probably to make it less likely that programmers will shoot
>  >  > themselves in the foot with pathological data or bad hash functions.
>  >
>  >  yes... a division takes roughly 40 cycles on modern i386 hw, while
>  >  and is just 1, but does it matter compared to the access times of
>  >  memory these days?
>  >
>  >  the ratio between cpu-speed/mem-speed has changed a lot. I am not
>  >  arguing if it's still true that avoiding the division helps the performance
>  >  these days...
>
>  My 2c - I'd poke the assembler, a book or two on current
>  architectures, and combine it with some benchmarking followed by
>  logical reasoning.
>
>  Modern microprocessors don't execute instructions like they used to
>  before I was born; "divide versus logical shift/operator" speed may be
>  secondary to pipeline and IU effects, memory access (as mentioned
>  before), etc.
>
>  (I know its not much - but I'm a firm believer in "Science!", and this
>  is one of those questions which can be understood with a little bit of
>  it..)
>
>

If a hash algorithm relies on prime sized tables to produce uniform
results it's a bad hash algorithm. =)
http://burtleburtle.net/bob/hash/index.html is a recommended read,
especially the article for Dr Dobb's.

/Johan