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

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