sched: Avoid select_idle_sibling() for wake_affine(.sync=true)
Peter Zijlstra
maintainerRFC PATCH 1/1 sched: Avoid select_idle_sibling() for wake_affine(.sync=true)
Subject: sched: Avoid select_idle_sibling() for wake_affine(.sync=true)
From: Peter Zijlstra <[email protected]>
Date: Wed Sep 25 08:28:39 CEST 2013
When a task is the only running task and does a sync wakeup; avoid going through select_idle_sibling() as it doesn't know the current CPU is going to be idle shortly.
Without this two sync wakers will ping-pong between CPUs for no reason.
--- kernel/sched/fair.c | 10 ++++++++++ 1 file changed, 10 insertions(+)
kernel/sched/fair.c +10 -0
@@ -3461,6 +3461,16 @@ select_task_rq_fair(struct task_struct *if (cpu != prev_cpu &&wake_affine (affine_sd, p, sync)) prev_cpu = cpu; +/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go away. Going +* through select_idle_sibling will only lead to pointless ping-pong. +*/ +if (sync && prev_cpu == cpu &&cpu_rq (cpu)->nr_running ==1 ) { + new_cpu = cpu; + goto unlock; + } + new_cpu =select_idle_sibling (p, prev_cpu); goto unlock; }
Quoted 10 lines · Peter Zijlstra
Subject: sched: Avoid
select_idle_sibling()forwake_affine(.sync=true)
From: Peter Zijlstra <[email protected]>
Date: Wed Sep 25 08:28:39 CEST 2013When a task is the only running task and does a sync wakeup; avoid going through
select_idle_sibling()as it doesn't know the current CPU is going to be idle shortly.Without this two sync wakers will ping-pong between CPUs for no reason.
That will make pipe-test go fugly -> pretty, and help very fast/light localhost network, but eat heavier localhost overlap recovery. We need a working (and cheap) overlap detector scheme, so we can know when there is enough to be worth going after.
(I sent you some lmbench numbers offline a while back showing the two-faced little <b-word> in action, doing both good and evil)
Quoted 25 lines
Suggested-by Rik van Riel <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 10 ++++++++++ 1 file changed, 10 insertions(+)kernel/sched/fair.c +10
-0@@ -3461,6 +3461,16 @@ select_task_rq_fair(struct task_struct *if (cpu != prev_cpu &&wake_affine (affine_sd, p, sync)) prev_cpu = cpu; +/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go away. Going +* through select_idle_sibling will only lead to pointless ping-pong. +*/ +if (sync && prev_cpu == cpu &&cpu_rq (cpu)->nr_running ==1 ) { + new_cpu = cpu; + goto unlock; + } + new_cpu =select_idle_sibling (p, prev_cpu); goto unlock; }
Quoted 12 lines · Mike Galbraith
Quoted 10 lines · Peter Zijlstra
Subject: sched: Avoid
select_idle_sibling()forwake_affine(.sync=true)
From: Peter Zijlstra <[email protected]>
Date: Wed Sep 25 08:28:39 CEST 2013When a task is the only running task and does a sync wakeup; avoid going through
select_idle_sibling()as it doesn't know the current CPU is going to be idle shortly.Without this two sync wakers will ping-pong between CPUs for no reason.
Quoted 7 lines
That will make pipe-test go fugly -> pretty, and help very fast/light localhost network, but eat heavier localhost overlap recovery. We need a working (and cheap) overlap detector scheme, so we can know when there is enough to be worth going after.
(I sent you some lmbench numbers offline a while back showing the two-faced little <b-word> in action, doing both good and evil)
It seems like the choice between the overhead and a little possibility to balance the load :)
Like the case when we have:
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
waker busy idle idle
If the sync wakeup was on cpu0, we can:
1. choose cpu in core1 sg like we did usually
some overhead but tend to make the load a little balance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
idle busy wakee idle
2. choose cpu0 like the patch proposed
no overhead but tend to make the load a little more unbalance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
wakee busy idle idle
May be we should add a higher scope load balance check in wake_affine(), but that means higher overhead which is just what the patch want to reduce...
What about some discount for sync case inside select_idle_sibling()? For example we consider sync cpu as idle and prefer it more than the others?
Regards,
Michael Wang
Quoted 33 lines
Quoted 15 lines
Suggested-by Rik van Riel <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 10 ++++++++++ 1 file changed, 10 insertions(+)kernel/sched/fair.c +3
-0@@ -3461,6 +3461,16 @@ select_task_rq_fair(struct task_struct *if (cpu != prev_cpu &&wake_affine (affine_sd, p, sync)) prev_cpu = cpu; +/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go away. Going kernel/sched/fair.c select_task_rq_fair(struct task_struct * · line 3476
Quoted 10 lines
kernel/sched/fair.c +7
-0+* through select_idle_sibling will only lead to pointless ping-pong. +*/ +if (sync && prev_cpu == cpu &&cpu_rq (cpu)->nr_running ==1 ) { + new_cpu = cpu; + goto unlock; + } + new_cpu =select_idle_sibling (p, prev_cpu); goto unlock; }--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 30 lines · Michael wang
Quoted 12 lines · Mike Galbraith
Quoted 10 lines · Peter Zijlstra
Subject: sched: Avoid
select_idle_sibling()forwake_affine(.sync=true)
From: Peter Zijlstra <[email protected]>
Date: Wed Sep 25 08:28:39 CEST 2013When a task is the only running task and does a sync wakeup; avoid going through
select_idle_sibling()as it doesn't know the current CPU is going to be idle shortly.Without this two sync wakers will ping-pong between CPUs for no reason.
Quoted 7 lines
That will make pipe-test go fugly -> pretty, and help very fast/light localhost network, but eat heavier localhost overlap recovery. We need a working (and cheap) overlap detector scheme, so we can know when there is enough to be worth going after.
(I sent you some lmbench numbers offline a while back showing the two-faced little <b-word> in action, doing both good and evil)
It seems like the choice between the overhead and a little possibility to balance the load :)
Like the case when we have:
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
waker busy idle idle
Quoted 7 lines
If the sync wakeup was on cpu0, we can:
1. choose cpu in core1 sg like we did usually
some overhead but tend to make the load a little balance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
idle busy wakee idle
Reducing latency and increasing throughput when the waker isn't really really going to immediately schedule off as the hint implies. Nice for bursty loads and ramp.
The breakeven point is going up though. If you don't have nohz throttled, you eat tick start/stop overhead, and the menu governor recently added yet more overhead, so maybe we should say hell with it.
Quoted 9 lines
2. choose cpu0 like the patch proposed
no overhead but tend to make the load a little more unbalance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
wakee busy idle idleMay be we should add a higher scope load balance check in
wake_affine(), but that means higher overhead which is just what the patch want to reduce...
Yeah, more overhead is the last thing we need.
Quoted 2 lines
What about some discount for sync case inside
select_idle_sibling()? For example we consider sync cpu as idle and prefer it more than the others?
That's what the sync hint does. Problem is, it's a hint. If it were truth, there would be no point in calling select_idle_sibling().
-Mike
On 09/26/2013 11:41 AM, Mike Galbraith wrote:
[snip]
Quoted 14 lines
Quoted 6 lines
Like the case when we have:
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
waker busy idle idleQuoted 7 lines
If the sync wakeup was on cpu0, we can:
1. choose cpu in core1 sg like we did usually
some overhead but tend to make the load a little balance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
idle busy wakee idle
Quoted 7 lines
Reducing latency and increasing throughput when the waker isn't really really going to immediately schedule off as the hint implies. Nice for bursty loads and ramp.
The breakeven point is going up though. If you don't have nohz throttled, you eat tick start/stop overhead, and the menu governor recently added yet more overhead, so maybe we should say hell with it.
Exactly, more and more factors to be considered, we say things get balanced but actually it's not the best choice...
Quoted 11 lines
Quoted 10 lines
2. choose cpu0 like the patch proposed
no overhead but tend to make the load a little more unbalance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
wakee busy idle idleMay be we should add a higher scope load balance check in
wake_affine(), but that means higher overhead which is just what the patch want to reduce...
Quoted 7 lines
Yeah, more overhead is the last thing we need.
Quoted 2 lines
What about some discount for sync case inside
select_idle_sibling()? For example we consider sync cpu as idle and prefer it more than the others?That's what the sync hint does. Problem is, it's a hint. If it were truth, there would be no point in calling
select_idle_sibling().
Just wondering if the hint was wrong in most of the time, then why don't we remove it...
Otherwise I think we can still utilize it to make some decision tends to be correct, don't we?
Regards,
Michael Wang
Quoted 9 lines
-Mike
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 40 lines · Michael wang
On 09/26/2013 11:41 AM, Mike Galbraith wrote:
[snip]Quoted 14 lines
Quoted 6 lines
Like the case when we have:
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
waker busy idle idleQuoted 7 lines
If the sync wakeup was on cpu0, we can:
1. choose cpu in core1 sg like we did usually
some overhead but tend to make the load a little balance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
idle busy wakee idleQuoted 7 lines
Reducing latency and increasing throughput when the waker isn't really really going to immediately schedule off as the hint implies. Nice for bursty loads and ramp.
The breakeven point is going up though. If you don't have nohz throttled, you eat tick start/stop overhead, and the menu governor recently added yet more overhead, so maybe we should say hell with it.
Exactly, more and more factors to be considered, we say things get balanced but actually it's not the best choice...
Quoted 13 lines
Quoted 10 lines
2. choose cpu0 like the patch proposed
no overhead but tend to make the load a little more unbalance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
wakee busy idle idleMay be we should add a higher scope load balance check in
wake_affine(), but that means higher overhead which is just what the patch want to reduce...Yeah, more overhead is the last thing we need.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
What about some discount for sync case inside
select_idle_sibling()? For example we consider sync cpu as idle and prefer it more than the others?That's what the sync hint does. Problem is, it's a hint. If it were truth, there would be no point in calling
select_idle_sibling().Just wondering if the hint was wrong in most of the time, then why don't we remove it...
For very fast/light network ping-pong micro-benchmarks, it is right. For pipe-test, it's absolutely right, jabbering parties are 100% synchronous, there is nada/nil/zip/diddly squat overlap reclaimable.. but in the real world, it ain't necessarily so.
Quoted 2 lines
Otherwise I think we can still utilize it to make some decision tends to be correct, don't we?
Sometimes :)
-Mike
Quoted 55 lines · Mike Galbraith
Quoted 40 lines · Michael wang
On 09/26/2013 11:41 AM, Mike Galbraith wrote:
[snip]Quoted 14 lines
Quoted 6 lines
Like the case when we have:
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
waker busy idle idleQuoted 7 lines
If the sync wakeup was on cpu0, we can:
1. choose cpu in core1 sg like we did usually
some overhead but tend to make the load a little balance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
idle busy wakee idleQuoted 7 lines
Reducing latency and increasing throughput when the waker isn't really really going to immediately schedule off as the hint implies. Nice for bursty loads and ramp.
The breakeven point is going up though. If you don't have nohz throttled, you eat tick start/stop overhead, and the menu governor recently added yet more overhead, so maybe we should say hell with it.
Exactly, more and more factors to be considered, we say things get balanced but actually it's not the best choice...
Quoted 13 lines
Quoted 10 lines
2. choose cpu0 like the patch proposed
no overhead but tend to make the load a little more unbalance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
wakee busy idle idleMay be we should add a higher scope load balance check in
wake_affine(), but that means higher overhead which is just what the patch want to reduce...Yeah, more overhead is the last thing we need.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
What about some discount for sync case inside
select_idle_sibling()? For example we consider sync cpu as idle and prefer it more than the others?That's what the sync hint does. Problem is, it's a hint. If it were truth, there would be no point in calling
select_idle_sibling().Just wondering if the hint was wrong in most of the time, then why don't we remove it...
For very fast/light network ping-pong micro-benchmarks, it is right. For pipe-test, it's absolutely right, jabbering parties are 100% synchronous, there is nada/nil/zip/diddly squat overlap reclaimable.. but in the real world, it ain't necessarily so.
Quoted 4 lines
Quoted 2 lines
Otherwise I think we can still utilize it to make some decision tends to be correct, don't we?
Sometimes :)
P.S. while we're slapping select_idle_sibling()'s _evil_ face, let's give it a pat on the head too. It showed regressions in bright red. Put pipe-test on one core, you only see scheduler weight.. but entering and exiting idle is part of the fast path, whether you're exercising it by doing something silly or not.
-Mike
Quoted 55 lines · Mike Galbraith
Quoted 40 lines · Michael wang
On 09/26/2013 11:41 AM, Mike Galbraith wrote:
[snip]Quoted 14 lines
Quoted 6 lines
Like the case when we have:
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
waker busy idle idleQuoted 7 lines
If the sync wakeup was on cpu0, we can:
1. choose cpu in core1 sg like we did usually
some overhead but tend to make the load a little balance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
idle busy wakee idleQuoted 7 lines
Reducing latency and increasing throughput when the waker isn't really really going to immediately schedule off as the hint implies. Nice for bursty loads and ramp.
The breakeven point is going up though. If you don't have nohz throttled, you eat tick start/stop overhead, and the menu governor recently added yet more overhead, so maybe we should say hell with it.
Exactly, more and more factors to be considered, we say things get balanced but actually it's not the best choice...
Quoted 13 lines
Quoted 10 lines
2. choose cpu0 like the patch proposed
no overhead but tend to make the load a little more unbalance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
wakee busy idle idleMay be we should add a higher scope load balance check in
wake_affine(), but that means higher overhead which is just what the patch want to reduce...Yeah, more overhead is the last thing we need.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
What about some discount for sync case inside
select_idle_sibling()? For example we consider sync cpu as idle and prefer it more than the others?That's what the sync hint does. Problem is, it's a hint. If it were truth, there would be no point in calling
select_idle_sibling().Just wondering if the hint was wrong in most of the time, then why don't we remove it...
For very fast/light network ping-pong micro-benchmarks, it is right. For pipe-test, it's absolutely right, jabbering parties are 100% synchronous, there is nada/nil/zip/diddly squat overlap reclaimable.. but in the real world, it ain't necessarily so.
Quoted 4 lines
Quoted 2 lines
Otherwise I think we can still utilize it to make some decision tends to be correct, don't we?
Sometimes :)
Ok, a double-edged sword I see :)
May be we can wave it carefully here, give the discount to a bigger scope not the sync cpu, for example:
sg1 sg2 cpu0 cpu1 cpu2 cpu3 cpu4 cpu5 cpu6 cpu7 waker idle idle idle idle idle idle idle
If it's sync wakeup on cpu0 (only waker), and the sg is wide enough, which means one cpu is not so influencial, then suppose cpu0 to be idle could be more safe, also prefer sg1 than sg2 is more likely to be right.
And we can still choose idle-cpu at final step, like cpu1 in this case, to avoid the risk that waker don't get off as it said.
The key point is to reduce the influence of sync, trust a little but not totally ;-)
Regards,
Michael Wang
Quoted 9 lines
-Mike
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 74 lines · Michael wang
Quoted 55 lines · Mike Galbraith
Quoted 40 lines · Michael wang
On 09/26/2013 11:41 AM, Mike Galbraith wrote:
[snip]Quoted 14 lines
Quoted 6 lines
Like the case when we have:
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
waker busy idle idleQuoted 7 lines
If the sync wakeup was on cpu0, we can:
1. choose cpu in core1 sg like we did usually
some overhead but tend to make the load a little balance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
idle busy wakee idleQuoted 7 lines
Reducing latency and increasing throughput when the waker isn't really really going to immediately schedule off as the hint implies. Nice for bursty loads and ramp.
The breakeven point is going up though. If you don't have nohz throttled, you eat tick start/stop overhead, and the menu governor recently added yet more overhead, so maybe we should say hell with it.
Exactly, more and more factors to be considered, we say things get balanced but actually it's not the best choice...
Quoted 13 lines
Quoted 10 lines
2. choose cpu0 like the patch proposed
no overhead but tend to make the load a little more unbalance
core0 sg core1 sg
cpu0 cpu1 cpu2 cpu3
wakee busy idle idleMay be we should add a higher scope load balance check in
wake_affine(), but that means higher overhead which is just what the patch want to reduce...Yeah, more overhead is the last thing we need.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
What about some discount for sync case inside
select_idle_sibling()? For example we consider sync cpu as idle and prefer it more than the others?That's what the sync hint does. Problem is, it's a hint. If it were truth, there would be no point in calling
select_idle_sibling().Just wondering if the hint was wrong in most of the time, then why don't we remove it...
For very fast/light network ping-pong micro-benchmarks, it is right. For pipe-test, it's absolutely right, jabbering parties are 100% synchronous, there is nada/nil/zip/diddly squat overlap reclaimable.. but in the real world, it ain't necessarily so.
Quoted 4 lines
Quoted 2 lines
Otherwise I think we can still utilize it to make some decision tends to be correct, don't we?
Sometimes :)
Ok, a double-edged sword I see :)
May be we can wave it carefully here, give the discount to a bigger scope not the sync cpu, for example:
sg1 sg2 cpu0 cpu1 cpu2 cpu3 cpu4 cpu5 cpu6 cpu7 waker idle idle idle idle idle idle idleIf it's sync wakeup on cpu0 (only waker), and the sg is wide enough, which means one cpu is not so influencial, then suppose cpu0 to be idle could be more safe, also prefer sg1 than sg2 is more likely to be right.
Quoted 5 lines
And we can still choose idle-cpu at final step, like cpu1 in this case, to avoid the risk that waker don't get off as it said.
The key point is to reduce the influence of sync, trust a little but not totally ;-)
What we need is a dirt cheap way to fairly accurately predict overlap potential (todo: write omniscience().. patent, buy planet).
-Mike
On 09/26/2013 03:09 PM, Mike Galbraith wrote:
[snip]
Quoted 14 lines
Quoted 14 lines
Ok, a double-edged sword I see :)
May be we can wave it carefully here, give the discount to a bigger scope not the sync cpu, for example:
sg1 sg2 cpu0 cpu1 cpu2 cpu3 cpu4 cpu5 cpu6 cpu7 waker idle idle idle idle idle idle idleIf it's sync wakeup on cpu0 (only waker), and the sg is wide enough, which means one cpu is not so influencial, then suppose cpu0 to be idle could be more safe, also prefer sg1 than sg2 is more likely to be right.
Quoted 8 lines
Quoted 5 lines
And we can still choose idle-cpu at final step, like cpu1 in this case, to avoid the risk that waker don't get off as it said.
The key point is to reduce the influence of sync, trust a little but not totally ;-)
What we need is a dirt cheap way to fairly accurately predict overlap potential (todo: write
omniscience().. patent, buy planet).
Agree, solutions for such cases are usually incredible ;-)
Regards,
Michael Wang
Quoted 9 lines
-Mike
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Peter Zijlstra
maintainerQuoted 4 lines · Mike Galbraith
That will make pipe-test go fugly -> pretty, and help very fast/light localhost network, but eat heavier localhost overlap recovery. We need a working (and cheap) overlap detector scheme, so we can know when there is enough to be worth going after.
We used to have an overlap detectoring thing.. It went away though.
But see if you can make something like the below work?
You could make it a general overlap thing and try without the sync too I suppose..
--- include/linux/sched.h | 3 +++ kernel/sched/fair.c | 25 +++++++++++++++++++++++++ 2 files changed, 28 insertions(+)
include/linux/sched.h +3 -0
@@ -974,6 +974,9 @@ struct sched_entity {u64 vruntime;u64 prev_sum_exec_runtime; +u64 last_sync_wakeup; +u64 avg_overlap; +u64 nr_migrations;#ifdef CONFIG_SCHEDSTATS
kernel/sched/fair.c +25 -0
@@ -2913,6 +2913,17 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)struct sched_entity *se = &p->se;int task_sleep = flags &DEQUEUE_SLEEP ; +if (se->last_sync_wakeup) { +u64 overlap; +s64 diff; + + overlap = rq->clock - se->last_sync_wakeup; + se->last_sync_wakeup =0 ; + + diff = overlap - se->avg_overlap; + se->avg_overlap += diff >>8 ; + } +for_each_sched_entity (se) { cfs_rq =cfs_rq_of (se);dequeue_entity (cfs_rq, se, flags);
@@ -3429,6 +3440,9 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)int want_affine =0 ;int sync = wake_flags &WF_SYNC ; +if (sync) + p->se.last_sync_wakeup =sched_clock_cpu (cpu); +if (p->nr_cpus_allowed ==1 )return prev_cpu;
@@ -3461,6 +3475,17 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)if (cpu != prev_cpu &&wake_affine (affine_sd, p, sync)) prev_cpu = cpu; +/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go-away. Going +* through select_idle_sibling will only lead to pointless ping-pong. +*/ +if (sync && prev_cpu == cpu &&cpu_rq (cpu)->nr_running ==1 && + current->se.avg_overlap <10000 ) { + new_cpu = cpu; + goto unlock; + } + new_cpu =select_idle_sibling (p, prev_cpu); goto unlock; }
Peter Zijlstra
maintainerkernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3448
Quoted 10 lines · Peter Zijlstra
kernel/sched/fair.c +3
-0@@ -3429,6 +3440,9 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)int want_affine =0 ;int sync = wake_flags &WF_SYNC ; +if (sync) + p->se.last_sync_wakeup =sched_clock_cpu (cpu); +if (p->nr_cpus_allowed ==1 )return prev_cpu;
Oh, I suppose something like:
if (sync && !p->se.last_sync_wakeup)
p->se.last_sync_wakeup = sched_clock_cpu(cpu);
is also a nice variation to try..
Quoted 65 lines · Peter Zijlstra
Quoted 4 lines · Mike Galbraith
That will make pipe-test go fugly -> pretty, and help very fast/light localhost network, but eat heavier localhost overlap recovery. We need a working (and cheap) overlap detector scheme, so we can know when there is enough to be worth going after.
We used to have an overlap detectoring thing.. It went away though.
But see if you can make something like the below work?
You could make it a general overlap thing and try without the sync too I suppose..
--- include/linux/sched.h | 3 +++ kernel/sched/fair.c | 25 +++++++++++++++++++++++++ 2 files changed, 28 insertions(+)include/linux/sched.h +3
-0@@ -974,6 +974,9 @@ struct sched_entity {u64 vruntime;u64 prev_sum_exec_runtime; +u64 last_sync_wakeup; +u64 avg_overlap; +u64 nr_migrations;#ifdef CONFIG_SCHEDSTATS kernel/sched/fair.c +14
-0@@ -2913,6 +2913,17 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)struct sched_entity *se = &p->se;int task_sleep = flags &DEQUEUE_SLEEP ; +if (se->last_sync_wakeup) { +u64 overlap; +s64 diff; + + overlap = rq->clock - se->last_sync_wakeup; + se->last_sync_wakeup =0 ; + + diff = overlap - se->avg_overlap; + se->avg_overlap += diff >>8 ; + } +for_each_sched_entity (se) { cfs_rq =cfs_rq_of (se);dequeue_entity (cfs_rq, se, flags);@@ -3429,6 +3440,9 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)int want_affine =0 ;int sync = wake_flags &WF_SYNC ; +if (sync) + p->se.last_sync_wakeup =sched_clock_cpu (cpu); +if (p->nr_cpus_allowed ==1 )return prev_cpu;
kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3483
Quoted 9 lines
kernel/sched/fair.c +6
-0@@ -3461,6 +3475,17 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)if (cpu != prev_cpu &&wake_affine (affine_sd, p, sync)) prev_cpu = cpu; +/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go-away. Going +* through select_idle_sibling will only lead to pointless ping-pong. +*/ + if (sync && prev_cpu == cpu && cpu_rq(cpu)->nr_running == 1 &&
I've long thought of trying something like this.
I like the intent but I'd go a step further in that I think we want to also implicitly extract WF_SYNC itself. While pipe_test is a good microbenchmark it's not entirely representative since, in reality, overlap is most usefully applied to threads in the same process -- and they rarely communicate using a pipe.
What we really then care about is predicting the overlap associated with userspace synchronization objects, typically built on top of futexes. Unfortunately the existence/use of per-thread futexes reduces how much state you could usefully associate with the futex. One approach might be to hash (with some small saturating counter) against rip. But this gets more complicated quite quickly.
Quoted 8 lines
kernel/sched/fair.c +5
-0+ current->se.avg_overlap < 10000) { + new_cpu = cpu; + goto unlock; + } + new_cpu =select_idle_sibling (p, prev_cpu); goto unlock; }
Peter Zijlstra
maintainerQuoted 11 lines · Paul Turner
kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3483
Quoted 6 lines
kernel/sched/fair.c +6
-0+/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go-away. Going +* through select_idle_sibling will only lead to pointless ping-pong. +*/ + if (sync && prev_cpu == cpu && cpu_rq(cpu)->nr_running == 1 &&I've long thought of trying something like this.
I like the intent but I'd go a step further in that I think we want to also implicitly extract
WF_SYNCitself.
I have vague memories of actually trying something like that a good number of years ago.. sadly that's all I remember about it.
Quoted 6 lines
What we really then care about is predicting the overlap associated with userspace synchronization objects, typically built on top of futexes. Unfortunately the existence/use of per-thread futexes reduces how much state you could usefully associate with the futex. One approach might be to hash (with some small saturating counter) against rip. But this gets more complicated quite quickly.
Why would you need per object storage? To further granulate the predicted overlap? instead of having one per task, you have one per object?
Quoted 23 lines · Peter Zijlstra
Quoted 11 lines · Paul Turner
kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3483
Quoted 6 lines
kernel/sched/fair.c +6
-0+/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go-away. Going +* through select_idle_sibling will only lead to pointless ping-pong. +*/ + if (sync && prev_cpu == cpu && cpu_rq(cpu)->nr_running == 1 &&I've long thought of trying something like this.
I like the intent but I'd go a step further in that I think we want to also implicitly extract
WF_SYNCitself.I have vague memories of actually trying something like that a good number of years ago.. sadly that's all I remember about it.
Quoted 6 lines
What we really then care about is predicting the overlap associated with userspace synchronization objects, typically built on top of futexes. Unfortunately the existence/use of per-thread futexes reduces how much state you could usefully associate with the futex. One approach might be to hash (with some small saturating counter) against rip. But this gets more complicated quite quickly.
Quoted 3 lines
Why would you need per object storage? To further granulate the predicted overlap? instead of having one per task, you have one per object?
It is my intuition that there are a few common objects with fairly polarized behavior: I.e. For condition variables and producer consumer queues, a wakeup strongly predicts blocking. Whereas for locks protecting objects, e.g. a Mutex, would be expected to have the opposite behavior.
For this hint to be beneficial you have to get it right frequently, getting it wrong in the first case hurts cache and in the second hurts parallelism. Today we always err on the side of hurting locality since the cost of getting it wrong is better bounded. These are sufficiently common, and likely to be interspersed, that I suspect allowing them to interact on a thread-wide counter will basically give a mush result (or even be an anti predictor since it will strongly favor the last observation) an an input.
Peter Zijlstra
maintainerQuoted 5 lines · Paul Turner
It is my intuition that there are a few common objects with fairly polarized behavior: I.e. For condition variables and producer consumer queues, a wakeup strongly predicts blocking. Whereas for locks protecting objects, e.g. a Mutex, would be expected to have the opposite behavior.
Agreed; however none of those seem to have the property we're looking for.
Even produces consumer queues on their own don't generate the alternating patterns we're looking for with the SYNC hint.
We need a 'guarantee' that the waker is going to stop until the wakee is done.
What we're looking for is the typical synchronous request-reply like pattern -- and that doesn't seem to correlate to any one locking object.
Rather it is an inter-task relation; so task state does make sense in finding them. We could for instance try and infer which task is servicing requests; and then we know that requesting tasks will sleep until reply.
Peter Zijlstra
maintainerQuoted 16 lines · Peter Zijlstra
Quoted 5 lines · Paul Turner
It is my intuition that there are a few common objects with fairly polarized behavior: I.e. For condition variables and producer consumer queues, a wakeup strongly predicts blocking. Whereas for locks protecting objects, e.g. a Mutex, would be expected to have the opposite behavior.
Agreed; however none of those seem to have the property we're looking for.
Even produces consumer queues on their own don't generate the alternating patterns we're looking for with the SYNC hint.
We need a 'guarantee' that the waker is going to stop until the wakee is done.
Quoted 8 lines
What we're looking for is the typical synchronous request-reply like pattern -- and that doesn't seem to correlate to any one locking object.
Rather it is an inter-task relation; so task state does make sense in finding them. We could for instance try and infer which task is servicing requests; and then we know that requesting tasks will sleep until reply.
Oh never mind, I see what you meant, the edges in that graph are the locks.
Can't use RIPs for futexes though; you'd likely end up in the one pthread_mutex_lock() implementation or such.
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Mike Galbraith
That will make pipe-test go fugly -> pretty, and help very fast/light localhost network, but eat heavier localhost overlap recovery. We need a working (and cheap) overlap detector scheme, so we can know when there is enough to be worth going after.
We used to have an overlap detectoring thing.. It went away though.
Yup.. guilty as charged your honor.
Quoted 1 line
But see if you can make something like the below work?
It'll have the same, preemption etc., problems as the whacked. Could bring that back and have another go at making it actually work, maybe it'll be good enough to cause more gain than pain.
Quoted 72 lines
You could make it a general overlap thing and try without the sync too I suppose..
--- include/linux/sched.h | 3 +++ kernel/sched/fair.c | 25 +++++++++++++++++++++++++ 2 files changed, 28 insertions(+)include/linux/sched.h +3
-0@@ -974,6 +974,9 @@ struct sched_entity {u64 vruntime;u64 prev_sum_exec_runtime; +u64 last_sync_wakeup; +u64 avg_overlap; +u64 nr_migrations;#ifdef CONFIG_SCHEDSTATS kernel/sched/fair.c +25
-0@@ -2913,6 +2913,17 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)struct sched_entity *se = &p->se;int task_sleep = flags &DEQUEUE_SLEEP ; +if (se->last_sync_wakeup) { +u64 overlap; +s64 diff; + + overlap = rq->clock - se->last_sync_wakeup; + se->last_sync_wakeup =0 ; + + diff = overlap - se->avg_overlap; + se->avg_overlap += diff >>8 ; + } +for_each_sched_entity (se) { cfs_rq =cfs_rq_of (se);dequeue_entity (cfs_rq, se, flags);@@ -3429,6 +3440,9 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)int want_affine =0 ;int sync = wake_flags &WF_SYNC ; +if (sync) + p->se.last_sync_wakeup =sched_clock_cpu (cpu); +if (p->nr_cpus_allowed ==1 )return prev_cpu;@@ -3461,6 +3475,17 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)if (cpu != prev_cpu &&wake_affine (affine_sd, p, sync)) prev_cpu = cpu; +/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go-away. Going +* through select_idle_sibling will only lead to pointless ping-pong. +*/ +if (sync && prev_cpu == cpu &&cpu_rq (cpu)->nr_running ==1 && + current->se.avg_overlap <10000 ) { + new_cpu = cpu; + goto unlock; + } + new_cpu =select_idle_sibling (p, prev_cpu); goto unlock; }
Hi, Peter
On 09/26/2013 05:58 PM, Peter Zijlstra wrote:
[snip]
Quoted 23 lines
kernel/sched/fair.c +11
-0@@ -2913,6 +2913,17 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)struct sched_entity *se = &p->se;int task_sleep = flags &DEQUEUE_SLEEP ; +if (se->last_sync_wakeup) { +u64 overlap; +s64 diff; + + overlap = rq->clock - se->last_sync_wakeup; + se->last_sync_wakeup =0 ; + + diff = overlap - se->avg_overlap; + se->avg_overlap += diff >>8 ; + } +for_each_sched_entity (se) { cfs_rq =cfs_rq_of (se);dequeue_entity (cfs_rq, se, flags);
kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3444
Quoted 5 lines
kernel/sched/fair.c +2
-0@@ -3429,6 +3440,9 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)int want_affine =0 ;int sync = wake_flags &WF_SYNC ; +if (sync) + p->se.last_sync_wakeup =sched_clock_cpu (cpu);
Forgive me but I'm trying to understand it... why not 'current' but 'p' here? we want the get off speed of waker or the working time of wakee?
Regards,
Michael Wang
Quoted 28 lines
kernel/sched/fair.c +12
-1+if (p->nr_cpus_allowed ==1 )return prev_cpu;@@ -3461,6 +3475,17 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)if (cpu != prev_cpu &&wake_affine (affine_sd, p, sync)) prev_cpu = cpu; +/* +* Don't bother with select_idle_sibling() in the case of a sync wakeup +* where we know the only running task will soon go-away. Going +* through select_idle_sibling will only lead to pointless ping-pong. +*/ +if (sync && prev_cpu == cpu &&cpu_rq (cpu)->nr_running ==1 && + current->se.avg_overlap <10000 ) { + new_cpu = cpu; + goto unlock; + } + new_cpu =select_idle_sibling (p, prev_cpu); goto unlock; } --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Peter Zijlstra
maintainerQuoted 5 lines · Michael wang
kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3444
Quoted 2 lines
kernel/sched/fair.c +2
-0+if (sync) + p->se.last_sync_wakeup =sched_clock_cpu (cpu);Forgive me but I'm trying to understand it... why not 'current' but 'p' here? we want the get off speed of waker or the working time of wakee?
Because I'm an idiot? ;-)
Quoted 8 lines · Peter Zijlstra
Quoted 5 lines · Michael wang
kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3444
Quoted 2 lines
kernel/sched/fair.c +2
-0+if (sync) + p->se.last_sync_wakeup =sched_clock_cpu (cpu);Forgive me but I'm trying to understand it... why not 'current' but 'p' here? we want the get off speed of waker or the working time of wakee?
Because I'm an idiot? ;-)
Well, I know you are full of good ideas ;-)
Regards,
Michael Wang
Quoted 6 lines
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/