[Crash-utility] Re: [PATCH v2] symbols: optimize symval_hash_init with O(1) tail insertion

On 8/7/26 6:04 PM, Dave Young wrote: > Hi 启瑞, > > On 8/3/26 8:28 PM, 启瑞 wrote: >> From: Rui Qi <qirui.001(a)bytedance.com&gt; >> >> Replace the O(n) tail traversal with O(1) tail insertion using a local >> per-bucket tail tracking array. 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. >> >> This reduces hash table initialization from O(n^2) to O(n). >> >> Benchmark on an x86_64 machine (kernel 5.10.135, ~112k symbols): >> >> Before: 5.54 s (mean, n=6, sigma=0.12) >> After: 5.31 s (mean, n=6, sigma=0.12) >> Speedup: 1.04x (-4.1%) >> >> Benchmark on an ARM64 Neoverse-N2 machine (kernel 5.15.152.bsk.4-arm64, >> ~132k nm symbols): >> >> Before: 3.4113 s (mean, n=48, sigma=0.0698) >> After: 2.5073 s (mean, n=48, sigma=0.0394) >> Speedup: 1.36x (-26.5%), with improved consistency. >> User CPU: 4.1706 s -> 3.2768 s (-21.4%). >> >> Benchmark retest on a RISC-V machine (kernel >> 6.12.13.bsk.1-rc14-riscv64, ~198k nm symbols): >> >> $ printf 'q\n' | ./crash vmlinux /proc/kcore >> >> Before: 11.934 s (mean, n=3, sigma=0.880; samples: 12.921, 11.231, 11.651) >> After: 10.255 s (mean, n=3, sigma=0.835; samples: 11.131, 9.467, 10.168) >> Speedup: 1.16x (-14.1%) >> >> Signed-off-by: Rui Qi <qirui.001(a)bytedance.com&gt; >> Changes from V1 [1]: >> - Use a separate local tails[] array for tail tracking instead of reusing >> val_hash_last, to preserve its original semantics as a last-visited-entry >> cache for symval_hash_search(). (Dave Young, Tao Liu) >> - Add benchmarks on x86_64 and ARM64 in addition to RISC-V. (Tao Liu) >> >> [1] https://lists.crash-utility.osci.io/archives/list/devel@lists.crash-utili... >> >> --- >> symbols.c | 17 ++++++++--------- >> 1 file changed, 8 insertions(+), 9 deletions(-) >> >> diff --git a/symbols.c b/symbols.c >> index 03511c8cbe8c..42e0058a102e 100644 >> --- a/symbols.c >> +++ b/symbols.c >> @@ -1085,12 +1085,16 @@ 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. > > the above comment still says val_has_last.. > >> */ >> static void >> symval_hash_init(void) >> { >> int index; >> - struct syment *sp, *sph; >> + struct syment *sp; >> + struct syment *tails[SYMVAL_HASH]; >> + >> + BZERO(tails, sizeof(tails)); > > I would suggest to malloc the array memory instead. > >> >> for (sp = st->symtable; sp < st->symend; sp++) { >> index = SYMVAL_HASH_INDEX(sp->value); >> @@ -1098,14 +1102,9 @@ 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; >> - } >> - >> - sph = st->symval_hash[index].val_hash_head; >> - while (sph->val_hash_next) >> - sph = sph->val_hash_next; >> - >> - sph->val_hash_next = sp; >> + } else >> + tails[index]->val_hash_next = sp; >> + tails[index] = sp; >> } >> } >> > > Thanks > Dave Hi Dave, Thanks for the review. You're right, the comment is misleading — the O(1) tail insertion is achieved by the local tails[] array, not val_hash_last. I'll fix the comment to accurately reflect the mechanism. Regarding malloc: since SYMVAL_HASH is 512 and each entry is a pointer (8 bytes on 64-bit), the tails[] array is only 4KB on the stack. As a user-space application with a default 8MB stack limit, this is safe and negligible. Using malloc would add a NULL check and free call for no real benefit in this one-time initialization path. I'd prefer to keep the stack allocation, but I'm happy to change it if you feel strongly about it.

Thanks, Rui -- 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