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

[David Laight <david.laight.linux@gmail.com>]

On Tue, 22 Sep 2026 01:19:18 -0600
Jim Cromie <jim.cromie@gmail.com> wrote:

> kallsyms_lookup_names() resolves symbol names to addresses using a
> 17-step binary search over kallsyms_names[] (~184k 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 ~3.8 us latency penalty per hit and
> ~3.6 us per miss.

How much does just doing change 1 give you?
Might be worth putting that patch first.

If you do the binary chop using only 256 aligned symbols it won't add
any more stages but means you don't need to scan until the 256 symbol
block has been identified.
At that point there are two options:
B: A linear scan - average 128 compare per lookup.
A: Generate a table of the offsets for the next 128 symbols and do
   a binary scan (only read the second 128 if in the second half).

The linear scan may not be too bad.
You can get the first data byte while sorting out the length and then
to an initial check that the first few characters match before adding
in the complexity of the loop along the compressed data.

David