Re: [PATCH v2 09/18] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion

[Alireza Haghdoost]

On Tue, Oct 27, 2026 at 4:15 PM Ian Rogers <irogers@xxxxxxxxxx> wrote:
> + for (unsigned int k = i - 1; k > 0; k--) {
> + struct symbol *same = symbols->symbols[k - 1];
>
> + if (symbol__start(same) != symbol__start(prev) ||
> + symbol__end(same) != symbol__start(same))
> + break;
> + symbol__set_end(same, symbol__end(prev));
> + }

This changes which kallsyms alias survives. Every kallsyms symbol
starts with zero size. Before, only the last alias at an address got
an end, so symbols__fixup_duplicate() always kept that one. With this
loop every alias gets the same end, and choose_best_symbol() falls
through to its underscore and name-length rules. On x86_64, perf
record -e cpu-clock -g of a getuid/getpid loop, before and after:

0.20% [k] __x64_sys_getuid
0.20% [k] __ia32_sys_getuid

2.87% [k] __memset
2.87% [k] memset

This host has 79 kernel text addresses with more than one name. The
losing alias is deleted, so looking up __x64_sys_getuid by name fails
too. If the change is intended, it needs its own patch and a test with
alias groups. Otherwise, keeping the old "last alias wins" result would
avoid it.

Separately, __symbols__insert_sorted() shifts the tail with memmove(),
so n out-of-order inserts cost O(n^2). In a benchmark of this code,
300k random inserts took 3.4 s, where the rb-tree was O(log n) per
insert. db-export with many unique unresolved addresses would hit
that.

Thanks,
Alireza