scratch/hash-table-perf 8f608cb4a1c 28/35: Use key Qunbound instead of hash value hash_unused for free entries

[Mattias Engdegård]

branch: scratch/hash-table-perf
commit 8f608cb4a1c5ce87f8308aa93057eeef9aa62c29
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>

    Use key Qunbound instead of hash value hash_unused for free entries
    
    This allows us to change the hash representation to one that does not
    have an unused value.
    
    * src/lisp.h (hash_unused): Remove.
    All uses adapted to calling hash_unused_entry_key_p on the key instead.
    The hash values for unused hash table entries are now undefined; all
    initialisation and assignment to hash_unused has been removed.
---
 src/fns.c     | 16 +++-------------
 src/lisp.h    |  7 +------
 src/macfont.m |  2 +-
 src/pdumper.c | 13 ++++++++-----
 4 files changed, 13 insertions(+), 25 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index 48c0e603c5d..4acef3f5682 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -4560,8 +4560,6 @@ make_hash_table (const struct hash_table_test *test, 
EMACS_INT size,
     h->key_and_value[i] = HASH_UNUSED_ENTRY_KEY;
 
   h->hash = hash_table_alloc_bytes (size * sizeof *h->hash);
-  for (ptrdiff_t i = 0; i < size; i++)
-    h->hash[i] = hash_unused;
 
   h->next = hash_table_alloc_bytes (size * sizeof *h->next);
   for (ptrdiff_t i = 0; i < size - 1; i++)
@@ -4663,8 +4661,6 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
 
       hash_hash_t *hash = hash_table_alloc_bytes (new_size * sizeof *hash);
       memcpy (hash, h->hash, old_size * sizeof *hash);
-      for (ptrdiff_t i = old_size; i < new_size; i++)
-       hash[i] = hash_unused;
 
       ptrdiff_t old_index_size = h->index_size;
       ptrdiff_t index_size = hash_index_size (new_size);
@@ -4693,7 +4689,7 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
 
       /* Rehash.  */
       for (ptrdiff_t i = 0; i < old_size; i++)
-       if (HASH_HASH (h, i) != hash_unused)
+       if (!hash_unused_entry_key_p (HASH_KEY (h, i)))
          {
            hash_hash_t hash_code = HASH_HASH (h, i);
            ptrdiff_t start_of_bucket = hash_index_index (h, hash_code);
@@ -4736,8 +4732,6 @@ hash_table_thaw (Lisp_Object hash_table)
   h->next_free = -1;
 
   h->hash = hash_table_alloc_bytes (size * sizeof *h->hash);
-  for (ptrdiff_t i = 0; i < size; i++)
-    h->hash[i] = hash_unused;
 
   h->next = hash_table_alloc_bytes (size * sizeof *h->next);
   for (ptrdiff_t i = 0; i < size; i++)
@@ -4812,14 +4806,13 @@ ptrdiff_t
 hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value,
          hash_hash_t hash)
 {
-  eassert (!BASE_EQ (key, Qunbound));
+  eassert (!hash_unused_entry_key_p (key));
   /* Increment count after resizing because resizing may fail.  */
   maybe_resize_hash_table (h);
   h->count++;
 
   /* Store key/value in the key_and_value vector.  */
   ptrdiff_t i = h->next_free;
-  eassert (HASH_HASH (h, i) == hash_unused);
   eassert (hash_unused_entry_key_p (HASH_KEY (h, i)));
   h->next_free = HASH_NEXT (h, i);
   set_hash_key_slot (h, i, key);
@@ -4864,7 +4857,6 @@ hash_remove_from_table (struct Lisp_Hash_Table *h, 
Lisp_Object key)
             the free list.  */
          set_hash_key_slot (h, i, HASH_UNUSED_ENTRY_KEY);
          set_hash_value_slot (h, i, Qnil);
-         set_hash_hash_slot (h, i, hash_unused);
          set_hash_next_slot (h, i, h->next_free);
          h->next_free = i;
          h->count--;
@@ -4887,7 +4879,6 @@ hash_clear (struct Lisp_Hash_Table *h)
       ptrdiff_t size = HASH_TABLE_SIZE (h);
       for (ptrdiff_t i = 0; i < size; i++)
        {
-         set_hash_hash_slot (h, i, hash_unused);
          set_hash_next_slot (h, i, i < size - 1 ? i + 1 : -1);
          set_hash_key_slot (h, i, HASH_UNUSED_ENTRY_KEY);
          set_hash_value_slot (h, i, Qnil);
@@ -4967,10 +4958,9 @@ sweep_weak_table (struct Lisp_Hash_Table *h, bool 
remove_entries_p)
                  set_hash_next_slot (h, i, h->next_free);
                  h->next_free = i;
 
-                 /* Clear key, value, and hash.  */
+                 /* Clear key and value.  */
                  set_hash_key_slot (h, i, HASH_UNUSED_ENTRY_KEY);
                  set_hash_value_slot (h, i, Qnil);
-                 set_hash_hash_slot (h, i, hash_unused);
 
                   eassert (h->count != 0);
                   h->count--;
diff --git a/src/lisp.h b/src/lisp.h
index 0dfe1faeba1..e7808be538d 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2425,11 +2425,6 @@ typedef enum {
                            both key and value remain.  */
 } hash_table_weakness_t;
 
-/* An value that marks an unused hash entry.
-   Any hash_hash_t value that is not a valid fixnum will do here.  */
-enum { hash_unused = (hash_hash_t)MOST_POSITIVE_FIXNUM + 1 };
-verify (FIXNUM_OVERFLOW_P (hash_unused));
-
 /* The type of a hash table index, both for table indices and index
    (hash) indices.  It's signed and a subtype of ptrdiff_t.  */
 typedef int32_t hash_idx_t;
@@ -2472,7 +2467,7 @@ struct Lisp_Hash_Table
      This vector is index_size entries long.  */
   hash_idx_t *index;
 
-  /* Vector of hash codes.  The value hash_unused marks an unused table entry.
+  /* Vector of hash codes.  Unused entries have undefined values.
      This vector is table_size entries long.  */
   hash_hash_t *hash;
 
diff --git a/src/macfont.m b/src/macfont.m
index 43b57914700..2dc114224f0 100644
--- a/src/macfont.m
+++ b/src/macfont.m
@@ -980,7 +980,7 @@ macfont_invalidate_family_cache (void)
       ptrdiff_t i, size = HASH_TABLE_SIZE (h);
 
       for (i = 0; i < size; ++i)
-       if (HASH_HASH (h, i) != hash_unused)
+       if (!hash_unused_entry_key_p (HASH_KEY (h, i)))
          {
            Lisp_Object value = HASH_VALUE (h, i);
 
diff --git a/src/pdumper.c b/src/pdumper.c
index 3f6240a5076..0bc3a9bd958 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2676,11 +2676,14 @@ hash_table_contents (struct Lisp_Hash_Table *h)
      relies on it by expecting hash table indices to stay constant
      across the dump.  */
   for (ptrdiff_t i = 0; i < old_size; i++)
-    if (HASH_HASH (h, i) != hash_unused)
-      {
-       key_and_value[n++] = HASH_KEY (h, i);
-       key_and_value[n++] = HASH_VALUE (h, i);
-      }
+    {
+      Lisp_Object key = HASH_KEY (h, i);
+      if (!hash_unused_entry_key_p (key))
+       {
+         key_and_value[n++] = key;
+         key_and_value[n++] = HASH_VALUE (h, i);
+       }
+    }
 
   return key_and_value;
 }