Path: ...!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: Sun, 26 May 2024 10:20:55 -0700
Organization: A noiseless patient Spider
Lines: 45
Message-ID: <86ed9ofq14.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> <v2sudq$2trh1$1@raubtier-asyl.eternal-september.org> <8634q5hjsp.fsf@linuxsc.com> <v2vmhr$3ffjk$1@raubtier-asyl.eternal-september.org> <86le3wfsmd.fsf@linuxsc.com> <v2voe7$3fr50$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sun, 26 May 2024 19:20:57 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="4466c3f20a2aa0adfb23676e01f9e74a";
	logging-data="3681216"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+7qAxiykCvQNA7yxBKVsyuo4hva1DVpUc="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:SkeCTfDImtFQblcAnZWVCoC0Fjc=
	sha1:RVpOEtE1RLnNnENz41NplkQYJFs=
Bytes: 3023

Bonita Montero <Bonita.Montero@gmail.com> writes:

> Am 26.05.2024 um 18:24 schrieb Tim Rentsch:
>
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>>> Am 25.05.2024 um 19:40 schrieb Tim Rentsch:
>>>
>>>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>>>
>>>>> Am 25.05.2024 um 11:12 schrieb Tim Rentsch:
>>>>>
>>>>>> Your hash function is expensive to compute, moreso even
>>>>>> than the "FNV" function shown earlier.  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.
>>>>>
>>>>> A (size_t)pointer * LARGE_PRIME can be sufficient,
>>>>> ignoring the overflow.
>>>>
>>>> Plenty fast but the output quality is poor. ...
>>>
>>> If the prime is large enough there'e no regular distribution.
>>
>> Your conjecture is contradicted by empirical facts.
>
> There are no empirival facts for that since two times the
> taken prime is beyond the 64 bit address space.

You don't listen very well do you?

I say the output quality is poor because I have run tests that
show the poor output quality.  I've done that with a prime of my
own choosing and also with 18446744073709551557, the value you
suggested.  In both cases the test runs show results that are
clearly worse than all the other hash functions tested, including
bart's and malcolm's.  Furthermore the results for your suggested
calculation are worse across the board, on every variety of
dynamic workload in my test suite.

Your proposed hash function is too weak to be taken as a serious
candidate.