Re: [PATCH v1 5/9] perf util: Remove a set of shadow stats static variables

[Jiri Olsa]

On Tue, Nov 21, 2017 at 10:03:50AM -0800, Andi Kleen wrote:
> > all this is about switching from array to rb_list for the --per-thread case,
> > which can be considered as a special use case.. how much do we suffer in
> > performance with new code? how about the "perf stat -I 100", would it scale
> > ok for extreme cases (many events in -e or -dddd..)
> 
> rbtrees scale by log N, with N being the entries in the tree.
> 
> Even in extreme cases, let's say 10000 events and 1000 cpus it would
> need only 8 memory accesses and comparisons for each look up.
> Even if we assume cache misses for all of the memory lookups,
> at ~200ns per cache miss it's still only 1us per event, which 
> is negligible.
> 
> In practice not all memory accesses will be misses because
> the upper levels of the tree are almost certainly cached
> from earlier accesses.

sounds good, thanks

jirka