From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753014AbcIMAAC (ORCPT ); Mon, 12 Sep 2016 20:00:02 -0400 Received: from LGEAMRELO13.lge.com ([156.147.23.53]:35294 "EHLO lgeamrelo13.lge.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751222AbcIMAAA (ORCPT ); Mon, 12 Sep 2016 20:00:00 -0400 X-Original-SENDERIP: 156.147.1.126 X-Original-MAILFROM: namhyung@kernel.org X-Original-SENDERIP: 165.244.98.76 X-Original-MAILFROM: namhyung@kernel.org X-Original-SENDERIP: 10.177.227.17 X-Original-MAILFROM: namhyung@kernel.org Date: Tue, 13 Sep 2016 08:59:57 +0900 From: Namhyung Kim To: Arnaldo Carvalho de Melo CC: Ingo Molnar , Peter Zijlstra , Jiri Olsa , LKML , Andi Kleen Subject: Re: [PATCH 2/7] perf hist: Introduce hists__match_hierarchy() Message-ID: <20160912235957.GA3641@sejong> References: <20160912061958.16656-1-namhyung@kernel.org> <20160912061958.16656-3-namhyung@kernel.org> <20160912142530.GC4897@kernel.org> MIME-Version: 1.0 In-Reply-To: <20160912142530.GC4897@kernel.org> User-Agent: Mutt/1.7.0 (2016-08-17) X-MIMETrack: Itemize by SMTP Server on LGEKRMHUB06/LGE/LG Group(Release 8.5.3FP6|November 21, 2013) at 2016/09/13 08:59:57, Serialize by Router on LGEKRMHUB06/LGE/LG Group(Release 8.5.3FP6|November 21, 2013) at 2016/09/13 08:59:57, Serialize complete at 2016/09/13 08:59:57 Content-Type: text/plain; charset="utf-8" Content-Disposition: inline Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi Arnaldo, On Mon, Sep 12, 2016 at 11:25:30AM -0300, Arnaldo Carvalho de Melo wrote: > Em Mon, Sep 12, 2016 at 03:19:53PM +0900, Namhyung Kim escreveu: > > The hists__match_hierarchy() is to find matching hist entries in a > > group. It needs to search all matching children in the hierarchy. > > Can you please enrich this changeset log? Define "matching", an example > of how the output of a hierarchy + group would help people trying to > understand the changes you're making, for instance. Ok. How about this? The hists__match_hierarchy() is to find matching hist entries in a group. A matching entry has same values for all sort keys given. With event group, a leader event should show other members in a group. So each entry in the leader should be able to find its pair entries which have same values. With hierarchy mode, it needs to search all matching children in a hierarchy. An example output below: # Overhead Command / Shared Object / Symbol # ...................... .................................. # 25.74% 27.18% sh 19.96% 24.14% libc-2.24.so 9.55% 14.64% [.] __strcmp_sse2 1.54% 0.00% [.] __tfind 1.07% 1.13% [.] _int_malloc ... In the above example, two overhead were shown - one for leader and another for member. They were matched since their command, dso and symbol have same values. Thanks, Namhyung > > > Signed-off-by: Namhyung Kim > > --- > > tools/perf/util/hist.c | 51 ++++++++++++++++++++++++++++++++++++++++++++++++++ > > 1 file changed, 51 insertions(+) > > > > diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c > > index de15dbcdcecf..be3f5ce31303 100644 > > --- a/tools/perf/util/hist.c > > +++ b/tools/perf/util/hist.c > > @@ -2174,6 +2174,51 @@ static struct hist_entry *hists__find_entry(struct hists *hists, > > return NULL; > > } > > > > +static struct hist_entry *hists__find_hierarchy_entry(struct rb_root *root, > > + struct hist_entry *he) > > +{ > > + struct rb_node *n = root->rb_node; > > + > > + while (n) { > > + struct hist_entry *iter; > > + struct perf_hpp_fmt *fmt; > > + int64_t cmp = 0; > > + > > + iter = rb_entry(n, struct hist_entry, rb_node_in); > > + perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) { > > + cmp = fmt->collapse(fmt, iter, he); > > + if (cmp) > > + break; > > + } > > + > > + if (cmp < 0) > > + n = n->rb_left; > > + else if (cmp > 0) > > + n = n->rb_right; > > + else > > + return iter; > > + } > > + > > + return NULL; > > +} > > + > > +static void hists__match_hierarchy(struct rb_root *leader_root, > > + struct rb_root *other_root) > > +{ > > + struct rb_node *nd; > > + struct hist_entry *pos, *pair; > > + > > + for (nd = rb_first(leader_root); nd; nd = rb_next(nd)) { > > + pos = rb_entry(nd, struct hist_entry, rb_node_in); > > + pair = hists__find_hierarchy_entry(other_root, pos); > > + > > + if (pair) { > > + hist_entry__add_pair(pair, pos); > > + hists__match_hierarchy(&pos->hroot_in, &pair->hroot_in); > > + } > > + } > > +} > > + > > /* > > * Look for pairs to link to the leader buckets (hist_entries): > > */ > > @@ -2183,6 +2228,12 @@ void hists__match(struct hists *leader, struct hists *other) > > struct rb_node *nd; > > struct hist_entry *pos, *pair; > > > > + if (symbol_conf.report_hierarchy) { > > + /* hierarchy report always collapses entries */ > > + return hists__match_hierarchy(&leader->entries_collapsed, > > + &other->entries_collapsed); > > + } > > + > > if (hists__has(leader, need_collapse)) > > root = &leader->entries_collapsed; > > else > > -- > > 2.9.3