diff options
| author | Davidlohr Bueso <dave@stgolabs.net> | 2018-12-06 22:18:18 +0300 |
|---|---|---|
| committer | Arnaldo Carvalho de Melo <acme@redhat.com> | 2019-01-25 17:12:10 +0300 |
| commit | 2eb3d6894ae3b9cc8a94c91458a041c45773f23d (patch) | |
| tree | 146c0a9ee9b5177a0142319aa606dc1dd18de79b /tools/perf/util/hist.h | |
| parent | 7137ff50b68a48bc28270c91b1c313259ab0c1c4 (diff) | |
| download | linux-2eb3d6894ae3b9cc8a94c91458a041c45773f23d.tar.xz | |
perf hist: Use cached rbtrees
At the cost of an extra pointer, we can avoid the O(logN) cost of
finding the first element in the tree (smallest node), which is
something heavily required for histograms. Specifically, the following
are converted to rb_root_cached, and users accordingly:
hist::entries_in_array
hist::entries_in
hist::entries
hist::entries_collapsed
hist_entry::hroot_in
hist_entry::hroot_out
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Tested-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Namhyung Kim <namhyung@kernel.org>
Link: http://lkml.kernel.org/r/20181206191819.30182-7-dave@stgolabs.net
[ Added some missing conversions to rb_first_cached() ]
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Diffstat (limited to 'tools/perf/util/hist.h')
| -rw-r--r-- | tools/perf/util/hist.h | 10 |
1 files changed, 5 insertions, 5 deletions
diff --git a/tools/perf/util/hist.h b/tools/perf/util/hist.h index 664b5eda8d51..08267af7439c 100644 --- a/tools/perf/util/hist.h +++ b/tools/perf/util/hist.h @@ -70,10 +70,10 @@ struct thread; struct dso; struct hists { - struct rb_root entries_in_array[2]; - struct rb_root *entries_in; - struct rb_root entries; - struct rb_root entries_collapsed; + struct rb_root_cached entries_in_array[2]; + struct rb_root_cached *entries_in; + struct rb_root_cached entries; + struct rb_root_cached entries_collapsed; u64 nr_entries; u64 nr_non_filtered_entries; u64 callchain_period; @@ -230,7 +230,7 @@ static __pure inline bool hists__has_callchains(struct hists *hists) int hists__init(void); int __hists__init(struct hists *hists, struct perf_hpp_list *hpp_list); -struct rb_root *hists__get_rotate_entries_in(struct hists *hists); +struct rb_root_cached *hists__get_rotate_entries_in(struct hists *hists); struct perf_hpp { char *buf; |