Messages in this thread Patch in this message | | | Date | Wed, 17 Sep 2014 09:22:04 +0300 | From | Adrian Hunter <> | Subject | Re: [PATCH v2] perf mem: improves DSO long names search speed with RB tree |
| |
On 09/16/2014 10:08 PM, Waiman Long wrote: > With workload that spawns and destroys many threads and processes, > it was found that perf-mem could took a long time to post-process > the perf data after the target workload had completed its operation. > The performance bottleneck was found to be searching and insertion > of the new DSO structures (thousands of them in this case). > > In a dual-socket Ivy-Bridge E7-4890 v2 machine (30-core, 60-thread), > the perf profile below shows what perf was doing after the profiled > AIM7 shared workload completed: > > - 83.94% perf libc-2.11.3.so [.] __strcmp_sse42 > - __strcmp_sse42 > - 99.82% map__new > machine__process_mmap_event > perf_session_deliver_event > perf_session__process_event > __perf_session__process_events > cmd_record > cmd_mem > run_builtin > main > __libc_start_main > - 13.17% perf perf [.] __dsos__findnew > __dsos__findnew > map__new > machine__process_mmap_event > perf_session_deliver_event > perf_session__process_event > __perf_session__process_events > cmd_record > cmd_mem > run_builtin > main > __libc_start_main > > So about 97% of CPU times were spent in the map__new() function > trying to insert new DSO entry into the DSO linked list. The whole > post-processing step took about 9 minutes. > > The DSO structures are currently searched linearly. So the total > processing time will be proportional to n^2. > > To overcome this performance problem, the DSO code is modified to > also put the DSO structures in a RB tree sorted by its long name > in additional to being in a simple linked list. With this change, > the processing time will become proportional to n*log(n) which will > be much quicker for large n. However, the short name will still > be searched using the old linear searching method which is slow. > With that patch in place, the same perf-mem post-processing step took > less than 30 seconds to complete. > > Signed-off-by: Waiman Long <Waiman.Long@hp.com> > --- > tools/perf/util/dso.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++-- > tools/perf/util/dso.h | 1 + > 2 files changed, 84 insertions(+), 4 deletions(-) > > diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c > index 819f104..fccb2f0 100644 > --- a/tools/perf/util/dso.c > +++ b/tools/perf/util/dso.c > @@ -611,17 +611,93 @@ struct dso *dso__kernel_findnew(struct machine *machine, const char *name, > return dso; > } > > +/* > + * RB root of DSOs sorted by the long name > + */ > +static struct rb_root dso__longname_root = { NULL };
Global variable!
Why not just change the lists to rbtrees i.e.
diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h index 6a6bcc1..fa30780 100644 --- a/tools/perf/util/machine.h +++ b/tools/perf/util/machine.h @@ -32,8 +32,8 @@ struct machine { struct list_head dead_threads; struct thread *last_match; struct vdso_info *vdso_info; - struct list_head user_dsos; - struct list_head kernel_dsos; + struct rb_root user_dsos; + struct rb_root kernel_dsos; struct map_groups kmaps; struct map *vmlinux_maps[MAP__NR_TYPES]; u64 kernel_start; And make all the resulting adjustments.
| |