All of lore.kernel.org
 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 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


  reply	other threads:[~2026-11-17 19:03 UTC|newest]

Thread overview: 22+ 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-18  6:12   ` Namhyung Kim
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-18  6:28   ` Namhyung Kim
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-18  6:34   ` Namhyung Kim
2026-11-17 18:53 ` [PATCH v6 7/9] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-17 19:25   ` sashiko-bot
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 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.