[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scratch/hash-table-perf 8f608cb4a1c 28/35: Use key Qunbound instead of h
From: |
Mattias Engdegård |
Subject: |
scratch/hash-table-perf 8f608cb4a1c 28/35: Use key Qunbound instead of hash value hash_unused for free entries |
Date: |
Fri, 12 Jan 2024 10:53:26 -0500 (EST) |
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;
}
- branch scratch/hash-table-perf created (now 8ec0e030b66), Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf a39bca66533 03/35: Decouple profiler from Lisp hash table internals, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf dd89a9fb76d 04/35: Refactor: less layering violation in composite.h, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 05694f4491d 08/35: ; * src/alloc.c (purecopy_hash_table): Simplify, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf b9b2c5a12a8 10/35: ; * src/fns.c (Fmake_hash_table): ensure `test` is a bare symbol, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf b96f48232ac 11/35: ; * src/lisp.h (struct Lisp_Hash_Table): Add ASCII art., Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf d7dbbc74a00 13/35: * src/print.c (print_object): Don't print empty hash-table data, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 9b39cee78e3 12/35: * src/print.c (print_object): Don't print hash table test if `eql`., Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 08acca67739 14/35: Don't print or read the hash table size parameter, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf b1218be258a 18/35: Allow zero hash table size, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 8f608cb4a1c 28/35: Use key Qunbound instead of hash value hash_unused for free entries,
Mattias Engdegård <=
- scratch/hash-table-perf 93d6326e6c0 32/35: Hash-table documentation updates, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 1462fca6dce 16/35: Remove rehash-threshold and rehash-size struct members, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 3b3fea97ecc 22/35: Use hash_idx_t for storing hash indices, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 58559a83827 29/35: * src/lisp.h (hash_hash_t): Change to uint32_t., Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 441c4d53cf6 31/35: Don't pretend that hash-table-size is useful, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf a0560e90d3b 26/35: Change hash_idx_t to int32_t on all platforms, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 8ec0e030b66 35/35: Combine hash and next vector into a single array, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf b9a0b88aea8 05/35: ; * src/fns.c (collect_interval): Move misplaced function., Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf ed4ce0af9a9 06/35: Refactor: extract hash and index computations to functions, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf e55fcdafa07 09/35: Abstract predicate and constant for unused hash keys, Mattias Engdegård, 2024/01/12