GNU bug report logs - #68244
hash-table improvements

Previous Next

Full log

Message #70 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, Stefan Kangas <stefankangas <at> gmail.com>
Subject: Re: bug#68244: hash-table improvements
Date: Sat, 13 Jan 2024 21:06:06 +0100

All right, I've pushed the parts that I have little doubt about being a definite improvement: a batch of refactoring steps, then the hash-table printing reforms, the representation and growth algorithm improvements, and finally documentation updates, all now on master.

Not part of this yet:

- unifying hash and next vectors (or hash, next and key_and_value) in a single array: pending benchmarks.

- Knuth range reduction: probably a gain as described earlier, but I want to study the behaviour in more of an apples-to-apples comparison since the table and index sizes were changed at the same time.

- turning hash_table_test structures into Lisp objects so that they can be referenced from a symbol property: seemed to worsen performance slightly so putting this on hold for the time being.

- adaptive index vector width: measurements needed.

- fancier hashing: to be implemented.

Maybe we should promote equal-including-properties to a first-class hash table test? It's defined as a user test in  two places in the Emacs tree, and user tests are much slower than built-in ones.

Previous Next

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