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

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!

Hi Rui & Dave, On Mon, Aug 10, 2026 at 3:40 PM Rui Qi <qirui.001(a)bytedance.com&gt; wrote: > > On 8/9/26 9:22 AM, Dave Young wrote: > > 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. Before you draft the new patch, please use GETBUF/FREEBUF rather than pure malloc/free. GETBUF & FREEBUF is preferred in crash, E.g. if one crash command which usd GETBUF() fails, memory allocated by GETBUF() will be taken care of by crash itself, but malloc()'s won't. Thanks, Tao Liu > >>> > >>>> > >>>> 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! > > > > Hi Dave, > > Thanks for the review and the Reviewed-by. > > Regarding the malloc suggestion: I originally chose stack allocation > for a few reasons: > > 1. SYMVAL_HASH is 512, so tails[] is only 4KB (512 * 8 bytes) on the > stack, which is negligible for a user-space application with an 8MB > stack limit. Even if the macro were to grow to 4096 or 8192, that would > still be only 32KB-64KB -- well within safe bounds. > > 2. If SYMVAL_HASH were ever changed to a value large enough to cause > stack issues, the person making that change would need to audit all its > usage sites -- symval_hash_init would not be the only affected function. > > 3. Stack allocation avoids the malloc NULL check, the error path, and > the free call, keeping the one-time initialization function simpler. > > 4. The same reasoning would imply that every stack array sized by a > macro in the codebase should be heap-allocated, which is neither > practical nor consistent with how the rest of the code is written. > > That said, I understand your concern about forward compatibility, and > as the maintainer this is ultimately your call. I've updated v3 to > use malloc/free as suggested. > > Thanks, > Rui > > > >> > >> 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 > > >