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

On 8/8/26 3:05 PM, Rui Qi wrote: > 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. I know it should be ok for the time being, but who knows if the macro could change in the future or not, maybe it is just a personal taste. Yes, please update it if you can, and feel free to add my reviewed-by tag Thanks a lot!