lkml.org 
[lkml]   [2011]   [Nov]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH] perf_events: fix and improve x86 event scheduling
From
On Mon, Nov 7, 2011 at 12:10 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Mon, 2011-11-07 at 12:01 +0100, Stephane Eranian wrote:
>> +                       /*
>> +                        * scan all possible counters for this event
>> +                        * but use the one with the smallest counter weight,
>> +                        * i.e., give a chance to other less constrained events
>> +                        */
>>                         for_each_set_bit(j, c->idxmsk, X86_PMC_IDX_MAX) {
>>
>> +                               if (test_bit(j, used_mask))
>> +                                       continue;
>> +
>> +                               if (wcnt[j] < min_wcnt) {
>> +                                       min_wcnt = wcnt[j];
>> +                                       wcnt_idx = j;
>> +                               }
>> +                       }
>
> The problem with this is that it will typically hit the worst case for
> Intel fixed-purpose events since the fixed purpose counters have the
> highest counter index and their constraint masks are the heaviest in the
> system ensuring we hit the max loop count on the top loop.
>
Yes, but to avoid this you'd need some form of sorting.
We could also cut down on top loop iterations by caching the weight list
of the events and examining only the weights we do have.

As for the complexity, I think it is mostly bound to the number of
counters rather
than event.

The top loop is about event weights, that's bound by the number of counters.
The middle loop is about the number of events.
The inner loop is about the number of counters.

So I'd expect the complexity to be O(c^2*n)
where c is the number of counters, n the number of events.
But given we limit the number of events to that of counters,
we do have O(c^3).

As for the map_idx, it's there to track the position of each event in the
initial event list. We shuffle events between constrained and unconstrained.
By stashing the map_idx in the hw_perf_event struct we avoid having to
pass around yet another array.

> Then again, with Robert's approach we have to mark all fixed purpose
> thingies as redo and we might hit some weird cases there as well, can't
> seem to get me brain straight on that case though.
>
>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2011-11-07 14:55    [W:0.214 / U:2.892 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site