GNU bug report logs - #36597
27.0.50; rehash hash tables eagerly in pdumper

Previous Next

Full log

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

From: Pip Cet <pipcet <at> gmail.com>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: Eli Zaretskii <eliz <at> gnu.org>, Paul Eggert <eggert <at> cs.ucla.edu>,
 36597 <at> debbugs.gnu.org
Subject: Re: bug#36597: 27.0.50; rehash hash tables eagerly in pdumper
Date: Mon, 10 Aug 2020 11:51:42 +0000

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

On Sun, Aug 9, 2020 at 7:28 PM Lars Ingebrigtsen <larsi <at> gnus.org> wrote:
> >> Well, at least they'll require rebasing, particularly of the
> >> no-internal-freelists patch :-)
> >
> > Rebased patches attached. The performance measurements don't seem to
> > change significantly.
>
> And this was the final message in this thread.  I think the general
> consensus was that Pip's patches were a good idea...  unless they had
> any negative performance impact?

I'm not aware of any remaining negative performance impact, but I do
seem to recall Daniel was somewhat opposed to the patch.

> So I tried applying the patch now to Emacs 28 to do some benchmarking,
> but it didn't apply cleanly, so I gave up.

I'll try to rebase them again. Does the attached work for you?

> Is this still something worth pursuing?

I think it is, at least in the case of the "rehash eagerly" patch.

As for the more general rewrite of hash tables, it might be a good
idea to summarize and discuss this idea some more. Here are some
initial notes, but I'll make a proper proposal once things are ready:

- there's a new lisp.h type for hash cells, which is four words long
and holds a hash, key, value, and a next link (either another hash
cell, or the hash table this cell belongs to, or nil if it no longer
belongs to any hash table)
- hash tables are essentially vectors of such hash cells
- hash cells are invisible to Lisp code, but C code can hold on to
hash cell Lisp Objects, guaranteeing they won't be collected (they can
still be removed from the hash table)
- in my current implementation, hash cells aren't pseudovectors,
they're cons-like objects with four cells rather than two.

The implications are:

- more work for the garbage collector
- a somewhat ambitious rewrite of the profiler to keep hash cells pre-allocated
- shrinkable hash tables
- genuinely unordered hash tables, since there's no more HASH_INDEX
- rehash thresholds would be interpreted differently

There's also a slight reduction in memory usage for hash tables.

[0001-Rehash-hash-tables-eagerly-after-loading-a-dump.patch (text/x-patch, attachment)]

Previous Next

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