Use non-Lisp allocation for internal hash-table vectors

Using xmalloc for allocating these arrays is much cheaper than using
Lisp vectors since they are no longer marked or swept by the GC, and
deallocated much sooner.  This makes GC faster and less frequent, and
improves temporal locality.

Zero-sized tables use NULL for their (0-length) vectors except the
index vector which has size 1 and uses a shared constant static vector
since it cannot be modified anyway.  This makes creation and
destruction of zero-sized hash tables very fast; they consume no
memory outside the base object.

* src/lisp.h (struct Lisp_Hash_Table): Retype the index, next, hash
and key_and_value vectors from Lisp_Object to appropriately typed
arrays (although hash values are still stored as Lisp fixnums).  Add
explicit table_size and index_size members.  All users updated.
* src/alloc.c (gcstat): Add total_hash_table_bytes.
(hash_table_allocated_bytes): New.
(cleanup_vector): Free hash table vectors when sweeping
the object.
(hash_table_alloc_bytes, hash_table_free_bytes): New.
(sweep_vectors): Update gcstat.total_hash_table_bytes.
(total_bytes_of_live_objects): Use it.
(purecopy_hash_table): Adapt allocation of hash table vectors.
(process_mark_stack): No more Lisp slots in the struct to trace.
* src/fns.c (empty_hash_index_vector): New.
(allocate_hash_table): Allocate without automatically GCed slots.
(alloc_larger_vector): Remove.
(make_hash_table, copy_hash_table, maybe_resize_hash_table):
Adapt vector allocation and initialisation.
* src/pdumper.c (hash_table_freeze, hash_table_thaw, dump_hash_table)
(dump_hash_table_contents):
Adapt dumping and loading to field changes.

1 files changed, 75 insertions, 11 deletions

diff --git a/src/alloc.c b/src/alloc.c
index 636b4972c84..7432163db25 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -359,8 +359,16 @@ static struct gcstat
   object_ct total_floats, total_free_floats;
   object_ct total_intervals, total_free_intervals;
   object_ct total_buffers;
+
+  /* Size of the ancillary arrays of live hash-table objects.
+     The objects themselves are not included (counted as vectors above).  */
+  byte_ct total_hash_table_bytes;
 } gcstat;
 
+/* Total size of ancillary arrays of all allocated hash-table objects,
+   both dead and alive.  This number is always kept up-to-date.  */
+static ptrdiff_t hash_table_allocated_bytes = 0;
+
 /* Points to memory space allocated as "spare", to be freed if we run
    out of memory.  We keep one large block, four cons-blocks, and
    two string blocks.  */
@@ -3430,6 +3438,23 @@ cleanup_vector (struct Lisp_Vector *vector)
       }
 #endif
       break;
+    case PVEC_HASH_TABLE:
+      {
+        struct Lisp_Hash_Table *h = PSEUDOVEC_STRUCT (vector, Lisp_Hash_Table);
+        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:
     case PVEC_FREE:
@@ -3440,7 +3465,6 @@ cleanup_vector (struct Lisp_Vector *vector)
     case PVEC_WINDOW:
     case PVEC_BOOL_VECTOR:
     case PVEC_BUFFER:
-    case PVEC_HASH_TABLE:
     case PVEC_TERMINAL:
     case PVEC_WINDOW_CONFIGURATION:
     case PVEC_OTHER:
@@ -3554,6 +3578,8 @@ sweep_vectors (void)
           lisp_free (lv);
         }
     }
+
+  gcstat.total_hash_table_bytes = hash_table_allocated_bytes;
 }
 
 /* Maximum number of elements in a vector.  This is a macro so that it
@@ -5606,6 +5632,28 @@ valid_lisp_object_p (Lisp_Object obj)
   return 0;
 }
 
+/* Like xmalloc, but makes allocation count toward the total consing.
+   Return NULL for a zero-sized allocation.  */
+void *
+hash_table_alloc_bytes (ptrdiff_t nbytes)
+{
+  if (nbytes == 0)
+    return NULL;
+  tally_consing (nbytes);
+  hash_table_allocated_bytes += nbytes;
+  return xmalloc (nbytes);
+}
+
+/* Like xfree, but makes allocation count toward the total consing.  */
+void
+hash_table_free_bytes (void *p, ptrdiff_t nbytes)
+{
+  tally_consing (-nbytes);
+  hash_table_allocated_bytes -= nbytes;
+  xfree (p);
+}
+
+
 /***********************************************************************
                        Pure Storage Management
  ***********************************************************************/
@@ -5897,10 +5945,28 @@ purecopy_hash_table (struct Lisp_Hash_Table *table)
   pure->test.name = purecopy (table->test.name);
   pure->test.user_hash_function = purecopy (table->test.user_hash_function);
   pure->test.user_cmp_function = purecopy (table->test.user_cmp_function);
-  pure->hash = purecopy (table->hash);
-  pure->next = purecopy (table->next);
-  pure->index = purecopy (table->index);
-  pure->key_and_value = purecopy (table->key_and_value);
+
+  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;
 }
@@ -6084,6 +6150,7 @@ total_bytes_of_live_objects (void)
   tot += object_bytes (gcstat.total_floats, sizeof (struct Lisp_Float));
   tot += object_bytes (gcstat.total_intervals, sizeof (struct interval));
   tot += object_bytes (gcstat.total_strings, sizeof (struct Lisp_String));
+  tot += gcstat.total_hash_table_bytes;
   return tot;
 }
 
@@ -7227,23 +7294,20 @@ process_mark_stack (ptrdiff_t base_sp)
               case PVEC_HASH_TABLE:
                 {
                   struct Lisp_Hash_Table *h = (struct Lisp_Hash_Table *)ptr;
-                  ptrdiff_t size = ptr->header.size & PSEUDOVECTOR_SIZE_MASK;
                   set_vector_marked (ptr);
-                  mark_stack_push_values (ptr->contents, size);
                   mark_stack_push_value (h->test.name);
                   mark_stack_push_value (h->test.user_hash_function);
                   mark_stack_push_value (h->test.user_cmp_function);
                   if (h->weakness == Weak_None)
-                    mark_stack_push_value (h->key_and_value);
+                    mark_stack_push_values (h->key_and_value,
+                                            2 * h->table_size);
                   else
                     {
-                      /* For weak tables, mark only the vector and not its
+                      /* For weak tables, don't mark the
                          contents --- that's what makes it weak.  */
                       eassert (h->next_weak == NULL);
                       h->next_weak = weak_hash_tables;
                       weak_hash_tables = h;
-                      if (!PURE_P (h->key_and_value))
-                        set_vector_marked (XVECTOR (h->key_and_value));
                     }
                   break;
                 }