Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1712368 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

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

Hi Peter,

On 07.08.2017 10:17, Alexey Budankov wrote:
> On 04.08.2017 17:36, Peter Zijlstra wrote:
>> On Thu, Aug 03, 2017 at 11:30:09PM +0300, Alexey Budankov wrote:
>>> On 03.08.2017 16:00, Peter Zijlstra wrote:
>>>> On Wed, Aug 02, 2017 at 11:13:54AM +0300, Alexey Budankov wrote:
>>
>>>>> +/*
>>>>> + * Find group list by a cpu key and rotate it.
>>>>> + */
>>>>> +static void
>>>>> +perf_event_groups_rotate(struct rb_root *groups, int cpu)
>>>>> +{
>>>>> +	struct rb_node *node;
>>>>> +	struct perf_event *node_event;
>>>>> +
>>>>> +	node = groups->rb_node;
>>>>> +
>>>>> +	while (node) {
>>>>> +		node_event = container_of(node,
>>>>> +				struct perf_event, group_node);
>>>>> +
>>>>> +		if (cpu < node_event->cpu) {
>>>>> +			node = node->rb_left;
>>>>> +		} else if (cpu > node_event->cpu) {
>>>>> +			node = node->rb_right;
>>>>> +		} else {
>>>>> +			list_rotate_left(&node_event->group_list);
>>>>> +			break;
>>>>> +		}
>>>>> +	}
>>>>> +}
>>>>
>>>> Ah, you worry about how to rotate inside a tree?
>>>
>>> Exactly.
>>>
>>>>
>>>> You can do that by adding (run)time based ordering, and you'll end up
>>>> with a runtime based scheduler.
>>>
>>> Do you mean replacing a CPU indexed rb_tree of lists with 
>>> an CPU indexed rb_tree of counter indexed rb_trees?
>>
>> No, single tree, just more complicated ordering rules.
>>
>>>> A trivial variant keeps a simple counter per tree that is incremented
>>>> for each rotation. That should end up with the events ordered exactly
>>>> like the list. And if you have that comparator like above, expressing
>>>> that additional ordering becomes simple ;-)
>>>>
>>>> Something like:
>>>>
>>>> struct group {
>>>>   u64 vtime;
>>>>   rb_tree tree;
>>>> };
>>>>
>>>> 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);
>>>> }
>>>>
>>>> Then every time you use insert_group(.tail=1) it goes to the end of that
>>>> CPU's 'list'.
>>>>
>>>
>>> Could you elaborate more on how to implement rotation?
>>
>> Its almost all there, but let me write a complete replacement for your
>> perf_event_group_rotate() above.
>>
>> /* find the leftmost event matching @cpu */
>> /* XXX not sure how to best parametrise a subtree search, */
>> /* again, C sucks... */
>> struct perf_event *__group_find_cpu(group, cpu)
>> {
>> 	struct rb_node *node = group->tree.rb_node;
>> 	struct perf_event *event, *match = NULL;
>>
>> 	while (node) {
>> 		event = container_of(node, struct perf_event, group_node);
>>
>> 		if (cpu > event->cpu) {
>> 			node = node->rb_right;
>> 		} else if (cpu < event->cpu) {
>> 			node = node->rb_left;
>> 		} else {
>> 			/*
>> 			 * subtree match, try left subtree for a
>> 			 * 'smaller' match.
>> 			 */
>> 			match = event;
>> 			node = node->rb_left;
>> 		}
>> 	}
>>
>> 	return match;
>> }
>>
>> void perf_event_group_rotate(group, int cpu)
>> {
>> 	struct perf_event *event = __group_find_cpu(cpu);
>>
>> 	if (!event)
>> 		return;
>>
>> 	tree_delete(&group->tree, event);
>> 	insert_group(group, event, 1);
>> }
>>
>> So we have a tree ordered by {cpu,vtime} and what we do is find the
>> leftmost {cpu} entry, that is the smallest vtime entry for that cpu. We
>> then take it out and re-insert it with a vtime number larger than any
>> other, which places it as the rightmost entry for that cpu.
>>
>>
>> So given:
>>
>>        {1,1}
>>        / \
>>     {0,5} {1,2}
>>    / \        \
>> {0,1} {0,6}  {1,4}
>>
>>
>> __group_find_cpu(.cpu=1) will return {1,1} as being the leftmost entry
>> with cpu=1. We'll then remove it, update its vtime to 7 and re-insert.
>> resulting in something like:
>>
>>        {1,2}
>>        / \
>>     {0,5} {1,4}
>>    / \        \
>> {0,1} {0,6}  {1,7}
>>
> 
> Makes sense. The implementation becomes a bit simpler. The drawbacks 
> may be several rotations of potentially big tree on the critical path, 
> instead of updating four pointers in case of the tree of lists.

I implemented the approach you had suggested (as I understood it),
tested it and got results that are drastically different from what 
I am getting for the tree of lists. Specifically I did:

1. keeping all groups in the same single tree by employing a 64-bit index
   additionally to CPU key;
   
2. implementing special _less() function and rotation by re-inserting
   group with incremented index;

3. replacing API with a callback in the signature by a macro
   perf_event_groups_for_each();

Employing all that shrunk the total patch size, however I am still 
struggling with the correctness issues.

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

and it is unclear how to iterate cpu==0 part of tree in this case.

Iterating cpu specific subtree like this:

#define for_each_group_event(event, group, cpu, pmu, field)	 \
	for (event = rb_entry_safe(group_first(group, cpu, pmu), \
				   typeof(*event), field);	 \
	     event && event->cpu == cpu && event->pmu == pmu;	 \
	     event = rb_entry_safe(rb_next(&event->field),	 \
				   typeof(*event), field))

misses event==03 for the case above and I guess this is where I loose 
samples in my testing. 

Please advise how to proceed.

Thanks,
Alexey

> 
>>
>>
>>
>>
> 
> 

[toc] | [next] | [standalone]

#1718358

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

[toc] | [prev] | [next] | [standalone]

#1718395

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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web