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: Sun, 07 Jan 2024 14:10:29 -0500

> I've pushed two new changes: a correction to the GC accounting for the
> ancillary hash-table vectors, and a rather more interesting change to the
> hash table range reduction. It now uses a Knuth multiplicative method
> instead of the expensive remainder, so the index is now always a power of
> 2 in size.

The change gives good results for small tables but less so for big ones.
I don't have a good intuition for why that would be: none of the
operations directly involved seem to be more costly for large tables, so
my best guess is that it leads to more collisions somehow, tho I don't
have a good idea about why that would be.


        Stefan

Previous Next

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