Linux Perf Users
 help / color / mirror / Atom feed
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

  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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox