Re: [PATCH 0/3] kallsyms: Accelerate symbol name lookups by ~19x

["Lorenzo Stoakes (ARM)" <ljs@kernel.org>]

On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote:
> kallsyms_lookup_names() resolves symbol names to addresses using a
> 17-step binary search over kallsyms_names[] (~191k symbols on x86_64).
> At each step of the search, two bottlenecks compound to create
> substantial lookup latency:
>
> 0. Marker scanning: get_symbol_offset() scans sequentially from the
>    nearest 256-symbol marker, decoding an average of ~128 ULEB128 record
>    headers per probe (~2,176 header decodes per lookup).
>
> 1. Redundant string expansion: kallsyms_expand_symbol() decompresses
>    the entire candidate symbol into a 512-byte stack buffer (namebuf)
>    before calling strcmp(), even though ~94% of binary search probes
>    mismatch on the first 1-2 characters.
>
> Together, these bottlenecks impose a ~4.3 us latency penalty per hit and
> ~3.8 us per miss.
>
> This 3-patch series eliminates both overheads while keeping the symbol
> table strictly in sequential address order:
>
> 0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to
>    measure name hits, name misses, sprint_symbol(), and table iteration
>    latency, with built-in correctness validation and a sysfs trigger.
>
> 1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct
>    index into kallsyms_names[].  This turns get_symbol_offset() into an
>    O(1) table lookup, dropping the ~2,176 marker hops per lookup and
>    eliminating the legacy kallsyms_markers[] table.
>
> 2. Patch 3 introduces kallsyms_strcmp_symbol() to compare ASCII queries
>    against compressed tokens incrementally on the fly, bailing out on
>    the first mismatched character without expanding subsequent tokens.
>    This drops the 512-byte namebuf buffer from the kernel stack.
>
> Context & Lineage:
>
> This series was originally developed and benchmarked on mainline (v7.3-rc3).
> To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3),
> it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the
> kernel with pigz if available").
>
> Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to
> align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's
> direct binary streaming path (write_incbin).
>
> Glomming onto Lorenzo's build-time acceleration push extends the speedup
> theme into runtime: his series speeds up the compile and link, and this
> series speeds up runtime symbol lookups by ~18x.
>
> Live Microbenchmark Results (via test_kallsyms_perf, 100k iters):
>
> Metric                    Baseline      Patched       Speedup
> -----------------------------------------------------------------
> Name Search Hit           4,370 ns      247 ns        17.7x
> Name Search Miss          3,860 ns      195 ns        19.8x
> sprint_symbol               440 ns      441 ns        parity
> sprint_symbol_no_offset     315 ns      307 ns        parity
> Table Full Walk           14,500 us   14,437 us       parity
>
> Address-to-name resolution (sprint_symbol) and sequential table walks
> (/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
> hardware prefetching.
>
> Hardware PMU Event Counters (perf stat via sysfs run_test trigger):
>
> $ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \
>     sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test'
>
> Counter                 Baseline          Patched           Delta
> ------------------------------------------------------------------------
> Wall-clock elapsed      1.746 s           0.852 s           -51.2%
> CPU cycles              7,320,048,030     3,628,523,081     -50.4%
> Instructions            9,943,172,792     5,034,260,318     -49.4%
> Branches                2,391,663,821     1,173,258,010     -51.0%
> Branch-misses             117,241,513        99,805,938     -14.9%
> Cache-misses               84,996,149           731,025     -99.1%
>
> Dropping marker scans and avoiding redundant string expansions cuts
> 4.91 billion instructions (-49.4%) and drops 84.2 million cache misses
> (-99.1%) across the test workload.
>
> Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
> symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
> kallsyms_markers[].
>
> Signed-off-by: Jim Cromie <jim.cromie@gmail.com>

All very nice :)

I'm glad this work seems to be inspiring other work in the same area! I think
there's a load of improvements to be had across the board.

I will try to have a look through through though my workload is crazy
lately and the build stuff is often taking chunks of the weekend so not
sure if I'll have time, but I did at least want to say - awesome :)

> ---
> Jim Cromie (3):
>       kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
>       kallsyms: Add 3-byte index into compressed symbols to replace marker scans
>       kallsyms: Match compressed tokens on the fly during binary search
>
>  kernel/kallsyms.c          | 138 ++++++++++++++-------------
>  kernel/kallsyms_internal.h |   2 +-
>  lib/Kconfig.debug          |  10 ++
>  lib/Makefile               |   1 +
>  lib/test_kallsyms_perf.c   | 228 +++++++++++++++++++++++++++++++++++++++++++++
>  scripts/kallsyms.c         |  30 +++---
>  6 files changed, 322 insertions(+), 87 deletions(-)
> ---
> base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513
> change-id: 20260919-ksyms-tune-e22a42d8a31a
>
> Best regards,
> --
> Jim Cromie <jim.cromie@gmail.com>
>

--
Cheers, Lorenzo