Combine hash and next vector into a single arrayscratch/hash-table-perf

This shrinks the hash object by one word and should give better
locality since these values are often accessed at the same time.

1 files changed, 10 insertions, 12 deletions

diff --git a/src/lisp.h b/src/lisp.h
index 64e8e0c11c3..30e452ffbb0 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2429,6 +2429,11 @@ typedef enum {
    (hash) indices.  It's signed and a subtype of ptrdiff_t.  */
 typedef int32_t hash_idx_t;
 
+struct hash_next {
+  hash_hash_t hash;  /* Hash value for entry.  Undefined for unused entries.  */
+  hash_idx_t next;   /* Next index in bucket or free list, or -1 if last.  */
+};
+
 struct Lisp_Hash_Table
 {
   union vectorlike_header header;
@@ -2455,11 +2460,11 @@ struct Lisp_Hash_Table
                                |
                            next_free
 
-     The table is physically split into three vectors (hash, next,
+     The table is physically split into two vectors (hash_next,
      key_and_value) which may or may not be beneficial.  */
 
   hash_idx_t index_size;   /* Size of the index vector.  */
-  hash_idx_t table_size;   /* Size of the next and hash vectors.  */
+  hash_idx_t table_size;   /* Size of hash_next and key_and_value arrays.  */
 
   /* Bucket vector.  An entry of -1 indicates no item is present,
      and a nonnegative entry is the index of the first item in
@@ -2470,9 +2475,9 @@ struct Lisp_Hash_Table
      Otherwise it is heap-allocated.  */
   hash_idx_t *index;
 
-  /* Vector of hash codes.  Unused entries have undefined values.
+  /* Vector of hash values and next indices.
      This vector is table_size entries long.  */
-  hash_hash_t *hash;
+  struct hash_next *hash_next;
 
   /* Vector of keys and values.  The key of item I is found at index
      2 * I, the value is found at index 2 * I + 1.
@@ -2484,13 +2489,6 @@ struct Lisp_Hash_Table
   /* The comparison and hash functions.  */
   const struct hash_table_test *test;
 
-  /* Vector used to chain entries.  If entry I is free, next[I] is the
-     entry number of the next free item.  If entry I is non-free,
-     next[I] is the index of the next entry in the collision chain,
-     or -1 if there is no such entry.
-     This vector is table_size entries long.  */
-  hash_idx_t *next;
-
   /* Number of key/value entries in the table.  */
   hash_idx_t count;
 
@@ -2565,7 +2563,7 @@ INLINE hash_hash_t
 HASH_HASH (const struct Lisp_Hash_Table *h, ptrdiff_t idx)
 {
   eassert (idx >= 0 && idx < h->table_size);
-  return h->hash[idx];
+  return h->hash_next[idx].hash;
 }
 
 /* Value is the size of hash table H.  */