From: Ian Rogers <irogers@google.com>
To: Namhyung Kim <namhyung@kernel.org>,
Arnaldo Carvalho de Melo <acme@kernel.org>,
Alireza Haghdoost <haghdoost@uber.com>,
Ian Rogers <irogers@google.com>
Cc: Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>, Jiri Olsa <jolsa@kernel.org>,
Adrian Hunter <adrian.hunter@intel.com>,
James Clark <james.clark@linaro.org>,
linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail
Date: Fri, 20 Nov 2026 23:16:48 -0800 [thread overview]
Message-ID: <20261121071651.67118-8-irogers@google.com> (raw)
In-Reply-To: <20261121071651.67118-1-irogers@google.com>
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@google.com>
---
tools/perf/util/symbol.c | 192 ++++++++++++++++++++++++++++++++++++---
tools/perf/util/symbol.h | 11 ++-
2 files changed, 189 insertions(+), 14 deletions(-)
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 114fe5ea3891..0eaeced63cd4 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -219,6 +219,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;
@@ -233,6 +234,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;
@@ -432,12 +434,47 @@ static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n,
static void symbols__sort_locked(struct symbols *symbols)
{
- if (symbols->sorted)
+ unsigned int m = symbols->sorted_cnt;
+ unsigned int k;
+
+ if (symbols->sorted && symbols->sorted_cnt == symbols->cnt)
+ return;
+
+ if (m > symbols->cnt)
+ m = 0;
+ k = symbols->cnt - m;
+
+ if (k == 0) {
+ symbols->sorted = true;
return;
+ }
- if (symbols->cnt <= 64) {
+ /*
+ * 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, symbols->cnt);
- } else {
+ 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, symbols->cnt);
+ }
+ } else if (m <= 1) {
struct symbol **tmp = malloc(((symbols->cnt + 1) / 2) * sizeof(struct symbol *));
if (tmp) {
@@ -446,19 +483,31 @@ static void symbols__sort_locked(struct symbols *symbols)
} else {
symbols__insertion_sort_range(symbols->symbols, 0, 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, 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)
NO_THREAD_SAFETY_ANALYSIS
{
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);
@@ -507,6 +556,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;
@@ -682,9 +732,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);
@@ -693,6 +749,69 @@ static int __symbols__insert(struct symbols *symbols, struct symbol *sym)
return 0;
}
+static int __symbols__insert_sorted(struct symbols *symbols, struct symbol *sym)
+{
+ 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;
@@ -711,7 +830,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;
@@ -724,8 +845,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
@@ -734,6 +857,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++) {
@@ -750,12 +875,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;
@@ -900,7 +1051,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)
@@ -908,11 +1065,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;
@@ -1259,6 +1420,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);
@@ -1333,6 +1495,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);
@@ -1479,6 +1642,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;
@@ -1508,12 +1672,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 9d7de66cc284..dfdcf026a8c1 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -113,11 +113,20 @@ struct symbols {
struct symbol **symbols_by_name;
/** @cnt: Number of valid entries in @symbols. */
unsigned int cnt;
+ /**
+ * @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;
/** @allocated: Capacity (in entries) of the @symbols allocation. */
unsigned int allocated;
/** @num_by_name: Number of valid entries in @symbols_by_name. */
unsigned int num_by_name;
- /** @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;
/**
* @sorted_by_name: True when @symbols_by_name is populated and sorted
--
2.56.1.750.gf70dc682cf-goog
next prev parent reply other threads:[~2026-11-21 7:17 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
2026-11-21 7:16 ` [PATCH v7 01/10] perf kmem: Fix alloc_func_regex leak on error in build_alloc_func_list() Ian Rogers
2026-11-21 7:16 ` [PATCH v7 02/10] perf maps: Add tail fast-path check in first_ending_after() Ian Rogers
2026-11-21 7:16 ` [PATCH v7 03/10] perf symbol: Convert map__for_each_symbol() to callback-based iteration Ian Rogers
2026-11-21 7:16 ` [PATCH v7 04/10] perf symbol: Use callback iteration instead of open-coded symbol loops Ian Rogers
2026-11-21 7:16 ` [PATCH v7 05/10] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
2026-11-21 7:16 ` [PATCH v7 06/10] perf symbol: Replace qsort() with natural-run merge sort Ian Rogers
2026-11-21 7:16 ` Ian Rogers [this message]
2026-11-21 7:26 ` [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail sashiko-bot
2026-11-21 7:16 ` [PATCH v7 08/10] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-21 7:16 ` [PATCH v7 09/10] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-21 7:16 ` [PATCH v7 10/10] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
2026-11-21 7:35 ` [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking sashiko-bot
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261121071651.67118-8-irogers@google.com \
--to=irogers@google.com \
--cc=acme@kernel.org \
--cc=adrian.hunter@intel.com \
--cc=haghdoost@uber.com \
--cc=james.clark@linaro.org \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=namhyung@kernel.org \
--cc=peterz@infradead.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox