Re: [PATCH v2] perf mem: improves DSO long names search speed with RB tree

[Adrian Hunter <adrian.hunter@intel.com>]

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.