summaryrefslogtreecommitdiff
path: root/tools/perf/tests
diff options
context:
space:
mode:
authorDavidlohr Bueso <dave@stgolabs.net>2018-12-06 22:18:18 +0300
committerArnaldo Carvalho de Melo <acme@redhat.com>2019-01-25 17:12:10 +0300
commit2eb3d6894ae3b9cc8a94c91458a041c45773f23d (patch)
tree146c0a9ee9b5177a0142319aa606dc1dd18de79b /tools/perf/tests
parent7137ff50b68a48bc28270c91b1c313259ab0c1c4 (diff)
downloadlinux-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/tests')
-rw-r--r--tools/perf/tests/hists_common.c8
-rw-r--r--tools/perf/tests/hists_cumulate.c14
-rw-r--r--tools/perf/tests/hists_link.c8
-rw-r--r--tools/perf/tests/hists_output.c32
4 files changed, 31 insertions, 31 deletions
diff --git a/tools/perf/tests/hists_common.c b/tools/perf/tests/hists_common.c
index b889a28fd80b..6b0649c8b33e 100644
--- a/tools/perf/tests/hists_common.c
+++ b/tools/perf/tests/hists_common.c
@@ -161,7 +161,7 @@ out:
void print_hists_in(struct hists *hists)
{
int i = 0;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
if (hists__has(hists, need_collapse))
@@ -170,7 +170,7 @@ void print_hists_in(struct hists *hists)
root = hists->entries_in;
pr_info("----- %s --------\n", __func__);
- node = rb_first(root);
+ node = rb_first_cached(root);
while (node) {
struct hist_entry *he;
@@ -191,13 +191,13 @@ void print_hists_in(struct hists *hists)
void print_hists_out(struct hists *hists)
{
int i = 0;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
root = &hists->entries;
pr_info("----- %s --------\n", __func__);
- node = rb_first(root);
+ node = rb_first_cached(root);
while (node) {
struct hist_entry *he;
diff --git a/tools/perf/tests/hists_cumulate.c b/tools/perf/tests/hists_cumulate.c
index 65fe02bebbee..4ca417d1a06b 100644
--- a/tools/perf/tests/hists_cumulate.c
+++ b/tools/perf/tests/hists_cumulate.c
@@ -125,8 +125,8 @@ out:
static void del_hist_entries(struct hists *hists)
{
struct hist_entry *he;
- struct rb_root *root_in;
- struct rb_root *root_out;
+ struct rb_root_cached *root_in;
+ struct rb_root_cached *root_out;
struct rb_node *node;
if (hists__has(hists, need_collapse))
@@ -136,12 +136,12 @@ static void del_hist_entries(struct hists *hists)
root_out = &hists->entries;
- while (!RB_EMPTY_ROOT(root_out)) {
- node = rb_first(root_out);
+ while (!RB_EMPTY_ROOT(&root_out->rb_root)) {
+ node = rb_first_cached(root_out);
he = rb_entry(node, struct hist_entry, rb_node);
- rb_erase(node, root_out);
- rb_erase(&he->rb_node_in, root_in);
+ rb_erase_cached(node, root_out);
+ rb_erase_cached(&he->rb_node_in, root_in);
hist_entry__delete(he);
}
}
@@ -198,7 +198,7 @@ static int do_test(struct hists *hists, struct result *expected, size_t nr_expec
print_hists_out(hists);
}
- root = &hists->entries;
+ root = &hists->entries.rb_root;
for (node = rb_first(root), i = 0;
node && (he = rb_entry(node, struct hist_entry, rb_node));
node = rb_next(node), i++) {
diff --git a/tools/perf/tests/hists_link.c b/tools/perf/tests/hists_link.c
index 9a9d06cb0222..af633db63f4d 100644
--- a/tools/perf/tests/hists_link.c
+++ b/tools/perf/tests/hists_link.c
@@ -142,7 +142,7 @@ static int find_sample(struct sample *samples, size_t nr_samples,
static int __validate_match(struct hists *hists)
{
size_t count = 0;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
/*
@@ -153,7 +153,7 @@ static int __validate_match(struct hists *hists)
else
root = hists->entries_in;
- node = rb_first(root);
+ node = rb_first_cached(root);
while (node) {
struct hist_entry *he;
@@ -192,7 +192,7 @@ static int __validate_link(struct hists *hists, int idx)
size_t count = 0;
size_t count_pair = 0;
size_t count_dummy = 0;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
/*
@@ -205,7 +205,7 @@ static int __validate_link(struct hists *hists, int idx)
else
root = hists->entries_in;
- node = rb_first(root);
+ node = rb_first_cached(root);
while (node) {
struct hist_entry *he;
diff --git a/tools/perf/tests/hists_output.c b/tools/perf/tests/hists_output.c
index faacb4f41460..6c4bc68a77ee 100644
--- a/tools/perf/tests/hists_output.c
+++ b/tools/perf/tests/hists_output.c
@@ -91,8 +91,8 @@ out:
static void del_hist_entries(struct hists *hists)
{
struct hist_entry *he;
- struct rb_root *root_in;
- struct rb_root *root_out;
+ struct rb_root_cached *root_in;
+ struct rb_root_cached *root_out;
struct rb_node *node;
if (hists__has(hists, need_collapse))
@@ -102,12 +102,12 @@ static void del_hist_entries(struct hists *hists)
root_out = &hists->entries;
- while (!RB_EMPTY_ROOT(root_out)) {
- node = rb_first(root_out);
+ while (!RB_EMPTY_ROOT(&root_out->rb_root)) {
+ node = rb_first_cached(root_out);
he = rb_entry(node, struct hist_entry, rb_node);
- rb_erase(node, root_out);
- rb_erase(&he->rb_node_in, root_in);
+ rb_erase_cached(node, root_out);
+ rb_erase_cached(&he->rb_node_in, root_in);
hist_entry__delete(he);
}
}
@@ -126,7 +126,7 @@ static int test1(struct perf_evsel *evsel, struct machine *machine)
int err;
struct hists *hists = evsel__hists(evsel);
struct hist_entry *he;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
field_order = NULL;
@@ -162,7 +162,7 @@ static int test1(struct perf_evsel *evsel, struct machine *machine)
}
root = &hists->entries;
- node = rb_first(root);
+ node = rb_first_cached(root);
he = rb_entry(node, struct hist_entry, rb_node);
TEST_ASSERT_VAL("Invalid hist entry",
!strcmp(COMM(he), "perf") && !strcmp(DSO(he), "perf") &&
@@ -228,7 +228,7 @@ static int test2(struct perf_evsel *evsel, struct machine *machine)
int err;
struct hists *hists = evsel__hists(evsel);
struct hist_entry *he;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
field_order = "overhead,cpu";
@@ -262,7 +262,7 @@ static int test2(struct perf_evsel *evsel, struct machine *machine)
}
root = &hists->entries;
- node = rb_first(root);
+ node = rb_first_cached(root);
he = rb_entry(node, struct hist_entry, rb_node);
TEST_ASSERT_VAL("Invalid hist entry",
CPU(he) == 1 && PID(he) == 100 && he->stat.period == 300);
@@ -284,7 +284,7 @@ static int test3(struct perf_evsel *evsel, struct machine *machine)
int err;
struct hists *hists = evsel__hists(evsel);
struct hist_entry *he;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
field_order = "comm,overhead,dso";
@@ -316,7 +316,7 @@ static int test3(struct perf_evsel *evsel, struct machine *machine)
}
root = &hists->entries;
- node = rb_first(root);
+ node = rb_first_cached(root);
he = rb_entry(node, struct hist_entry, rb_node);
TEST_ASSERT_VAL("Invalid hist entry",
!strcmp(COMM(he), "bash") && !strcmp(DSO(he), "bash") &&
@@ -358,7 +358,7 @@ static int test4(struct perf_evsel *evsel, struct machine *machine)
int err;
struct hists *hists = evsel__hists(evsel);
struct hist_entry *he;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
field_order = "dso,sym,comm,overhead,dso";
@@ -394,7 +394,7 @@ static int test4(struct perf_evsel *evsel, struct machine *machine)
}
root = &hists->entries;
- node = rb_first(root);
+ node = rb_first_cached(root);
he = rb_entry(node, struct hist_entry, rb_node);
TEST_ASSERT_VAL("Invalid hist entry",
!strcmp(DSO(he), "perf") && !strcmp(SYM(he), "cmd_record") &&
@@ -460,7 +460,7 @@ static int test5(struct perf_evsel *evsel, struct machine *machine)
int err;
struct hists *hists = evsel__hists(evsel);
struct hist_entry *he;
- struct rb_root *root;
+ struct rb_root_cached *root;
struct rb_node *node;
field_order = "cpu,pid,comm,dso,sym";
@@ -497,7 +497,7 @@ static int test5(struct perf_evsel *evsel, struct machine *machine)
}
root = &hists->entries;
- node = rb_first(root);
+ node = rb_first_cached(root);
he = rb_entry(node, struct hist_entry, rb_node);
TEST_ASSERT_VAL("Invalid hist entry",