Messages in this thread | | | Date | Thu, 21 Feb 2008 12:21:33 +0530 | From | Balbir Singh <> | Subject | Re: Make yield_task_fair more efficient |
| |
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
| |