bug#68244: hash-table improvements

["Mattias Engdegård" <mattias.engdegard@gmail.com>]

4 jan. 2024 kl. 17.39 skrev Eli Zaretskii <eliz@gnu.org>:

> Any data about the actual performance gains?

Lots, naturally, but hash tables have many moving parts and performance is many-dimensional which is why I didn't include the raw data; it's voluminous and not always easy to interpret. Giving a single number as in 'now 20 % faster' is impossible if we want to stay honest, because there are so many different aspects, contexts and operations.

The reforms so far actually don't change the basic algorithms or data structures much but concentrate on slimming the internal and external representation, both of which are basically guaranteed to provide performance gains (and they do).

External representation improvements means that printing and reading is substantially faster, especially for small tables (otherwise most of the time is just spent printing and reading the data), but many tables are small.

Internal representation means that we now use much less memory for the basic hash table objects and for the tables, and even more importantly avoid expensive GC involvement where not absolutely necessary. This gives some measurable speed-up itself, but provides benefits for other code.

I do want to change some of the hashing and range reduction code, though, but this requires even more careful benchmarking to be sure that we don't end up with any surprises.