From 9afcf930b1fa1158b0878afeba3eff299300dc65 Mon Sep 17 00:00:00 2001 From: Namhyung Kim Date: Mon, 10 Dec 2012 17:29:54 +0900 Subject: perf hists: Exchange order of comparing items when collapsing hists 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. Signed-off-by: Namhyung Kim Acked-by: Jiri Olsa Cc: Ingo Molnar Cc: Jiri Olsa Cc: Paul Mackerras Cc: Peter Zijlstra Cc: Stephane Eranian Link: http://lkml.kernel.org/r/1355128197-18193-2-git-send-email-namhyung@kernel.org Signed-off-by: Arnaldo Carvalho de Melo --- tools/perf/builtin-diff.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'tools/perf/builtin-diff.c') diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c index b2e7d39f099b..4dda6f4dc618 100644 --- a/tools/perf/builtin-diff.c +++ b/tools/perf/builtin-diff.c @@ -285,7 +285,7 @@ static void insert_hist_entry_by_name(struct rb_root *root, while (*p != NULL) { parent = *p; iter = rb_entry(parent, struct hist_entry, rb_node); - if (hist_entry__cmp(he, iter) < 0) + if (hist_entry__cmp(iter, he) < 0) p = &(*p)->rb_left; else p = &(*p)->rb_right; -- cgit v1.2.3 From ce74f60eab3cc8b7a3b0cb9c29ec9b1e1abac7d2 Mon Sep 17 00:00:00 2001 From: Namhyung Kim Date: Mon, 10 Dec 2012 17:29:55 +0900 Subject: perf hists: Link hist entries before inserting to an output tree 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. Signed-off-by: Namhyung Kim Acked-by: Jiri Olsa Cc: Ingo Molnar Cc: Jiri Olsa Cc: Paul Mackerras Cc: Peter Zijlstra Cc: Stephane Eranian Link: http://lkml.kernel.org/r/1355128197-18193-3-git-send-email-namhyung@kernel.org Signed-off-by: Arnaldo Carvalho de Melo --- tools/perf/builtin-diff.c | 65 +++++++++++++---------------------------------- 1 file changed, 17 insertions(+), 48 deletions(-) (limited to 'tools/perf/builtin-diff.c') diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c index 4dda6f4dc618..8b896f5eded0 100644 --- a/tools/perf/builtin-diff.c +++ b/tools/perf/builtin-diff.c @@ -275,43 +275,6 @@ 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(iter, he) < 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) -{ - struct rb_root tmp = RB_ROOT; - struct rb_node *next = rb_first(&self->entries); - - while (next != NULL) { - struct hist_entry *n = rb_entry(next, struct hist_entry, rb_node); - - next = rb_next(&n->rb_node); - - rb_erase(&n->rb_node, &self->entries); - insert_hist_entry_by_name(&tmp, n); - } - - self->entries = tmp; -} - static struct perf_evsel *evsel_match(struct perf_evsel *evsel, struct perf_evlist *evlist) { @@ -324,30 +287,34 @@ 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__collapse_resort(struct perf_evlist *evlist) { struct perf_evsel *evsel; list_for_each_entry(evsel, &evlist->entries, node) { struct hists *hists = &evsel->hists; - hists__output_resort(hists); - - if (name) - hists__name_resort(hists); + hists__collapse_resort(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); } } @@ -471,6 +438,8 @@ static void hists__process(struct hists *old, struct hists *new) else hists__link(new, old); + hists__output_resort(new); + if (sort_compute) { hists__precompute(new); hists__compute_resort(new); @@ -505,8 +474,8 @@ static int __cmd_diff(void) evlist_old = older->evlist; evlist_new = newer->evlist; - perf_evlist__resort_hists(evlist_old, true); - perf_evlist__resort_hists(evlist_new, false); + perf_evlist__collapse_resort(evlist_old); + perf_evlist__collapse_resort(evlist_new); list_for_each_entry(evsel, &evlist_new->entries, node) { struct perf_evsel *evsel_old; -- cgit v1.2.3 From 66f97ed3ac44c24958171bbc5cc04896147752b7 Mon Sep 17 00:00:00 2001 From: Namhyung Kim Date: Mon, 10 Dec 2012 17:29:56 +0900 Subject: perf diff: Use internal rb tree for compute resort 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. Signed-off-by: Namhyung Kim Acked-by: Jiri Olsa Cc: Ingo Molnar Cc: Jiri Olsa Cc: Paul Mackerras Cc: Peter Zijlstra Cc: Stephane Eranian Link: http://lkml.kernel.org/r/1355128197-18193-4-git-send-email-namhyung@kernel.org Signed-off-by: Arnaldo Carvalho de Melo --- tools/perf/builtin-diff.c | 31 +++++++++++++++++++++---------- 1 file changed, 21 insertions(+), 10 deletions(-) (limited to 'tools/perf/builtin-diff.c') diff --git a/tools/perf/builtin-diff.c b/tools/perf/builtin-diff.c index 8b896f5eded0..4af0b580b046 100644 --- a/tools/perf/builtin-diff.c +++ b/tools/perf/builtin-diff.c @@ -414,19 +414,30 @@ 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); + + hists->nr_entries = 0; + hists->stats.total_period = 0; + hists__reset_col_len(hists); 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__inc_nr_entries(hists, he); } - - hists->entries = tmp; } static void hists__process(struct hists *old, struct hists *new) @@ -438,11 +449,11 @@ static void hists__process(struct hists *old, struct hists *new) else hists__link(new, old); - hists__output_resort(new); - if (sort_compute) { hists__precompute(new); hists__compute_resort(new); + } else { + hists__output_resort(new); } hists__fprintf(new, true, 0, 0, stdout); -- cgit v1.2.3