[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scratch/hash-table-perf ed4ce0af9a9 06/35: Refactor: extract hash and in
From: |
Mattias Engdegård |
Subject: |
scratch/hash-table-perf ed4ce0af9a9 06/35: Refactor: extract hash and index computations to functions |
Date: |
Fri, 12 Jan 2024 10:53:23 -0500 (EST) |
branch: scratch/hash-table-perf
commit ed4ce0af9a9111cc22561fea19843f5530475861
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>
Refactor: extract hash and index computations to functions
* src/lisp.h (hash_from_key):
* src/fns.c (hash_index_index): New.
(hash_table_rehash, hash_lookup, hash_remove_from_table):
(maybe_resize_hash_table, hash_put):
* src/composite.c (composition_gstring_put_cache): Use them.
---
src/composite.c | 2 +-
src/fns.c | 34 ++++++++++++++++++----------------
src/lisp.h | 7 +++++++
3 files changed, 26 insertions(+), 17 deletions(-)
diff --git a/src/composite.c b/src/composite.c
index aeae02fd1ce..142259acadf 100644
--- a/src/composite.c
+++ b/src/composite.c
@@ -653,7 +653,7 @@ composition_gstring_put_cache (Lisp_Object gstring,
ptrdiff_t len)
{
struct Lisp_Hash_Table *h = XHASH_TABLE (gstring_hash_table);
Lisp_Object header = LGSTRING_HEADER (gstring);
- Lisp_Object hash = h->test.hashfn (header, h);
+ Lisp_Object hash = hash_from_key (h, header);
if (len < 0)
{
ptrdiff_t glyph_len = LGSTRING_GLYPH_LEN (gstring);
diff --git a/src/fns.c b/src/fns.c
index e0e52adb77f..aeaeea7375f 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -4631,6 +4631,13 @@ copy_hash_table (struct Lisp_Hash_Table *h1)
}
+/* Compute index into the index vector from a hash value. */
+static inline ptrdiff_t
+hash_index_index (struct Lisp_Hash_Table *h, Lisp_Object hash_code)
+{
+ return XUFIXNUM (hash_code) % ASIZE (h->index);
+}
+
/* Resize hash table H if it's too full. If H cannot be resized
because it's already too large, throw an error. */
@@ -4689,8 +4696,8 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h)
for (ptrdiff_t i = 0; i < old_size; i++)
if (!NILP (HASH_HASH (h, i)))
{
- EMACS_UINT hash_code = XUFIXNUM (HASH_HASH (h, i));
- ptrdiff_t start_of_bucket = hash_code % ASIZE (h->index);
+ Lisp_Object hash_code = HASH_HASH (h, i);
+ ptrdiff_t start_of_bucket = hash_index_index (h, hash_code);
set_hash_next_slot (h, i, HASH_INDEX (h, start_of_bucket));
set_hash_index_slot (h, start_of_bucket, i);
}
@@ -4718,8 +4725,8 @@ hash_table_rehash (Lisp_Object hash)
for (i = 0; i < count; i++)
{
Lisp_Object key = HASH_KEY (h, i);
- Lisp_Object hash_code = h->test.hashfn (key, h);
- ptrdiff_t start_of_bucket = XUFIXNUM (hash_code) % ASIZE (h->index);
+ Lisp_Object hash_code = hash_from_key (h, key);
+ ptrdiff_t start_of_bucket = hash_index_index (h, hash_code);
set_hash_hash_slot (h, i, hash_code);
set_hash_next_slot (h, i, HASH_INDEX (h, start_of_bucket));
set_hash_index_slot (h, start_of_bucket, i);
@@ -4738,15 +4745,12 @@ hash_table_rehash (Lisp_Object hash)
ptrdiff_t
hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object *hash)
{
- ptrdiff_t start_of_bucket, i;
-
- Lisp_Object hash_code;
- hash_code = h->test.hashfn (key, h);
+ Lisp_Object hash_code = hash_from_key (h, key);
if (hash)
*hash = hash_code;
- start_of_bucket = XUFIXNUM (hash_code) % ASIZE (h->index);
-
+ ptrdiff_t start_of_bucket = hash_index_index (h, hash_code);
+ ptrdiff_t i;
for (i = HASH_INDEX (h, start_of_bucket); 0 <= i; i = HASH_NEXT (h, i))
if (EQ (key, HASH_KEY (h, i))
|| (h->test.cmpfn
@@ -4773,14 +4777,12 @@ ptrdiff_t
hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value,
Lisp_Object hash)
{
- ptrdiff_t start_of_bucket, i;
-
/* Increment count after resizing because resizing may fail. */
maybe_resize_hash_table (h);
h->count++;
/* Store key/value in the key_and_value vector. */
- i = h->next_free;
+ ptrdiff_t i = h->next_free;
eassert (NILP (HASH_HASH (h, i)));
eassert (BASE_EQ (Qunbound, (HASH_KEY (h, i))));
h->next_free = HASH_NEXT (h, i);
@@ -4791,7 +4793,7 @@ hash_put (struct Lisp_Hash_Table *h, Lisp_Object key,
Lisp_Object value,
set_hash_hash_slot (h, i, hash);
/* Add new entry to its collision chain. */
- start_of_bucket = XUFIXNUM (hash) % ASIZE (h->index);
+ ptrdiff_t start_of_bucket = hash_index_index (h, hash);
set_hash_next_slot (h, i, HASH_INDEX (h, start_of_bucket));
set_hash_index_slot (h, start_of_bucket, i);
return i;
@@ -4803,8 +4805,8 @@ hash_put (struct Lisp_Hash_Table *h, Lisp_Object key,
Lisp_Object value,
void
hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key)
{
- Lisp_Object hash_code = h->test.hashfn (key, h);
- ptrdiff_t start_of_bucket = XUFIXNUM (hash_code) % ASIZE (h->index);
+ Lisp_Object hash_code = hash_from_key (h, key);
+ ptrdiff_t start_of_bucket = hash_index_index (h, hash_code);
ptrdiff_t prev = -1;
for (ptrdiff_t i = HASH_INDEX (h, start_of_bucket);
diff --git a/src/lisp.h b/src/lisp.h
index c28d52af8b8..863a0fe4a3e 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2524,6 +2524,13 @@ HASH_TABLE_SIZE (const struct Lisp_Hash_Table *h)
return size;
}
+/* Compute hash value for KEY in hash table H. */
+INLINE Lisp_Object
+hash_from_key (struct Lisp_Hash_Table *h, Lisp_Object key)
+{
+ return h->test.hashfn (key, h);
+}
+
void hash_table_rehash (Lisp_Object);
/* Default size for hash tables if not specified. */
- scratch/hash-table-perf b1218be258a 18/35: Allow zero hash table size, (continued)
- 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, 2024/01/12
- 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 <=
- scratch/hash-table-perf e55fcdafa07 09/35: Abstract predicate and constant for unused hash keys, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 594152bf667 01/35: Add internal hash-table debug functions, Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf 422c91a822a 02/35: ; * src/pdumper.c (dump_hash_table): Remove unused argument., Mattias Engdegård, 2024/01/12
- scratch/hash-table-perf f2d6e2713c0 07/35: Refactor hash table vector reallocation, Mattias Engdegård, 2024/01/12
- 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