bug#68244: hash-table improvements

[Mattias Engdegård]

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.