[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scratch/hash-table-perf c805d2173f8 33/35: Use a static index vector for
From: |
Mattias Engdegård |
Subject: |
scratch/hash-table-perf c805d2173f8 33/35: Use a static index vector for zero-sized tables |
Date: |
Fri, 12 Jan 2024 10:53:27 -0500 (EST) |
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.
- scratch/hash-table-perf dd4ee2c634b 15/35: Represent hash table weakness as an enum internally, (continued)
- scratch/hash-table-perf dd4ee2c634b 15/35: Represent hash table weakness as an enum internally, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 615d3e4cdc6 17/35: Leaner hash table dumping and thawing, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf d003b84c484 19/35: Use non-Lisp allocation for internal hash-table vectors, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf afd2185bfdb 20/35: Store hash values as integers instead of Lisp_Object, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf c98ba3d4fa6 21/35: Inlined and specialised hash table look-up, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 414470d1e24 23/35: Share hash table test structs, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 589318470c1 24/35: ; Reorder structs (hash and test), Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf bf1f1c5a9a4 25/35: Faster hash table growth, starting smaller, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 8811c5d81e7 27/35: Don't dump Qunbound, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf ef0323e9029 30/35: Adapt hash functions to produce a hash_hash_t eventually, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf c805d2173f8 33/35: Use a static index vector for zero-sized tables,
Mattias Engdegård <=
- scratch/hash-table-perf 8884720dce8 34/35: Change default hash table size to 0, Mattias Engdegård, 2024/01/12