linux-kernel - Re: Make yield_task

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 21 Feb 2008 12:21:33 +0530
From:	Balbir Singh <balbir@...ux.vnet.ibm.com>
To:	Ingo Molnar <mingo@...e.hu>
CC:	Peter Zijlstra <peter@...gramming.kicks-ass.net>,
	Srivatsa Vaddagiri <vatsa@...ux.vnet.ibm.com>,
	Dhaval Giani <dhaval@...ux.vnet.ibm.com>,
	linux-kernel@...r.kernel.org
Subject: Re: Make yield_task_fair more efficient

Ingo Molnar wrote:
> * Balbir Singh <balbir@...ux.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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/