From: sashiko-bot@kernel.org
To: "Ian Rogers" <irogers@google.com>
Cc: linux-perf-users@vger.kernel.org
Subject: Re: [PATCH v6 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion
Date: Tue, 17 Nov 2026 19:03:30 +0000 [thread overview]
Message-ID: <sashiko-outbox-219430@kernel.org> (raw)
In-Reply-To: <20261117185305.108003-7-irogers@google.com>
> ELF .symtab and .dynsym sections are typically already mostly ordered by
> address in ascending runs, and dynamic symbol resolution
> (dso__insert_symbol()) frequently inserts one or a few symbols into an
> already-sorted DSO symbol table. Invoking full-array qsort() on every
> sort after incremental insertions or across pre-ordered ELF runs spends
> avoidable CPU time in symbol comparisons.
>
> Speed up symbol array sorting and out-of-order symbol insertions:
>
> - Track the sorted prefix length (@sorted_cnt) in struct symbols and
> replace full-array qsort() with a natural-run merge sort
> (symbols__sort_range_with_tmp()) and galloping binary-search merge
> (symbols__merge_runs()), plus an O(N) in-place binary insertion fast
> path when <= 8 symbols are appended.
> - Insert directly into sorted position in dso__insert_symbol() when
> symbols->sorted is true so dynamic single-symbol insertions maintain
> the sorted invariant without triggering full re-sorts.
>
> 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)
> Average append + lookup: 40429.750 usec (+- 507.578 usec)
> After (-7.0% load, -13.9% bulk, -99.6% append):
> Average DSO load + sort: 5.808 msec (+- 0.047 msec)
> Average bulk insert + lookup: 1209.250 usec (+- 18.446 usec)
> Average append + lookup: 152.900 usec (+- 0.736 usec)
>
> Signed-off-by: Ian Rogers <irogers@google.com>
Sashiko has reviewed this patch and found no issues.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261117185305.108003-1-irogers@google.com?part=6
next prev parent reply other threads:[~2026-11-17 19:03 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-17 18:52 [PATCH v6 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
2026-11-17 18:52 ` [PATCH v6 1/9] perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes Ian Rogers
2026-11-17 19:03 ` sashiko-bot
2026-11-17 18:52 ` [PATCH v6 2/9] perf annotate: Move struct annotation to a hashmap and remove symbol_conf.priv_size Ian Rogers
2026-11-17 19:04 ` sashiko-bot
2026-11-17 18:52 ` [PATCH v6 3/9] perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup Ian Rogers
2026-11-17 19:00 ` sashiko-bot
2026-11-17 18:53 ` [PATCH v6 4/9] perf maps: Optimize tail insertion and small-append sorting Ian Rogers
2026-11-17 19:10 ` sashiko-bot
2026-11-17 18:53 ` [PATCH v6 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
2026-11-17 19:17 ` sashiko-bot
2026-11-17 18:53 ` [PATCH v6 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion Ian Rogers
2026-11-17 19:03 ` sashiko-bot [this message]
2026-11-17 18:53 ` [PATCH v6 7/9] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-17 18:53 ` [PATCH v6 8/9] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-17 19:15 ` sashiko-bot
2026-11-17 18:53 ` [PATCH v6 9/9] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
2026-11-17 19:14 ` 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=sashiko-outbox-219430@kernel.org \
--to=sashiko-bot@kernel.org \
--cc=irogers@google.com \
--cc=linux-perf-users@vger.kernel.org \
--cc=sashiko-reviews@lists.linux.dev \
/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