[Crash-utility] Re: [PATCH] symbols: optimize symval_hash_init with O(1) tail insertion
Hi Dave & Rui,
On Fri, Jul 31, 2026 at 8:45 PM Dave Young <yangrr.2009(a)tsinghua.org.cn> wrote:
Hi,
I'm trying to understanding the crash tool and help some review as I know the
maintainers time resources are limited for the time being.
From: "启瑞" <qirui.001(a)bytedance.com>
Date: 2026-07-22 16:00:47
To: ltao(a)redhat.com
Cc: devel(a)lists.crash-utility.osci.io,Rui Qi <qirui.001(a)bytedance.com>
Subject: [Crash-utility] [PATCH] symbols: optimize symval_hash_init with O(1) tail
insertion>From: Rui Qi <qirui.001(a)bytedance.com>
>
>Replace the O(n) tail traversal with O(1) tail insertion using the
>existing val_hash_last pointer. The original code traversed the entire
>linked list on every insert to find the tail, resulting in O(n^2)
>complexity for hash table initialization.
>
>The new implementation uses the val_hash_last pointer that was already
>maintained in the data structure:
It seems the val_has_last pointer is created for the "last visited entry"
instead of the "tail" of the table. But you are using it as the tail pointer.
Agreed, original val_hash_last is "the last visited entry", not the
last entry of the hash bucket. And from symval_hash_search(), I see
the val_hash_last is used to split the chain as:
val_hash_head --- val_hash_last --- the end entry.
So any entry with a larger value will be searched from val_hash_last
rather from val_hash_head, thus making the search len averge to n/2.
Your approach shortened the initialization time for the hash table,
but it might increase the time required for value searching.
However I'm not saying the current algorithm is perfect, if you'd like
to improve it, please:
1) improve symval_hash_search() as well, because the meaning of
val_hash_last is unchanged in this function;
2) You need to prove the performance is better after the change on
other different CPU archs, at least on x86_64 && arm64, as well as
your riscv64, because the modified code serves for all archs, only on
riscv64 is not persuasive in this case.
Thanks,
Tao Liu
>- Insert at tail in O(1) time
>- Update val_hash_last after each insertion
>- Set val_hash_next to NULL for each new entry
>
>This reduces hash table initialization from O(n^2) to O(n).
>
>Benchmark on a RISC-V 64-core machine (kernel 6.12.95, ~200k symbols):
>
> $ echo q | ./crash /proc/kcore vmlinux
>
> Before: 44.67 s (mean, n=6, σ=5.61)
> After: 36.56 s (mean, n=6, σ=2.30)
> Speedup: 1.22x (-18.1%), with improved consistency.
>
>Signed-off-by: Rui Qi <qirui.001(a)bytedance.com>
>---
> symbols.c | 15 +++++++--------
> 1 file changed, 7 insertions(+), 8 deletions(-)
>
>diff --git a/symbols.c b/symbols.c
>index 03511c8..0b564d2 100644
>--- a/symbols.c
>+++ b/symbols.c
>@@ -1085,12 +1085,13 @@ symbol_value_from_proc_kallsyms(char *symname)
>
> /*
> * Install all static kernel symbol values into the symval_hash.
>+ * Uses val_hash_last for O(1) tail insertion.
> */
> static void
> symval_hash_init(void)
> {
> int index;
>- struct syment *sp, *sph;
>+ struct syment *sp;
>
> for (sp = st->symtable; sp < st->symend; sp++) {
> index = SYMVAL_HASH_INDEX(sp->value);
>@@ -1098,14 +1099,12 @@ symval_hash_init(void)
> if (st->symval_hash[index].val_hash_head == NULL) {
> st->symval_hash[index].val_hash_head = sp;
> st->symval_hash[index].val_hash_last = sp;
>- continue;
>+ } else {
>+ /* O(1) tail insertion using val_hash_last */
>+ st->symval_hash[index].val_hash_last->val_hash_next = sp;
if the head pointer is NULL, could the last value be NULL as well?
>+ st->symval_hash[index].val_hash_last = sp;
> }
>-
>- sph = st->symval_hash[index].val_hash_head;
>- while (sph->val_hash_next)
>- sph = sph->val_hash_next;
>-
>- sph->val_hash_next = sp;
>+ sp->val_hash_next = NULL;
> }
> }
>
>--
>2.47.3
>--
>Crash-utility mailing list -- devel(a)lists.crash-utility.osci.io
>To unsubscribe send an email to devel-leave(a)lists.crash-utility.osci.io
>https://${domain_name}/admin/lists/devel.lists.crash-utility.osci.io/
>Contribution Guidelines: https://github.com/crash-utility/crash/wiki
Thanks
Dave