Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Davidlohr Bueso <dave@stgolabs.net>
To:     acme@kernel.org
Cc:     jolsa@redhat.com, ak@linux.intel.com, mingo@redhat.com,
        dave@stgolabs.net, linux-kernel@vger.kernel.org
Subject: [PATCH -tip 0/7] tools/perf: Update rbtree implementation and optimize users
Date:   Sun, 26 Nov 2017 18:30:39 -0800
Message-Id: <20171127023046.19139-1-dave@stgolabs.net>
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Hi,

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.

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.16.

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           |  50 ++++++++-
 tools/include/linux/rbtree_augmented.h |  60 ++++++++--
 tools/lib/rbtree.c                     | 171 ++++++++++++++++++++--------
 tools/perf/builtin-annotate.c          |   4 +-
 tools/perf/builtin-c2c.c               |   6 +-
 tools/perf/builtin-diff.c              |  10 +-
 tools/perf/builtin-report.c            |   2 +-
 tools/perf/builtin-sched.c             |  45 ++++----
 tools/perf/builtin-top.c               |   6 +-
 tools/perf/tests/hists_common.c        |   8 +-
 tools/perf/tests/hists_cumulate.c      |  19 ++--
 tools/perf/tests/hists_link.c          |   8 +-
 tools/perf/tests/hists_output.c        |  32 +++---
 tools/perf/tests/vmlinux-kallsyms.c    |   3 +-
 tools/perf/ui/browsers/hists.c         |  16 +--
 tools/perf/ui/gtk/hists.c              |   6 +-
 tools/perf/ui/stdio/hist.c             |   3 +-
 tools/perf/util/build-id.c             |  12 +-
 tools/perf/util/dso.c                  |   7 +-
 tools/perf/util/dso.h                  |   6 +-
 tools/perf/util/hist.c                 | 198 ++++++++++++++++++---------------
 tools/perf/util/hist.h                 |  10 +-
 tools/perf/util/intlist.h              |   2 +-
 tools/perf/util/machine.c              |  52 +++++----
 tools/perf/util/machine.h              |   4 +-
 tools/perf/util/map.c                  |   8 +-
 tools/perf/util/metricgroup.c          |   2 +-
 tools/perf/util/probe-event.c          |   3 +-
 tools/perf/util/rblist.c               |  30 +++--
 tools/perf/util/rblist.h               |   2 +-
 tools/perf/util/sort.h                 |   4 +-
 tools/perf/util/srcline.c              |  21 ++--
 tools/perf/util/srcline.h              |   6 +-
 tools/perf/util/stat-shadow.c          |   2 +-
 tools/perf/util/strlist.h              |   2 +-
 tools/perf/util/symbol.c               |  85 +++++++-------
 tools/perf/util/symbol.h               |  12 +-
 tools/perf/util/symbol_fprintf.c       |   3 +-
 38 files changed, 570 insertions(+), 350 deletions(-)

-- 
2.13.6


From 1585507772352648893@xxx Thu Nov 30 16:07:20 +0000 2017
X-GM-THRID: 1585491498407736730
X-Gmail-Labels: Inbox,Category Forums,HistoricalUnread