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.

1 files changed, 4 insertions, 3 deletions

diff --git a/src/alloc.c b/src/alloc.c
index 15bb65cf74f..6abe9e28650 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3443,7 +3443,7 @@ cleanup_vector (struct Lisp_Vector *vector)
         struct Lisp_Hash_Table *h = PSEUDOVEC_STRUCT (vector, Lisp_Hash_Table);
         if (h->table_size > 0)
           {
-            eassert (h->index_size > 1);
+            eassert (h->index_bits > 0);
             xfree (h->index);
             xfree (h->key_and_value);
             xfree (h->next);
@@ -3451,7 +3451,7 @@ cleanup_vector (struct Lisp_Vector *vector)
             ptrdiff_t bytes = (h->table_size * (2 * sizeof *h->key_and_value
                                                 + sizeof *h->hash
                                                 + sizeof *h->next)
-                               + h->index_size * sizeof *h->index);
+                               + hash_table_index_size (h) * sizeof *h->index);
             hash_table_allocated_bytes -= bytes;
           }
       }
@@ -5959,7 +5959,8 @@ purecopy_hash_table (struct Lisp_Hash_Table *table)
       for (ptrdiff_t i = 0; i < nvalues; i++)
         pure->key_and_value[i] = purecopy (table->key_and_value[i]);
 
-      ptrdiff_t index_bytes = table->index_size * sizeof *table->index;
+      ptrdiff_t index_bytes = hash_table_index_size (table)
+                              * sizeof *table->index;
       pure->index = pure_alloc (index_bytes, -(int)sizeof *table->index);
       memcpy (pure->index, table->index, index_bytes);
     }