]> git.eshelyaron.com Git - emacs.git/commit
Change hash range reduction from remainder to multiplication
authorMattias EngdegÄrd <mattiase@acm.org>
Mon, 15 Jan 2024 08:25:02 +0000 (09:25 +0100)
committerEshel Yaron <me@eshelyaron.com>
Wed, 7 Feb 2024 10:56:00 +0000 (11:56 +0100)
commit38d558f2f8c37ba7ff6e0ebd4e3d5fd48ed49775
treec8dfb6df278adcf78fcd423bf177b2a2bebb5427
parentce6b52e92d84c73e730355ec62a3fd12cf967026
Change hash range reduction from remainder to multiplication

This makes both lookups and rehashing cheaper.  The index vector size
is now always a power of 2.  The first table size is reduced to
6 (from 8), because index vectors would become excessively big
otherwise.

* src/lisp.h (struct Lisp_Hash_Table): Replace index_size with
index_bits.  All references adapted.
(hash_table_index_size): New accessor; use it where applicable.
* src/fns.c (hash_index_size): Replace with...
(compute_hash_index_bits): ...this new function, returning the log2 of the
index size.  All callers adapted.
(hash_index_index): Knuth multiplicative hashing instead of remainder.
(maybe_resize_hash_table): Reduce first table size from 8 to 6.

(cherry picked from commit e66870400d45e3d08265df9f6acd4631a5712139)
src/alloc.c
src/fns.c
src/lisp.h
src/pdumper.c