Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Mon, 10 Jun 2024 15:14:53 +0300
Organization: A noiseless patient Spider
Lines: 67
Message-ID: <20240610151453.000027ef@yahoo.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>
	<86ed9ofq14.fsf@linuxsc.com>
	<20240605005916.00001b33@yahoo.com>
	<v3vkvp$268b2$1@raubtier-asyl.eternal-september.org>
	<v4441o$3f3lt$1@raubtier-asyl.eternal-september.org>
	<v45hmd$3t9dq$1@dont-email.me>
	<86le3dlh24.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 10 Jun 2024 14:14:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="880dcd519fee37eed7f03a0e29de7d3f";
	logging-data="434032"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+R8OjWKbYM5ABHEsOMZSr6O8Mf+2DLZMo="
Cancel-Lock: sha1:WkXlRMF4xwewa9sR/JvTN80uEWU=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 4274

On Sun, 09 Jun 2024 18:31:15 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> 
> > On 09/06/2024 12:35, Bonita Montero wrote:
> >  
> >> uint64_t MichaelsHash( uint64_t key )
> >> {
> >>  __m128i xkey = _mm_set_epi64x( key, 42 );
> >>  using bar_t = pair<uint64_t, uint64_t>;
> >>  static bar_t const bars[8] =
> >>  {
> >>   { 0xBB09BBCC90B24BF2, 0x825C622FF2792A01 },
> >>   { 0x94F0535CB06D4060, 0x939C756246DBFD1D },
> >>   { 0x5B835E01A7E14CA1, 0xAC2BDAFC023CDD06 },
> >>   { 0xE0B6A4735B774AEC, 0x9CAFB43E7DDE494C },
> >>  };
> >>  for( bar_t const &bar : bars )
> >>   xkey = _mm_aesenc_si128( xkey, _mm_set_epi64x( bar.second,
> >> bar.first ) );
> >>  return xkey.m128i_u64[0];
> >> }
> >>
> >> Now the code is about six times faster and I get a eight times
> >> speedup over single-threaded processing with the same code.  Of
> >> course the results are still the same.  
> >
> > I have your permission to drop that in?  
> 
> Note that this code was cribbed from Michael S.

I don't permit to use my name in variant, modified by Bonita.
I prefer if my name is not used even on my own variant.
This code was never intended for production use. It is intended for use
as reference, as something that is "certainly random enough and then
many billions times more than enough". It is much much slower than
necessary for non-crypto hash.
On the other hand, it is probably billions of billions times weaker
than what now considered "good enough" for crypto hash.

If you ask my personal opinion, I think that multiplication modulo
2**64 by prime (or even non-prime) close in absolute value to 2**63.5
is sufficient, as long as it used with appropriate method of conversion
of hash function to table index, which, for this hash function, happens
to be linear scaling by size of hash table.
Ironically, it was the method originally proposed by Bonita. The only
thing (s)he didn't understand was that factors that contain many
consecutive '0' or '1' bits, esp. so in more significant bits,
should be avoided.

> If you
> think it's important to ask permission, I think he is
> the one you should be asking.
> 
> By the way, I thought you were looking for code that works
> in standard C, and acceptable under C90 rules.  Have you
> changed your mind about that?  The code above is a far
> cry from C, let alone C90.

Exactly.
I think that all methods that are both good and fast rely on 64-bit
unsigned integer arithmetic. And it seems to me that C90 does not
provide it in portable manner.
So, under portable C90 constraints one has to choose between good and
fast.