* [PATCH 0/3] perf hists: Changes on hists__{link,match}
@ 2012-12-04 4:44 Namhyung Kim
2012-12-04 4:44 ` [PATCH 1/3] perf hists: Exchange order of comparing items when collapsing hists Namhyung Kim
` (3 more replies)
0 siblings, 4 replies; 10+ messages in thread
From: Namhyung Kim @ 2012-12-04 4:44 UTC (permalink / raw)
To: Arnaldo Carvalho de Melo
Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Jiri Olsa,
Stephane Eranian, Namhyung Kim
Hi Arnaldo,
This is what I talked to Jiri yesterday, and it can be a common basis
of both event group and multiple diff patchset. The point is using
internal input or collapsed rb tree to sort hist entries rather than
output tree with unnessary resort.
Please take a look.
Thanks,
Namhyung
Cc: Jiri Olsa <jolsa@redhat.com>
Cc: Stephane Eranian <eranian@google.com>
Cc: Namhyung Kim <namhyung.kim@lge.com>
Namhyung Kim (3):
perf hists: Exchange order of comparing items when collapsing hists
perf hists: Link hist entries before inserting to an output tree
perf diff: Use internal rb tree for compute resort
tools/perf/builtin-diff.c | 95 +++++++++++++++++++++--------------------------
tools/perf/util/hist.c | 51 ++++++++++++++++++-------
2 files changed, 80 insertions(+), 66 deletions(-)
--
1.7.11.7
^ permalink raw reply [flat|nested] 10+ messages in thread* [PATCH 1/3] perf hists: Exchange order of comparing items when collapsing hists 2012-12-04 4:44 [PATCH 0/3] perf hists: Changes on hists__{link,match} Namhyung Kim @ 2012-12-04 4:44 ` Namhyung Kim 2012-12-04 13:44 ` Arnaldo Carvalho de Melo 2012-12-04 4:44 ` [PATCH 2/3] perf hists: Link hist entries before inserting to an output tree Namhyung Kim ` (2 subsequent siblings) 3 siblings, 1 reply; 10+ messages in thread From: Namhyung Kim @ 2012-12-04 4:44 UTC (permalink / raw) To: Arnaldo Carvalho de Melo Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Namhyung Kim, Jiri Olsa, Stephane Eranian From: Namhyung Kim <namhyung.kim@lge.com> When comparing entries for collapsing put the given entry first, and then the iterated entry. This is not the case of hist_entry__cmp() when called if given sort keys don't require collapsing. So change the order for the sake of consistency. It will be required for matching and/or linking multiple hist entries. Cc: Jiri Olsa <jolsa@redhat.com> Cc: Stephane Eranian <eranian@google.com> Signed-off-by: Namhyung Kim <namhyung@kernel.org> --- tools/perf/util/hist.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c index 82df1b26f0d4..161c35e7ed0e 100644 --- a/tools/perf/util/hist.c +++ b/tools/perf/util/hist.c @@ -433,7 +433,7 @@ static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused, parent = *p; iter = rb_entry(parent, struct hist_entry, rb_node_in); - cmp = hist_entry__collapse(iter, he); + cmp = hist_entry__collapse(he, iter); if (!cmp) { he_stat__add_stat(&iter->stat, &he->stat); -- 1.7.11.7 ^ permalink raw reply related [flat|nested] 10+ messages in thread
* Re: [PATCH 1/3] perf hists: Exchange order of comparing items when collapsing hists 2012-12-04 4:44 ` [PATCH 1/3] perf hists: Exchange order of comparing items when collapsing hists Namhyung Kim @ 2012-12-04 13:44 ` Arnaldo Carvalho de Melo 2012-12-04 14:57 ` Namhyung Kim 0 siblings, 1 reply; 10+ messages in thread From: Arnaldo Carvalho de Melo @ 2012-12-04 13:44 UTC (permalink / raw) To: Namhyung Kim Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Namhyung Kim, Jiri Olsa, Stephane Eranian Em Tue, Dec 04, 2012 at 01:44:23PM +0900, Namhyung Kim escreveu: > From: Namhyung Kim <namhyung.kim@lge.com> > > When comparing entries for collapsing put the given entry first, and > then the iterated entry. This is not the case of hist_entry__cmp() > when called if given sort keys don't require collapsing. So change > the order for the sake of consistency. It will be required for > matching and/or linking multiple hist entries. > > Cc: Jiri Olsa <jolsa@redhat.com> > Cc: Stephane Eranian <eranian@google.com> > Signed-off-by: Namhyung Kim <namhyung@kernel.org> > --- > tools/perf/util/hist.c | 2 +- > 1 file changed, 1 insertion(+), 1 deletion(-) > > diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c > index 82df1b26f0d4..161c35e7ed0e 100644 > --- a/tools/perf/util/hist.c > +++ b/tools/perf/util/hist.c > @@ -433,7 +433,7 @@ static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused, > parent = *p; > iter = rb_entry(parent, struct hist_entry, rb_node_in); > > - cmp = hist_entry__collapse(iter, he); > + cmp = hist_entry__collapse(he, iter); > > if (!cmp) { > he_stat__add_stat(&iter->stat, &he->stat); What about this he_stat__add_stat call? Now the hist_entry__collapse receives (he, iter) while this right next function call receives (iter, he). - Arnaldo > -- > 1.7.11.7 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 1/3] perf hists: Exchange order of comparing items when collapsing hists 2012-12-04 13:44 ` Arnaldo Carvalho de Melo @ 2012-12-04 14:57 ` Namhyung Kim 0 siblings, 0 replies; 10+ messages in thread From: Namhyung Kim @ 2012-12-04 14:57 UTC (permalink / raw) To: Arnaldo Carvalho de Melo Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Namhyung Kim, Jiri Olsa, Stephane Eranian On Tue, 4 Dec 2012 10:44:05 -0300, Arnaldo Carvalho de Melo wrote: > Em Tue, Dec 04, 2012 at 01:44:23PM +0900, Namhyung Kim escreveu: >> From: Namhyung Kim <namhyung.kim@lge.com> >> >> When comparing entries for collapsing put the given entry first, and >> then the iterated entry. This is not the case of hist_entry__cmp() >> when called if given sort keys don't require collapsing. So change >> the order for the sake of consistency. It will be required for >> matching and/or linking multiple hist entries. >> >> Cc: Jiri Olsa <jolsa@redhat.com> >> Cc: Stephane Eranian <eranian@google.com> >> Signed-off-by: Namhyung Kim <namhyung@kernel.org> >> --- >> tools/perf/util/hist.c | 2 +- >> 1 file changed, 1 insertion(+), 1 deletion(-) >> >> diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c >> index 82df1b26f0d4..161c35e7ed0e 100644 >> --- a/tools/perf/util/hist.c >> +++ b/tools/perf/util/hist.c >> @@ -433,7 +433,7 @@ static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused, >> parent = *p; >> iter = rb_entry(parent, struct hist_entry, rb_node_in); >> >> - cmp = hist_entry__collapse(iter, he); >> + cmp = hist_entry__collapse(he, iter); >> >> if (!cmp) { >> he_stat__add_stat(&iter->stat, &he->stat); > > What about this he_stat__add_stat call? Now the hist_entry__collapse > receives (he, iter) while this right next function call receives (iter, > he). Hmm.. I thought they're diffent kind of operation. hist_entry__collapse is in a process of iteration and he_stat__add_stat is not. It's just adding or copying entry's stat, so I thought it's something like memcpy - hence the order. If you really concern about ordering between them, maybe I can change hist_entry__cmp() to receive (iter, he). Thanks, Namhyung ^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 2/3] perf hists: Link hist entries before inserting to an output tree 2012-12-04 4:44 [PATCH 0/3] perf hists: Changes on hists__{link,match} Namhyung Kim 2012-12-04 4:44 ` [PATCH 1/3] perf hists: Exchange order of comparing items when collapsing hists Namhyung Kim @ 2012-12-04 4:44 ` Namhyung Kim 2012-12-04 4:44 ` [PATCH 3/3] perf diff: Use internal rb tree for compute resort Namhyung Kim 2012-12-04 13:54 ` [PATCH 0/3] perf hists: Changes on hists__{link,match} Jiri Olsa 3 siblings, 0 replies; 10+ messages in thread From: Namhyung Kim @ 2012-12-04 4:44 UTC (permalink / raw) To: Arnaldo Carvalho de Melo Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Namhyung Kim, Jiri Olsa, Stephane Eranian From: Namhyung Kim <namhyung.kim@lge.com> For matching and/or linking hist entries, they need to be sorted by given sort keys. However current hists__match/link did this on the output trees, so that the entries in the output tree need to be resort before doing it. This looks not so good since we have trees for collecting or collapsing entries before passing them to an output tree and they're already sorted by the given sort keys. Since we don't need to print anything at the time of matching/linking, we can use these internal trees directly instead of bothering with double resort on the output tree. Its only user - at the time of this writing - perf diff can be easily converted to use the internal tree and can save some lines too by getting rid of unnecessary resorting codes. It seems we need to do output resort on baseline hists for displacement prior to the match/link. But AFAIK it's okay since the resort doesn't make any change to the internal tree - i.e. every entries in the internal tree remain as is and just linked to both of internal and output tree using different keys. So linking entries in the internal tree after output resorting will not cause any harm IMHO. Cc: Jiri Olsa <jolsa@redhat.com> Cc: Stephane Eranian <eranian@google.com> Signed-off-by: Namhyung Kim <namhyung@kernel.org> --- tools/perf/builtin-diff.c | 73 ++++++++++++++++++----------------------------- tools/perf/util/hist.c | 49 +++++++++++++++++++++++-------- 2 files changed, 65 insertions(+), 57 deletions(-) diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c index d869029fb75e..b52f5d8c4a6b 100644 --- a/tools/perf/builtin-diff.c +++ b/tools/perf/builtin-diff.c @@ -276,46 +276,19 @@ static struct perf_tool tool = { .ordering_requires_timestamps = true, }; -static void insert_hist_entry_by_name(struct rb_root *root, - struct hist_entry *he) -{ - struct rb_node **p = &root->rb_node; - struct rb_node *parent = NULL; - struct hist_entry *iter; - - while (*p != NULL) { - parent = *p; - iter = rb_entry(parent, struct hist_entry, rb_node); - if (hist_entry__cmp(he, iter) < 0) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } - - rb_link_node(&he->rb_node, parent, p); - rb_insert_color(&he->rb_node, root); -} - -static void hists__name_resort(struct hists *self, bool sort) +static void hists__compute_position(struct hists *hists) { unsigned long position = 1; - struct rb_root tmp = RB_ROOT; - struct rb_node *next = rb_first(&self->entries); + struct rb_node *next = rb_first(&hists->entries); while (next != NULL) { - struct hist_entry *n = rb_entry(next, struct hist_entry, rb_node); + struct hist_entry *he; - next = rb_next(&n->rb_node); - n->position = position++; + he = rb_entry(next, struct hist_entry, rb_node); + he->position = position++; - if (sort) { - rb_erase(&n->rb_node, &self->entries); - insert_hist_entry_by_name(&tmp, n); - } + next = rb_next(next); } - - if (sort) - self->entries = tmp; } static struct perf_evsel *evsel_match(struct perf_evsel *evsel, @@ -330,34 +303,39 @@ static struct perf_evsel *evsel_match(struct perf_evsel *evsel, return NULL; } -static void perf_evlist__resort_hists(struct perf_evlist *evlist, bool name) +static void perf_evlist__resort_hists(struct perf_evlist *evlist, bool base) { struct perf_evsel *evsel; list_for_each_entry(evsel, &evlist->entries, node) { struct hists *hists = &evsel->hists; - hists__output_resort(hists); + hists__collapse_resort(hists); - /* - * The hists__name_resort only sets possition - * if name is false. - */ - if (name || ((!name) && show_displacement)) - hists__name_resort(hists, name); + if (base && show_displacement) { + hists__output_resort(hists); + hists__compute_position(hists); + } } } static void hists__baseline_only(struct hists *hists) { - struct rb_node *next = rb_first(&hists->entries); + struct rb_root *root; + struct rb_node *next; + + if (sort__need_collapse) + root = &hists->entries_collapsed; + else + root = hists->entries_in; + next = rb_first(root); while (next != NULL) { - struct hist_entry *he = rb_entry(next, struct hist_entry, rb_node); + struct hist_entry *he = rb_entry(next, struct hist_entry, rb_node_in); - next = rb_next(&he->rb_node); + next = rb_next(&he->rb_node_in); if (!hist_entry__next_pair(he)) { - rb_erase(&he->rb_node, &hists->entries); + rb_erase(&he->rb_node_in, root); hist_entry__free(he); } } @@ -481,6 +459,11 @@ static void hists__process(struct hists *old, struct hists *new) else hists__link(new, old); + hists__output_resort(new); + + if (show_displacement) + hists__compute_position(new); + if (sort_compute) { hists__precompute(new); hists__compute_resort(new); diff --git a/tools/perf/util/hist.c b/tools/perf/util/hist.c index 161c35e7ed0e..f9e7d004835c 100644 --- a/tools/perf/util/hist.c +++ b/tools/perf/util/hist.c @@ -720,16 +720,24 @@ void hists__inc_nr_events(struct hists *hists, u32 type) static struct hist_entry *hists__add_dummy_entry(struct hists *hists, struct hist_entry *pair) { - struct rb_node **p = &hists->entries.rb_node; + struct rb_root *root; + struct rb_node **p; struct rb_node *parent = NULL; struct hist_entry *he; int cmp; + if (sort__need_collapse) + root = &hists->entries_collapsed; + else + root = hists->entries_in; + + p = &root->rb_node; + while (*p != NULL) { parent = *p; - he = rb_entry(parent, struct hist_entry, rb_node); + he = rb_entry(parent, struct hist_entry, rb_node_in); - cmp = hist_entry__cmp(pair, he); + cmp = hist_entry__collapse(pair, he); if (!cmp) goto out; @@ -744,8 +752,8 @@ static struct hist_entry *hists__add_dummy_entry(struct hists *hists, if (he) { memset(&he->stat, 0, sizeof(he->stat)); he->hists = hists; - rb_link_node(&he->rb_node, parent, p); - rb_insert_color(&he->rb_node, &hists->entries); + rb_link_node(&he->rb_node_in, parent, p); + rb_insert_color(&he->rb_node_in, root); hists__inc_nr_entries(hists, he); } out: @@ -755,11 +763,16 @@ out: static struct hist_entry *hists__find_entry(struct hists *hists, struct hist_entry *he) { - struct rb_node *n = hists->entries.rb_node; + struct rb_node *n; + + if (sort__need_collapse) + n = hists->entries_collapsed.rb_node; + else + n = hists->entries_in->rb_node; while (n) { - struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node); - int64_t cmp = hist_entry__cmp(he, iter); + struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in); + int64_t cmp = hist_entry__collapse(he, iter); if (cmp < 0) n = n->rb_left; @@ -777,11 +790,17 @@ static struct hist_entry *hists__find_entry(struct hists *hists, */ void hists__match(struct hists *leader, struct hists *other) { + struct rb_root *root; struct rb_node *nd; struct hist_entry *pos, *pair; - for (nd = rb_first(&leader->entries); nd; nd = rb_next(nd)) { - pos = rb_entry(nd, struct hist_entry, rb_node); + if (sort__need_collapse) + root = &leader->entries_collapsed; + else + root = leader->entries_in; + + for (nd = rb_first(root); nd; nd = rb_next(nd)) { + pos = rb_entry(nd, struct hist_entry, rb_node_in); pair = hists__find_entry(other, pos); if (pair) @@ -796,11 +815,17 @@ void hists__match(struct hists *leader, struct hists *other) */ int hists__link(struct hists *leader, struct hists *other) { + struct rb_root *root; struct rb_node *nd; struct hist_entry *pos, *pair; - for (nd = rb_first(&other->entries); nd; nd = rb_next(nd)) { - pos = rb_entry(nd, struct hist_entry, rb_node); + if (sort__need_collapse) + root = &other->entries_collapsed; + else + root = other->entries_in; + + for (nd = rb_first(root); nd; nd = rb_next(nd)) { + pos = rb_entry(nd, struct hist_entry, rb_node_in); if (!hist_entry__has_pairs(pos)) { pair = hists__add_dummy_entry(leader, pos); -- 1.7.11.7 ^ permalink raw reply related [flat|nested] 10+ messages in thread
* [PATCH 3/3] perf diff: Use internal rb tree for compute resort 2012-12-04 4:44 [PATCH 0/3] perf hists: Changes on hists__{link,match} Namhyung Kim 2012-12-04 4:44 ` [PATCH 1/3] perf hists: Exchange order of comparing items when collapsing hists Namhyung Kim 2012-12-04 4:44 ` [PATCH 2/3] perf hists: Link hist entries before inserting to an output tree Namhyung Kim @ 2012-12-04 4:44 ` Namhyung Kim 2012-12-04 13:45 ` Arnaldo Carvalho de Melo 2012-12-04 13:54 ` [PATCH 0/3] perf hists: Changes on hists__{link,match} Jiri Olsa 3 siblings, 1 reply; 10+ messages in thread From: Namhyung Kim @ 2012-12-04 4:44 UTC (permalink / raw) To: Arnaldo Carvalho de Melo Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Namhyung Kim, Jiri Olsa, Stephane Eranian From: Namhyung Kim <namhyung.kim@lge.com> There's no reason to run hists_compute_resort() using output tree. Convert it to use internal tree so that it can remove unnecessary _output_resort. Also move position computation below the resort since it changes the output ordering. Cc: Jiri Olsa <jolsa@redhat.com> Cc: Stephane Eranian <eranian@google.com> Signed-off-by: Namhyung Kim <namhyung@kernel.org> --- tools/perf/builtin-diff.c | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-) diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c index b52f5d8c4a6b..4e18cea7c845 100644 --- a/tools/perf/builtin-diff.c +++ b/tools/perf/builtin-diff.c @@ -435,19 +435,25 @@ static void insert_hist_entry_by_compute(struct rb_root *root, static void hists__compute_resort(struct hists *hists) { - struct rb_root tmp = RB_ROOT; - struct rb_node *next = rb_first(&hists->entries); + struct rb_root *root; + struct rb_node *next; + + if (sort__need_collapse) + root = &hists->entries_collapsed; + else + root = hists->entries_in; + + hists->entries = RB_ROOT; + next = rb_first(root); while (next != NULL) { - struct hist_entry *he = rb_entry(next, struct hist_entry, rb_node); + struct hist_entry *he; - next = rb_next(&he->rb_node); + he = rb_entry(next, struct hist_entry, rb_node_in); + next = rb_next(&he->rb_node_in); - rb_erase(&he->rb_node, &hists->entries); - insert_hist_entry_by_compute(&tmp, he, compute); + insert_hist_entry_by_compute(&hists->entries, he, compute); } - - hists->entries = tmp; } static void hists__process(struct hists *old, struct hists *new) @@ -459,16 +465,16 @@ static void hists__process(struct hists *old, struct hists *new) else hists__link(new, old); - hists__output_resort(new); - - if (show_displacement) - hists__compute_position(new); - if (sort_compute) { hists__precompute(new); hists__compute_resort(new); + } else { + hists__output_resort(new); } + if (show_displacement) + hists__compute_position(new); + hists__fprintf(new, true, 0, 0, stdout); } -- 1.7.11.7 ^ permalink raw reply related [flat|nested] 10+ messages in thread
* Re: [PATCH 3/3] perf diff: Use internal rb tree for compute resort 2012-12-04 4:44 ` [PATCH 3/3] perf diff: Use internal rb tree for compute resort Namhyung Kim @ 2012-12-04 13:45 ` Arnaldo Carvalho de Melo 2012-12-04 15:03 ` Namhyung Kim 0 siblings, 1 reply; 10+ messages in thread From: Arnaldo Carvalho de Melo @ 2012-12-04 13:45 UTC (permalink / raw) To: Namhyung Kim Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Namhyung Kim, Jiri Olsa, Stephane Eranian Em Tue, Dec 04, 2012 at 01:44:25PM +0900, Namhyung Kim escreveu: > From: Namhyung Kim <namhyung.kim@lge.com> > > There's no reason to run hists_compute_resort() using output tree. > Convert it to use internal tree so that it can remove unnecessary > _output_resort. Also move position computation below the resort since > it changes the output ordering. Have you tested this with 'perf top'? With the highest frequency? - Arnaldo > Cc: Jiri Olsa <jolsa@redhat.com> > Cc: Stephane Eranian <eranian@google.com> > Signed-off-by: Namhyung Kim <namhyung@kernel.org> > --- > tools/perf/builtin-diff.c | 32 +++++++++++++++++++------------- > 1 file changed, 19 insertions(+), 13 deletions(-) > > diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c > index b52f5d8c4a6b..4e18cea7c845 100644 > --- a/tools/perf/builtin-diff.c > +++ b/tools/perf/builtin-diff.c > @@ -435,19 +435,25 @@ static void insert_hist_entry_by_compute(struct rb_root *root, > > static void hists__compute_resort(struct hists *hists) > { > - struct rb_root tmp = RB_ROOT; > - struct rb_node *next = rb_first(&hists->entries); > + struct rb_root *root; > + struct rb_node *next; > + > + if (sort__need_collapse) > + root = &hists->entries_collapsed; > + else > + root = hists->entries_in; > + > + hists->entries = RB_ROOT; > + next = rb_first(root); > > while (next != NULL) { > - struct hist_entry *he = rb_entry(next, struct hist_entry, rb_node); > + struct hist_entry *he; > > - next = rb_next(&he->rb_node); > + he = rb_entry(next, struct hist_entry, rb_node_in); > + next = rb_next(&he->rb_node_in); > > - rb_erase(&he->rb_node, &hists->entries); > - insert_hist_entry_by_compute(&tmp, he, compute); > + insert_hist_entry_by_compute(&hists->entries, he, compute); > } > - > - hists->entries = tmp; > } > > static void hists__process(struct hists *old, struct hists *new) > @@ -459,16 +465,16 @@ static void hists__process(struct hists *old, struct hists *new) > else > hists__link(new, old); > > - hists__output_resort(new); > - > - if (show_displacement) > - hists__compute_position(new); > - > if (sort_compute) { > hists__precompute(new); > hists__compute_resort(new); > + } else { > + hists__output_resort(new); > } > > + if (show_displacement) > + hists__compute_position(new); > + > hists__fprintf(new, true, 0, 0, stdout); > } > > -- > 1.7.11.7 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 3/3] perf diff: Use internal rb tree for compute resort 2012-12-04 13:45 ` Arnaldo Carvalho de Melo @ 2012-12-04 15:03 ` Namhyung Kim 0 siblings, 0 replies; 10+ messages in thread From: Namhyung Kim @ 2012-12-04 15:03 UTC (permalink / raw) To: Arnaldo Carvalho de Melo Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Namhyung Kim, Jiri Olsa, Stephane Eranian On Tue, 4 Dec 2012 10:45:44 -0300, Arnaldo Carvalho de Melo wrote: > Em Tue, Dec 04, 2012 at 01:44:25PM +0900, Namhyung Kim escreveu: >> From: Namhyung Kim <namhyung.kim@lge.com> >> >> There's no reason to run hists_compute_resort() using output tree. >> Convert it to use internal tree so that it can remove unnecessary >> _output_resort. Also move position computation below the resort since >> it changes the output ordering. > > Have you tested this with 'perf top'? With the highest frequency? After testing 'perf top -F 100000' couple of minutes, I couldn't find any visible problem. Basically this patchset changes hists__link/match path which only called from 'perf diff' - I'm working on making use of that for event group report though. So I didn't check perf top side seriously. Any reason do you mention it that I'm missing? Thanks, Namhyung ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 0/3] perf hists: Changes on hists__{link,match} 2012-12-04 4:44 [PATCH 0/3] perf hists: Changes on hists__{link,match} Namhyung Kim ` (2 preceding siblings ...) 2012-12-04 4:44 ` [PATCH 3/3] perf diff: Use internal rb tree for compute resort Namhyung Kim @ 2012-12-04 13:54 ` Jiri Olsa 3 siblings, 0 replies; 10+ messages in thread From: Jiri Olsa @ 2012-12-04 13:54 UTC (permalink / raw) To: Namhyung Kim Cc: Arnaldo Carvalho de Melo, Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Stephane Eranian, Namhyung Kim On Tue, Dec 04, 2012 at 01:44:22PM +0900, Namhyung Kim wrote: > Hi Arnaldo, > > This is what I talked to Jiri yesterday, and it can be a common basis > of both event group and multiple diff patchset. The point is using > internal input or collapsed rb tree to sort hist entries rather than > output tree with unnessary resort. > > Please take a look. > > Thanks, > Namhyung > > > Cc: Jiri Olsa <jolsa@redhat.com> > Cc: Stephane Eranian <eranian@google.com> > Cc: Namhyung Kim <namhyung.kim@lge.com> > > Namhyung Kim (3): > perf hists: Exchange order of comparing items when collapsing hists > perf hists: Link hist entries before inserting to an output tree > perf diff: Use internal rb tree for compute resort hi, could you please push branch with this? thanks, jirka ^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH v2 0/3] perf hists: Changes on hists__{match,link}
@ 2012-12-05 6:56 Namhyung Kim
2012-12-05 6:56 ` [PATCH 3/3] perf diff: Use internal rb tree for compute resort Namhyung Kim
0 siblings, 1 reply; 10+ messages in thread
From: Namhyung Kim @ 2012-12-05 6:56 UTC (permalink / raw)
To: Arnaldo Carvalho de Melo
Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Jiri Olsa
Hi Arnaldo,
I exchanged arguments of hist_entry__cmp() and friends as you
requested. You can get this on my perf/link-v2 branch at
git://git.kernel.org/pub/scm/linux/kernel/git/namhyung/linux-perf.git
Thanks,
Namhyung
Namhyung Kim (3):
perf hists: Exchange order of comparing items when collapsing hists
perf hists: Link hist entries before inserting to an output tree
perf diff: Use internal rb tree for compute resort
tools/perf/builtin-diff.c | 95 +++++++++++++++++++++--------------------------
tools/perf/util/hist.c | 51 ++++++++++++++++++-------
2 files changed, 80 insertions(+), 66 deletions(-)
--
1.7.11.7
^ permalink raw reply [flat|nested] 10+ messages in thread* [PATCH 3/3] perf diff: Use internal rb tree for compute resort 2012-12-05 6:56 [PATCH v2 0/3] perf hists: Changes on hists__{match,link} Namhyung Kim @ 2012-12-05 6:56 ` Namhyung Kim 0 siblings, 0 replies; 10+ messages in thread From: Namhyung Kim @ 2012-12-05 6:56 UTC (permalink / raw) To: Arnaldo Carvalho de Melo Cc: Peter Zijlstra, Paul Mackerras, Ingo Molnar, LKML, Jiri Olsa, Namhyung Kim, Stephane Eranian From: Namhyung Kim <namhyung.kim@lge.com> There's no reason to run hists_compute_resort() using output tree. Convert it to use internal tree so that it can remove unnecessary _output_resort. Also move position computation below the resort since it changes the output ordering. Cc: Jiri Olsa <jolsa@redhat.com> Cc: Stephane Eranian <eranian@google.com> Signed-off-by: Namhyung Kim <namhyung@kernel.org> --- tools/perf/builtin-diff.c | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-) diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c index b52f5d8c4a6b..4e18cea7c845 100644 --- a/tools/perf/builtin-diff.c +++ b/tools/perf/builtin-diff.c @@ -435,19 +435,25 @@ static void insert_hist_entry_by_compute(struct rb_root *root, static void hists__compute_resort(struct hists *hists) { - struct rb_root tmp = RB_ROOT; - struct rb_node *next = rb_first(&hists->entries); + struct rb_root *root; + struct rb_node *next; + + if (sort__need_collapse) + root = &hists->entries_collapsed; + else + root = hists->entries_in; + + hists->entries = RB_ROOT; + next = rb_first(root); while (next != NULL) { - struct hist_entry *he = rb_entry(next, struct hist_entry, rb_node); + struct hist_entry *he; - next = rb_next(&he->rb_node); + he = rb_entry(next, struct hist_entry, rb_node_in); + next = rb_next(&he->rb_node_in); - rb_erase(&he->rb_node, &hists->entries); - insert_hist_entry_by_compute(&tmp, he, compute); + insert_hist_entry_by_compute(&hists->entries, he, compute); } - - hists->entries = tmp; } static void hists__process(struct hists *old, struct hists *new) @@ -459,16 +465,16 @@ static void hists__process(struct hists *old, struct hists *new) else hists__link(new, old); - hists__output_resort(new); - - if (show_displacement) - hists__compute_position(new); - if (sort_compute) { hists__precompute(new); hists__compute_resort(new); + } else { + hists__output_resort(new); } + if (show_displacement) + hists__compute_position(new); + hists__fprintf(new, true, 0, 0, stdout); } -- 1.7.11.7 ^ permalink raw reply related [flat|nested] 10+ messages in thread
end of thread, other threads:[~2012-12-05 6:57 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-12-04 4:44 [PATCH 0/3] perf hists: Changes on hists__{link,match} Namhyung Kim
2012-12-04 4:44 ` [PATCH 1/3] perf hists: Exchange order of comparing items when collapsing hists Namhyung Kim
2012-12-04 13:44 ` Arnaldo Carvalho de Melo
2012-12-04 14:57 ` Namhyung Kim
2012-12-04 4:44 ` [PATCH 2/3] perf hists: Link hist entries before inserting to an output tree Namhyung Kim
2012-12-04 4:44 ` [PATCH 3/3] perf diff: Use internal rb tree for compute resort Namhyung Kim
2012-12-04 13:45 ` Arnaldo Carvalho de Melo
2012-12-04 15:03 ` Namhyung Kim
2012-12-04 13:54 ` [PATCH 0/3] perf hists: Changes on hists__{link,match} Jiri Olsa
2012-12-05 6:56 [PATCH v2 0/3] perf hists: Changes on hists__{match,link} Namhyung Kim
2012-12-05 6:56 ` [PATCH 3/3] perf diff: Use internal rb tree for compute resort Namhyung Kim
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).