From: Davidlohr Bueso <dave@stgolabs.net>
To: acme@kernel.org
Cc: jolsa@redhat.com, ak@linux.intel.com, mingo@redhat.com,
dave@stgolabs.net, linux-kernel@vger.kernel.org,
Davidlohr Bueso <dbueso@suse.de>
Subject: [PATCH 4/7] perf util: Use cached rbtree for rblists
Date: Sun, 26 Nov 2017 18:30:43 -0800 [thread overview]
Message-ID: <20171127023046.19139-5-dave@stgolabs.net> (raw)
In-Reply-To: <20171127023046.19139-1-dave@stgolabs.net>
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 required for any of the strlist or intlist traversals
(XXX_for_each_entry()). There are a number of users in perf of
these (particularly strlists), including probes, and buildid.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
tools/perf/util/intlist.h | 2 +-
tools/perf/util/metricgroup.c | 2 +-
tools/perf/util/rblist.c | 30 ++++++++++++++++++------------
tools/perf/util/rblist.h | 2 +-
tools/perf/util/stat-shadow.c | 2 +-
tools/perf/util/strlist.h | 2 +-
6 files changed, 23 insertions(+), 17 deletions(-)
diff --git a/tools/perf/util/intlist.h b/tools/perf/util/intlist.h
index 85bab8735fa9..5c19ee001299 100644
--- a/tools/perf/util/intlist.h
+++ b/tools/perf/util/intlist.h
@@ -45,7 +45,7 @@ static inline unsigned int intlist__nr_entries(const struct intlist *ilist)
/* For intlist iteration */
static inline struct int_node *intlist__first(struct intlist *ilist)
{
- struct rb_node *rn = rb_first(&ilist->rblist.entries);
+ struct rb_node *rn = rb_first_cached(&ilist->rblist.entries);
return rn ? rb_entry(rn, struct int_node, rb_node) : NULL;
}
static inline struct int_node *intlist__next(struct int_node *in)
diff --git a/tools/perf/util/metricgroup.c b/tools/perf/util/metricgroup.c
index 0ddd9c199227..59a08a9eebb9 100644
--- a/tools/perf/util/metricgroup.c
+++ b/tools/perf/util/metricgroup.c
@@ -350,7 +350,7 @@ void metricgroup__print(bool metrics, bool metricgroups, char *filter,
else if (metrics && !raw)
printf("\nMetrics:\n\n");
- for (node = rb_first(&groups.entries); node; node = next) {
+ for (node = rb_first_cached(&groups.entries); node; node = next) {
struct mep *me = container_of(node, struct mep, nd);
if (metricgroups)
diff --git a/tools/perf/util/rblist.c b/tools/perf/util/rblist.c
index 0dfe27d99458..8256545344ed 100644
--- a/tools/perf/util/rblist.c
+++ b/tools/perf/util/rblist.c
@@ -13,8 +13,9 @@
int rblist__add_node(struct rblist *rblist, const void *new_entry)
{
- struct rb_node **p = &rblist->entries.rb_node;
+ struct rb_node **p = &rblist->entries.rb_root.rb_node;
struct rb_node *parent = NULL, *new_node;
+ bool leftmost = true;
while (*p != NULL) {
int rc;
@@ -24,9 +25,10 @@ int rblist__add_node(struct rblist *rblist, const void *new_entry)
rc = rblist->node_cmp(parent, new_entry);
if (rc > 0)
p = &(*p)->rb_left;
- else if (rc < 0)
+ else if (rc < 0) {
p = &(*p)->rb_right;
- else
+ leftmost = false;
+ } else
return -EEXIST;
}
@@ -35,7 +37,7 @@ int rblist__add_node(struct rblist *rblist, const void *new_entry)
return -ENOMEM;
rb_link_node(new_node, parent, p);
- rb_insert_color(new_node, &rblist->entries);
+ rb_insert_color_cached(new_node, &rblist->entries, leftmost);
++rblist->nr_entries;
return 0;
@@ -43,7 +45,7 @@ int rblist__add_node(struct rblist *rblist, const void *new_entry)
void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node)
{
- rb_erase(rb_node, &rblist->entries);
+ rb_erase_cached(rb_node, &rblist->entries);
--rblist->nr_entries;
rblist->node_delete(rblist, rb_node);
}
@@ -52,8 +54,9 @@ static struct rb_node *__rblist__findnew(struct rblist *rblist,
const void *entry,
bool create)
{
- struct rb_node **p = &rblist->entries.rb_node;
+ struct rb_node **p = &rblist->entries.rb_root.rb_node;
struct rb_node *parent = NULL, *new_node = NULL;
+ bool leftmost = true;
while (*p != NULL) {
int rc;
@@ -63,9 +66,10 @@ static struct rb_node *__rblist__findnew(struct rblist *rblist,
rc = rblist->node_cmp(parent, entry);
if (rc > 0)
p = &(*p)->rb_left;
- else if (rc < 0)
+ else if (rc < 0) {
p = &(*p)->rb_right;
- else
+ leftmost = false;
+ } else
return parent;
}
@@ -73,7 +77,8 @@ static struct rb_node *__rblist__findnew(struct rblist *rblist,
new_node = rblist->node_new(rblist, entry);
if (new_node) {
rb_link_node(new_node, parent, p);
- rb_insert_color(new_node, &rblist->entries);
+ rb_insert_color_cached(new_node,
+ &rblist->entries, leftmost);
++rblist->nr_entries;
}
}
@@ -94,7 +99,7 @@ struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry)
void rblist__init(struct rblist *rblist)
{
if (rblist != NULL) {
- rblist->entries = RB_ROOT;
+ rblist->entries = RB_ROOT_CACHED;
rblist->nr_entries = 0;
}
@@ -104,7 +109,7 @@ void rblist__init(struct rblist *rblist)
void rblist__delete(struct rblist *rblist)
{
if (rblist != NULL) {
- struct rb_node *pos, *next = rb_first(&rblist->entries);
+ struct rb_node *pos, *next = rb_first_cached(&rblist->entries);
while (next) {
pos = next;
@@ -119,7 +124,8 @@ struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx)
{
struct rb_node *node;
- for (node = rb_first(&rblist->entries); node; node = rb_next(node)) {
+ for (node = rb_first_cached(&rblist->entries);
+ node; node = rb_next(node)) {
if (!idx--)
return node;
}
diff --git a/tools/perf/util/rblist.h b/tools/perf/util/rblist.h
index 4c8638a22571..4b16fc48a46d 100644
--- a/tools/perf/util/rblist.h
+++ b/tools/perf/util/rblist.h
@@ -20,7 +20,7 @@
*/
struct rblist {
- struct rb_root entries;
+ struct rb_root_cached entries;
unsigned int nr_entries;
int (*node_cmp)(struct rb_node *rbn, const void *entry);
diff --git a/tools/perf/util/stat-shadow.c b/tools/perf/util/stat-shadow.c
index 855e35cbb1dc..a7ed1180d878 100644
--- a/tools/perf/util/stat-shadow.c
+++ b/tools/perf/util/stat-shadow.c
@@ -164,7 +164,7 @@ void perf_stat__reset_shadow_stats(void)
memset(runtime_smi_num_stats, 0, sizeof(runtime_smi_num_stats));
memset(runtime_aperf_stats, 0, sizeof(runtime_aperf_stats));
- next = rb_first(&runtime_saved_values.entries);
+ next = rb_first_cached(&runtime_saved_values.entries);
while (next) {
pos = next;
next = rb_next(pos);
diff --git a/tools/perf/util/strlist.h b/tools/perf/util/strlist.h
index d58f1e08b170..7e82c71dcc42 100644
--- a/tools/perf/util/strlist.h
+++ b/tools/perf/util/strlist.h
@@ -57,7 +57,7 @@ static inline unsigned int strlist__nr_entries(const struct strlist *slist)
/* For strlist iteration */
static inline struct str_node *strlist__first(struct strlist *slist)
{
- struct rb_node *rn = rb_first(&slist->rblist.entries);
+ struct rb_node *rn = rb_first_cached(&slist->rblist.entries);
return rn ? rb_entry(rn, struct str_node, rb_node) : NULL;
}
static inline struct str_node *strlist__next(struct str_node *sn)
--
2.13.6
next prev parent reply other threads:[~2017-11-27 2:34 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-11-27 2:30 [PATCH -tip 0/7] tools/perf: Update rbtree implementation and optimize users Davidlohr Bueso
2017-11-27 2:30 ` [PATCH 1/7] tools/perf: Update rbtree implementation Davidlohr Bueso
2017-11-27 2:30 ` [PATCH 2/7] perf machine: Use cached rbtrees Davidlohr Bueso
2018-01-04 5:51 ` [lkp-robot] [perf machine] 8edf8850d5: stderr./usr/src/linux-perf-x86_64-rhel-#/tools/perf/util/rb_resort.h:#:#:error:passing_argument#of'threads_sorted__new'from_incompatible_pointer_type[-Werror=incompatible-pointer-types] kernel test robot
2018-01-05 17:04 ` Davidlohr Bueso
2017-11-27 2:30 ` [PATCH 3/7] perf callchain: Use cached rbtrees Davidlohr Bueso
2017-11-27 2:30 ` Davidlohr Bueso [this message]
2017-11-27 2:30 ` [PATCH 5/7] perf symbols: " Davidlohr Bueso
2017-11-27 2:30 ` [PATCH 6/7] perf hist: " Davidlohr Bueso
2017-11-27 2:30 ` [PATCH 7/7] perf sched: " Davidlohr Bueso
2017-11-27 6:06 ` [PATCH -tip 0/7] tools/perf: Update rbtree implementation and optimize users Andi Kleen
2017-11-27 16:14 ` Davidlohr Bueso
2017-11-27 17:14 ` Arnaldo Carvalho de Melo
2018-12-06 19:18 [PATCH v2 " Davidlohr Bueso
2018-12-06 19:18 ` [PATCH 4/7] perf util: Use cached rbtree for rblists Davidlohr Bueso
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=20171127023046.19139-5-dave@stgolabs.net \
--to=dave@stgolabs.net \
--cc=acme@kernel.org \
--cc=ak@linux.intel.com \
--cc=dbueso@suse.de \
--cc=jolsa@redhat.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@redhat.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).