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

Replace the O(n) tail traversal with O(1) tail insertion using a dynamically-allocated 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 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 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; Reviewed-by: Dave Young <yangrr.2009(a)tsinghua.org.cn&gt; --- Changes since v2: - Fix the comment to reference the dynamically-allocated tails[] array instead of val_hash_last (suggested by Dave Young) - Use malloc/free for the tails[] array instead of stack allocation (suggested by Dave Young) 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) symbols.c | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-) diff --git a/symbols.c b/symbols.c index 03511c8cbe8c..2859afa7f6e0 100644 --- a/symbols.c +++ b/symbols.c @@ -1085,12 +1085,18 @@ symbol_value_from_proc_kallsyms(char *symname) /* * Install all static kernel symbol values into the symval_hash. + * Uses a dynamically-allocated tails[] array for O(1) tail insertion. */ static void symval_hash_init(void) { int index; - struct syment *sp, *sph; + struct syment *sp, **tails; + + tails = (struct syment **)malloc(SYMVAL_HASH * sizeof(struct syment *)); + if (tails == NULL) + error(FATAL, "symval_hash_init tails malloc: %s\n", strerror(errno)); + BZERO(tails, SYMVAL_HASH * sizeof(struct syment *)); for (sp = st->symtable; sp < st->symend; sp++) { index = SYMVAL_HASH_INDEX(sp->value); @@ -1098,15 +1104,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; - } - - 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; } + + free(tails); } /* -- 2.20.1