Path: ...!3.eu.feeder.erje.net!feeder.erje.net!usenet.goja.nl.eu.org!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Sat, 25 May 2024 11:12:43 -0700
Organization: A noiseless patient Spider
Lines: 86
Message-ID: <86y17xg3qc.fsf@linuxsc.com>
References: <v2n88p$1nlcc$1@dont-email.me> <v2qm8m$2el55$1@raubtier-asyl.eternal-september.org> <v2qnue$2evlu$1@dont-email.me> <v2r9br$2hva2$1@dont-email.me> <86fru6gsqr.fsf@linuxsc.com> <v2si1h$2rs39$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 25 May 2024 20:12:46 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="8137c08e2aeaf8da9fb9d9b9c4e0a9a5";
	logging-data="3145496"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18mTZBgQWJKiyzUWpEWR9H/cJazgzowzqg="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:znpj83BzaFAeQRALUjXcSaBeTSc=
	sha1:9cj3yZanHmer8avpJRRYDIZI/9E=
Bytes: 4814

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.