Re: Good hash for pointers

bart <bc@freeuk.com> writes:

On 25/05/2024 10:12, Tim Rentsch wrote:
>

bart <bc@freeuk.com> writes:
[...]
It looks like your hash function was tuned for this testing
setup.  With different choices for testing it does much
worse.

>
It wasn't tuned at all;  it was a copy of what I've longed used
within my lexers.
>
It is designed to give a good spread when inputs are similar or
change sequentially.  (Well, not exactly designed;  more trial
and error.)

The trial and error process you mention had the effect of tuning
your function for the testing setup used, whether you meant it to
or not.

The testing is done with malloc() blocks all of the same
requested size, and that size is 1.  Typical workloads
are likely to be both larger and more variable.
>
When adding a new entry finds a collision with an old
entry, linear probing is used to find a free slot.  It's
well understood that linear probing suffers badly as the
load factor goes up.  Better to take a few high bits of
the hash value -- as few as five or six is fine -- to
have the reprobe sequences have different strides.
>
Your hash function is expensive to compute, moreso even
than the "FNV" function shown earlier.

>
You mean Malcolm's version?  That also uses a loop.  Neither
need to process all 8 bytes of a 64-bit pointer; 6 will do, and
probably just 4.
And such a loop can be trivially unrolled.

Both your function and the function posted by Malcolm are slow.
It's just that yours is slower.  It isn't hard to produce a
hash function of equal quality that runs more than twice as
fast.

In a case like
this one where the compares are cheap, it's better to
have a dumb-but-fast hash function that might need a
few more looks to find an open slot, because the cost
of looking is so cheap compared to computing the hash
function.

>
My first thought in this thread was to just make use of the
pointer value directly.  My version was written only to compare
against Malcolm's FNV code.
>
If I try the other suggestions, RH's and KK's which simply
shift the pointer value (similar to my idea), the results I got
were interesting:  sometimes there were zero clashes (almost as
though bits 4 to 19 of the pointer were a perfect hash), but
sometimes there were millions.
>
But when I tried to mix up the input values, then all methods
seemed to converge to similar results.
>
In that case you might as well use the simplest and fastest
method.
>
However it really needs testing within the actual application.

Let me tell you a little secret.  Hash functions are like random
number generators:  good ones never do exceptionally well or
exceptionally poorly.  The reason for this is simple - whenever
there are scenarios where one does well then inevitably there are
other scenarios where it does poorly.  A really high quality hash
function will never do badly, no matter what mix of inputs is
given.  The key takeaway here is to try as many different input
sets as you can, but don't look for candidates that do well;
rather, throw away any that do poorly on any input mix.  The ones
that are left are all, with high probability, just fine no matter
what application they are used in.  That is not to say there is
no need to test within the intended application, it's always good
to do a sanity check, but the point of the sanity check is just
to make sure the earlier process didn't miss something;  it isn't
the right way to compare alternatives.