From: sashiko-bot@kernel.org
To: "Ian Rogers" <irogers@google.com>
Cc: linux-perf-users@vger.kernel.org
Subject: Re: [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail
Date: Sat, 21 Nov 2026 07:26:28 +0000 [thread overview]
Message-ID: <sashiko-outbox-226773@kernel.org> (raw)
In-Reply-To: <20261121071651.67118-8-irogers@google.com>
Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [Low] perf symbol: redundant prefix scan in symbols__sort_locked()
fast path
--
commit 1abf9914a30c24a8a1249efd5024c7868a9413c0
Author: Ian Rogers <irogers@google.com>
perf symbol: Optimize incremental symbol insertion with sorted tail
This commit optimizes incremental symbol insertion and small-append sorting
by tracking a sorted prefix length in struct symbols, adding an in-place
binary insertion fast path for small appends, and maintaining a sorted tail
buffer for out-of-order dynamic symbol insertions.
> diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
> index 114fe5ea38915..0eaeced63cd47 100644
> --- a/tools/perf/util/symbol.c
> +++ b/tools/perf/util/symbol.c
[ ... ]
> @@ -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;
> + }
[Severity: Low]
Does passing start = 0 to symbols__insertion_sort_range() in the k <= 8 fast
path scan the entire already-sorted prefix [0 .. m)?
tools/perf/util/symbol.c:symbols__insertion_sort_range() {
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);
...
}
When symbols__sort_locked() is called after 1 to 8 out-of-order symbols are
appended to a large sorted table, the loop walks i from 1 through m - 1 and
dereferences every pair of adjacent struct symbol pointers in the prefix
before reaching the k new entries at index m. Starting the insertion loop at
max(m, 1U) while keeping the binary search base at index 0 would avoid
scanning the sorted prefix.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261121071651.67118-1-irogers@google.com?part=7
next prev parent reply other threads:[~2026-11-21 7:26 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 ` [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail Ian Rogers
2026-11-21 7:26 ` sashiko-bot [this message]
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=sashiko-outbox-226773@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 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.