From: Ian Rogers <irogers@google.com>
To: Andi Kleen <ak@linux.intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>,
Arnaldo Carvalho de Melo <acme@kernel.org>,
Mark Rutland <mark.rutland@arm.com>,
Alexander Shishkin <alexander.shishkin@linux.intel.com>,
Jiri Olsa <jolsa@redhat.com>, Namhyung Kim <namhyung@kernel.org>,
Alexei Starovoitov <ast@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Martin KaFai Lau <kafai@fb.com>, Song Liu <songliubraving@fb.com>,
Yonghong Song <yhs@fb.com>, Andrii Nakryiko <andriin@fb.com>,
John Fastabend <john.fastabend@gmail.com>,
KP Singh <kpsingh@chromium.org>, Kajol Jain <kjain@linux.ibm.com>,
John Garry <john.garry@huawei.com>,
Jin Yao <yao.jin@linux.intel.com>,
Kan Liang <kan.liang@linux.intel.com>,
Cong Wang <xiyou.wangcong@gmail.com>,
Kim Phillips <kim.phillips@amd.com>,
LKML <linux-kernel@vger.kernel.org>,
Networking <netdev@vger.kernel.org>, bpf <bpf@vger.kernel.org>,
linux-perf-users <linux-perf-users@vger.kernel.org>,
Vince Weaver <vincent.weaver@maine.edu>,
Stephane Eranian <eranian@google.com>
Subject: Re: [RFC PATCH v3 12/14] perf metricgroup: order event groups by size
Date: Fri, 8 May 2020 17:40:00 -0700 [thread overview]
Message-ID: <CAP-5=fWYO2e9yVPuXGVKZ7TBP4PP6MjyEFiSd+20DOxYSLC--w@mail.gmail.com> (raw)
In-Reply-To: <20200509002518.GF3538@tassilo.jf.intel.com>
On Fri, May 8, 2020 at 5:25 PM Andi Kleen <ak@linux.intel.com> wrote:
>
> On Thu, May 07, 2020 at 10:36:27PM -0700, Ian Rogers wrote:
> > When adding event groups to the group list, insert them in size order.
> > This performs an insertion sort on the group list. By placing the
> > largest groups at the front of the group list it is possible to see if a
> > larger group contains the same events as a later group. This can make
> > the later group redundant - it can reuse the events from the large group.
> > A later patch will add this sharing.
>
> I'm not sure if size is that great an heuristic. The dedup algorithm should
> work in any case even if you don't order by size, right?
Consider two metrics:
- metric 1 with events {A,B}
- metric 2 with events {A,B,C,D}
If the list isn't sorted then as the matching takes the first group
with all the events, metric 1 will match {A,B} and metric 2 {A,B,C,D}.
If the order is sorted to {A,B,C,D},{A,B} then metric 1 matches within
the {A,B,C,D} group as does metric 2. The events in metric 1 aren't
used and are removed.
The dedup algorithm is very naive :-)
> I suppose in theory some kind of topological sort would be better.
We could build something more complex, such as a directed acyclic
graph where metrics with a subset of events are children of parent
metrics. Children could have >1 parent for example
{A,B,C,D},{A,B,E},{A,B} where {A,B} is a subset of both {A,B,C,D} and
{A,B,E} and so a child of both. Presumably in that case it'd be better
to match {A,B} with {A,B,E} to reduce multiplexing. As we're merging
smaller groups into bigger, the sorting of the list is a quick and
dirty approximation of this.
Thanks,
Ian
> -Andi
> >
> > Signed-off-by: Ian Rogers <irogers@google.com>
> > ---
> > tools/perf/util/metricgroup.c | 16 +++++++++++++++-
> > 1 file changed, 15 insertions(+), 1 deletion(-)
> >
> > diff --git a/tools/perf/util/metricgroup.c b/tools/perf/util/metricgroup.c
> > index 2a6456fa178b..69fbff47089f 100644
> > --- a/tools/perf/util/metricgroup.c
> > +++ b/tools/perf/util/metricgroup.c
> > @@ -520,7 +520,21 @@ static int __metricgroup__add_metric(struct list_head *group_list,
> > return -EINVAL;
> > }
> >
> > - list_add_tail(&eg->nd, group_list);
> > + if (list_empty(group_list))
> > + list_add(&eg->nd, group_list);
> > + else {
> > + struct list_head *pos;
> > +
> > + /* Place the largest groups at the front. */
> > + list_for_each_prev(pos, group_list) {
> > + struct egroup *old = list_entry(pos, struct egroup, nd);
> > +
> > + if (hashmap__size(&eg->pctx.ids) <=
> > + hashmap__size(&old->pctx.ids))
> > + break;
> > + }
> > + list_add(&eg->nd, pos);
> > + }
> >
> > return 0;
> > }
> > --
> > 2.26.2.645.ge9eca65c58-goog
> >
next prev parent reply other threads:[~2020-05-09 0:40 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-05-08 5:36 [RFC PATCH v3 00/14] Share events between metrics Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 01/14] perf parse-events: expand add PMU error/verbose messages Ian Rogers
2020-05-09 0:14 ` Andi Kleen
2020-05-08 5:36 ` [RFC PATCH v3 02/14] perf test: improve pmu event metric testing Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 03/14] lib/bpf hashmap: increase portability Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 04/14] libbpf: Fix memory leak and possible double-free in hashmap__clear Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 05/14] perf expr: fix memory leaks in bison Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 06/14] perf evsel: fix 2 memory leaks Ian Rogers
2020-05-09 0:39 ` Andi Kleen
2020-05-09 0:41 ` Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 07/14] perf expr: migrate expr ids table to libbpf's hashmap Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 08/14] perf metricgroup: change evlist_used to a bitmap Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 09/14] perf metricgroup: free metric_events on error Ian Rogers
2020-05-21 17:07 ` Arnaldo Carvalho de Melo
2020-05-08 5:36 ` [RFC PATCH v3 10/14] perf metricgroup: always place duration_time last Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 11/14] perf metricgroup: delay events string creation Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 12/14] perf metricgroup: order event groups by size Ian Rogers
2020-05-09 0:25 ` Andi Kleen
2020-05-09 0:40 ` Ian Rogers [this message]
2020-05-09 2:40 ` Andi Kleen
2020-05-20 7:46 ` Ian Rogers
2020-05-08 5:36 ` [RFC PATCH v3 13/14] perf metricgroup: remove duped metric group events Ian Rogers
2020-05-09 0:38 ` Andi Kleen
2020-05-08 5:36 ` [RFC PATCH v3 14/14] perf metricgroup: add options to not group or merge Ian Rogers
2020-05-09 0:12 ` [RFC PATCH v3 00/14] Share events between metrics Andi Kleen
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='CAP-5=fWYO2e9yVPuXGVKZ7TBP4PP6MjyEFiSd+20DOxYSLC--w@mail.gmail.com' \
--to=irogers@google.com \
--cc=acme@kernel.org \
--cc=ak@linux.intel.com \
--cc=alexander.shishkin@linux.intel.com \
--cc=andriin@fb.com \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eranian@google.com \
--cc=john.fastabend@gmail.com \
--cc=john.garry@huawei.com \
--cc=jolsa@redhat.com \
--cc=kafai@fb.com \
--cc=kan.liang@linux.intel.com \
--cc=kim.phillips@amd.com \
--cc=kjain@linux.ibm.com \
--cc=kpsingh@chromium.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=mark.rutland@arm.com \
--cc=mingo@redhat.com \
--cc=namhyung@kernel.org \
--cc=netdev@vger.kernel.org \
--cc=peterz@infradead.org \
--cc=songliubraving@fb.com \
--cc=vincent.weaver@maine.edu \
--cc=xiyou.wangcong@gmail.com \
--cc=yao.jin@linux.intel.com \
--cc=yhs@fb.com \
/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).