tools/perf: Update rbtree implementation and optimize users
v2 cover tools/perf: Update rbtree implementation and optimize users
Hi,
Per acme's request, this is a rebase (and basically rewrite) of v1.
The following optimizes the rb_first() lookups in perf tooling such that we can avoid walking down the tree finding the first element. Tree traversals (and overall computing the first node in the tree) is a surprisingly common operation. On a Xeon E5-2450 @ 2.10GHz, the cost of an rb_first() was ~60 cycles for 100 nodes, and ~75 cycles with 1000 nodes.
The first patch adds the updated implementation of rbtrees, including the cached interfaces, taken from the kernel. The rest of the patches make use of this for the users I thought might care the most.
With these patches I am able to build and use perf without anything going wrong (but needs more testing no doubt, as changes while redundant can be a little tricky depending on if the user get smart about the trees). I'm sorry if some patches seem too big, I've tried to split them the best I could.
Applies on today's -tip tree. Please consider for v4.21.
Thanks!
Davidlohr Bueso (7):
tools/perf: Update rbtree implementation
perf machine: Use cached rbtrees
perf callchain: Use cached rbtrees
perf util: Use cached rbtree for rblists
perf symbols: Use cached rbtrees
perf hist: Use cached rbtrees
perf sched: Use cached rbtrees
tools/include/linux/rbtree.h | 52 ++++++++- tools/include/linux/rbtree_augmented.h | 60 ++++++++-- tools/lib/rbtree.c | 178 ++++++++++++++++++++++------- tools/perf/builtin-annotate.c | 4 +- tools/perf/builtin-c2c.c | 6 +- tools/perf/builtin-diff.c | 10 +- tools/perf/builtin-report.c | 3 +- tools/perf/builtin-sched.c | 45 ++++---- tools/perf/builtin-top.c | 2 +- tools/perf/tests/hists_common.c | 8 +- tools/perf/tests/hists_cumulate.c | 14 +-- tools/perf/tests/hists_link.c | 8 +- tools/perf/tests/hists_output.c | 32 +++--- tools/perf/ui/browsers/hists.c | 6 +- tools/perf/ui/gtk/hists.c | 4 +- tools/perf/ui/stdio/hist.c | 3 +- tools/perf/util/build-id.c | 12 +- tools/perf/util/dso.c | 8 +- tools/perf/util/dso.h | 10 +- tools/perf/util/hist.c | 199 +++++++++++++++++++-------------- tools/perf/util/hist.h | 10 +- tools/perf/util/intlist.h | 2 +- tools/perf/util/machine.c | 53 +++++---- tools/perf/util/machine.h | 12 +- tools/perf/util/map.c | 8 +- tools/perf/util/metricgroup.c | 2 +- tools/perf/util/probe-event.c | 3 +- tools/perf/util/rb_resort.h | 8 +- tools/perf/util/rblist.c | 28 +++-- tools/perf/util/rblist.h | 2 +- tools/perf/util/sort.h | 4 +- tools/perf/util/srcline.c | 43 ++++--- tools/perf/util/srcline.h | 13 ++- tools/perf/util/stat-shadow.c | 2 +- tools/perf/util/strlist.h | 2 +- tools/perf/util/symbol.c | 87 +++++++------- tools/perf/util/symbol.h | 13 ++- tools/perf/util/symbol_fprintf.c | 2 +- 38 files changed, 598 insertions(+), 360 deletions(-)
Signature · 1 line
2.16.4
PATCH v2 1/7 tools/perf: Update rbtree implementation
There have been a number of changes in the kernel's rbrtee implementation, including loose lockless searching guarantees and rb_root_cached, which later patches will use as an optimization.
--- tools/include/linux/rbtree.h | 52 ++++++++-- tools/include/linux/rbtree_augmented.h | 60 ++++++++--- tools/lib/rbtree.c | 178 +++++++++++++++++++++++++-------- 3 files changed, 229 insertions(+), 61 deletions(-)
tools/include/linux/rbtree.h +46 -6
@@ -43,13 +43,28 @@ struct rb_root {struct rb_node *rb_node; }; +/* +* Leftmost-cached rbtrees. +* +* We do not cache the rightmost node based on footprint +* size vs number of potential users that could benefit +* from O(1) rb_last(). Just not worth it, users that want +* this feature can always implement the logic explicitly. +* Furthermore, users that want to cache both pointers may +* find it a bit asymmetric, but that's ok. +*/ +struct rb_root_cached { +struct rb_root rb_root; +struct rb_node *rb_leftmost; +};#define rb_parent (r) ((struct rb_node *)((r)->__rb_parent_color & ~3))#define RB_ROOT (struct rb_root) { NULL, } +#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }#define rb_entry (ptr, type, member) container_of(ptr, type, member) -#define RB_EMPTY_ROOT (root) ((root)->rb_node == NULL) +#define RB_EMPTY_ROOT (root) (READ_ONCE((root)->rb_node) == NULL)/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */ #define RB_EMPTY_NODE (node) \
@@ -68,6 +83,12 @@ extern struct rb_node *rb_prev(const struct rb_node *);extern struct rb_node *rb_first (const struct rb_root *);extern struct rb_node *rb_last (const struct rb_root *); +extern void rb_insert_color_cached (struct rb_node *, +struct rb_root_cached *,bool ); +extern void rb_erase_cached (struct rb_node *node,struct rb_root_cached *); +/* Same as rb_first(), but O(1) */ +#define rb_first_cached (root) (root)->rb_leftmost +/* Postorder iteration - always visit the parent after its children */ extern struct rb_node *rb_first_postorder (const struct rb_root *);extern struct rb_node *rb_next_postorder (const struct rb_node *);
@@ -75,6 +96,8 @@ extern struct rb_node *rb_next_postorder(const struct rb_node *);/* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node (struct rb_node *victim,struct rb_node *new,struct rb_root *root); +extern void rb_replace_node_cached (struct rb_node *victim,struct rb_node *new, +struct rb_root_cached *root);static inline void rb_link_node (struct rb_node *node,struct rb_node *parent,struct rb_node **rb_link)
@@ -90,12 +113,29 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, ____ptr ?rb_entry (____ptr, type, member) :NULL ; \ }) - -/* -* Handy for checking that we are not deleting an entry that is -* already in a list, found in block/{blk-throttle,cfq-iosched}.c, -* probably should be moved to lib/rbtree.c... +/** +* rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of +* given type allowing the backing memory of @pos to be invalidated +* +* @pos: the 'type *' to use as a loop cursor. +* @n: another 'type *' to use as temporary storage +* @root: 'rb_root *' of the rbtree. +* @field: the name of the rb_node field within 'type'. +* +* rbtree_postorder_for_each_entry_safe() provides a similar guarantee as +* list_for_each_entry_safe() and allows the iteration to continue independent +* of changes to @pos by the body of the loop. +* +* Note, however, that it cannot handle other modifications that re-order the +* rbtree it is iterating over. This includes calling rb_erase() on @pos, as +* rb_erase() may rebalance the tree, causing us to miss some nodes. */ +#define rbtree_postorder_for_each_entry_safe (pos, n, root, field) \ + for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \ + pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \ + typeof(*pos), field); 1; }); \ + pos = n) +static inline void rb_erase_init (struct rb_node *n,struct rb_root *root) {rb_erase (n, root);
tools/include/linux/rbtree_augmented.h +48 -12
132 lines not on this page · raw message
tools/lib/rbtree.c +135 -43
326 lines not on this page · raw message
Signature · 1 line
2.16.4
tip-bot for Davidlohr Bueso
merge bot[tip:perf/core] tools: Update rbtree implementation
tools: Update rbtree implementation
Commit-ID: 3aef2cad5d51ee66d2a614dd2f70cb34c74caf77 Gitweb: https://git.kernel.org/tip/3aef2cad5d51ee66d2a614dd2f70cb34c74caf77 Author: Davidlohr Bueso <[email protected]> AuthorDate: Thu, 6 Dec 2018 11:18:13 -0800 Committer: Arnaldo Carvalho de Melo <[email protected]> CommitDate: Fri, 25 Jan 2019 15:12:09 +0100
tools: Update rbtree implementation
There have been a number of changes in the kernel's rbrtee implementation, including loose lockless searching guarantees and rb_root_cached, which later patches will use as an optimization.
--- tools/include/linux/rbtree.h | 52 ++++++++-- tools/include/linux/rbtree_augmented.h | 60 ++++++++--- tools/lib/rbtree.c | 178 +++++++++++++++++++++++++-------- 3 files changed, 229 insertions(+), 61 deletions(-)
tools/include/linux/rbtree.h +46 -6
@@ -43,13 +43,28 @@ struct rb_root {struct rb_node *rb_node; }; +/* +* Leftmost-cached rbtrees. +* +* We do not cache the rightmost node based on footprint +* size vs number of potential users that could benefit +* from O(1) rb_last(). Just not worth it, users that want +* this feature can always implement the logic explicitly. +* Furthermore, users that want to cache both pointers may +* find it a bit asymmetric, but that's ok. +*/ +struct rb_root_cached { +struct rb_root rb_root; +struct rb_node *rb_leftmost; +};#define rb_parent (r) ((struct rb_node *)((r)->__rb_parent_color & ~3))#define RB_ROOT (struct rb_root) { NULL, } +#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }#define rb_entry (ptr, type, member) container_of(ptr, type, member) -#define RB_EMPTY_ROOT (root) ((root)->rb_node == NULL) +#define RB_EMPTY_ROOT (root) (READ_ONCE((root)->rb_node) == NULL)/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */ #define RB_EMPTY_NODE (node) \
@@ -68,6 +83,12 @@ extern struct rb_node *rb_prev(const struct rb_node *);extern struct rb_node *rb_first (const struct rb_root *);extern struct rb_node *rb_last (const struct rb_root *); +extern void rb_insert_color_cached (struct rb_node *, +struct rb_root_cached *,bool ); +extern void rb_erase_cached (struct rb_node *node,struct rb_root_cached *); +/* Same as rb_first(), but O(1) */ +#define rb_first_cached (root) (root)->rb_leftmost +/* Postorder iteration - always visit the parent after its children */ extern struct rb_node *rb_first_postorder (const struct rb_root *);extern struct rb_node *rb_next_postorder (const struct rb_node *);
@@ -75,6 +96,8 @@ extern struct rb_node *rb_next_postorder(const struct rb_node *);/* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node (struct rb_node *victim,struct rb_node *new,struct rb_root *root); +extern void rb_replace_node_cached (struct rb_node *victim,struct rb_node *new, +struct rb_root_cached *root);static inline void rb_link_node (struct rb_node *node,struct rb_node *parent,struct rb_node **rb_link)
@@ -90,12 +113,29 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, ____ptr ?rb_entry (____ptr, type, member) :NULL ; \ }) - -/* -* Handy for checking that we are not deleting an entry that is -* already in a list, found in block/{blk-throttle,cfq-iosched}.c, -* probably should be moved to lib/rbtree.c... +/** +* rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of +* given type allowing the backing memory of @pos to be invalidated +* +* @pos: the 'type *' to use as a loop cursor. +* @n: another 'type *' to use as temporary storage +* @root: 'rb_root *' of the rbtree. +* @field: the name of the rb_node field within 'type'. +* +* rbtree_postorder_for_each_entry_safe() provides a similar guarantee as +* list_for_each_entry_safe() and allows the iteration to continue independent +* of changes to @pos by the body of the loop. +* +* Note, however, that it cannot handle other modifications that re-order the +* rbtree it is iterating over. This includes calling rb_erase() on @pos, as +* rb_erase() may rebalance the tree, causing us to miss some nodes. */ +#define rbtree_postorder_for_each_entry_safe (pos, n, root, field) \ + for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \ + pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \ + typeof(*pos), field); 1; }); \ + pos = n) +static inline void rb_erase_init (struct rb_node *n,struct rb_root *root) {rb_erase (n, root);
tools/include/linux/rbtree_augmented.h +48 -12
132 lines not on this page · raw message
tools/lib/rbtree.c +135 -43
326 lines not on this page · raw message
PATCH v2 2/7 perf machine: Use cached rbtrees
In reply to Davidlohr BuesoAt 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 nearly every operation dealing with machine->guests and threads->entries.
The conversion is straightforward, however, it's worth noticing that the rb_erase_init() calls have been replaced by rb_erase_cached() which has no _init() flavor, however, the node is explicitly cleared next anyway, which was redundant until now.
--- tools/perf/builtin-report.c | 3 ++- tools/perf/util/build-id.c | 12 ++++++---- tools/perf/util/machine.c | 53 ++++++++++++++++++++++++++------------------- tools/perf/util/machine.h | 12 +++++----- tools/perf/util/rb_resort.h | 6 ++--- 5 files changed, 50 insertions(+), 36 deletions(-)
tools/perf/builtin-report.c +2 -1
@@ -752,7 +752,8 @@ static int tasks_print(struct report *rep, FILE *fp)for (i =0 ; i <THREADS__TABLE_SIZE ; i++) {struct threads *threads = &machine->threads[i]; -for (nd =rb_first (&threads->entries); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&threads->entries); nd; + nd =rb_next (nd)) { task = tasks + itask++; task->thread = rb_entry(nd, struct thread, rb_node);
tools/perf/util/build-id.c +8 -4
@@ -363,7 +363,8 @@ int perf_session__write_buildid_table(struct perf_session *session,if (err)return err; -for (nd =rb_first (&session->machines.guests); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&session->machines.guests); nd; + nd =rb_next (nd)) { struct machine *pos = rb_entry(nd, struct machine, rb_node); err =machine__write_buildid_table (pos, fd);if (err)
@@ -396,7 +397,8 @@ int dsos__hit_all(struct perf_session *session)if (err)return err; -for (nd =rb_first (&session->machines.guests); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&session->machines.guests); nd; + nd =rb_next (nd)) { struct machine *pos = rb_entry(nd, struct machine, rb_node); err =machine__hit_all_dsos (pos);
@@ -849,7 +851,8 @@ int perf_session__cache_build_ids(struct perf_session *session) ret =machine__cache_build_ids (&session->machines.host); -for (nd =rb_first (&session->machines.guests); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&session->machines.guests); nd; + nd =rb_next (nd)) { struct machine *pos = rb_entry(nd, struct machine, rb_node); ret |=machine__cache_build_ids (pos); }
@@ -866,7 +869,8 @@ bool perf_session__read_build_ids(struct perf_session *session, bool with_hits)struct rb_node *nd;bool ret =machine__read_build_ids (&session->machines.host, with_hits); -for (nd =rb_first (&session->machines.guests); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&session->machines.guests); nd; + nd =rb_next (nd)) { struct machine *pos = rb_entry(nd, struct machine, rb_node); ret |=machine__read_build_ids (pos, with_hits); }
tools/perf/util/machine.c +31 -22
188 lines not on this page · raw message
tools/perf/util/machine.h +6 -6
@@ -29,11 +29,11 @@ struct vdso_info;#define THREADS__TABLE_SIZE (1 << THREADS__TABLE_BITS)struct threads { -struct rb_root entries; -struct rw_semaphore lock; -unsigned int nr; -struct list_head dead; -struct thread *last_match; +struct rb_root_cached entries; +struct rw_semaphore lock; +unsigned int nr; +struct list_head dead; +struct thread *last_match; };struct machine {
@@ -134,7 +134,7 @@ typedef void (*machine__process_t)(struct machine *machine, void *data);struct machines {struct machine host; -struct rb_root guests; +struct rb_root_cached guests; };void machines__init (struct machines *machines);
tools/perf/util/rb_resort.h +3 -3
@@ -144,8 +144,8 @@ struct __name##_sorted *__name = __name##_sorted__new __ilist->rblist.nr_entries)/* For 'struct machine->threads' */ -#define DECLARE_RESORT_RB_MACHINE_THREADS (__name, __machine, hash_bucket) \ - DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries, \ - __machine->threads[hash_bucket].nr) +#define DECLARE_RESORT_RB_MACHINE_THREADS (__name, __machine, hash_bucket) \ + DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries.rb_root, \ + __machine->threads[hash_bucket].nr)#endif /* _PERF_RESORT_RB_H_ */
Signature · 1 line
2.16.4
tip-bot for Davidlohr Bueso
merge bot[tip:perf/core] perf machine: Use cached rbtrees
perf machine: Use cached rbtrees
Commit-ID: f3acb3a8a2081344801974ac5ec8e1b0d6f0ef36 Gitweb: https://git.kernel.org/tip/f3acb3a8a2081344801974ac5ec8e1b0d6f0ef36 Author: Davidlohr Bueso <[email protected]> AuthorDate: Thu, 6 Dec 2018 11:18:14 -0800 Committer: Arnaldo Carvalho de Melo <[email protected]> CommitDate: Fri, 25 Jan 2019 15:12:09 +0100
perf machine: 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 required for nearly every operation dealing with machine->guests and threads->entries.
The conversion is straightforward, however, it's worth noticing that the rb_erase_init() calls have been replaced by rb_erase_cached() which has no _init() flavor, however, the node is explicitly cleared next anyway, which was redundant until now.
--- tools/perf/builtin-report.c | 3 ++- tools/perf/util/build-id.c | 12 ++++++---- tools/perf/util/machine.c | 53 ++++++++++++++++++++++++++------------------- tools/perf/util/machine.h | 12 +++++----- tools/perf/util/rb_resort.h | 6 ++--- 5 files changed, 50 insertions(+), 36 deletions(-)
tools/perf/builtin-report.c +2 -1
@@ -753,7 +753,8 @@ static int tasks_print(struct report *rep, FILE *fp)for (i =0 ; i <THREADS__TABLE_SIZE ; i++) {struct threads *threads = &machine->threads[i]; -for (nd =rb_first (&threads->entries); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&threads->entries); nd; + nd =rb_next (nd)) { task = tasks + itask++; task->thread = rb_entry(nd, struct thread, rb_node);
tools/perf/util/build-id.c +8 -4
@@ -364,7 +364,8 @@ int perf_session__write_buildid_table(struct perf_session *session,if (err)return err; -for (nd =rb_first (&session->machines.guests); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&session->machines.guests); nd; + nd =rb_next (nd)) { struct machine *pos = rb_entry(nd, struct machine, rb_node); err =machine__write_buildid_table (pos, fd);if (err)
@@ -397,7 +398,8 @@ int dsos__hit_all(struct perf_session *session)if (err)return err; -for (nd =rb_first (&session->machines.guests); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&session->machines.guests); nd; + nd =rb_next (nd)) { struct machine *pos = rb_entry(nd, struct machine, rb_node); err =machine__hit_all_dsos (pos);
@@ -850,7 +852,8 @@ int perf_session__cache_build_ids(struct perf_session *session) ret =machine__cache_build_ids (&session->machines.host); -for (nd =rb_first (&session->machines.guests); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&session->machines.guests); nd; + nd =rb_next (nd)) { struct machine *pos = rb_entry(nd, struct machine, rb_node); ret |=machine__cache_build_ids (pos); }
@@ -867,7 +870,8 @@ bool perf_session__read_build_ids(struct perf_session *session, bool with_hits)struct rb_node *nd;bool ret =machine__read_build_ids (&session->machines.host, with_hits); -for (nd =rb_first (&session->machines.guests); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&session->machines.guests); nd; + nd =rb_next (nd)) { struct machine *pos = rb_entry(nd, struct machine, rb_node); ret |=machine__read_build_ids (pos, with_hits); }
tools/perf/util/machine.c +31 -22
188 lines not on this page · raw message
tools/perf/util/machine.h +6 -6
@@ -29,11 +29,11 @@ struct vdso_info;#define THREADS__TABLE_SIZE (1 << THREADS__TABLE_BITS)struct threads { -struct rb_root entries; -struct rw_semaphore lock; -unsigned int nr; -struct list_head dead; -struct thread *last_match; +struct rb_root_cached entries; +struct rw_semaphore lock; +unsigned int nr; +struct list_head dead; +struct thread *last_match; };struct machine {
@@ -140,7 +140,7 @@ typedef void (*machine__process_t)(struct machine *machine, void *data);struct machines {struct machine host; -struct rb_root guests; +struct rb_root_cached guests; };void machines__init (struct machines *machines);
tools/perf/util/rb_resort.h +3 -3
@@ -144,8 +144,8 @@ struct __name##_sorted *__name = __name##_sorted__new __ilist->rblist.nr_entries)/* For 'struct machine->threads' */ -#define DECLARE_RESORT_RB_MACHINE_THREADS (__name, __machine, hash_bucket) \ - DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries, \ - __machine->threads[hash_bucket].nr) +#define DECLARE_RESORT_RB_MACHINE_THREADS (__name, __machine, hash_bucket) \ + DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries.rb_root, \ + __machine->threads[hash_bucket].nr)#endif /* _PERF_RESORT_RB_H_ */
PATCH v2 3/7 perf callchain: Use cached rbtrees
In reply to Davidlohr BuesoAt 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 nearly every in/srcline callchain node deletion (in/srcline__tree_delete()).
--- tools/perf/util/dso.c | 4 ++-- tools/perf/util/dso.h | 4 ++-- tools/perf/util/srcline.c | 43 +++++++++++++++++++++++++------------------ tools/perf/util/srcline.h | 13 +++++++------ 4 files changed, 36 insertions(+), 28 deletions(-)
tools/perf/util/dso.c +2 -2
@@ -1197,8 +1197,8 @@ struct dso *dso__new(const char *name)dso__set_short_name (dso, dso->name, false); dso->symbols = dso->symbol_names =RB_ROOT ; dso->data.cache =RB_ROOT ; - dso->inlined_nodes =RB_ROOT ; - dso->srclines =RB_ROOT ; + dso->inlined_nodes =RB_ROOT_CACHED ; + dso->srclines =RB_ROOT_CACHED ; dso->data.fd =-1 ; dso->data.status =DSO_DATA_STATUS_UNKNOWN ; dso->symtab_type =DSO_BINARY_TYPE__NOT_FOUND ;
tools/perf/util/dso.h +2 -2
@@ -142,8 +142,8 @@ struct dso {struct rb_root *root;/* root of rbtree that rb_node is in */ struct rb_root symbols;struct rb_root symbol_names; -struct rb_root inlined_nodes; -struct rb_root srclines; +struct rb_root_cached inlined_nodes; +struct rb_root_cached srclines;struct {u64 addr;struct symbol *symbol;
tools/perf/util/srcline.c +25 -18
110 lines not on this page · raw message
tools/perf/util/srcline.h +7 -6
@@ -18,11 +18,11 @@ char *__get_srcline(struct dso *dso, u64 addr, struct symbol *sym,void free_srcline (char *srcline);/* insert the srcline into the DSO, which will take ownership */ -void srcline__tree_insert (struct rb_root *tree,u64 addr,char *srcline); +void srcline__tree_insert (struct rb_root_cached *tree,u64 addr,char *srcline);/* find previously inserted srcline */ -char *srcline__tree_find (struct rb_root *tree,u64 addr); +char *srcline__tree_find (struct rb_root_cached *tree,u64 addr);/* delete all srclines within the tree */ -void srcline__tree_delete (struct rb_root *tree); +void srcline__tree_delete (struct rb_root_cached *tree);#define SRCLINE_UNKNOWN ((char *) "??:0")
@@ -45,10 +45,11 @@ struct inline_node *dso__parse_addr_inlines(struct dso *dso, u64 addr,void inline_node__delete (struct inline_node *node);/* insert the inline node list into the DSO, which will take ownership */ -void inlines__tree_insert (struct rb_root *tree,struct inline_node *inlines); +void inlines__tree_insert (struct rb_root_cached *tree, +struct inline_node *inlines);/* find previously inserted inline node list */ -struct inline_node *inlines__tree_find (struct rb_root *tree,u64 addr); +struct inline_node *inlines__tree_find (struct rb_root_cached *tree,u64 addr);/* delete all nodes within the tree of inline_node s */ -void inlines__tree_delete (struct rb_root *tree); +void inlines__tree_delete (struct rb_root_cached *tree);#endif /* PERF_SRCLINE_H */
Signature · 1 line
2.16.4
tip-bot for Davidlohr Bueso
merge bot[tip:perf/core] perf callchain: Use cached rbtrees
perf callchain: Use cached rbtrees
Commit-ID: 55ecd6310f9fe48cf7e435be408862da1e0e6baa Gitweb: https://git.kernel.org/tip/55ecd6310f9fe48cf7e435be408862da1e0e6baa Author: Davidlohr Bueso <[email protected]> AuthorDate: Thu, 6 Dec 2018 11:18:15 -0800 Committer: Arnaldo Carvalho de Melo <[email protected]> CommitDate: Fri, 25 Jan 2019 15:12:09 +0100
perf callchain: 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 required for nearly every in/srcline callchain node deletion (in/srcline__tree_delete()).
--- tools/perf/util/dso.c | 4 ++-- tools/perf/util/dso.h | 4 ++-- tools/perf/util/srcline.c | 43 +++++++++++++++++++++++++------------------ tools/perf/util/srcline.h | 13 +++++++------ 4 files changed, 36 insertions(+), 28 deletions(-)
tools/perf/util/dso.c +2 -2
@@ -1199,8 +1199,8 @@ struct dso *dso__new(const char *name)dso__set_short_name (dso, dso->name, false); dso->symbols = dso->symbol_names =RB_ROOT ; dso->data.cache =RB_ROOT ; - dso->inlined_nodes =RB_ROOT ; - dso->srclines =RB_ROOT ; + dso->inlined_nodes =RB_ROOT_CACHED ; + dso->srclines =RB_ROOT_CACHED ; dso->data.fd =-1 ; dso->data.status =DSO_DATA_STATUS_UNKNOWN ; dso->symtab_type =DSO_BINARY_TYPE__NOT_FOUND ;
tools/perf/util/dso.h +2 -2
@@ -143,8 +143,8 @@ struct dso {struct rb_root *root;/* root of rbtree that rb_node is in */ struct rb_root symbols;struct rb_root symbol_names; -struct rb_root inlined_nodes; -struct rb_root srclines; +struct rb_root_cached inlined_nodes; +struct rb_root_cached srclines;struct {u64 addr;struct symbol *symbol;
tools/perf/util/srcline.c +25 -18
110 lines not on this page · raw message
tools/perf/util/srcline.h +7 -6
@@ -19,11 +19,11 @@ void free_srcline(char *srcline);char *get_srcline_split (struct dso *dso,u64 addr,unsigned *line);/* insert the srcline into the DSO, which will take ownership */ -void srcline__tree_insert (struct rb_root *tree,u64 addr,char *srcline); +void srcline__tree_insert (struct rb_root_cached *tree,u64 addr,char *srcline);/* find previously inserted srcline */ -char *srcline__tree_find (struct rb_root *tree,u64 addr); +char *srcline__tree_find (struct rb_root_cached *tree,u64 addr);/* delete all srclines within the tree */ -void srcline__tree_delete (struct rb_root *tree); +void srcline__tree_delete (struct rb_root_cached *tree);#define SRCLINE_UNKNOWN ((char *) "??:0")
@@ -46,10 +46,11 @@ struct inline_node *dso__parse_addr_inlines(struct dso *dso, u64 addr,void inline_node__delete (struct inline_node *node);/* insert the inline node list into the DSO, which will take ownership */ -void inlines__tree_insert (struct rb_root *tree,struct inline_node *inlines); +void inlines__tree_insert (struct rb_root_cached *tree, +struct inline_node *inlines);/* find previously inserted inline node list */ -struct inline_node *inlines__tree_find (struct rb_root *tree,u64 addr); +struct inline_node *inlines__tree_find (struct rb_root_cached *tree,u64 addr);/* delete all nodes within the tree of inline_node s */ -void inlines__tree_delete (struct rb_root *tree); +void inlines__tree_delete (struct rb_root_cached *tree);#endif /* PERF_SRCLINE_H */
PATCH v2 4/7 perf util: Use cached rbtree for rblists
In reply to Davidlohr BuesoAt 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.
--- tools/perf/util/intlist.h | 2 +- tools/perf/util/metricgroup.c | 2 +- tools/perf/util/rb_resort.h | 2 +- tools/perf/util/rblist.c | 28 ++++++++++++++++++---------- tools/perf/util/rblist.h | 2 +- tools/perf/util/stat-shadow.c | 2 +- tools/perf/util/strlist.h | 2 +- 7 files changed, 24 insertions(+), 16 deletions(-)
tools/perf/util/intlist.h +1 -1
@@ -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)
tools/perf/util/metricgroup.c +1 -1
@@ -352,7 +352,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)
tools/perf/util/rb_resort.h +1 -1
@@ -140,7 +140,7 @@ struct __name##_sorted *__name = __name##_sorted__new/* For 'struct intlist' */ #define DECLARE_RESORT_RB_INTLIST (__name, __ilist) \ - DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries, \ + DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries.rb_root, \ __ilist->rblist.nr_entries)/* For 'struct machine->threads' */
tools/perf/util/rblist.c +18 -10
@@ -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,8 +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; + leftmost = false; + }else return -EEXIST ; }
@@ -35,7 +38,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 +46,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 +55,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,8 +67,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; + leftmost = false; + }else return parent; }
@@ -73,7 +79,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 +101,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 ; }
@@ -103,7 +110,7 @@ void rblist__init(struct rblist *rblist)void rblist__exit (struct rblist *rblist) { -struct rb_node *pos, *next =rb_first (&rblist->entries); +struct rb_node *pos, *next =rb_first_cached (&rblist->entries);while (next) { pos = next;
@@ -124,7 +131,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; }
tools/perf/util/rblist.h +1 -1
@@ -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);
tools/perf/util/stat-shadow.c +1 -1
@@ -168,7 +168,7 @@ static void reset_stat(struct runtime_stat *st)struct rb_node *pos, *next; rblist = &st->value_list; - next =rb_first (&rblist->entries); + next =rb_first_cached (&rblist->entries);while (next) { pos = next; next =rb_next (pos);
tools/perf/util/strlist.h +1 -1
@@ -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)
Signature · 1 line
2.16.4
tip-bot for Davidlohr Bueso
merge bot[tip:perf/core] perf util: Use cached rbtree for rblists
perf util: Use cached rbtree for rblists
Commit-ID: ca2270292e6c3415102242bf9dc3d05f622b7b28 Gitweb: https://git.kernel.org/tip/ca2270292e6c3415102242bf9dc3d05f622b7b28 Author: Davidlohr Bueso <[email protected]> AuthorDate: Thu, 6 Dec 2018 11:18:16 -0800 Committer: Arnaldo Carvalho de Melo <[email protected]> CommitDate: Fri, 25 Jan 2019 15:12:10 +0100
perf util: Use cached rbtree for rblists
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.
--- tools/perf/util/intlist.h | 2 +- tools/perf/util/metricgroup.c | 2 +- tools/perf/util/rb_resort.h | 2 +- tools/perf/util/rblist.c | 28 ++++++++++++++++++---------- tools/perf/util/rblist.h | 2 +- tools/perf/util/stat-shadow.c | 2 +- tools/perf/util/strlist.h | 2 +- 7 files changed, 24 insertions(+), 16 deletions(-)
tools/perf/util/intlist.h +1 -1
@@ -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)
tools/perf/util/metricgroup.c +1 -1
@@ -352,7 +352,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)
tools/perf/util/rb_resort.h +1 -1
@@ -140,7 +140,7 @@ struct __name##_sorted *__name = __name##_sorted__new/* For 'struct intlist' */ #define DECLARE_RESORT_RB_INTLIST (__name, __ilist) \ - DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries, \ + DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries.rb_root, \ __ilist->rblist.nr_entries)/* For 'struct machine->threads' */
tools/perf/util/rblist.c +18 -10
@@ -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,8 +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; + leftmost = false; + }else return -EEXIST ; }
@@ -35,7 +38,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 +46,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 +55,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,8 +67,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; + leftmost = false; + }else return parent; }
@@ -73,7 +79,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 +101,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 ; }
@@ -103,7 +110,7 @@ void rblist__init(struct rblist *rblist)void rblist__exit (struct rblist *rblist) { -struct rb_node *pos, *next =rb_first (&rblist->entries); +struct rb_node *pos, *next =rb_first_cached (&rblist->entries);while (next) { pos = next;
@@ -124,7 +131,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; }
tools/perf/util/rblist.h +1 -1
@@ -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);
tools/perf/util/stat-shadow.c +1 -1
@@ -168,7 +168,7 @@ static void reset_stat(struct runtime_stat *st)struct rb_node *pos, *next; rblist = &st->value_list; - next =rb_first (&rblist->entries); + next =rb_first_cached (&rblist->entries);while (next) { pos = next; next =rb_next (pos);
tools/perf/util/strlist.h +1 -1
@@ -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)
PATCH v2 5/7 perf symbols: Use cached rbtrees
In reply to Davidlohr BuesoAt the cost of an extra pointer, we can avoid the O(logN) cost of finding the first element in the tree (smallest node).
--- tools/perf/builtin-annotate.c | 2 +- tools/perf/util/dso.c | 4 +- tools/perf/util/dso.h | 6 +-- tools/perf/util/map.c | 8 ++-- tools/perf/util/probe-event.c | 3 +- tools/perf/util/symbol.c | 87 ++++++++++++++++++++++------------------ tools/perf/util/symbol.h | 13 +++--- tools/perf/util/symbol_fprintf.c | 2 +- 8 files changed, 67 insertions(+), 58 deletions(-)
tools/perf/builtin-annotate.c +1 -1
@@ -227,7 +227,7 @@ static int perf_evsel__add_sample(struct perf_evsel *evsel,* the DSO? */ if (al->sym !=NULL ) { -rb_erase (&al->sym->rb_node, +rb_erase_cached (&al->sym->rb_node, &al->map->dso->symbols);symbol__delete (al->sym);dso__reset_find_symbol_cache (al->map->dso);
tools/perf/util/dso.c +2 -2
@@ -1195,7 +1195,7 @@ struct dso *dso__new(const char *name)strcpy (dso->name, name);dso__set_long_name (dso, dso->name, false);dso__set_short_name (dso, dso->name, false); - dso->symbols = dso->symbol_names =RB_ROOT ; + dso->symbols = dso->symbol_names =RB_ROOT_CACHED ; dso->data.cache =RB_ROOT ; dso->inlined_nodes =RB_ROOT_CACHED ; dso->srclines =RB_ROOT_CACHED ;
@@ -1467,7 +1467,7 @@ size_t dso__fprintf(struct dso *dso, FILE *fp) ret +=fprintf (fp,"%sloaded, " ,dso__loaded (dso) ?"" :"NOT " ); ret +=dso__fprintf_buildid (dso, fp); ret +=fprintf (fp,")\n" ); -for (nd =rb_first (&dso->symbols); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&dso->symbols); nd; nd =rb_next (nd)) { struct symbol *pos = rb_entry(nd, struct symbol, rb_node); ret +=symbol__fprintf (pos, fp); }
tools/perf/util/dso.h +3 -3
@@ -140,8 +140,8 @@ struct dso {struct list_head node;struct rb_node rb_node;/* rbtree node sorted by long name */ struct rb_root *root;/* root of rbtree that rb_node is in */ -struct rb_root symbols; -struct rb_root symbol_names; +struct rb_root_cached symbols; +struct rb_root_cached symbol_names;struct rb_root_cached inlined_nodes;struct rb_root_cached srclines;struct {
@@ -235,7 +235,7 @@ bool dso__loaded(const struct dso *dso);static inline bool dso__has_symbols (const struct dso *dso) { -return !RB_EMPTY_ROOT (&dso->symbols); +return !RB_EMPTY_ROOT (&dso->symbols.rb_root); }bool dso__sorted_by_name (const struct dso *dso);
tools/perf/util/map.c +4 -4
@@ -285,8 +285,8 @@ void map__put(struct map *map)void map__fixup_start (struct map *map) { -struct rb_root *symbols = &map->dso->symbols; -struct rb_node *nd =rb_first (symbols); +struct rb_root_cached *symbols = &map->dso->symbols; +struct rb_node *nd =rb_first_cached (symbols);if (nd !=NULL ) { struct symbol *sym = rb_entry(nd, struct symbol, rb_node); map->start = sym->start;
@@ -295,8 +295,8 @@ void map__fixup_start(struct map *map)void map__fixup_end (struct map *map) { -struct rb_root *symbols = &map->dso->symbols; -struct rb_node *nd =rb_last (symbols); +struct rb_root_cached *symbols = &map->dso->symbols; +struct rb_node *nd =rb_last (&symbols->rb_root);if (nd !=NULL ) { struct symbol *sym = rb_entry(nd, struct symbol, rb_node); map->end = sym->end;
tools/perf/util/probe-event.c +2 -1
@@ -3528,7 +3528,8 @@ int show_available_funcs(const char *target, struct nsinfo *nsi,/* Show all (filtered) symbols */ setup_pager (); -for (nd =rb_first (&map->dso->symbol_names); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&map->dso->symbol_names); nd; + nd =rb_next (nd)) { struct symbol_name_rb_node *pos = rb_entry(nd, struct symbol_name_rb_node, rb_node);if (strfilter__compare (_filter, pos->sym.name))
tools/perf/util/symbol.c +47 -40
245 lines not on this page · raw message
tools/perf/util/symbol.h +7 -6
@@ -67,7 +67,7 @@ struct symbol { };void symbol__delete (struct symbol *sym); -void symbols__delete (struct rb_root *symbols); +void symbols__delete (struct rb_root_cached *symbols);/* symbols__for_each_entry - iterate over symbols (rb_root) *
@@ -76,7 +76,7 @@ void symbols__delete(struct rb_root *symbols);* @nd: the 'struct rb_node *' to use as a temporary storage */ #define symbols__for_each_entry (symbols, pos, nd) \ - for (nd = rb_first(symbols); \ + for (nd = rb_first_cached(symbols); \ nd && (pos = rb_entry(nd, struct symbol, rb_node)); \ nd = rb_next(nd))
@@ -309,10 +309,11 @@ int dso__synthesize_plt_symbols(struct dso *dso, struct symsrc *ss);char *dso__demangle_sym (struct dso *dso,int kmodule,const char *elf_name); -void __symbols__insert (struct rb_root *symbols,struct symbol *sym,bool kernel); -void symbols__insert (struct rb_root *symbols,struct symbol *sym); -void symbols__fixup_duplicate (struct rb_root *symbols); -void symbols__fixup_end (struct rb_root *symbols); +void __symbols__insert (struct rb_root_cached *symbols,struct symbol *sym, +bool kernel); +void symbols__insert (struct rb_root_cached *symbols,struct symbol *sym); +void symbols__fixup_duplicate (struct rb_root_cached *symbols); +void symbols__fixup_end (struct rb_root_cached *symbols);void map_groups__fixup_end (struct map_groups *mg);typedef int (*mapfn_t )(u64 start,u64 len,u64 pgoff,void *data);
tools/perf/util/symbol_fprintf.c +1 -1
@@ -64,7 +64,7 @@ size_t dso__fprintf_symbols_by_name(struct dso *dso,struct rb_node *nd;struct symbol_name_rb_node *pos; -for (nd =rb_first (&dso->symbol_names); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&dso->symbol_names); nd; nd =rb_next (nd)) { pos = rb_entry(nd, struct symbol_name_rb_node, rb_node);fprintf (fp,"%s\n" , pos->sym.name); }
Signature · 1 line
2.16.4
tip-bot for Davidlohr Bueso
merge bot[tip:perf/core] perf symbols: Use cached rbtrees
perf symbols: Use cached rbtrees
Commit-ID: 7137ff50b68a48bc28270c91b1c313259ab0c1c4 Gitweb: https://git.kernel.org/tip/7137ff50b68a48bc28270c91b1c313259ab0c1c4 Author: Davidlohr Bueso <[email protected]> AuthorDate: Thu, 6 Dec 2018 11:18:17 -0800 Committer: Arnaldo Carvalho de Melo <[email protected]> CommitDate: Fri, 25 Jan 2019 15:12:10 +0100
perf symbols: 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).
--- tools/perf/builtin-annotate.c | 2 +- tools/perf/util/dso.c | 4 +- tools/perf/util/dso.h | 6 +-- tools/perf/util/map.c | 8 ++-- tools/perf/util/probe-event.c | 3 +- tools/perf/util/symbol.c | 87 ++++++++++++++++++++++------------------ tools/perf/util/symbol.h | 13 +++--- tools/perf/util/symbol_fprintf.c | 2 +- 8 files changed, 67 insertions(+), 58 deletions(-)
tools/perf/builtin-annotate.c +1 -1
@@ -227,7 +227,7 @@ static int perf_evsel__add_sample(struct perf_evsel *evsel,* the DSO? */ if (al->sym !=NULL ) { -rb_erase (&al->sym->rb_node, +rb_erase_cached (&al->sym->rb_node, &al->map->dso->symbols);symbol__delete (al->sym);dso__reset_find_symbol_cache (al->map->dso);
tools/perf/util/dso.c +2 -2
@@ -1197,7 +1197,7 @@ struct dso *dso__new(const char *name)strcpy (dso->name, name);dso__set_long_name (dso, dso->name, false);dso__set_short_name (dso, dso->name, false); - dso->symbols = dso->symbol_names =RB_ROOT ; + dso->symbols = dso->symbol_names =RB_ROOT_CACHED ; dso->data.cache =RB_ROOT ; dso->inlined_nodes =RB_ROOT_CACHED ; dso->srclines =RB_ROOT_CACHED ;
@@ -1469,7 +1469,7 @@ size_t dso__fprintf(struct dso *dso, FILE *fp) ret +=fprintf (fp,"%sloaded, " ,dso__loaded (dso) ?"" :"NOT " ); ret +=dso__fprintf_buildid (dso, fp); ret +=fprintf (fp,")\n" ); -for (nd =rb_first (&dso->symbols); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&dso->symbols); nd; nd =rb_next (nd)) { struct symbol *pos = rb_entry(nd, struct symbol, rb_node); ret +=symbol__fprintf (pos, fp); }
tools/perf/util/dso.h +3 -3
@@ -141,8 +141,8 @@ struct dso {struct list_head node;struct rb_node rb_node;/* rbtree node sorted by long name */ struct rb_root *root;/* root of rbtree that rb_node is in */ -struct rb_root symbols; -struct rb_root symbol_names; +struct rb_root_cached symbols; +struct rb_root_cached symbol_names;struct rb_root_cached inlined_nodes;struct rb_root_cached srclines;struct {
@@ -236,7 +236,7 @@ bool dso__loaded(const struct dso *dso);static inline bool dso__has_symbols (const struct dso *dso) { -return !RB_EMPTY_ROOT (&dso->symbols); +return !RB_EMPTY_ROOT (&dso->symbols.rb_root); }bool dso__sorted_by_name (const struct dso *dso);
tools/perf/util/map.c +4 -4
@@ -286,8 +286,8 @@ void map__put(struct map *map)void map__fixup_start (struct map *map) { -struct rb_root *symbols = &map->dso->symbols; -struct rb_node *nd =rb_first (symbols); +struct rb_root_cached *symbols = &map->dso->symbols; +struct rb_node *nd =rb_first_cached (symbols);if (nd !=NULL ) { struct symbol *sym = rb_entry(nd, struct symbol, rb_node); map->start = sym->start;
@@ -296,8 +296,8 @@ void map__fixup_start(struct map *map)void map__fixup_end (struct map *map) { -struct rb_root *symbols = &map->dso->symbols; -struct rb_node *nd =rb_last (symbols); +struct rb_root_cached *symbols = &map->dso->symbols; +struct rb_node *nd =rb_last (&symbols->rb_root);if (nd !=NULL ) { struct symbol *sym = rb_entry(nd, struct symbol, rb_node); map->end = sym->end;
tools/perf/util/probe-event.c +2 -1
@@ -3529,7 +3529,8 @@ int show_available_funcs(const char *target, struct nsinfo *nsi,/* Show all (filtered) symbols */ setup_pager (); -for (nd =rb_first (&map->dso->symbol_names); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&map->dso->symbol_names); nd; + nd =rb_next (nd)) { struct symbol_name_rb_node *pos = rb_entry(nd, struct symbol_name_rb_node, rb_node);if (strfilter__compare (_filter, pos->sym.name))
tools/perf/util/symbol.c +47 -40
245 lines not on this page · raw message
tools/perf/util/symbol.h +7 -6
@@ -68,7 +68,7 @@ struct symbol { };void symbol__delete (struct symbol *sym); -void symbols__delete (struct rb_root *symbols); +void symbols__delete (struct rb_root_cached *symbols);/* symbols__for_each_entry - iterate over symbols (rb_root) *
@@ -77,7 +77,7 @@ void symbols__delete(struct rb_root *symbols);* @nd: the 'struct rb_node *' to use as a temporary storage */ #define symbols__for_each_entry (symbols, pos, nd) \ - for (nd = rb_first(symbols); \ + for (nd = rb_first_cached(symbols); \ nd && (pos = rb_entry(nd, struct symbol, rb_node)); \ nd = rb_next(nd))
@@ -247,10 +247,11 @@ int dso__synthesize_plt_symbols(struct dso *dso, struct symsrc *ss);char *dso__demangle_sym (struct dso *dso,int kmodule,const char *elf_name); -void __symbols__insert (struct rb_root *symbols,struct symbol *sym,bool kernel); -void symbols__insert (struct rb_root *symbols,struct symbol *sym); -void symbols__fixup_duplicate (struct rb_root *symbols); -void symbols__fixup_end (struct rb_root *symbols); +void __symbols__insert (struct rb_root_cached *symbols,struct symbol *sym, +bool kernel); +void symbols__insert (struct rb_root_cached *symbols,struct symbol *sym); +void symbols__fixup_duplicate (struct rb_root_cached *symbols); +void symbols__fixup_end (struct rb_root_cached *symbols);void map_groups__fixup_end (struct map_groups *mg);typedef int (*mapfn_t )(u64 start,u64 len,u64 pgoff,void *data);
tools/perf/util/symbol_fprintf.c +1 -1
@@ -65,7 +65,7 @@ size_t dso__fprintf_symbols_by_name(struct dso *dso,struct rb_node *nd;struct symbol_name_rb_node *pos; -for (nd =rb_first (&dso->symbol_names); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&dso->symbol_names); nd; nd =rb_next (nd)) { pos = rb_entry(nd, struct symbol_name_rb_node, rb_node);fprintf (fp,"%s\n" , pos->sym.name); }
PATCH v2 6/7 perf hist: Use cached rbtrees
In reply to Davidlohr BuesoAt 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_arrayhist::entries_inhist::entrieshist::entries_collapsedhist_entry::hroot_inhist_entry::hroot_out
--- tools/perf/builtin-annotate.c | 2 +- tools/perf/builtin-c2c.c | 6 +- tools/perf/builtin-diff.c | 10 +- tools/perf/builtin-top.c | 2 +- tools/perf/tests/hists_common.c | 8 +- tools/perf/tests/hists_cumulate.c | 14 +-- tools/perf/tests/hists_link.c | 8 +- tools/perf/tests/hists_output.c | 32 +++--- tools/perf/ui/browsers/hists.c | 6 +- tools/perf/ui/gtk/hists.c | 4 +- tools/perf/ui/stdio/hist.c | 3 +- tools/perf/util/hist.c | 199 +++++++++++++++++++++----------------- tools/perf/util/hist.h | 10 +- tools/perf/util/sort.h | 4 +- 14 files changed, 167 insertions(+), 141 deletions(-)
tools/perf/builtin-annotate.c +1 -1
@@ -305,7 +305,7 @@ static void hists__find_annotations(struct hists *hists,struct perf_evsel *evsel, struct perf_annotate *ann) { - struct rb_node *nd = rb_first(&hists->entries), *next; + struct rb_node *nd = rb_first_cached(&hists->entries), *next;int key =K_RIGHT ;while (nd) {
tools/perf/builtin-c2c.c +3 -3
@@ -2088,7 +2088,7 @@ static int resort_hitm_cb(struct hist_entry *he)static int hists__iterate_cb (struct hists *hists,hists__resort_cb_t cb) { -struct rb_node *next =rb_first (&hists->entries); +struct rb_node *next =rb_first_cached (&hists->entries);int ret =0 ;while (next) {
@@ -2215,7 +2215,7 @@ static void print_pareto(FILE *out)if (WARN_ONCE (ret,"failed to setup sort entries\n" ))return ; - nd =rb_first (&c2c.hists.hists.entries); + nd =rb_first_cached (&c2c.hists.hists.entries);for (; nd; nd =rb_next (nd)) { struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
@@ -2283,7 +2283,7 @@ static void perf_c2c__hists_fprintf(FILE *out, struct perf_session *session)static void c2c_browser__update_nr_entries (struct hist_browser *hb) {u64 nr_entries =0 ; -struct rb_node *nd =rb_first (&hb->hists->entries); +struct rb_node *nd =rb_first_cached (&hb->hists->entries);while (nd) { struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
tools/perf/builtin-diff.c +5 -5
@@ -429,7 +429,7 @@ get_pair_fmt(struct hist_entry *he, struct diff_hpp_fmt *dfmt)static void hists__baseline_only (struct hists *hists) { -struct rb_root *root; +struct rb_root_cached *root;struct rb_node *next;if (hists__has (hists, need_collapse))
@@ -437,13 +437,13 @@ static void hists__baseline_only(struct hists *hists)else root = hists->entries_in; - next =rb_first (root); + next =rb_first_cached (root);while (next !=NULL ) { struct hist_entry *he = rb_entry(next, struct hist_entry, rb_node_in); next =rb_next (&he->rb_node_in);if (!hist_entry__next_pair (he)) { -rb_erase (&he->rb_node_in, root); +rb_erase_cached (&he->rb_node_in, root);hist_entry__delete (he); } }
@@ -451,7 +451,7 @@ static void hists__baseline_only(struct hists *hists)static void hists__precompute (struct hists *hists) { -struct rb_root *root; +struct rb_root_cached *root;struct rb_node *next;if (hists__has (hists, need_collapse))
@@ -459,7 +459,7 @@ static void hists__precompute(struct hists *hists)else root = hists->entries_in; - next =rb_first (root); + next =rb_first_cached (root);while (next !=NULL ) {struct hist_entry *he, *pair;struct data__file *d;
tools/perf/builtin-top.c +1 -1
@@ -367,7 +367,7 @@ static void perf_top__prompt_symbol(struct perf_top *top, const char *msg)if (p) *p =0 ; - next =rb_first (&hists->entries); + next =rb_first_cached (&hists->entries);while (next) { n = rb_entry(next, struct hist_entry, rb_node);if (n->ms.sym && !strcmp (buf, n->ms.sym->name)) {
tools/perf/tests/hists_common.c +4 -4
@@ -161,7 +161,7 @@ struct machine *setup_fake_machine(struct machines *machines)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;
tools/perf/tests/hists_cumulate.c +7 -7
@@ -125,8 +125,8 @@ static int add_hist_entries(struct hists *hists, struct machine *machine)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_expecprint_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++) {
tools/perf/tests/hists_link.c +4 -4
@@ -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;
tools/perf/tests/hists_output.c +16 -16
@@ -91,8 +91,8 @@ static int add_hist_entries(struct hists *hists, struct machine *machine)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",
tools/perf/ui/browsers/hists.c +3 -3
@@ -49,7 +49,7 @@ static int hist_browser__get_folding(struct hist_browser *browser)struct hists *hists = browser->hists;int unfolded_rows =0 ; -for (nd =rb_first (&hists->entries); +for (nd =rb_first_cached (&hists->entries); (nd =hists__filter_entries (nd, browser->min_pcnt)) !=NULL ; nd =rb_hierarchy_next (nd)) { struct hist_entry *he =
@@ -267,7 +267,7 @@ static int hierarchy_count_rows(struct hist_browser *hb, struct hist_entry *he,if (he->has_no_entry)return 1 ; - node =rb_first (&he->hroot_out); + node =rb_first_cached (&he->hroot_out);while (node) {float percent;
@@ -372,7 +372,7 @@ static void hist_entry__init_have_children(struct hist_entry *he) he->has_children = !RB_EMPTY_ROOT (&he->sorted_chain);callchain__init_have_children (&he->sorted_chain); }else { - he->has_children = !RB_EMPTY_ROOT (&he->hroot_out); + he->has_children = !RB_EMPTY_ROOT (&he->hroot_out.rb_root); } he->init_have_children = true;
tools/perf/ui/gtk/hists.c +2 -2
@@ -353,7 +353,7 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,g_object_unref (GTK_TREE_MODEL (store)); -for (nd =rb_first (&hists->entries); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&hists->entries); nd; nd =rb_next (nd)) { struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);GtkTreeIter iter;u64 total =hists__total_period (h->hists);
@@ -578,7 +578,7 @@ static void perf_gtk__show_hierarchy(GtkWidget *window, struct hists *hists,gtk_tree_view_set_model (GTK_TREE_VIEW (view),GTK_TREE_MODEL (store));g_object_unref (GTK_TREE_MODEL (store)); -perf_gtk__add_hierarchy_entries (hists, &hists->entries, store, +perf_gtk__add_hierarchy_entries (hists, &hists->entries.rb_root, store,NULL , &hpp, min_pcnt);gtk_tree_view_set_rules_hint (GTK_TREE_VIEW (view), TRUE);
tools/perf/ui/stdio/hist.c +2 -1
@@ -788,7 +788,8 @@ size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows, indent =hists__overhead_width (hists) +4 ; -for (nd =rb_first (&hists->entries); nd; nd =__rb_hierarchy_next (nd,HMD_FORCE_CHILD )) { +for (nd =rb_first_cached (&hists->entries); nd; + nd =__rb_hierarchy_next (nd,HMD_FORCE_CHILD )) { struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);float percent;
tools/perf/util/hist.c +112 -87
614 lines not on this page · raw message
tools/perf/util/hist.h +5 -5
@@ -69,10 +69,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;
@@ -229,7 +229,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;
tools/perf/util/sort.h +2 -2
@@ -145,8 +145,8 @@ struct hist_entry {union {/* this is for hierarchical entry structure */ struct { -struct rb_root hroot_in; -struct rb_root hroot_out; +struct rb_root_cached hroot_in; +struct rb_root_cached hroot_out; };/* non-leaf entries */ struct rb_root sorted_chain;/* leaf entry has callchains */ };
Signature · 1 line
2.16.4
Arnaldo Carvalho de Melo
maintainerRe: [PATCH 6/7] perf hist: Use cached rbtrees
Em Thu, Dec 06, 2018 at 11:18:18AM -0800, Davidlohr Bueso escreveu:
Quoted 11 lines
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_arrayhist::entries_inhist::entrieshist::entries_collapsedhist_entry::hroot_inhist_entry::hroot_out
CC /tmp/build/perf/util/hist.oui/browsers/hists.c: In function ‘hierarchy_set_folding’:ui/browsers/hists.c:511:21: error: passing argument 1 of ‘rb_first’ from incompatible pointer type [-Werror=incompatible-pointer-types]
for (nd = rb_first(&he->hroot_out); nd; nd = rb_next(nd)) {
^~~~~~~~~~~~~~
In file included from ui/browsers/hists.c:8:
/home/acme/git/perf/tools/include/linux/rbtree.h:83:24: note: expected ‘const struct rb_root *’ but argument is of type ‘struct rb_root_cached *’
extern struct rb_node *rb_first(const struct rb_root *);
^~~~~~~~
ui/browsers/hists.c: In function ‘__hist_browser__set_folding’:
ui/browsers/hists.c:569:16: error: passing argument 1 of ‘rb_first’ from incompatible pointer type [-Werror=incompatible-pointer-types]
nd = rb_first(&browser->hists->entries);
^~~~~~~~~~~~~~~~~~~~~~~~So I added this on top, please check:
tools/perf/ui/browsers/hists.c +5 -5
@@ -508,7 +508,7 @@ static int hierarchy_set_folding(struct hist_browser *hb, struct hist_entry *he,struct hist_entry *child;int n =0 ; -for (nd =rb_first (&he->hroot_out); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&he->hroot_out); nd; nd =rb_next (nd)) { child = rb_entry(nd, struct hist_entry, rb_node); percent =hist_entry__get_percent_limit (child);if (!child->filtered && percent >= hb->min_pcnt)
@@ -566,7 +566,7 @@ __hist_browser__set_folding(struct hist_browser *browser, bool unfold)struct rb_node *nd;struct hist_entry *he; - nd =rb_first (&browser->hists->entries); + nd =rb_first_cached (&browser->hists->entries);while (nd) { he = rb_entry(nd, struct hist_entry, rb_node);
@@ -1738,7 +1738,7 @@ static void ui_browser__hists_init_top(struct ui_browser *browser)struct hist_browser *hb; hb = container_of(browser, struct hist_browser, b); - browser->top =rb_first (&hb->hists->entries); + browser->top =rb_first_cached (&hb->hists->entries); } }
@@ -2649,7 +2649,7 @@ add_socket_opt(struct hist_browser *browser, struct popup_action *act,static void hist_browser__update_nr_entries (struct hist_browser *hb) {u64 nr_entries =0 ; -struct rb_node *nd =rb_first (&hb->hists->entries); +struct rb_node *nd =rb_first_cached (&hb->hists->entries);if (hb->min_pcnt ==0 && !symbol_conf.report_hierarchy) { hb->nr_non_filtered_entries = hb->hists->nr_non_filtered_entries;
@@ -2669,7 +2669,7 @@ static void hist_browser__update_percent_limit(struct hist_browser *hb, double percent) {struct hist_entry *he; -struct rb_node *nd =rb_first (&hb->hists->entries); +struct rb_node *nd =rb_first_cached (&hb->hists->entries);u64 total =hists__total_period (hb->hists);u64 min_callchain_hits = total * (percent /100 );
tools/perf/ui/gtk/hists.c +3 -3
@@ -401,7 +401,7 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists, } static void perf_gtk__add_hierarchy_entries(struct hists *hists, - struct rb_root *root, + struct rb_root_cached *root, GtkTreeStore *store, GtkTreeIter *parent, struct perf_hpp *hpp,
@@ -415,7 +415,7 @@ static void perf_gtk__add_hierarchy_entries(struct hists *hists,u64 total =hists__total_period (hists);int size; -for (node =rb_first (root); node; node =rb_next (node)) { +for (node =rb_first_cached (root); node; node =rb_next (node)) {GtkTreeIter iter;float percent;char *bf;
@@ -578,7 +578,7 @@ static void perf_gtk__show_hierarchy(GtkWidget *window, struct hists *hists,gtk_tree_view_set_model (GTK_TREE_VIEW (view),GTK_TREE_MODEL (store));g_object_unref (GTK_TREE_MODEL (store)); -perf_gtk__add_hierarchy_entries (hists, &hists->entries.rb_root, store, +perf_gtk__add_hierarchy_entries (hists, &hists->entries, store,NULL , &hpp, min_pcnt);gtk_tree_view_set_rules_hint (GTK_TREE_VIEW (view), TRUE);
Re: [PATCH 6/7] perf hist: Use cached rbtrees
Quoted 27 lines · Arnaldo Carvalho de Melo
Em Thu, Dec 06, 2018 at 11:18:18AM -0800, Davidlohr Bueso escreveu:
Quoted 11 lines
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_arrayhist::entries_inhist::entrieshist::entries_collapsedhist_entry::hroot_inhist_entry::hroot_outCC
/tmp/build/perf/util/hist.oui/browsers/hists.c: In function ???hierarchy_set_folding???:ui/browsers/hists.c:511:21: error: passing argument 1 of ???rb_first??? from incompatible pointer type [-Werror=incompatible-pointer-types]for (nd = rb_first(&he->hroot_out); nd; nd = rb_next(nd)) { ^~~~~~~~~~~~~~ In file included from ui/browsers/hists.c:8: /home/acme/git/perf/tools/include/linux/rbtree.h:83:24: note: expected ???const struct rb_root *??? but argument is of type ???struct rb_root_cached *??? extern struct rb_node *rb_first(const struct rb_root *); ^~~~~~~~ ui/browsers/hists.c: In function ???__hist_browser__set_folding???: ui/browsers/hists.c:569:16: error: passing argument 1 of ???rb_first??? from incompatible pointer type [-Werror=incompatible-pointer-types] nd = rb_first(&browser->hists->entries); ^~~~~~~~~~~~~~~~~~~~~~~~
Quoted 1 line
So I added this on top, please check:
Looks good thanks (sorry I thought I had tested all this -- even ran perf several times :/)
Thanks,
Davidlohr
tip-bot for Davidlohr Bueso
merge bot[tip:perf/core] perf hist: Use cached rbtrees
In reply to Davidlohr Buesoperf hist: Use cached rbtrees
Commit-ID: 2eb3d6894ae3b9cc8a94c91458a041c45773f23d Gitweb: https://git.kernel.org/tip/2eb3d6894ae3b9cc8a94c91458a041c45773f23d Author: Davidlohr Bueso <[email protected]> AuthorDate: Thu, 6 Dec 2018 11:18:18 -0800 Committer: Arnaldo Carvalho de Melo <[email protected]> CommitDate: Fri, 25 Jan 2019 15:12:10 +0100
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_arrayhist::entries_inhist::entrieshist::entries_collapsedhist_entry::hroot_inhist_entry::hroot_out
--- tools/perf/builtin-annotate.c | 2 +- tools/perf/builtin-c2c.c | 6 +- tools/perf/builtin-diff.c | 10 +- tools/perf/builtin-top.c | 2 +- tools/perf/tests/hists_common.c | 8 +- tools/perf/tests/hists_cumulate.c | 14 +-- tools/perf/tests/hists_link.c | 8 +- tools/perf/tests/hists_output.c | 32 +++--- tools/perf/ui/browsers/hists.c | 16 +-- tools/perf/ui/gtk/hists.c | 6 +- tools/perf/ui/stdio/hist.c | 3 +- tools/perf/util/hist.c | 199 +++++++++++++++++++++----------------- tools/perf/util/hist.h | 10 +- tools/perf/util/sort.h | 4 +- 14 files changed, 173 insertions(+), 147 deletions(-)
tools/perf/builtin-annotate.c +1 -1
@@ -305,7 +305,7 @@ static void hists__find_annotations(struct hists *hists,struct perf_evsel *evsel, struct perf_annotate *ann) { - struct rb_node *nd = rb_first(&hists->entries), *next; + struct rb_node *nd = rb_first_cached(&hists->entries), *next;int key =K_RIGHT ;while (nd) {
tools/perf/builtin-c2c.c +3 -3
@@ -2088,7 +2088,7 @@ static int resort_hitm_cb(struct hist_entry *he)static int hists__iterate_cb (struct hists *hists,hists__resort_cb_t cb) { -struct rb_node *next =rb_first (&hists->entries); +struct rb_node *next =rb_first_cached (&hists->entries);int ret =0 ;while (next) {
@@ -2215,7 +2215,7 @@ static void print_pareto(FILE *out)if (WARN_ONCE (ret,"failed to setup sort entries\n" ))return ; - nd =rb_first (&c2c.hists.hists.entries); + nd =rb_first_cached (&c2c.hists.hists.entries);for (; nd; nd =rb_next (nd)) { struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
@@ -2283,7 +2283,7 @@ static void perf_c2c__hists_fprintf(FILE *out, struct perf_session *session)static void c2c_browser__update_nr_entries (struct hist_browser *hb) {u64 nr_entries =0 ; -struct rb_node *nd =rb_first (&hb->hists->entries); +struct rb_node *nd =rb_first_cached (&hb->hists->entries);while (nd) { struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
tools/perf/builtin-diff.c +5 -5
@@ -429,7 +429,7 @@ get_pair_fmt(struct hist_entry *he, struct diff_hpp_fmt *dfmt)static void hists__baseline_only (struct hists *hists) { -struct rb_root *root; +struct rb_root_cached *root;struct rb_node *next;if (hists__has (hists, need_collapse))
@@ -437,13 +437,13 @@ static void hists__baseline_only(struct hists *hists)else root = hists->entries_in; - next =rb_first (root); + next =rb_first_cached (root);while (next !=NULL ) { struct hist_entry *he = rb_entry(next, struct hist_entry, rb_node_in); next =rb_next (&he->rb_node_in);if (!hist_entry__next_pair (he)) { -rb_erase (&he->rb_node_in, root); +rb_erase_cached (&he->rb_node_in, root);hist_entry__delete (he); } }
@@ -451,7 +451,7 @@ static void hists__baseline_only(struct hists *hists)static void hists__precompute (struct hists *hists) { -struct rb_root *root; +struct rb_root_cached *root;struct rb_node *next;if (hists__has (hists, need_collapse))
@@ -459,7 +459,7 @@ static void hists__precompute(struct hists *hists)else root = hists->entries_in; - next =rb_first (root); + next =rb_first_cached (root);while (next !=NULL ) {struct hist_entry *he, *pair;struct data__file *d;
tools/perf/builtin-top.c +1 -1
@@ -367,7 +367,7 @@ static void perf_top__prompt_symbol(struct perf_top *top, const char *msg)if (p) *p =0 ; - next =rb_first (&hists->entries); + next =rb_first_cached (&hists->entries);while (next) { n = rb_entry(next, struct hist_entry, rb_node);if (n->ms.sym && !strcmp (buf, n->ms.sym->name)) {
tools/perf/tests/hists_common.c +4 -4
@@ -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;
tools/perf/tests/hists_cumulate.c +7 -7
@@ -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_expecprint_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++) {
tools/perf/tests/hists_link.c +4 -4
@@ -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;
tools/perf/tests/hists_output.c +16 -16
@@ -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",
tools/perf/ui/browsers/hists.c +8 -8
@@ -49,7 +49,7 @@ static int hist_browser__get_folding(struct hist_browser *browser)struct hists *hists = browser->hists;int unfolded_rows =0 ; -for (nd =rb_first (&hists->entries); +for (nd =rb_first_cached (&hists->entries); (nd =hists__filter_entries (nd, browser->min_pcnt)) !=NULL ; nd =rb_hierarchy_next (nd)) { struct hist_entry *he =
@@ -267,7 +267,7 @@ static int hierarchy_count_rows(struct hist_browser *hb, struct hist_entry *he,if (he->has_no_entry)return 1 ; - node =rb_first (&he->hroot_out); + node =rb_first_cached (&he->hroot_out);while (node) {float percent;
@@ -372,7 +372,7 @@ static void hist_entry__init_have_children(struct hist_entry *he) he->has_children = !RB_EMPTY_ROOT (&he->sorted_chain);callchain__init_have_children (&he->sorted_chain); }else { - he->has_children = !RB_EMPTY_ROOT (&he->hroot_out); + he->has_children = !RB_EMPTY_ROOT (&he->hroot_out.rb_root); } he->init_have_children = true;
@@ -508,7 +508,7 @@ static int hierarchy_set_folding(struct hist_browser *hb, struct hist_entry *he,struct hist_entry *child;int n =0 ; -for (nd =rb_first (&he->hroot_out); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&he->hroot_out); nd; nd =rb_next (nd)) { child = rb_entry(nd, struct hist_entry, rb_node); percent =hist_entry__get_percent_limit (child);if (!child->filtered && percent >= hb->min_pcnt)
@@ -566,7 +566,7 @@ __hist_browser__set_folding(struct hist_browser *browser, bool unfold)struct rb_node *nd;struct hist_entry *he; - nd =rb_first (&browser->hists->entries); + nd =rb_first_cached (&browser->hists->entries);while (nd) { he = rb_entry(nd, struct hist_entry, rb_node);
@@ -1738,7 +1738,7 @@ static void ui_browser__hists_init_top(struct ui_browser *browser)struct hist_browser *hb; hb = container_of(browser, struct hist_browser, b); - browser->top =rb_first (&hb->hists->entries); + browser->top =rb_first_cached (&hb->hists->entries); } }
@@ -2649,7 +2649,7 @@ add_socket_opt(struct hist_browser *browser, struct popup_action *act,static void hist_browser__update_nr_entries (struct hist_browser *hb) {u64 nr_entries =0 ; -struct rb_node *nd =rb_first (&hb->hists->entries); +struct rb_node *nd =rb_first_cached (&hb->hists->entries);if (hb->min_pcnt ==0 && !symbol_conf.report_hierarchy) { hb->nr_non_filtered_entries = hb->hists->nr_non_filtered_entries;
@@ -2669,7 +2669,7 @@ static void hist_browser__update_percent_limit(struct hist_browser *hb, double percent) {struct hist_entry *he; -struct rb_node *nd =rb_first (&hb->hists->entries); +struct rb_node *nd =rb_first_cached (&hb->hists->entries);u64 total =hists__total_period (hb->hists);u64 min_callchain_hits = total * (percent /100 );
tools/perf/ui/gtk/hists.c +3 -3
@@ -353,7 +353,7 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists,g_object_unref (GTK_TREE_MODEL (store)); -for (nd =rb_first (&hists->entries); nd; nd =rb_next (nd)) { +for (nd =rb_first_cached (&hists->entries); nd; nd =rb_next (nd)) { struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);GtkTreeIter iter;u64 total =hists__total_period (h->hists);
@@ -401,7 +401,7 @@ static void perf_gtk__show_hists(GtkWidget *window, struct hists *hists, } static void perf_gtk__add_hierarchy_entries(struct hists *hists, - struct rb_root *root, + struct rb_root_cached *root, GtkTreeStore *store, GtkTreeIter *parent, struct perf_hpp *hpp,
@@ -415,7 +415,7 @@ static void perf_gtk__add_hierarchy_entries(struct hists *hists,u64 total =hists__total_period (hists);int size; -for (node =rb_first (root); node; node =rb_next (node)) { +for (node =rb_first_cached (root); node; node =rb_next (node)) {GtkTreeIter iter;float percent;char *bf;
tools/perf/ui/stdio/hist.c +2 -1
@@ -788,7 +788,8 @@ size_t hists__fprintf(struct hists *hists, bool show_header, int max_rows, indent =hists__overhead_width (hists) +4 ; -for (nd =rb_first (&hists->entries); nd; nd =__rb_hierarchy_next (nd,HMD_FORCE_CHILD )) { +for (nd =rb_first_cached (&hists->entries); nd; + nd =__rb_hierarchy_next (nd,HMD_FORCE_CHILD )) { struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);float percent;
tools/perf/util/hist.c +112 -87
614 lines not on this page · raw message
tools/perf/util/hist.h +5 -5
@@ -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;
tools/perf/util/sort.h +2 -2
@@ -145,8 +145,8 @@ struct hist_entry {union {/* this is for hierarchical entry structure */ struct { -struct rb_root hroot_in; -struct rb_root hroot_out; +struct rb_root_cached hroot_in; +struct rb_root_cached hroot_out; };/* non-leaf entries */ struct rb_root sorted_chain;/* leaf entry has callchains */ };
PATCH v2 7/7 perf sched: Use cached rbtrees
In reply to Davidlohr BuesoAt 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 perf-sched.
--- tools/perf/builtin-sched.c | 45 +++++++++++++++++++++++++-------------------- 1 file changed, 25 insertions(+), 20 deletions(-)
tools/perf/builtin-sched.c +25 -20
@@ -213,7 +213,7 @@ struct perf_sched {u64 all_runtime;u64 all_count;u64 cpu_last_switched[MAX_CPUS ]; -struct rb_root atom_root, sorted_atom_root, merged_atom_root; +struct rb_root_cached atom_root, sorted_atom_root, merged_atom_root;struct list_head sort_list, cmp_pid;bool force;bool skip_merge;
@@ -271,7 +271,7 @@ struct evsel_runtime {struct idle_thread_runtime {struct thread_runtime tr;struct thread *last_thread; -struct rb_root sorted_root; +struct rb_root_cached sorted_root;struct callchain_root callchain;struct callchain_cursor cursor; };
@@ -950,10 +950,10 @@ thread_lat_cmp(struct list_head *list, struct work_atoms *l, struct work_atoms * }static struct work_atoms * -thread_atoms_search (struct rb_root *root,struct thread *thread, +thread_atoms_search (struct rb_root_cached *root,struct thread *thread,struct list_head *sort_list) { -struct rb_node *node = root->rb_node; +struct rb_node *node = root->rb_root.rb_node;struct work_atoms key = { .thread = thread };while (node) {
@@ -976,10 +976,11 @@ thread_atoms_search(struct rb_root *root, struct thread *thread, }static void -__thread_latency_insert (struct rb_root *root,struct work_atoms *data, +__thread_latency_insert (struct rb_root_cached *root,struct work_atoms *data,struct list_head *sort_list) { -struct rb_node **new = &(root->rb_node), *parent =NULL ; +struct rb_node **new = &(root->rb_root.rb_node), *parent =NULL ; +bool leftmost = true;while (*new) {struct work_atoms *this;
@@ -992,12 +993,14 @@ __thread_latency_insert(struct rb_root *root, struct work_atoms *data,if (cmp >0 ) new = &((*new)->rb_left); -else +else { new = &((*new)->rb_right); + leftmost = false; + } }rb_link_node (&data->node, parent, new); -rb_insert_color (&data->node, root); +rb_insert_color_cached (&data->node, root, leftmost); }static int thread_atoms_insert (struct perf_sched *sched,struct thread *thread)
@@ -1447,15 +1450,15 @@ static int sort_dimension__add(const char *tok, struct list_head *list)static void perf_sched__sort_lat (struct perf_sched *sched) {struct rb_node *node; -struct rb_root *root = &sched->atom_root; +struct rb_root_cached *root = &sched->atom_root; again:for (;;) {struct work_atoms *data; - node =rb_first (root); + node =rb_first_cached (root);if (!node)break ; -rb_erase (node, root); +rb_erase_cached (node, root); data = rb_entry(node, struct work_atoms, node);__thread_latency_insert (&sched->sorted_atom_root, data, &sched->sort_list); }
@@ -2762,12 +2765,12 @@ static size_t callchain__fprintf_folded(FILE *fp, struct callchain_node *node)return ret; } -static size_t timehist_print_idlehist_callchain (struct rb_root *root) +static size_t timehist_print_idlehist_callchain (struct rb_root_cached *root) {size_t ret =0 ;FILE *fp = stdout;struct callchain_node *chain; -struct rb_node *rb_node =rb_first (root); +struct rb_node *rb_node =rb_first_cached (root);printf (" %16s %8s %s\n" ,"Idle time (msec)" ,"Count" ,"Callchains" ); printf(" %.16s %.8s %.50s\n", graph_dotted_line, graph_dotted_line,
@@ -2868,7 +2871,7 @@ static void timehist_print_summary(struct perf_sched *sched,if (itr ==NULL )continue ; - callchain_param.sort (&itr->sorted_root, &itr->callchain, + callchain_param.sort (&itr->sorted_root.rb_root, &itr->callchain,0 , &callchain_param);printf (" CPU %2d:" , i);
@@ -3074,11 +3077,12 @@ static void print_bad_events(struct perf_sched *sched) } } -static void __merge_work_atoms (struct rb_root *root,struct work_atoms *data) +static void __merge_work_atoms (struct rb_root_cached *root,struct work_atoms *data) { -struct rb_node **new = &(root->rb_node), *parent =NULL ; +struct rb_node **new = &(root->rb_root.rb_node), *parent =NULL ;struct work_atoms *this;const char *comm =thread__comm_str (data->thread), *this_comm; +bool leftmost = true;while (*new) {int cmp;
@@ -3092,6 +3096,7 @@ static void __merge_work_atoms(struct rb_root *root, struct work_atoms *data) new = &((*new)->rb_left); }else if (cmp <0 ) { new = &((*new)->rb_right); + leftmost = false; }else { this->num_merged++; this->total_runtime += data->total_runtime;
@@ -3109,7 +3114,7 @@ static void __merge_work_atoms(struct rb_root *root, struct work_atoms *data) data->num_merged++;rb_link_node (&data->node, parent, new); -rb_insert_color (&data->node, root); +rb_insert_color_cached (&data->node, root, leftmost); }static void perf_sched__merge_lat (struct perf_sched *sched)
@@ -3120,8 +3125,8 @@ static void perf_sched__merge_lat(struct perf_sched *sched)if (sched->skip_merge)return ; -while ((node =rb_first (&sched->atom_root))) { -rb_erase (node, &sched->atom_root); +while ((node =rb_first_cached (&sched->atom_root))) { +rb_erase_cached (node, &sched->atom_root); data = rb_entry(node, struct work_atoms, node);__merge_work_atoms (&sched->merged_atom_root, data); }
@@ -3143,7 +3148,7 @@ static int perf_sched__lat(struct perf_sched *sched)printf (" Task | Runtime ms | Switches | Average delay ms | Maximum delay ms | Maximum delay at |\n" );printf (" -----------------------------------------------------------------------------------------------------------------\n" ); - next =rb_first (&sched->sorted_atom_root); + next =rb_first_cached (&sched->sorted_atom_root);while (next) {struct work_atoms *work_list;
Signature · 1 line
2.16.4
tip-bot for Davidlohr Bueso
merge bot[tip:perf/core] perf sched: Use cached rbtrees
perf sched: Use cached rbtrees
Commit-ID: cb4c13a5137766c3666ae106e1a5549316992379 Gitweb: https://git.kernel.org/tip/cb4c13a5137766c3666ae106e1a5549316992379 Author: Davidlohr Bueso <[email protected]> AuthorDate: Thu, 6 Dec 2018 11:18:19 -0800 Committer: Arnaldo Carvalho de Melo <[email protected]> CommitDate: Fri, 25 Jan 2019 15:12:10 +0100
perf sched: 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 perf-sched.
--- tools/perf/builtin-sched.c | 45 +++++++++++++++++++++++++-------------------- 1 file changed, 25 insertions(+), 20 deletions(-)
tools/perf/builtin-sched.c +25 -20
@@ -213,7 +213,7 @@ struct perf_sched {u64 all_runtime;u64 all_count;u64 cpu_last_switched[MAX_CPUS ]; -struct rb_root atom_root, sorted_atom_root, merged_atom_root; +struct rb_root_cached atom_root, sorted_atom_root, merged_atom_root;struct list_head sort_list, cmp_pid;bool force;bool skip_merge;
@@ -271,7 +271,7 @@ struct evsel_runtime {struct idle_thread_runtime {struct thread_runtime tr;struct thread *last_thread; -struct rb_root sorted_root; +struct rb_root_cached sorted_root;struct callchain_root callchain;struct callchain_cursor cursor; };
@@ -950,10 +950,10 @@ thread_lat_cmp(struct list_head *list, struct work_atoms *l, struct work_atoms * }static struct work_atoms * -thread_atoms_search (struct rb_root *root,struct thread *thread, +thread_atoms_search (struct rb_root_cached *root,struct thread *thread,struct list_head *sort_list) { -struct rb_node *node = root->rb_node; +struct rb_node *node = root->rb_root.rb_node;struct work_atoms key = { .thread = thread };while (node) {
@@ -976,10 +976,11 @@ thread_atoms_search(struct rb_root *root, struct thread *thread, }static void -__thread_latency_insert (struct rb_root *root,struct work_atoms *data, +__thread_latency_insert (struct rb_root_cached *root,struct work_atoms *data,struct list_head *sort_list) { -struct rb_node **new = &(root->rb_node), *parent =NULL ; +struct rb_node **new = &(root->rb_root.rb_node), *parent =NULL ; +bool leftmost = true;while (*new) {struct work_atoms *this;
@@ -992,12 +993,14 @@ __thread_latency_insert(struct rb_root *root, struct work_atoms *data,if (cmp >0 ) new = &((*new)->rb_left); -else +else { new = &((*new)->rb_right); + leftmost = false; + } }rb_link_node (&data->node, parent, new); -rb_insert_color (&data->node, root); +rb_insert_color_cached (&data->node, root, leftmost); }static int thread_atoms_insert (struct perf_sched *sched,struct thread *thread)
@@ -1447,15 +1450,15 @@ static int sort_dimension__add(const char *tok, struct list_head *list)static void perf_sched__sort_lat (struct perf_sched *sched) {struct rb_node *node; -struct rb_root *root = &sched->atom_root; +struct rb_root_cached *root = &sched->atom_root; again:for (;;) {struct work_atoms *data; - node =rb_first (root); + node =rb_first_cached (root);if (!node)break ; -rb_erase (node, root); +rb_erase_cached (node, root); data = rb_entry(node, struct work_atoms, node);__thread_latency_insert (&sched->sorted_atom_root, data, &sched->sort_list); }
@@ -2762,12 +2765,12 @@ static size_t callchain__fprintf_folded(FILE *fp, struct callchain_node *node)return ret; } -static size_t timehist_print_idlehist_callchain (struct rb_root *root) +static size_t timehist_print_idlehist_callchain (struct rb_root_cached *root) {size_t ret =0 ;FILE *fp = stdout;struct callchain_node *chain; -struct rb_node *rb_node =rb_first (root); +struct rb_node *rb_node =rb_first_cached (root);printf (" %16s %8s %s\n" ,"Idle time (msec)" ,"Count" ,"Callchains" ); printf(" %.16s %.8s %.50s\n", graph_dotted_line, graph_dotted_line,
@@ -2868,7 +2871,7 @@ static void timehist_print_summary(struct perf_sched *sched,if (itr ==NULL )continue ; - callchain_param.sort (&itr->sorted_root, &itr->callchain, + callchain_param.sort (&itr->sorted_root.rb_root, &itr->callchain,0 , &callchain_param);printf (" CPU %2d:" , i);
@@ -3074,11 +3077,12 @@ static void print_bad_events(struct perf_sched *sched) } } -static void __merge_work_atoms (struct rb_root *root,struct work_atoms *data) +static void __merge_work_atoms (struct rb_root_cached *root,struct work_atoms *data) { -struct rb_node **new = &(root->rb_node), *parent =NULL ; +struct rb_node **new = &(root->rb_root.rb_node), *parent =NULL ;struct work_atoms *this;const char *comm =thread__comm_str (data->thread), *this_comm; +bool leftmost = true;while (*new) {int cmp;
@@ -3092,6 +3096,7 @@ static void __merge_work_atoms(struct rb_root *root, struct work_atoms *data) new = &((*new)->rb_left); }else if (cmp <0 ) { new = &((*new)->rb_right); + leftmost = false; }else { this->num_merged++; this->total_runtime += data->total_runtime;
@@ -3109,7 +3114,7 @@ static void __merge_work_atoms(struct rb_root *root, struct work_atoms *data) data->num_merged++;rb_link_node (&data->node, parent, new); -rb_insert_color (&data->node, root); +rb_insert_color_cached (&data->node, root, leftmost); }static void perf_sched__merge_lat (struct perf_sched *sched)
@@ -3120,8 +3125,8 @@ static void perf_sched__merge_lat(struct perf_sched *sched)if (sched->skip_merge)return ; -while ((node =rb_first (&sched->atom_root))) { -rb_erase (node, &sched->atom_root); +while ((node =rb_first_cached (&sched->atom_root))) { +rb_erase_cached (node, &sched->atom_root); data = rb_entry(node, struct work_atoms, node);__merge_work_atoms (&sched->merged_atom_root, data); }
@@ -3143,7 +3148,7 @@ static int perf_sched__lat(struct perf_sched *sched)printf (" Task | Runtime ms | Switches | Average delay ms | Maximum delay ms | Maximum delay at |\n" );printf (" -----------------------------------------------------------------------------------------------------------------\n" ); - next =rb_first (&sched->sorted_atom_root); + next =rb_first_cached (&sched->sorted_atom_root);while (next) {struct work_atoms *work_list;