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

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.

*/ static void symval_hash_init(void) { int index; - struct syment *sp, *sph; + struct syment *sp; + struct syment *tails[SYMVAL_HASH]; + + BZERO(tails, sizeof(tails));

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; } }