[PATCH v7 06/10] perf symbol: Replace qsort() with natural-run merge sort
From: Ian Rogers
Date: Sat Nov 21 2026 - 02:17:40 EST
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@xxxxxxxxxx>
---
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