sched: Check nr_running before calling pick_next_task in schedule().
PATCH 1/1 sched: Check nr_running before calling pick_next_task in schedule().
Currently at schedule(), when we call pick_next_task we don't check whether current rq is empty or not. Since idle_balance can fail, its nice to check whether we really have any task on rq or not. If not, we can call idle_sched_class.pick_next_task straight.
---
kernel/sched.c +8 -1
@@ -4273,7 +4273,14 @@ need_resched:idle_balance (cpu, rq);put_prev_task (rq, prev); - next =pick_next_task (rq); +/* Since idle_balance can fail, its better to check rq->nr_running. +* Otherwise we can call idle_sched_class.pick_next_task straight, +* cause we need to do some accounting. +*/ +if (likely (rq->nr_running)) + next =pick_next_task (rq); +else + next = idle_sched_class.pick_next_task (rq);clear_tsk_need_resched (prev); rq->skip_clock_update =0 ;
Hi Rakib,
This doesn't strike me as a very good trade.
It adds a branch to the case where we actually have work to save branches in the case when we're idle anyway?
- Paul
Quoted 28 lines · Rakib Mullick
Currently at
schedule(), when we callpick_next_taskwe don't check whether current rq is empty or not. Sinceidle_balancecan fail, its nice to check whether we really have any task on rq or not. If not, we can call idle_sched_class.pick_next_task straight.Signed-off-by Rakib Mullick<[email protected]>---
kernel/sched.c +8
-1@@ -4273,7 +4273,14 @@ need_resched:idle_balance (cpu, rq);put_prev_task (rq, prev); - next =pick_next_task (rq); +/* Since idle_balance can fail, its better to check rq->nr_running. +* Otherwise we can call idle_sched_class.pick_next_task straight, +* cause we need to do some accounting. +*/ +if (likely (rq->nr_running)) + next =pick_next_task (rq); +else + next = idle_sched_class.pick_next_task (rq);clear_tsk_need_resched (prev); rq->skip_clock_update =0 ;
Hi Rakib,
This doesn't strike me as a very good trade.
It adds a branch to the case where we actually have work to save branches in the case when we're idle anyway?
- Paul
Quoted 28 lines · Rakib Mullick
Currently at
schedule(), when we callpick_next_taskwe don't check whether current rq is empty or not. Sinceidle_balancecan fail, its nice to check whether we really have any task on rq or not. If not, we can call idle_sched_class.pick_next_task straight.Signed-off-by Rakib Mullick<[email protected]>---
kernel/sched.c +8
-1@@ -4273,7 +4273,14 @@ need_resched:idle_balance (cpu, rq);put_prev_task (rq, prev); - next =pick_next_task (rq); +/* Since idle_balance can fail, its better to check rq->nr_running. +* Otherwise we can call idle_sched_class.pick_next_task straight, +* cause we need to do some accounting. +*/ +if (likely (rq->nr_running)) + next =pick_next_task (rq); +else + next = idle_sched_class.pick_next_task (rq);clear_tsk_need_resched (prev); rq->skip_clock_update =0 ;
Hi Paul,
Quoted 4 lines · Paul Turner
Hi Rakib,
This doesn't strike me as a very good trade.
I'm not sure why. What am I missing here?
Quoted 2 lines
It adds a branch to the case where we actually have work to save branches in the case when we're idle anyway?
Yes, right. We're adding a branch here. Is it a misuse of branch? As I mentioned, idle_balance can fail (I think thats an unlikely case, that why I've added a branch). In that case, we don't need to call pick_next_task. Note, in pick_next_task there is a check for 'likely(rq->nr_running == rq->cfs.nr_running)' - by using this patch that case will be more likely (which itself calls fair_sched_class.pick_next_task directly - which is an optimization). If calling fair_sched_class.pick_next_task in case of all tasks are cfs task is being treat as an optimization then why, when we're idle calling idle_sched_class.pick_next_task, won't be an optimization?
Thanks,
Rakib
Quoted 3 lines
- Paul
Quoted 17 lines · Rakib Mullick
Currently at
schedule(), when we callpick_next_taskwe don't check whether current rq is empty or not. Sinceidle_balancecan fail, its nice to check whether we really have any task on rq or not. If not, we can call idle_sched_class.pick_next_task straight.Signed-off-by Rakib Mullick <[email protected]>---
kernel/sched.c +0
-1@@ -4273,7 +4273,14 @@ need_resched:idle_balance (cpu, rq);put_prev_task (rq, prev); - next =pick_next_task (rq);
kernel/sched.c need_resched: · line 4285
Quoted 10 lines
kernel/sched.c +8
-0+/* Since idle_balance can fail, its better to check rq->nr_running. +* Otherwise we can call idle_sched_class.pick_next_task straight, +* cause we need to do some accounting. +*/ +if (likely (rq->nr_running)) + next =pick_next_task (rq); +else + next = idle_sched_class.pick_next_task (rq);clear_tsk_need_resched (prev); rq->skip_clock_update =0 ;
Why!?
You're making the fast path -- picking a task -- slower by adding a branch, and making the slow path -- going into idle -- faster. That seems backwards at best.
You've completely failed to provide any sort of rationale for the patch nor did you provide a use-case with performance numbers. This just isn't making much sense at all.
Quoted 31 lines · Peter Zijlstra
Quoted 17 lines · Rakib Mullick
Currently at
schedule(), when we callpick_next_taskwe don't check whether current rq is empty or not. Sinceidle_balancecan fail, its nice to check whether we really have any task on rq or not. If not, we can call idle_sched_class.pick_next_task straight.Signed-off-by Rakib Mullick <[email protected]>---
kernel/sched.c +0
-1@@ -4273,7 +4273,14 @@ need_resched: idle_balance(cpu, rq); put_prev_task(rq, prev); - next = pick_next_task(rq);kernel/sched.c need_resched: · line 4285
Quoted 10 lines
kernel/sched.c +8
-0+ /* Since idle_balance can fail, its better to check rq->nr_running. + * Otherwise we can call idle_sched_class.pick_next_task straight, + * cause we need to do some accounting. + */ + if (likely(rq->nr_running)) + next = pick_next_task(rq); + else + next = idle_sched_class.pick_next_task(rq); clear_tsk_need_resched(prev); rq->skip_clock_update = 0;Why!?
Quoted 4 lines
You're making the fast path -- picking a task -- slower by adding a branch, and making the slow path -- going into idle -- faster. That seems backwards at best.
Well, yes - branching seems definitely have some side effects. Thinking from UP's perspective, it will only hit slow path -- going into idle. In that case, that likely branch will just fail. And on an UP system that slow path -- going into idle -- is the only way, taking the fast path (trying picking a task) isn't the right thing, isn't it?
Quoted 4 lines
You've completely failed to provide any sort of rationale for the patch nor did you provide a use-case with performance numbers. This just isn't making much sense at all.
Regarding taking branch, it needs performance numbers - I agree. But, I'm not quite agree that - it's not just making any sense. Will try to do some performance testing on it.
Thanks,
Rakib
Quoted 1 line · Rakib Mullick
Well, yes - branching seems definitely have some side effects.
It adds the cost of the test as well as a possible branch mis-predict.
Quoted 2 lines
Thinking from UP's perspective, it will only hit slow path -- going into idle.
Uhm, no, every time the machine is busy and does a schedule between tasks you still get to do that extra nr_running test and branch.
Quoted 4 lines
In that case, that likely branch will just fail. And on an
UP system that slow path -- going into idle -- is the only way, taking the fast path (trying picking a task) isn't the right thing, isn't it?
I'm not at all sure I even understand what you're trying to say. I really don't understand what's the problem with going the long way with picking the idle task, the machine is idle, it doesn't have anything useful to do, who cares.
Quoted 11 lines · Peter Zijlstra
Quoted 1 line · Rakib Mullick
Well, yes - branching seems definitely have some side effects.
It adds the cost of the test as well as a possible branch mis-predict.
Quoted 2 lines
Thinking from UP's perspective, it will only hit slow path -- going into idle.
Uhm, no, every time the machine is busy and does a schedule between tasks you still get to do that extra
nr_runningtest and branch.
Ok, for now I'm putting branch aside. I don't think checking nr_running isn't extra, it should be norm. Cause, if this rq has no nr_running it calls idle_balance, at that point due to idle_balance - we might have moved task from other rq if idle_balance is successful. But, idle_balance might not be successful that's why I was thinking about checking nr_running is necessary, in that case we don't need to call pick_next_task cause - we don't have any task.
Quoted 10 lines
Quoted 4 lines
In that case, that likely branch will just fail. And on an UP system that slow path -- going into idle -- is the only way, taking the fast path (trying picking a task) isn't the right thing, isn't it?
I'm not at all sure I even understand what you're trying to say. I really don't understand what's the problem with going the long way with picking the idle task, the machine is idle, it doesn't have anything useful to do, who cares.
Well, yes the machine is idle. I got your point that you're emphasizing that CPU is idle even if we take long path it doesn't matter. But, when we've two ways, one is going through pick_next_task other is calling idle_class straight I think calling idle_class is better. Actually that's how I think (and certainly it differs from yours). Note that, in pick_next_task there is branch, which checks likely(nr_running==cfs->nr_running) - chances for hitting this branch will increase - cause in case of !nr_running, pick_next_task won't be called. It will reduce pick_next_task's calling overhead.
Thanks,
Rakib
Quoted 30 lines · Rakib Mullick
Quoted 11 lines · Peter Zijlstra
Quoted 1 line · Rakib Mullick
Well, yes - branching seems definitely have some side effects.
It adds the cost of the test as well as a possible branch mis-predict.
Quoted 2 lines
Thinking from UP's perspective, it will only hit slow path -- going into idle.
Uhm, no, every time the machine is busy and does a schedule between tasks you still get to do that extra
nr_runningtest and branch.Ok, for now I'm putting branch aside. I don't think checking
nr_runningisn't extra, it should be norm. Cause, if this rq has nonr_runningit callsidle_balance, at that point due toidle_balance- we might have moved task from other rq ifidle_balanceis successful. But,idle_balancemight not be successful that's why I was thinking about checkingnr_runningis necessary, in that case we don't need to callpick_next_taskcause - we don't have any task.Quoted 10 lines
Quoted 4 lines
In that case, that likely branch will just fail. And on an UP system that slow path -- going into idle -- is the only way, taking the fast path (trying picking a task) isn't the right thing, isn't it?
I'm not at all sure I even understand what you're trying to say. I really don't understand what's the problem with going the long way with picking the idle task, the machine is idle, it doesn't have anything useful to do, who cares.
Quoted 10 lines
Well, yes the machine is idle. I got your point that you're emphasizing that CPU is idle even if we take long path it doesn't matter. But, when we've two ways, one is going through
pick_next_taskother is callingidle_classstraight I think callingidle_classis better. Actually that's how I think (and certainly it differs from yours). Note that, inpick_next_taskthere is branch, which checkslikely(nr_running==cfs->nr_running)- chances for hitting this branch will increase - cause in case of !nr_running,pick_next_taskwon't be called. It will reduce pick_next_task's calling overhead.
I made a mistake here, pick_next_task is inlined so function calling overhead isn't a problem.
Quoted 3 lines
Thanks,
Rakib
Quoted 10 lines · Rakib Mullick
Quoted 6 lines · Peter Zijlstra
On Sat, 2011-07-02 at 00:41 +0600, Rakib Mullick wrote:
You've completely failed to provide any sort of rationale for the patch nor did you provide a use-case with performance numbers. This just isn't making much sense at all.
Regarding taking branch, it needs performance numbers - I agree. But, I'm not quite agree that - it's not just making any sense. Will try to do some performance testing on it.
I tried to do some testing with the applied patch using kernbench (with likely branch removed). I did it twice with load -j {,2,4,6,8}. Kernel version tagged with -schedpatch indicates kernel with this applied and -noschedpatch is the default. In first case, with this patch applied Elapsed time is lesser. In the second run with -j 2 and -j 4 -schedpatch kernel is slow, but with -j 6 and -j 8 it takes less elapsed time. Also tested with 'nosmp', with this patch, elapsed time is lesser. So, for better interpretation and full log of test results I'm attaching the kernbench.log. Please, see whether it looks convincing to you or not. Tests are done on core i3 machine.
Thanks,
Rakib
Sun Jul 3 10:40:56 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 4 Run (std deviation):
Elapsed Time 13.61 (0.0608276)
User Time 27.5967 (0.12897)
System Time 14.2133 (0.119303)
Percent CPU 306.667 (2.51661)
Context Switches 7989.33 (58.398) Sleeps 10866.3 (43.6157)
Sun Jul 3 10:50:56 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 4 Run (std deviation):
Elapsed Time 13.65 (0.127671)
User Time 27.54 (0.112694)
System Time 14.1467 (0.155027)
Percent CPU 305 (3)
Context Switches 7983.33 (165.171) Sleeps 10902.3 (135.795)
Sun Jul 3 11:01:14 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 2 Run (std deviation):
Elapsed Time 17.63 (0.31241)
User Time 19.4333 (0.115036)
System Time 10.21 (0.0264575)
Percent CPU 167.667 (3.21455)
Context Switches 8419 (75.6241)
Sleeps 10580.7 (75.7254)
Sun Jul 3 11:12:36 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 2 Run (std deviation):
Elapsed Time 17.6067 (0.140475)
User Time 19.4033 (0.153079)
System Time 10.17 (0.105357)
Percent CPU 167.333 (1.1547)
Context Switches 8371.33 (16.1658) Sleeps 10548.3 (17.0392)
Wed Jul 6 22:24:19 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 6 Run (std deviation):
Elapsed Time 13.5833 (0.0450925)
User Time 28.3067 (0.176163)
System Time 14.6033 (0.143643)
Percent CPU 315.333 (1.1547)
Context Switches 9239 (90.3715)
Sleeps 11119.3 (38.0175)
Wed Jul 6 22:34:05 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 6 Run (std deviation):
Elapsed Time 13.8433 (0.433628)
User Time 27.9667 (0.390042)
System Time 14.6133 (0.0757188)
Percent CPU 307.333 (12.4231)
Context Switches 9409.33 (84.2397) Sleeps 11415 (328.638)
Wed Jul 6 22:41:46 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 8 Run (std deviation):
Elapsed Time 13.6133 (0.065064)
User Time 28.5367 (0.0208167)
System Time 14.6733 (0.133166)
Percent CPU 316.667 (0.57735)
Context Switches 9486 (135.104)
Sleeps 11842.7 (263.788)
Wed Jul 6 22:51:42 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 8 Run (std deviation):
Elapsed Time 13.5733 (0.061101)
User Time 28.4833 (0.080208)
System Time 14.5933 (0.100664)
Percent CPU 317 (1)
Context Switches 9547 (70.7036)
Sleeps 11855.7 (35.0761)
<============================================>
Fri Jul 8 08:22:29 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 2 Run (std deviation):
Elapsed Time 17.746 (0.487217)
User Time 19.424 (0.145017)
System Time 10.218 (0.0816701)
Percent CPU 166.4 (3.78153)
Context Switches 8385.4 (49.687)
Sleeps 10594 (76.7887)
Fri Jul 8 08:30:37 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 4 Run (std deviation):
Elapsed Time 13.718 (0.339809)
User Time 27.95 (0.246069)
System Time 14.546 (0.255402)
Percent CPU 309.4 (4.27785)
Context Switches 7838.4 (92.6569) Sleeps 11082.2 (648.594)
Fri Jul 8 08:38:23 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 6 Run (std deviation):
Elapsed Time 13.506 (0.0844393)
User Time 28.33 (0.0977241)
System Time 14.584 (0.118025)
Percent CPU 317.2 (1.64317)
Context Switches 9345.6 (90.7045) Sleeps 11046 (106.59)
Fri Jul 8 08:46:11 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 8 Run (std deviation):
Elapsed Time 13.566 (0.0466905)
User Time 28.63 (0.05)
System Time 14.566 (0.0770065)
Percent CPU 318 (1)
Context Switches 9352.8 (103.323) Sleeps 11805.8 (122.534)
Fri Jul 8 09:00:10 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 2 Run (std deviation):
Elapsed Time 17.628 (0.463379)
User Time 19.426 (0.100399)
System Time 10.162 (0.10663)
Percent CPU 167.6 (4.39318)
Context Switches 8370.2 (24.8636) Sleeps 10568.4 (99.2184)
Fri Jul 8 09:08:20 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 4 Run (std deviation):
Elapsed Time 13.598 (0.172974)
User Time 27.846 (0.105262)
System Time 14.464 (0.0750333)
Percent CPU 310.6 (3.97492)
Context Switches 7799.8 (81.561)
Sleeps 10784.6 (64.5508)
Fri Jul 8 09:15:46 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 6 Run (std deviation):
Elapsed Time 14.296 (0.972538)
User Time 27.796 (0.320047)
System Time 14.488 (0.191755)
Percent CPU 296.4 (21.1967)
Context Switches 10623.6 (499.773) Sleeps 11212.8 (202.849)
Fri Jul 8 09:23:51 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 8 Run (std deviation):
Elapsed Time 13.614 (0.0219089)
User Time 28.674 (0.0270185)
System Time 14.658 (0.100349)
Percent CPU 317.8 (0.83666)
Context Switches 9374.2 (93.1166) Sleeps 11795.4 (187.807)
<================= nosmp tests==============>
Fri Jul 8 09:44:14 BDT 2011 3.0.0-rc5-tip-schedpatch-gbc7db00-dirty Average Optimal load -j 1 Run (std deviation):
Elapsed Time 31.364 (0.817484)
User Time 18.248 (0.0526308)
System Time 8.69 (0.0961769)
Percent CPU 85.4 (1.94936)
Context Switches 5713.2 (24.9339) Sleeps 10624 (64.5717)
Fri Jul 8 10:02:55 BDT 2011 3.0.0-rc5-tip-noschedpatch-gbc7db00 Average Optimal load -j 1 Run (std deviation):
Elapsed Time 32.868 (1.02021)
User Time 18.268 (0.0923038)
System Time 8.79 (0.109316)
Percent CPU 81.8 (2.16795)
Context Switches 5826.2 (74.5064) Sleeps 10787 (117.712) <================= nosmp end ==============>