[PATCH v8 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail

From: Ian Rogers

Date: Sun Nov 22 2026 - 00:04:49 EST


Dynamic symbol resolution (dso__insert_symbol()) frequently inserts one
or a few symbols into an already-sorted DSO symbol table, and small
batches of symbols may also be appended after an initial sort.
Re-running full-array merge sort on every incremental insertion or
memmoving the entire sorted array on every out-of-order dynamic
insertion spends avoidable CPU time.

Speed up incremental symbol insertions and small-append sorting:

- Track the sorted prefix length (@sorted_cnt) in struct symbols and use
an O(N) in-place binary insertion fast path in symbols__sort_locked()
when <= 8 symbols have been appended.
- Add __symbols__insert_sorted() for dso__insert_symbol() so that when
symbols->sorted is true, ascending symbols append in O(1), small
tables (cnt < 64) binary-insert in place, and larger out-of-order
insertions maintain a sorted tail buffer at symbols[sorted_cnt .. cnt)
with an amortized sqrt(N) merge threshold.
- Search both the sorted prefix and any unmerged sorted tail in
symbols__find() while preserving the single-array highest start <= ip
semantics.

Using 'perf bench internals symbols':

Before:
Average append + lookup: 40429.750 usec (+- 507.578 usec)
After (-99.6%):
Average append + lookup: 152.900 usec (+- 0.736 usec)

Signed-off-by: Ian Rogers <irogers@xxxxxxxxxx>

# Conflicts:
# tools/perf/util/symbol.h
---
tools/perf/util/symbol.c | 206 +++++++++++++++++++++++++++++++++++----
tools/perf/util/symbol.h | 11 ++-
2 files changed, 198 insertions(+), 19 deletions(-)

diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 35b08c05a2fd..22b84e9a40fd 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -220,6 +220,7 @@ void symbols__init(struct symbols *symbols)
symbols->symbols = NULL;
symbols->symbols_by_name = NULL;
symbols->cnt = 0;
+ symbols->sorted_cnt = 0;
symbols->allocated = 0;
symbols->num_by_name = 0;
symbols->sorted = true;
@@ -235,6 +236,7 @@ static void symbols__delete_locked(struct symbols *symbols)
zfree(&symbols->symbols);
zfree(&symbols->symbols_by_name);
symbols->cnt = 0;
+ symbols->sorted_cnt = 0;
symbols->allocated = 0;
symbols->num_by_name = 0;
symbols->sorted = true;
@@ -283,9 +285,10 @@ static unsigned int symbols__upper_bound(struct symbol **arr, unsigned int len,

static void symbols__insertion_sort_range(struct symbol **arr,
unsigned int start,
+ unsigned int first_unsorted,
unsigned int end)
{
- for (unsigned int i = start + 1; i < end; i++) {
+ for (unsigned int i = max(first_unsorted, start + 1); i < end; i++) {
struct symbol *sym = arr[i];

if (!symbol__less_or_equal(arr[i - 1], sym)) {
@@ -359,7 +362,7 @@ static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n,
unsigned int i = 0;

if (n <= 32) {
- symbols__insertion_sort_range(arr, 0, n);
+ symbols__insertion_sort_range(arr, 0, 1, n);
return;
}

@@ -383,8 +386,10 @@ static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n,
}

if (i - start < 32 && i < n) {
+ unsigned int run_end = i;
+
i = min(start + 32U, n);
- symbols__insertion_sort_range(arr, start, i);
+ symbols__insertion_sort_range(arr, start, run_end, i);
}

runs[nr_runs++] = (struct symbol_run){
@@ -435,32 +440,79 @@ static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n,
static void symbols__sort_locked(struct symbols *symbols)
__must_hold(&symbols->lock)
{
- if (symbols->sorted)
+ unsigned int m = symbols->sorted_cnt;
+ unsigned int k;
+
+ if (symbols->sorted && symbols->sorted_cnt == symbols->cnt)
return;

- if (symbols->cnt <= 64) {
- symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
- } else {
+ if (m > symbols->cnt)
+ m = 0;
+ k = symbols->cnt - m;
+
+ if (k == 0) {
+ symbols->sorted = true;
+ return;
+ }
+
+ /*
+ * When only a few symbols have been appended since the last sort
+ * (including single-symbol insertions), insert them directly at
+ * their binary-searched sorted positions in O(N) without allocating.
+ */
+ if (k <= 8 || symbols->cnt <= 64) {
+ symbols__insertion_sort_range(symbols->symbols, 0, m, symbols->cnt);
+ symbols->sorted_cnt = symbols->cnt;
+ symbols->sorted = true;
+ return;
+ }
+
+ if (symbols->sorted) {
+ /*
+ * Both [0 .. m) and the sorted tail [m .. cnt) are already
+ * sorted; merge them into a single sorted run.
+ */
+ struct symbol **tmp = malloc(min(m, k) * sizeof(struct symbol *));
+
+ if (tmp) {
+ symbols__merge_runs(symbols->symbols, 0, m, symbols->cnt, tmp);
+ free(tmp);
+ } else {
+ symbols__insertion_sort_range(symbols->symbols, 0, m, symbols->cnt);
+ }
+ } else if (m <= 1) {
struct symbol **tmp = malloc(((symbols->cnt + 1) / 2) * sizeof(struct symbol *));

if (tmp) {
symbols__sort_range_with_tmp(symbols->symbols, symbols->cnt, tmp);
free(tmp);
} else {
- symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
+ symbols__insertion_sort_range(symbols->symbols, 0, m, symbols->cnt);
+ }
+ } else {
+ struct symbol **tmp = malloc(k * sizeof(struct symbol *));
+
+ if (tmp) {
+ symbols__sort_range_with_tmp(&symbols->symbols[m], k, tmp);
+ symbols__merge_runs(symbols->symbols, 0, m, symbols->cnt, tmp);
+ free(tmp);
+ } else {
+ symbols__insertion_sort_range(symbols->symbols, 0, m, symbols->cnt);
}
}
+
+ symbols->sorted_cnt = symbols->cnt;
symbols->sorted = true;
}

/*
* Acquire @symbols->lock for reading after ensuring @symbols->symbols is
- * sorted.
+ * fully sorted into a single contiguous run.
*/
void symbols__sort_read_lock(struct symbols *symbols)
{
down_read(&symbols->lock);
- while (!symbols->sorted) {
+ while (!symbols->sorted || symbols->sorted_cnt < symbols->cnt) {
up_read(&symbols->lock);
down_write(&symbols->lock);
symbols__sort_locked(symbols);
@@ -509,6 +561,7 @@ void symbols__fixup_duplicate(struct symbols *symbols)
}
}
symbols->cnt = write_idx + 1;
+ symbols->sorted_cnt = symbols->cnt;
zfree(&symbols->symbols_by_name);
symbols->num_by_name = 0;
symbols->sorted_by_name = false;
@@ -685,9 +738,15 @@ static int __symbols__insert(struct symbols *symbols, struct symbol *sym)
symbols->allocated = to_allocate;
}

- if (symbols->sorted && symbols->cnt > 0 &&
- !symbol__less_or_equal(symbols->symbols[symbols->cnt - 1], sym))
+ if (symbols->sorted && symbols->sorted_cnt == symbols->cnt) {
+ if (symbols->cnt == 0 ||
+ symbol__less_or_equal(symbols->symbols[symbols->cnt - 1], sym))
+ symbols->sorted_cnt = symbols->cnt + 1;
+ else
+ symbols->sorted = false;
+ } else {
symbols->sorted = false;
+ }

symbols->symbols[symbols->cnt++] = sym;
zfree(&symbols->symbols_by_name);
@@ -696,6 +755,70 @@ static int __symbols__insert(struct symbols *symbols, struct symbol *sym)
return 0;
}

+static int __symbols__insert_sorted(struct symbols *symbols, struct symbol *sym)
+ __must_hold(&symbols->lock)
+{
+ unsigned int idx;
+
+ if (!symbols->sorted)
+ return __symbols__insert(symbols, sym);
+
+ if (symbols->cnt == symbols->allocated) {
+ unsigned int to_allocate = symbols->allocated ? symbols->allocated * 2 : 32;
+ struct symbol **temp = realloc(symbols->symbols,
+ sizeof(struct symbol *) * to_allocate);
+
+ if (!temp) {
+ symbol__delete(sym);
+ return -ENOMEM;
+ }
+ symbols->symbols = temp;
+ symbols->allocated = to_allocate;
+ }
+
+ if (symbols->sorted_cnt == symbols->cnt) {
+ if (symbols->cnt == 0 ||
+ symbol__less_or_equal(symbols->symbols[symbols->cnt - 1], sym)) {
+ symbols->symbols[symbols->cnt++] = sym;
+ symbols->sorted_cnt = symbols->cnt;
+ } else if (symbols->cnt < 64) {
+ idx = symbols__upper_bound(symbols->symbols, symbols->cnt, sym);
+ memmove(&symbols->symbols[idx + 1], &symbols->symbols[idx],
+ (symbols->cnt - idx) * sizeof(struct symbol *));
+ symbols->symbols[idx] = sym;
+ symbols->cnt++;
+ symbols->sorted_cnt = symbols->cnt;
+ } else {
+ /*
+ * Start a sorted tail buffer at symbols[sorted_cnt .. cnt)
+ * so out-of-order insertions do not memmove the entire
+ * primary sorted prefix on every call.
+ */
+ symbols->symbols[symbols->cnt++] = sym;
+ }
+ } else {
+ unsigned int tail_cnt = symbols->cnt - symbols->sorted_cnt;
+
+ idx = symbols->sorted_cnt +
+ symbols__upper_bound(&symbols->symbols[symbols->sorted_cnt],
+ tail_cnt, sym);
+ memmove(&symbols->symbols[idx + 1], &symbols->symbols[idx],
+ (symbols->cnt - idx) * sizeof(struct symbol *));
+ symbols->symbols[idx] = sym;
+ symbols->cnt++;
+ tail_cnt++;
+
+ if (tail_cnt >= 256 &&
+ (size_t)tail_cnt * tail_cnt >= symbols->sorted_cnt)
+ symbols__sort_locked(symbols);
+ }
+
+ zfree(&symbols->symbols_by_name);
+ symbols->num_by_name = 0;
+ symbols->sorted_by_name = false;
+ return 0;
+}
+
int symbols__insert(struct symbols *symbols, struct symbol *sym)
{
int ret;
@@ -714,7 +837,9 @@ static inline bool symbol__covers(const struct symbol *s, u64 ip)
return ip >= start && (ip < end || (ip == end && ip == start));
}

-static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt, u64 ip)
+static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
+ u64 ip, bool *has_candidate,
+ u64 *candidate_start)
{
unsigned int low = 0, high = cnt, idx;
u64 start;
@@ -727,8 +852,10 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
else
high = mid;
}
- if (low == 0)
+ if (low == 0) {
+ *has_candidate = false;
return NULL;
+ }

/*
* Rewind across any equal-start group so a trailing zero-length or
@@ -737,6 +864,8 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
*/
idx = low - 1;
start = arr[idx]->start;
+ *has_candidate = true;
+ *candidate_start = start;
while (idx > 0 && arr[idx - 1]->start == start)
idx--;
for (; idx < low; idx++) {
@@ -753,12 +882,38 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
static struct symbol *symbols__find(struct symbols *symbols, u64 ip)
{
struct symbol *res;
+ bool has_prefix;
+ u64 prefix_start = 0;

if (symbols == NULL)
return NULL;

- symbols__sort_read_lock(symbols);
- res = symbols__find_range(symbols->symbols, symbols->cnt, ip);
+ down_read(&symbols->lock);
+ while (!symbols->sorted) {
+ up_read(&symbols->lock);
+ down_write(&symbols->lock);
+ symbols__sort_locked(symbols);
+ up_write(&symbols->lock);
+ down_read(&symbols->lock);
+ }
+
+ res = symbols__find_range(symbols->symbols, symbols->sorted_cnt, ip,
+ &has_prefix, &prefix_start);
+ if (symbols->sorted_cnt < symbols->cnt) {
+ struct symbol *tail_res;
+ bool has_tail;
+ u64 tail_start = 0;
+
+ tail_res = symbols__find_range(&symbols->symbols[symbols->sorted_cnt],
+ symbols->cnt - symbols->sorted_cnt, ip,
+ &has_tail, &tail_start);
+ if (has_tail) {
+ if (!has_prefix || tail_start > prefix_start)
+ res = tail_res;
+ else if (tail_start == prefix_start && !res)
+ res = tail_res;
+ }
+ }
up_read(&symbols->lock);

return res;
@@ -904,7 +1059,13 @@ static struct symbol *symbols__find_by_name(struct symbol *symbols[],

int dso__insert_symbol(struct dso *dso, struct symbol *sym)
{
- return symbols__insert(dso__symbols(dso), sym);
+ struct symbols *symbols = dso__symbols(dso);
+ int ret;
+
+ down_write(&symbols->lock);
+ ret = __symbols__insert_sorted(symbols, sym);
+ up_write(&symbols->lock);
+ return ret;
}

void dso__delete_symbol(struct dso *dso, struct symbol *sym)
@@ -912,11 +1073,15 @@ void dso__delete_symbol(struct dso *dso, struct symbol *sym)
struct symbols *symbols = dso__symbols(dso);

down_write(&symbols->lock);
- for (unsigned int i = 0; i < symbols->cnt; i++) {
+ for (unsigned int i = symbols->cnt; i-- > 0; ) {
if (symbols->symbols[i] == sym) {
memmove(&symbols->symbols[i], &symbols->symbols[i + 1],
(symbols->cnt - i - 1) * sizeof(struct symbol *));
symbols->cnt--;
+ if (i < symbols->sorted_cnt)
+ symbols->sorted_cnt--;
+ if (symbols->sorted_cnt == symbols->cnt)
+ symbols->sorted = true;
zfree(&symbols->symbols_by_name);
symbols->num_by_name = 0;
symbols->sorted_by_name = false;
@@ -1263,6 +1428,7 @@ static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso)
old_cnt = root->cnt;
root->symbols = NULL;
root->cnt = 0;
+ root->sorted_cnt = 0;
root->allocated = 0;
root->sorted = true;
zfree(&root->symbols_by_name);
@@ -1337,6 +1503,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
old_allocated = root->allocated;
root->symbols = NULL;
root->cnt = 0;
+ root->sorted_cnt = 0;
root->allocated = 0;
root->sorted = true;
zfree(&root->symbols_by_name);
@@ -1487,6 +1654,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
if (root->cnt == 0) {
root->symbols = old_symbols;
root->cnt = write_idx;
+ root->sorted_cnt = write_idx;
root->allocated = old_allocated;
root->sorted = true;
old_symbols = NULL;
@@ -1516,12 +1684,14 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
if (root->cnt == 0) {
root->symbols = old_symbols;
root->cnt = write_idx;
+ root->sorted_cnt = (delta == 0) ? write_idx : 0;
root->allocated = old_allocated;
root->sorted = (delta == 0);
old_symbols = NULL;
} else {
for (unsigned int j = 0; j < write_idx; j++)
__symbols__insert(root, old_symbols[j]);
+ root->sorted_cnt = 0;
root->sorted = false;
}
zfree(&root->symbols_by_name);
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index 8b8ab7e1e148..541ab9321d99 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -113,6 +113,12 @@ struct symbols {
struct symbol **symbols_by_name __guarded_by(&lock);
/** @cnt: Number of valid entries in @symbols. */
unsigned int cnt __guarded_by(&lock);
+ /**
+ * @sorted_cnt: Number of leading entries in @symbols that form the
+ * primary sorted prefix. When @sorted is true and @sorted_cnt < @cnt,
+ * the remaining tail @symbols[@sorted_cnt .. @cnt - 1] is also sorted.
+ */
+ unsigned int sorted_cnt __guarded_by(&lock);
/** @allocated: Capacity (in entries) of the @symbols allocation. */
unsigned int allocated __guarded_by(&lock);
/** @num_by_name: Number of valid entries in @symbols_by_name. */
@@ -122,7 +128,10 @@ struct symbols {
* by name.
*/
bool sorted_by_name __guarded_by(&lock);
- /** @sorted: True when @symbols is sorted by address range. */
+ /**
+ * @sorted: True when @symbols[0 .. @sorted_cnt - 1] and any tail
+ * @symbols[@sorted_cnt .. @cnt - 1] are sorted by start address.
+ */
bool sorted __guarded_by(&lock);
};

--
2.56.1.750.gf70dc682cf-goog