scratch/hash-table-perf c805d2173f8 33/35: Use a static index vector for zero-sized tables

[Mattias Engdegård]

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

    Use a static index vector for zero-sized tables
    
    It can never be modified anyway so we might just as well do without
    the heap allocation.
    
    * src/fns.c (empty_hash_index_vector): New.
    (make_hash_table, copy_hash_table, maybe_resize_hash_table):
    * src/alloc.c (cleanup_vector, purecopy_hash_table):
    Use empty_hash_index_vector for zero-sized tables,
    allocate otherwise.
---
 src/alloc.c | 60 +++++++++++++++++++++++++--------------------
 src/fns.c   | 81 ++++++++++++++++++++++++++++++++++++++-----------------------
 src/lisp.h  |  5 +++-
 3 files changed, 88 insertions(+), 58 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index b0dc08eb3f0..180b9995993 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3468,14 +3468,19 @@ cleanup_vector (struct Lisp_Vector *vector)
     case PVEC_HASH_TABLE:
       {
        struct Lisp_Hash_Table *h = PSEUDOVEC_STRUCT (vector, Lisp_Hash_Table);
-       xfree (h->index);
-       xfree (h->key_and_value);
-       xfree (h->next);
-       xfree (h->hash);
-       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_allocated_bytes -= bytes;
+       if (h->table_size > 0)
+         {
+           eassert (h->index_size > 1);
+           xfree (h->index);
+           xfree (h->key_and_value);
+           xfree (h->next);
+           xfree (h->hash);
+           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_allocated_bytes -= bytes;
+         }
       }
     /* Keep the switch exhaustive.  */
     case PVEC_NORMAL_VECTOR:
@@ -5967,24 +5972,27 @@ purecopy_hash_table (struct Lisp_Hash_Table *table)
   *pure = *table;
   pure->mutable = false;
 
-  ptrdiff_t hash_bytes = table->table_size * sizeof *table->hash;
-  pure->hash = pure_alloc (hash_bytes, -(int)sizeof *table->hash);
-  memcpy (pure->hash, table->hash, hash_bytes);
-
-  ptrdiff_t next_bytes = table->table_size * sizeof *table->next;
-  pure->next = pure_alloc (next_bytes, -(int)sizeof *table->next);
-  memcpy (pure->next, table->next, next_bytes);
-
-  ptrdiff_t nvalues = table->table_size * 2;
-  ptrdiff_t kv_bytes = nvalues * sizeof *table->key_and_value;
-  pure->key_and_value = pure_alloc (kv_bytes,
-                                    -(int)sizeof *table->key_and_value);
-  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;
-  pure->index = pure_alloc (index_bytes, -(int)sizeof *table->index);
-  memcpy (pure->index, table->index, index_bytes);
+  if (table->table_size > 0)
+    {
+      ptrdiff_t hash_bytes = table->table_size * sizeof *table->hash;
+      pure->hash = pure_alloc (hash_bytes, -(int)sizeof *table->hash);
+      memcpy (pure->hash, table->hash, hash_bytes);
+
+      ptrdiff_t next_bytes = table->table_size * sizeof *table->next;
+      pure->next = pure_alloc (next_bytes, -(int)sizeof *table->next);
+      memcpy (pure->next, table->next, next_bytes);
+
+      ptrdiff_t nvalues = table->table_size * 2;
+      ptrdiff_t kv_bytes = nvalues * sizeof *table->key_and_value;
+      pure->key_and_value = pure_alloc (kv_bytes,
+                                       -(int)sizeof *table->key_and_value);
+      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;
+      pure->index = pure_alloc (index_bytes, -(int)sizeof *table->index);
+      memcpy (pure->index, table->index, index_bytes);
+    }
 
   return pure;
 }
diff --git a/src/fns.c b/src/fns.c
index ebb8847ecd8..11e2f46b9d8 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -4533,6 +4533,10 @@ hash_index_size (ptrdiff_t size)
   return index_size;
 }
 
+/* Constant hash index vector used when the table size is zero.
+   This avoids allocating it from the heap.  */
+static const hash_idx_t empty_hash_index_vector[] = {-1};
+
 /* Create and initialize a new hash table.
 
    TEST specifies the test the hash table will use to compare keys.
@@ -4561,26 +4565,38 @@ make_hash_table (const struct hash_table_test *test, 
EMACS_INT size,
   h->weakness = weak;
   h->count = 0;
   h->table_size = size;
+  int index_size = hash_index_size (size);
+  h->index_size = index_size;
 
-  h->key_and_value = hash_table_alloc_bytes (2 * size
-                                            * sizeof *h->key_and_value);
-  for (ptrdiff_t i = 0; i < 2 * size; i++)
-    h->key_and_value[i] = HASH_UNUSED_ENTRY_KEY;
+  if (size == 0)
+    {
+      h->key_and_value = NULL;
+      h->hash = NULL;
+      h->next = NULL;
+      eassert (index_size == 1);
+      h->index = (hash_idx_t *)empty_hash_index_vector;
+      h->next_free = -1;
+    }
+  else
+    {
+      h->key_and_value = hash_table_alloc_bytes (2 * size
+                                                * sizeof *h->key_and_value);
+      for (ptrdiff_t i = 0; i < 2 * size; i++)
+       h->key_and_value[i] = HASH_UNUSED_ENTRY_KEY;
 
-  h->hash = hash_table_alloc_bytes (size * sizeof *h->hash);
+      h->hash = hash_table_alloc_bytes (size * sizeof *h->hash);
 
-  h->next = hash_table_alloc_bytes (size * sizeof *h->next);
-  for (ptrdiff_t i = 0; i < size - 1; i++)
-    h->next[i] = i + 1;
-  if (size > 0)
-    h->next[size - 1] = -1;
-  h->next_free = size > 0 ? 0 : -1;
-
-  ptrdiff_t nindex = hash_index_size (size);
-  h->index_size = nindex;
-  h->index = hash_table_alloc_bytes (nindex * sizeof *h->index);
-  for (ptrdiff_t i = 0; i < nindex; i++)
-    h->index[i] = -1;
+      h->next = hash_table_alloc_bytes (size * sizeof *h->next);
+      for (ptrdiff_t i = 0; i < size - 1; i++)
+       h->next[i] = i + 1;
+      h->next[size - 1] = -1;
+
+      h->index = hash_table_alloc_bytes (index_size * sizeof *h->index);
+      for (ptrdiff_t i = 0; i < index_size; i++)
+       h->index[i] = -1;
+
+      h->next_free = 0;
+    }
 
   h->next_weak = NULL;
   h->purecopy = purecopy;
@@ -4608,22 +4624,24 @@ copy_hash_table (struct Lisp_Hash_Table *h1)
   *h2 = *h1;
   h2->mutable = true;
 
-  ptrdiff_t kv_bytes = 2 * h1->table_size * sizeof *h1->key_and_value;
-  h2->key_and_value = hash_table_alloc_bytes (kv_bytes);
-  memcpy (h2->key_and_value, h1->key_and_value, kv_bytes);
-
-  ptrdiff_t hash_bytes = h1->table_size * sizeof *h1->hash;
-  h2->hash = hash_table_alloc_bytes (hash_bytes);
-  memcpy (h2->hash, h1->hash, hash_bytes);
+  if (h1->table_size > 0)
+    {
+      ptrdiff_t kv_bytes = 2 * h1->table_size * sizeof *h1->key_and_value;
+      h2->key_and_value = hash_table_alloc_bytes (kv_bytes);
+      memcpy (h2->key_and_value, h1->key_and_value, kv_bytes);
 
-  ptrdiff_t next_bytes = h1->table_size * sizeof *h1->next;
-  h2->next = hash_table_alloc_bytes (next_bytes);
-  memcpy (h2->next, h1->next, next_bytes);
+      ptrdiff_t hash_bytes = h1->table_size * sizeof *h1->hash;
+      h2->hash = hash_table_alloc_bytes (hash_bytes);
+      memcpy (h2->hash, h1->hash, hash_bytes);
 
-  ptrdiff_t index_bytes = h1->index_size * sizeof *h1->index;
-  h2->index = hash_table_alloc_bytes (index_bytes);
-  memcpy (h2->index, h1->index, index_bytes);
+      ptrdiff_t next_bytes = h1->table_size * sizeof *h1->next;
+      h2->next = hash_table_alloc_bytes (next_bytes);
+      memcpy (h2->next, h1->next, next_bytes);
 
+      ptrdiff_t index_bytes = h1->index_size * sizeof *h1->index;
+      h2->index = hash_table_alloc_bytes (index_bytes);
+      memcpy (h2->index, h1->index, index_bytes);
+    }
   XSET_HASH_TABLE (table, h2);
 
   return table;
@@ -4680,7 +4698,8 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
       h->table_size = new_size;
       h->next_free = old_size;
 
-      hash_table_free_bytes (h->index, old_index_size * sizeof *h->index);
+      if (old_index_size > 1)
+       hash_table_free_bytes (h->index, old_index_size * sizeof *h->index);
       h->index = index;
 
       hash_table_free_bytes (h->key_and_value,
diff --git a/src/lisp.h b/src/lisp.h
index d35e758c4d9..6735329b0df 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2464,7 +2464,10 @@ struct Lisp_Hash_Table
   /* Bucket vector.  An entry of -1 indicates no item is present,
      and a nonnegative entry is the index of the first item in
      a collision chain.
-     This vector is index_size entries long.  */
+     This vector is index_size entries long.
+     If index_size is 1 (and table_size is 0), then this is the
+     constant read-only vector {-1}, shared between all instances.
+     Otherwise it is heap-allocated.  */
   hash_idx_t *index;
 
   /* Vector of hash codes.  Unused entries have undefined values.