]> git.eshelyaron.com Git - emacs.git/commit
String hashing improvements (spread and performance)
authorMattias EngdegÄrd <mattiase@acm.org>
Tue, 13 Feb 2024 13:52:39 +0000 (14:52 +0100)
committerEshel Yaron <me@eshelyaron.com>
Wed, 14 Feb 2024 15:16:48 +0000 (16:16 +0100)
commit88bc2ca183c74fedd1291d6a18b75ab7fd7c4125
treed031e65ccad71d6714fbee381f32c9c4e6b390f3
parent6ce5bb47abf4c4986d0ac6ce332423cb85a4436d
String hashing improvements (spread and performance)

Fix gaps in hashing coverage in the middle and end of even fairly short
strings.  E.g., `outline-1`, `outline-2` etc all hashed to the exact
same value but with the patch, there are no collisions among the ~160000
symbols in the Emacs tree.

This change also improves average hashing speed by using fewer mixing
operations.

* src/fns.c (hash_string):
Use unit stride for fairly short strings, while retaining the cap of 8
samples for long ones.

Always hash the last word to ensure that the end of the string is
covered.  For strings shorter than a word, use fewer loads and a single
reduction step.

(cherry picked from commit 3a93e301ddc913758abe05c876aa3016e8b23af8)
src/fns.c