On Mon, 13 Feb 2012, Alexander Motin wrote:

It would be preferable to refetch the load on the target cpu and restart the selection if it has changed. Even this should have some maximum bound on the number of times it will spin and possibly be conditionally enabled. That two cpus are making the same decision indicates that the race window is occuring and contention will be guaranteed. As you have tested on only 8 cores that's not a good sign.

This was not pointless. Eliminate it and see. The point is that after some time has elapsed the cache is almost certainly useless and we should select the most appropriate cpu based on load, priority, etc. We don't have perfect information for any of these algorithms. But as an approximation it is useful to know whether affinity should even be considered. An improvement on this would be to look at the amount of time the core has been idle since the selecting thread last ran rather than just the current load. Tell me what the point of selecting for affinity is if so much time has passed that valid cache contents are almost guaranteed to be lost?

It can definitely be cheaper. But there are an equal number of cases where it will be more expensive. Some applications will have a lot of contention and shared state and these will want to be co-located. Others will simply want to get as much cache and cpu time as they can. There are a number of papers that have been published on determining which is which based on cpu performance counters. I believe sun does this in particular. Another option that apple has pursued is to give the application the option to mark threads as wanting to be close together or far away.

I think the particular heuristic you have here is too expensive and specific to go in. The potential negative consequences are very big. If you want to pursue apple or sun's approach to this problem I would be interested in that.

You're speaking of the stathz based accounting? Or you want more precise stats about other things? We've talked for years about event based accounting rather than sampling but no one has implemented it. Please go ahead if you would like. Keep in mind that cores can change frequency and tsc values may not be stable.

However, even with perfect stats, I'm not sure whether ignoring the current load will be the right thing. I had some changes that took the interactivity score into account to do this. If it is very very low, then maybe it makes sense.

I say this because I have tried nearly all of these heuristics in different forms. I don't object to the general idea of using a weighted score to select the target cpu. However, I do think several of these heuristics are problematic. While the current algorithm is far from perfect it is the product of an incredible amount of testing and experimentation. Significant changes to it are going to require an equal amount of effort to characterize and verify. And I do believe many pieces can be broken down and tested independently. For example, whether to ignore interactive load on the core, or whether to lock pickcpu, etc. can all easily be independently tested in a number of workloads.

Do you intend to clean up and commit your last, simpler patch? I have no objections to that and it simply fixes a bias in the load selection algorithm that shouldn't have existed.

Thanks, Jeff