Subject: bug#68244: hash-table improvements

From: Mattias Engdegård <[email-masked]>
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.