From: Davidlohr Bueso <dave@stgolabs.net>
To: acme@kernel.org
Cc: mingo@kernel.org, linux-kernel@vger.kernel.org, dave@stgolabs.net
Subject: [PATCH v2 -tip 0/7] tools/perf: Update rbtree implementation and optimize users
Date: Thu, 6 Dec 2018 11:18:12 -0800 [thread overview]
Message-ID: <20181206191819.30182-1-dave@stgolabs.net> (raw)
Hi,
Per acme's request, this is a rebase (and basically rewrite) of v1.
The following optimizes the rb_first() lookups in perf tooling such that we
can avoid walking down the tree finding the first element. Tree traversals
(and overall computing the first node in the tree) is a surprisingly common
operation. On a Xeon E5-2450 @ 2.10GHz, the cost of an rb_first() was ~60 cycles
for 100 nodes, and ~75 cycles with 1000 nodes.
The first patch adds the updated implementation of rbtrees, including the
cached interfaces, taken from the kernel. The rest of the patches make use
of this for the users I thought might care the most.
With these patches I am able to build and use perf without anything going wrong
(but needs more testing no doubt, as changes while redundant can be a little tricky
depending on if the user get smart about the trees). I'm sorry if some patches
seem too big, I've tried to split them the best I could.
Applies on today's -tip tree. Please consider for v4.21.
Thanks!
Davidlohr Bueso (7):
tools/perf: Update rbtree implementation
perf machine: Use cached rbtrees
perf callchain: Use cached rbtrees
perf util: Use cached rbtree for rblists
perf symbols: Use cached rbtrees
perf hist: Use cached rbtrees
perf sched: Use cached rbtrees
tools/include/linux/rbtree.h | 52 ++++++++-
tools/include/linux/rbtree_augmented.h | 60 ++++++++--
tools/lib/rbtree.c | 178 ++++++++++++++++++++++-------
tools/perf/builtin-annotate.c | 4 +-
tools/perf/builtin-c2c.c | 6 +-
tools/perf/builtin-diff.c | 10 +-
tools/perf/builtin-report.c | 3 +-
tools/perf/builtin-sched.c | 45 ++++----
tools/perf/builtin-top.c | 2 +-
tools/perf/tests/hists_common.c | 8 +-
tools/perf/tests/hists_cumulate.c | 14 +--
tools/perf/tests/hists_link.c | 8 +-
tools/perf/tests/hists_output.c | 32 +++---
tools/perf/ui/browsers/hists.c | 6 +-
tools/perf/ui/gtk/hists.c | 4 +-
tools/perf/ui/stdio/hist.c | 3 +-
tools/perf/util/build-id.c | 12 +-
tools/perf/util/dso.c | 8 +-
tools/perf/util/dso.h | 10 +-
tools/perf/util/hist.c | 199 +++++++++++++++++++--------------
tools/perf/util/hist.h | 10 +-
tools/perf/util/intlist.h | 2 +-
tools/perf/util/machine.c | 53 +++++----
tools/perf/util/machine.h | 12 +-
tools/perf/util/map.c | 8 +-
tools/perf/util/metricgroup.c | 2 +-
tools/perf/util/probe-event.c | 3 +-
tools/perf/util/rb_resort.h | 8 +-
tools/perf/util/rblist.c | 28 +++--
tools/perf/util/rblist.h | 2 +-
tools/perf/util/sort.h | 4 +-
tools/perf/util/srcline.c | 43 ++++---
tools/perf/util/srcline.h | 13 ++-
tools/perf/util/stat-shadow.c | 2 +-
tools/perf/util/strlist.h | 2 +-
tools/perf/util/symbol.c | 87 +++++++-------
tools/perf/util/symbol.h | 13 ++-
tools/perf/util/symbol_fprintf.c | 2 +-
38 files changed, 598 insertions(+), 360 deletions(-)
--
2.16.4
next reply other threads:[~2018-12-06 19:18 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-12-06 19:18 Davidlohr Bueso [this message]
2018-12-06 19:18 ` [PATCH 1/7] tools/perf: Update rbtree implementation Davidlohr Bueso
2019-01-26 10:01 ` [tip:perf/core] tools: " tip-bot for Davidlohr Bueso
2018-12-06 19:18 ` [PATCH 2/7] perf machine: Use cached rbtrees Davidlohr Bueso
2019-01-26 10:01 ` [tip:perf/core] " tip-bot for Davidlohr Bueso
2018-12-06 19:18 ` [PATCH 3/7] perf callchain: " Davidlohr Bueso
2019-01-26 10:02 ` [tip:perf/core] " tip-bot for Davidlohr Bueso
2018-12-06 19:18 ` [PATCH 4/7] perf util: Use cached rbtree for rblists Davidlohr Bueso
2019-01-26 10:03 ` [tip:perf/core] " tip-bot for Davidlohr Bueso
2018-12-06 19:18 ` [PATCH 5/7] perf symbols: Use cached rbtrees Davidlohr Bueso
2019-01-26 10:03 ` [tip:perf/core] " tip-bot for Davidlohr Bueso
2018-12-06 19:18 ` [PATCH 6/7] perf hist: " Davidlohr Bueso
2019-01-22 13:59 ` Arnaldo Carvalho de Melo
2019-01-22 15:22 ` Davidlohr Bueso
2019-01-26 10:04 ` [tip:perf/core] " tip-bot for Davidlohr Bueso
2018-12-06 19:18 ` [PATCH 7/7] perf sched: " Davidlohr Bueso
2019-01-26 10:05 ` [tip:perf/core] " tip-bot for Davidlohr Bueso
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=20181206191819.30182-1-dave@stgolabs.net \
--to=dave@stgolabs.net \
--cc=acme@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
/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;
as well as URLs for NNTP newsgroup(s).