GNU bug report logs - #68244
hash-table improvements

Previous Next

Full log

Message #47 received at 68244 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Dmitry Gutov <dmitry <at> gutov.dev>, Eli Zaretskii <eliz <at> gnu.org>,
 68244 <at> debbugs.gnu.org
Subject: Re: bug#68244: hash-table improvements
Date: Sun, 7 Jan 2024 19:36:17 +0100

[Message part 1 (text/plain, inline)]

7 jan. 2024 kl. 06.26 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

> The use of memory allocation as a way to decide when to do the next GC
> is just a crude tool anyway, which can often result in bad GC decisions,
> anyway (e.g. typically during long periods of initialization where we
> allocate many objects but don't generate almost any garbage).

In any case the changes to GC heuristics and policy that have been proposed aren't specific to hash-tables and while interesting are outside the scope of my work at hand. This means that I'll keep using the same kind of bookkeeping as before, so that the GC is reasonably well informed if we want to change it in the future.

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.

Benchmark results attached: the first column is the same as before, the middle after the accounting fix (which turned out not to be noticeable at all), and the rightmost what we got from Knuth. I'll probably keep both.

[pct.org (application/octet-stream, attachment)]

Previous Next

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