Messages in this thread | | | Subject | Re: [PATCH] perf_events: fix and improve x86 event scheduling | From | Peter Zijlstra <> | Date | Thu, 10 Nov 2011 19:52:47 +0100 |
| |
On Thu, 2011-11-10 at 19:41 +0100, Peter Zijlstra wrote: > On Thu, 2011-11-10 at 19:03 +0100, Robert Richter wrote: > > But this algorithm does not work for all cases and does not solve the > > problem in general. > > Yeah, the problem in general is O(n!) no O(n^3) algorithm can compute > the optimal solution for n>3 or so. > > I think the goal is to keep the 'normal' case O(n^2) but try and suck > less for the corner cases without degenerating into a full blown O(n!). > > So I think we want an amortized O(n^2) with an upper bound well below > O(n!).
I don't think its reasonable to require a perfect solver for the generic problem since O(n!) is well outside sanity.
Practically though, the most challenging problem is the AMD F15 thing, since those constraints are quite specific it might just be possible to construct an algorithm that finds optimal solutions well below O(n!) for that particular constraint set.
IIRC, Robert's proposal limits the rewind stack to 1, which, if my mind didn't completely stop working, should end up being something like O(n^3). Now I don't know if Robert's thing is perfect for AMD F15 or if there's still some odd fail cases, but since he's from AMD I suspect its good enough in practice.
In fact, I almost merged his code, my only complaint was a lack of comments and having had to spend several hours to fully understand the thing a few months ago, I felt it really could use some since I didn't want to have to spend that amount of effort every time I'd have to look at the thing.
| |