[Crash-utility] [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>
Reviewed-by: Dave Young <yangrr.2009(a)tsinghua.org.cn>
---
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