GNU bug report logs - #68244
hash-table improvements

Previous Next

Full log

View this message in rfc822 format

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 68244 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: bug#68244: hash-table improvements
Date: Thu, 4 Jan 2024 18:02:08 +0100

4 jan. 2024 kl. 17.39 skrev Eli Zaretskii <eliz <at> 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.

Previous Next

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