GNU bug report logs - #68244
hash-table improvements

Previous Next

Full log

View this message in rfc822 format

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: Dmitry Gutov <dmitry <at> gutov.dev>, Eli Zaretskii <eliz <at> gnu.org>, 68244 <at> debbugs.gnu.org
Subject: bug#68244: hash-table improvements
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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.