sched/fair: Optimize select_idle_core
PATCH 1/1 sched/fair: Optimize select_idle_core
Currently we loop through all threads of a core to evaluate if the core is idle or not. This is unnecessary. If a thread of a core is not idle, skip evaluating other threads of a core.
--- kernel/sched/fair.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/fair.c +4 -2
@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, intbool idle = true;for_each_cpu (cpu,cpu_smt_mask (core)) { -__cpumask_clear_cpu (cpu, cpus); -if (!available_idle_cpu (cpu)) +if (!available_idle_cpu (cpu)) { idle = false; +break ; + } } +cpumask_andnot (cpus, cpus,cpu_smt_mask (core));if (idle)return core;
Signature · 1 line
2.18.1
Vincent Guittot
maintainerHi Srikar,
Quoted 4 lines · Srikar Dronamraju
Currently we loop through all threads of a core to evaluate if the core is idle or not. This is unnecessary. If a thread of a core is not idle, skip evaluating other threads of a core.
I think that the goal is also to clear all CPUs of the core from the cpumask of the loop above so it will not try the same core next time
Quoted 28 lines
Signed-off-by Srikar Dronamraju <[email protected]>--- kernel/sched/fair.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)kernel/sched/fair.c +4
-3@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, intbool idle = true;for_each_cpu (cpu,cpu_smt_mask (core)) { -__cpumask_clear_cpu (cpu, cpus); -if (!available_idle_cpu (cpu)) +if (!available_idle_cpu (cpu)) { idle = false; +break ; + } } +cpumask_andnot (cpus, cpus,cpu_smt_mask (core));if (idle)return core; --2.18.1
Quoted 5 lines · Vincent Guittot
Hi Srikar,
Quoted 1 line · Srikar Dronamraju
Quoted 8 lines
Quoted 3 lines
Currently we loop through all threads of a core to evaluate if the core is idle or not. This is unnecessary. If a thread of a core is not idle, skip evaluating other threads of a core.
I think that the goal is also to clear all CPUs of the core from the cpumask of the loop above so it will not try the same core next time
Quoted 1 line
That goal we still continue to maintain by the way of cpumask_andnot. i.e instead of clearing CPUs one at a time, we clear all the CPUs in the core at one shot.
Quoted 27 lines
Quoted 27 lines
Signed-off-by Srikar Dronamraju <[email protected]>--- kernel/sched/fair.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)kernel/sched/fair.c +4
-3@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, intbool idle = true;for_each_cpu (cpu,cpu_smt_mask (core)) { -__cpumask_clear_cpu (cpu, cpus); -if (!available_idle_cpu (cpu)) +if (!available_idle_cpu (cpu)) { idle = false; +break ; + } } +cpumask_andnot (cpus, cpus,cpu_smt_mask (core));if (idle)return core; --2.18.1
Signature · 2 lines
Thanks and Regards Srikar Dronamraju
Vincent Guittot
maintainerQuoted 12 lines · Srikar Dronamraju
Quoted 9 lines · Vincent Guittot
Hi Srikar,
Quoted 4 lines · Srikar Dronamraju
Currently we loop through all threads of a core to evaluate if the core is idle or not. This is unnecessary. If a thread of a core is not idle, skip evaluating other threads of a core.
Quoted 8 lines
Quoted 4 lines
I think that the goal is also to clear all CPUs of the core from the cpumask of the loop above so it will not try the same core next time
Quoted 1 line
That goal we still continue to maintain by the way of
cpumask_andnot. i.e instead of clearing CPUs one at a time, we clear all the CPUs in the core at one shot.
ah yes sorry, I have been to quick and overlooked the cpumask_andnot line
Quoted 33 lines
Quoted 23 lines
Quoted 23 lines
Signed-off-by Srikar Dronamraju <[email protected]>--- kernel/sched/fair.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)kernel/sched/fair.c +4
-2@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, intbool idle = true;for_each_cpu (cpu,cpu_smt_mask (core)) { -__cpumask_clear_cpu (cpu, cpus); -if (!available_idle_cpu (cpu)) +if (!available_idle_cpu (cpu)) { idle = false; +break ; + } } +cpumask_andnot (cpus, cpus,cpu_smt_mask (core));Quoted 5 lines
Quoted 5 lines
kernel/sched/fair.c +0
-1if (idle)return core; --2.18.1
--
Thanks and Regards
Srikar Dronamraju
Quoted 19 lines · Vincent Guittot
Quoted 17 lines · Srikar Dronamraju
Quoted 13 lines · Vincent Guittot
Hi Srikar,
Quoted 4 lines · Srikar Dronamraju
Currently we loop through all threads of a core to evaluate if the core is idle or not. This is unnecessary. If a thread of a core is not idle, skip evaluating other threads of a core.
I think that the goal is also to clear all CPUs of the core from the cpumask of the loop above so it will not try the same core next time
Quoted 1 line
Quoted 6 lines
Quoted 3 lines
That goal we still continue to maintain by the way of
cpumask_andnot. i.e instead of clearing CPUs one at a time, we clear all the CPUs in the core at one shot.ah yes sorry, I have been to quick and overlooked the
cpumask_andnotline
Just to reiterate why this is necessary.
Currently, even if the first thread of a core is not idle, we iterate through all threads of the core and individually clear the CPU from the core mask.
Collecting ticks on a Power 9 SMT 8 system around select_idle_core while running schbench shows us that
(units are in ticks, hence lesser is better)
Without patch
N Min Max Median Avg Stddev
x 130 151 1083 284 322.72308 144.41494
With patch
N Min Max Median Avg Stddev Improvement
x 164 88 610 201 225.79268 106.78943 30.03%
Signature · 2 lines
Thanks and Regards Srikar Dronamraju
Quoted 43 lines · Srikar Dronamraju
Quoted 19 lines · Vincent Guittot
Quoted 17 lines · Srikar Dronamraju
Quoted 13 lines · Vincent Guittot
Hi Srikar,
Quoted 4 lines · Srikar Dronamraju
Currently we loop through all threads of a core to evaluate if the core is idle or not. This is unnecessary. If a thread of a core is not idle, skip evaluating other threads of a core.
I think that the goal is also to clear all CPUs of the core from the cpumask of the loop above so it will not try the same core next time
Quoted 1 line
Quoted 6 lines
Quoted 3 lines
That goal we still continue to maintain by the way of
cpumask_andnot. i.e instead of clearing CPUs one at a time, we clear all the CPUs in the core at one shot.ah yes sorry, I have been to quick and overlooked the
cpumask_andnotlineJust to reiterate why this is necessary.
Currently, even if the first thread of a core is not idle, we iterate through all threads of the core and individually clear the CPU from the core mask.Collecting ticks on a Power 9 SMT 8 system around
select_idle_corewhile running schbench shows us that(units are in ticks, hence lesser is better)
Without patch
N Min Max Median Avg Stddev
x 130 151 1083 284 322.72308 144.41494
Quoted 3 lines
With patch
N Min Max Median Avg Stddev Improvement
x 164 88 610 201 225.79268 106.78943 30.03%
Thanks for the figures. Might be good to include them in the commit message
Quoted 5 lines
--
Thanks and Regards
Srikar Dronamraju
Hi Vincent,
Quoted 10 lines
Quoted 10 lines
Collecting ticks on a Power 9 SMT 8 system around
select_idle_corewhile running schbench shows us that(units are in ticks, hence lesser is better)
Without patch
N Min Max Median Avg Stddev
x 130 151 1083 284 322.72308 144.41494
Quoted 6 lines
Quoted 3 lines
With patch
N Min Max Median Avg Stddev Improvement
x 164 88 610 201 225.79268 106.78943 30.03%Thanks for the figures. Might be good to include them in the commit message
Since I needed a debug/hack patch on top of upstream/my-patch to get these numbers, I wasn't sure if this would be ideal to be included in a commit message. But if you still think it's good to have, I can re-spin the patch with these numbers included.
Quoted 2 lines
Reviewed-by Vincent Guittot <[email protected]>
Thanks.
Signature · 2 lines
Thanks and Regards Srikar Dronamraju
Vincent Guittot
maintainerQuoted 17 lines · Srikar Dronamraju
Hi Vincent,
Quoted 14 lines
Quoted 13 lines
Collecting ticks on a Power 9 SMT 8 system around
select_idle_corewhile running schbench shows us that(units are in ticks, hence lesser is better)
Without patch
N Min Max Median Avg Stddev
x 130 151 1083 284 322.72308 144.41494With patch
N Min Max Median Avg Stddev Improvement
x 164 88 610 201 225.79268 106.78943 30.03%
Quoted 7 lines
Quoted 2 lines
Thanks for the figures. Might be good to include them in the commit message
Since I needed a debug/hack patch on top of upstream/my-patch to get these numbers, I wasn't sure if this would be ideal to be included in a commit message. But if you still think it's good to have, I can re-spin the patch with these numbers included.
IMHO, it's interesting to add figures even if you have instrumented the code to get them
Quoted 10 lines
Quoted 3 lines
Reviewed-by Vincent Guittot <[email protected]>Thanks.
--
Thanks and Regards
Srikar Dronamraju
Quoted 16 lines · Srikar Dronamraju
Currently we loop through all threads of a core to evaluate if the core is idle or not. This is unnecessary. If a thread of a core is not idle, skip evaluating other threads of a core.
Signed-off-by Srikar Dronamraju <[email protected]>--- kernel/sched/fair.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)kernel/sched/fair.c +0
-0@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, intbool idle = true;
kernel/sched/fair.c static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int · line 5881
Quoted 10 lines
kernel/sched/fair.c +4
-2for_each_cpu (cpu,cpu_smt_mask (core)) { -__cpumask_clear_cpu (cpu, cpus); -if (!available_idle_cpu (cpu)) +if (!available_idle_cpu (cpu)) { idle = false; +break ; + } } +cpumask_andnot (cpus, cpus,cpu_smt_mask (core));
That looks sensible enough to me. I do have one random thought, however.
Say you have a 4-core SMT2 system with the usual numbering scheme:
{0, 4} {1, 5} {2, 6} {3, 7}
CORE0 CORE1 CORE2 CORE3Say 'target' is the prev_cpu, in that case let's pick 5. Because we do a for_each_cpu_wrap(), our iteration for 'core' would start with
5, 6, 7, ...
So say CORE2 is entirely idle and CORE1 isn't, we would go through the inner loop on CORE1 (with 'core' == 5), then go through CORE2 (with 'core' == 6) and return 'core'. I find it a bit unusual that we wouldn't return the first CPU in the SMT mask, usually we try to fill sched_groups in cpumask order.
If we could have 'cpus' start with only primary CPUs, that would simplify things methinks:
for_each_cpu_wrap(core, cpus, target) {
bool idle = true;
for_each_cpu(cpu, cpu_smt_mask(core)) {
if (!available_idle_cpu(cpu)) {
idle = false;
break;
}
__cpumask_clear_cpu(core, cpus);
if (idle)
return core;Food for thought; your change itself looks fine as it is.
Quoted 3 lines
kernel/sched/fair.c +0
-0if (idle)return core;
Peter Zijlstra
maintainerQuoted 36 lines · Valentin Schneider
Say you have a 4-core SMT2 system with the usual numbering scheme:
{0, 4} {1, 5} {2, 6} {3, 7} CORE0 CORE1 CORE2 CORE3Say 'target' is the
prev_cpu, in that case let's pick 5. Because we do afor_each_cpu_wrap(), our iteration for 'core' would start with5, 6, 7, ...
So say CORE2 is entirely idle and CORE1 isn't, we would go through the inner loop on CORE1 (with 'core' == 5), then go through CORE2 (with 'core' == 6) and return 'core'. I find it a bit unusual that we wouldn't return the first CPU in the SMT mask, usually we try to fill
sched_groupsin cpumask order.If we could have 'cpus' start with only primary CPUs, that would simplify things methinks:
for_each_cpu_wrap(core, cpus, target) { bool idle = true; for_each_cpu(cpu, cpu_smt_mask(core)) { if (!available_idle_cpu(cpu)) { idle = false; break; } __cpumask_clear_cpu(core, cpus); if (idle) return core;
Quoted 1 line
Food for thought;
See here:
Hi Valentin,
Quoted 18 lines
Say you have a 4-core SMT2 system with the usual numbering scheme:
{0, 4} {1, 5} {2, 6} {3, 7} CORE0 CORE1 CORE2 CORE3Say 'target' is the
prev_cpu, in that case let's pick 5. Because we do afor_each_cpu_wrap(), our iteration for 'core' would start with5, 6, 7, ...
So say CORE2 is entirely idle and CORE1 isn't, we would go through the inner loop on CORE1 (with 'core' == 5), then go through CORE2 (with 'core' == 6) and return 'core'. I find it a bit unusual that we wouldn't return the first CPU in the SMT mask, usually we try to fill
sched_groupsin cpumask order.
Quoted 3 lines
If we could have 'cpus' start with only primary CPUs, that would simplify things methinks:
Its probably something to think over. I probably don't have an answer on why we are not choosing the starting cpu to be primary CPU. Would we have to think of the case where the Primary CPUs are online / offline etc? I mean with target cpu, we know the CPU is online for sure.
Quoted 15 lines
for_each_cpu_wrap(core, cpus, target) {
bool idle = true;
for_each_cpu(cpu, cpu_smt_mask(core)) {
if (!available_idle_cpu(cpu)) {
idle = false;
break;
}
__cpumask_clear_cpu(core, cpus);
if (idle)
return core;Quoted 4 lines
Food for thought; your change itself looks fine as it is.
Reviewed-by Valentin Schneider <[email protected]>
Thanks for the review.
Signature · 2 lines
Thanks and Regards Srikar Dronamraju
Quoted 5 lines · Srikar Dronamraju
Its probably something to think over. I probably don't have an answer on why we are not choosing the starting cpu to be primary CPU. Would we have to think of the case where the Primary CPUs are online / offline etc? I mean with target cpu, we know the CPU is online for sure.
Myes, CPU affinity also makes the thing much more painful (what if the task is affined to some of the core's threads, but not the primary one?). The current method has the merit of handling these cases.