Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups

From	Alexander Shishkin <alexander.shishkin@linux.intel.com>
Newsgroups	linux.kernel
Subject	Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups
Date	2017-08-23 15:50 +0200
Message-ID	<uhEcF-1bd-3@gated-at.bofh.it> (permalink)
References	(2 earlier) <uao31-n3-25@gated-at.bofh.it> <uav4t-5ap-5@gated-at.bofh.it> <uaLVF-8da-57@gated-at.bofh.it> <ubKuu-59V-19@gated-at.bofh.it> <ueNPb-4e6-3@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

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.

Regards,
--
Alex

Thread

Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-15 19:30 +0200
  Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexander Shishkin <alexander.shishkin@linux.intel.com> - 2017-08-23 15:50 +0200
    Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-23 16:20 +0200

csiph-web