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

[Andi Kleen]

> 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.


-Andi