[Crash-utility] [PATCH] 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 the existing val_hash_last pointer. 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. The new implementation uses the val_hash_last pointer that was already maintained in the data structure: - Insert at tail in O(1) time - Update val_hash_last after each insertion - Set val_hash_next to NULL for each new entry This reduces hash table initialization from O(n^2) to O(n). Benchmark on a RISC-V 64-core machine (kernel 6.12.95, ~200k symbols): $ echo q | ./crash /proc/kcore vmlinux Before: 44.67 s (mean, n=6, σ=5.61) After: 36.56 s (mean, n=6, σ=2.30) Speedup: 1.22x (-18.1%), with improved consistency. Signed-off-by: Rui Qi <qirui.001(a)bytedance.com&gt; --- symbols.c | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) diff --git a/symbols.c b/symbols.c index 03511c8..0b564d2 100644 --- a/symbols.c +++ b/symbols.c @@ -1085,12 +1085,13 @@ 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; for (sp = st->symtable; sp < st->symend; sp++) { index = SYMVAL_HASH_INDEX(sp->value); @@ -1098,14 +1099,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; + } else { + /* O(1) tail insertion using val_hash_last */ + st->symval_hash[index].val_hash_last->val_hash_next = sp; + st->symval_hash[index].val_hash_last = sp; } - - sph = st->symval_hash[index].val_hash_head; - while (sph->val_hash_next) - sph = sph->val_hash_next; - - sph->val_hash_next = sp; + sp->val_hash_next = NULL; } } -- 2.47.3