[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scratch/hash-table-perf 594152bf667 01/35: Add internal hash-table debug
From: |
Mattias Engdegård |
Subject: |
scratch/hash-table-perf 594152bf667 01/35: Add internal hash-table debug functions |
Date: |
Fri, 12 Jan 2024 10:53:22 -0500 (EST) |
branch: scratch/hash-table-perf
commit 594152bf6675b1bb802249e25311de7bffab0b24
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>
Add internal hash-table debug functions
These are useful for measuring hashing and collisions.
* src/fns.c (Finternal__hash_table_histogram)
(Finternal__hash_table_buckets, Finternal__hash_table_index_size):
New.
---
src/fns.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 65 insertions(+)
diff --git a/src/fns.c b/src/fns.c
index 84aa86d9eb6..724b2d40903 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -5560,6 +5560,68 @@ returns nil, then (funcall TEST x1 x2) also returns nil.
*/)
return Fput (name, Qhash_table_test, list2 (test, hash));
}
+DEFUN ("internal--hash-table-histogram",
+ Finternal__hash_table_histogram,
+ Sinternal__hash_table_histogram,
+ 1, 1, 0,
+ doc: /* Bucket size histogram of HASH-TABLE. Internal use only. */)
+ (Lisp_Object hash_table)
+{
+ struct Lisp_Hash_Table *h = check_hash_table (hash_table);
+ ptrdiff_t size = HASH_TABLE_SIZE (h);
+ ptrdiff_t *freq = xzalloc (size * sizeof *freq);
+ ptrdiff_t index_size = ASIZE (h->index);
+ for (ptrdiff_t i = 0; i < index_size; i++)
+ {
+ ptrdiff_t n = 0;
+ for (ptrdiff_t j = HASH_INDEX (h, i); j != -1; j = HASH_NEXT (h, j))
+ n++;
+ if (n > 0)
+ freq[n - 1]++;
+ }
+ Lisp_Object ret = Qnil;
+ for (ptrdiff_t i = 0; i < size; i++)
+ if (freq[i] > 0)
+ ret = Fcons (Fcons (make_int (i + 1), make_int (freq[i])),
+ ret);
+ xfree (freq);
+ return Fnreverse (ret);
+}
+
+DEFUN ("internal--hash-table-buckets",
+ Finternal__hash_table_buckets,
+ Sinternal__hash_table_buckets,
+ 1, 1, 0,
+ doc: /* (KEY . HASH) in HASH-TABLE, grouped by bucket.
+Internal use only. */)
+ (Lisp_Object hash_table)
+{
+ struct Lisp_Hash_Table *h = check_hash_table (hash_table);
+ Lisp_Object ret = Qnil;
+ ptrdiff_t index_size = ASIZE (h->index);
+ for (ptrdiff_t i = 0; i < index_size; i++)
+ {
+ Lisp_Object bucket = Qnil;
+ for (ptrdiff_t j = HASH_INDEX (h, i); j != -1; j = HASH_NEXT (h, j))
+ bucket = Fcons (Fcons (HASH_KEY (h, j), HASH_HASH (h, j)),
+ bucket);
+ if (!NILP (bucket))
+ ret = Fcons (Fnreverse (bucket), ret);
+ }
+ return Fnreverse (ret);
+}
+
+DEFUN ("internal--hash-table-index-size",
+ Finternal__hash_table_index_size,
+ Sinternal__hash_table_index_size,
+ 1, 1, 0,
+ doc: /* Index size of HASH-TABLE. Internal use only. */)
+ (Lisp_Object hash_table)
+{
+ struct Lisp_Hash_Table *h = check_hash_table (hash_table);
+ ptrdiff_t index_size = ASIZE (h->index);
+ return make_int (index_size);
+}
/************************************************************************
@@ -6250,6 +6312,9 @@ syms_of_fns (void)
defsubr (&Sremhash);
defsubr (&Smaphash);
defsubr (&Sdefine_hash_table_test);
+ defsubr (&Sinternal__hash_table_histogram);
+ defsubr (&Sinternal__hash_table_buckets);
+ defsubr (&Sinternal__hash_table_index_size);
defsubr (&Sstring_search);
defsubr (&Sobject_intervals);
defsubr (&Sline_number_at_pos);
- scratch/hash-table-perf 93d6326e6c0 32/35: Hash-table documentation updates, (continued)
- 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
- scratch/hash-table-perf 594152bf667 01/35: Add internal hash-table debug functions,
Mattias Engdegård <=
- 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
- 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