Messages in this thread | | | Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups | From | Alexey Budankov <> | Date | Wed, 23 Aug 2017 17:18:54 +0300 |
| |
On 23.08.2017 16:39, Alexander Shishkin wrote: > Alexey Budankov <alexey.budankov@linux.intel.com> writes: > >>>>>> bool event_less(left, right) >>>>>> { >>>>>> if (left->cpu < right->cpu) >>>>>> return true; >>>>>> >>>>>> if (left->cpu > right_cpu) >>>>>> return false; >>>>>> >>>>>> if (left->vtime < right->vtime) >>>>>> return true; >>>>>> >>>>>> return false; >>>>>> } >>>>>> >>>>>> insert_group(group, event, tail) >>>>>> { >>>>>> if (tail) >>>>>> event->vtime = ++group->vtime; >>>>>> >>>>>> tree_insert(&group->root, event); >>>>>> } > > [ ... ] > >> 2. implementing special _less() function and rotation by re-inserting >> group with incremented index; >> > > [ ... ] > >> Now I figured that not all indexed events are always located under >> the root with the same cpu, and it depends on the order of insertion >> e.g. with insertion order 01,02,03,14,15,16 we get this: >> >> 02 >> / \ >> 01 14 >> / \ >> 03 15 >> \ >> 16 > > How did you arrive at this? Seeing the actual code would help, because > this is not the ordering we're looking for. With Peter's earlier example > (quoted above) it shouldn't look like this.
I implemented the solution Peter suggested. Then I was testing and noticed considerable difference in amount of collected samples when multiplexing event, in comparison to the version with tree of lists.
I then looked for a fast way to emulate the idea with virtual index as a secondary key and found this RB tree emulator:
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
and it showed me the picture I mentioned above:
02 / \ 01 14 / \ 03 15 \ 16
I understand it is not 100% proof that index idea doesn't work however it means that in order to apply the idea to this patch some more changes are required additionally to what Peter shared earlier.
> > Regards, > -- > Alex > > >
| |