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 06/10] perf symbol: Replace qsort() with natural-run merge sort
Date: Fri, 20 Nov 2026 23:16:47 -0800 [thread overview]
Message-ID: <20261121071651.67118-7-irogers@google.com> (raw)
In-Reply-To: <20261121071651.67118-1-irogers@google.com>
ELF .symtab and .dynsym sections are typically already mostly ordered by
address in ascending runs. Invoking full-array qsort() across pre-ordered
ELF runs spends avoidable CPU time in symbol comparisons and does not
guarantee relative order preservation for equal-start symbol aliases
across C library implementations.
Replace qsort() in symbols__sort_locked() with a stable natural-run merge
sort (symbols__sort_range_with_tmp() and symbols__merge_runs()), falling
back to in-place binary insertion sort (symbols__insertion_sort_range())
for small arrays (cnt <= 64) or on scratch-buffer allocation failure.
Using 'perf bench internals symbols':
Before:
Average DSO load + sort: 6.242 msec (+- 0.057 msec)
Average bulk insert + lookup: 1404.150 usec (+- 18.752 usec)
After (-7.0% load, -13.9% bulk):
Average DSO load + sort: 5.808 msec (+- 0.047 msec)
Average bulk insert + lookup: 1209.250 usec (+- 18.446 usec)
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/util/symbol.c | 183 +++++++++++++++++++++++++++++++++++++--
1 file changed, 174 insertions(+), 9 deletions(-)
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 4119e061e939..114fe5ea3891 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -263,14 +263,171 @@ static inline bool symbol__less_or_equal(const struct symbol *a, const struct sy
return a->start <= b->start;
}
-static int symbols__sort_cmp(const void *vlhs, const void *vrhs)
+static unsigned int symbols__upper_bound(struct symbol **arr, unsigned int len,
+ const struct symbol *sym)
{
- const struct symbol *lhs = *((const struct symbol **)vlhs);
- const struct symbol *rhs = *((const struct symbol **)vrhs);
+ unsigned int low = 0, high = len;
- if (lhs->start != rhs->start)
- return lhs->start < rhs->start ? -1 : 1;
- return 0;
+ while (low < high) {
+ unsigned int mid = low + (high - low) / 2;
+
+ if (symbol__less_or_equal(arr[mid], sym))
+ low = mid + 1;
+ else
+ high = mid;
+ }
+ return low;
+}
+
+static void symbols__insertion_sort_range(struct symbol **arr,
+ unsigned int start,
+ unsigned int end)
+{
+ for (unsigned int i = start + 1; i < end; i++) {
+ struct symbol *sym = arr[i];
+
+ if (!symbol__less_or_equal(arr[i - 1], sym)) {
+ unsigned int pos = start +
+ symbols__upper_bound(&arr[start], i - start, sym);
+
+ memmove(&arr[pos + 1], &arr[pos],
+ (i - pos) * sizeof(struct symbol *));
+ arr[pos] = sym;
+ }
+ }
+}
+
+static void symbols__merge_runs(struct symbol **arr,
+ unsigned int left,
+ unsigned int mid,
+ unsigned int right,
+ struct symbol **tmp)
+{
+ unsigned int first_left, left_len, right_len;
+ unsigned int i, j, dst;
+
+ if (left >= mid || mid >= right)
+ return;
+ if (symbol__less_or_equal(arr[mid - 1], arr[mid]))
+ return;
+
+ first_left = left + symbols__upper_bound(&arr[left], mid - left, arr[mid]);
+ left_len = mid - first_left;
+ right_len = right - mid;
+
+ if (left_len <= right_len) {
+ memcpy(tmp, &arr[first_left], left_len * sizeof(struct symbol *));
+ i = 0;
+ j = mid;
+ dst = first_left;
+ while (i < left_len && j < right) {
+ if (symbol__less_or_equal(tmp[i], arr[j]))
+ arr[dst++] = tmp[i++];
+ else
+ arr[dst++] = arr[j++];
+ }
+ if (i < left_len)
+ memcpy(&arr[dst], &tmp[i], (left_len - i) * sizeof(struct symbol *));
+ } else {
+ memcpy(tmp, &arr[mid], right_len * sizeof(struct symbol *));
+ i = mid;
+ j = right_len;
+ dst = right;
+ while (i > first_left && j > 0) {
+ if (symbol__less_or_equal(arr[i - 1], tmp[j - 1]))
+ arr[--dst] = tmp[--j];
+ else
+ arr[--dst] = arr[--i];
+ }
+ if (j > 0)
+ memcpy(&arr[first_left], tmp, j * sizeof(struct symbol *));
+ }
+}
+
+struct symbol_run {
+ unsigned int start;
+ unsigned int len;
+};
+
+static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n,
+ struct symbol **tmp)
+{
+ struct symbol_run runs[64];
+ unsigned int nr_runs = 0;
+ unsigned int i = 0;
+
+ if (n <= 32) {
+ symbols__insertion_sort_range(arr, 0, n);
+ return;
+ }
+
+ while (i < n) {
+ unsigned int start = i++;
+
+ if (i < n) {
+ if (symbol__less_or_equal(arr[i - 1], arr[i])) {
+ while (i < n && symbol__less_or_equal(arr[i - 1], arr[i]))
+ i++;
+ } else {
+ while (i < n && !symbol__less_or_equal(arr[i - 1], arr[i]))
+ i++;
+ for (unsigned int lo = start, hi = i - 1; lo < hi; lo++, hi--) {
+ struct symbol *swap = arr[lo];
+
+ arr[lo] = arr[hi];
+ arr[hi] = swap;
+ }
+ }
+ }
+
+ if (i - start < 32 && i < n) {
+ i = min(start + 32U, n);
+ symbols__insertion_sort_range(arr, start, i);
+ }
+
+ runs[nr_runs++] = (struct symbol_run){
+ .start = start,
+ .len = i - start,
+ };
+
+ while (nr_runs > 1) {
+ unsigned int r = nr_runs - 2;
+
+ if (nr_runs >= 3 &&
+ runs[nr_runs - 3].len <=
+ runs[nr_runs - 2].len + runs[nr_runs - 1].len) {
+ if (runs[nr_runs - 3].len < runs[nr_runs - 1].len)
+ r = nr_runs - 3;
+ } else if (runs[nr_runs - 2].len > runs[nr_runs - 1].len &&
+ nr_runs < ARRAY_SIZE(runs)) {
+ break;
+ }
+
+ symbols__merge_runs(arr, runs[r].start,
+ runs[r + 1].start,
+ runs[r + 1].start + runs[r + 1].len,
+ tmp);
+ runs[r].len += runs[r + 1].len;
+ if (r + 2 < nr_runs)
+ runs[r + 1] = runs[r + 2];
+ nr_runs--;
+ }
+ }
+
+ while (nr_runs > 1) {
+ unsigned int r = nr_runs - 2;
+
+ if (nr_runs >= 3 && runs[nr_runs - 3].len < runs[nr_runs - 1].len)
+ r = nr_runs - 3;
+ symbols__merge_runs(arr, runs[r].start,
+ runs[r + 1].start,
+ runs[r + 1].start + runs[r + 1].len,
+ tmp);
+ runs[r].len += runs[r + 1].len;
+ if (r + 2 < nr_runs)
+ runs[r + 1] = runs[r + 2];
+ nr_runs--;
+ }
}
static void symbols__sort_locked(struct symbols *symbols)
@@ -278,9 +435,17 @@ static void symbols__sort_locked(struct symbols *symbols)
if (symbols->sorted)
return;
- if (symbols->cnt > 1) {
- qsort(symbols->symbols, symbols->cnt, sizeof(struct symbol *),
- symbols__sort_cmp);
+ if (symbols->cnt <= 64) {
+ symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
+ } else {
+ 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->sorted = true;
}
--
2.56.1.750.gf70dc682cf-goog
next prev parent reply other threads:[~2026-11-21 7:17 UTC|newest]
Thread overview: 11+ 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 ` Ian Rogers [this message]
2026-11-21 7:16 ` [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail Ian Rogers
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
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-7-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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.