Re: Make yield_task_fair more efficient

[Balbir Singh <balbir@linux.vnet.ibm.com>]

Ingo Molnar wrote:
> * Balbir Singh <balbir@linux.vnet.ibm.com> wrote:
> 
>> __pick_last_entity() walks the entire tree on O(lgn) time to find the 
>> rightmost entry. This patch makes the routine more efficient by 
>> reducing the cost of the lookup
> 
> hm, i'm not sure we want to do this: we'd be slowing down the fastpath 
> of all the other common scheduler functions, for the sake of a rarely 
> used (and broken ...) API: yield. And note that an rbtree walk is not 
> slow at all - if you are yielding frequently it's probably all cached.
> 
> 	Ingo

Ingo,

I disagree. The cost is only adding a field to cfs_rq and we already have the
logic to track the leftmost node, we just update the rightmost node as well.
For a large number of tasks - say 10000, we need to walk 14 levels before we
reach the node (each time). Doesn't matter if the data is cached, we are still
spending CPU time looking through pointers and walking to the right node. If all
the threads get a chance to run, you can imagine the effect it has on efficiency
and the data cache.

I see a boost in sched_yield performance and no big hit on regular performance.
Could you please test it to see if your apprehensions are correct.

PS: You missed to add me on the cc/to list.


-- 
	Warm Regards,
	Balbir Singh
	Linux Technology Center
	IBM, ISTL