Subject: Re: bug#68244: hash-table improvements

From: Stefan Monnier <[email-masked]>
Date: Mon, 08 Jan 2024 19:33:13 -0500

> The left columns are for the standard hash tables with remainder-based range
> reduction, the right ones with Knuth reduction.
> 'size' is the table size, 'idxsiz' the index vector size, '1st%' the portion
> of entries accessed with a single lookup, 'avg' the average number of
> accesses and 'max' the maximum number of accesses required.
>
> The old code looks perfect (no collisions!), but the new shiny code is a disappointment.

Ah, that could explain it, indeed.

BTW, what is the "per-entry byte-size" of your new code?
The old code had about 6 words per entry, IIRC.

> We could try switching to a high-quality hash function (or family thereof),
> like Murmur or Jenkins. Then range reduction is just a matter of masking off
> the required number of bits.

I don't see a strong need for it.

BTW, I see in the Knuth reduction you extract the bits 32..32+N of
the multiplication.  Any reason not to use the top N bits instead (so
we're not limited to 32 bits, for example)?

        Stefan