Skip to contentSkip to conversation

sched/fair: Optimize select_idle_core

PATCH Superseded Srikar Dronamraju 4 participants 12 messages Dec 5, 2019 – Dec 6, 2019 Scheduler

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

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
index 69a81a5709ff..b9d628128cfc 100644
@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int
 		bool 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
maintainer
#1 lore raw

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 28 lines
---
 kernel/sched/fair.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/fair.c +4 -3
index 69a81a5709ff..b9d628128cfc 100644
@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int
                bool 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

#2 lore raw
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
---
 kernel/sched/fair.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/fair.c +4 -3
index 69a81a5709ff..b9d628128cfc 100644
@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int
                bool 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
maintainer
#3 lore raw
Quoted 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
---
 kernel/sched/fair.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/fair.c +4 -2
index 69a81a5709ff..b9d628128cfc 100644
@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int
                bool 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 -1
                if (idle)
                        return core;
--

2.18.1

--
Thanks and Regards
Srikar Dronamraju

#4 lore raw
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_andnot line

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
maintainer Reviewed-by
#5 lore raw
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_andnot line

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

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

#6 lore raw

Hi Vincent,

Quoted 10 lines
Quoted 10 lines

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

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

Thanks.

Signature · 2 lines
Thanks and Regards
Srikar Dronamraju
maintainer
#7 lore raw
Quoted 17 lines · Srikar Dronamraju

Hi Vincent,

Quoted 14 lines
Quoted 13 lines

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%

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

Thanks.

--
Thanks and Regards
Srikar Dronamraju

Reviewed-by on v1 1/1
#8 lore raw
In reply to 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.

---
 kernel/sched/fair.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/fair.c +0 -0
index 69a81a5709ff..b9d628128cfc 100644
@@ -5872,10 +5872,12 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int
 		bool 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 -2
 		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));
 

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   CORE3

Say '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 -0
 		if (idle)
 			return core;
maintainer
#9 lore raw
Quoted 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   CORE3

Say '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;
Quoted 1 line

Food for thought;

See here:

https://lkml.kernel.org/r/[email protected]

#10 lore raw
In reply to Valentin Schneider

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   CORE3

Say '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.

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.

Thanks for the review.

Signature · 2 lines
Thanks and Regards
Srikar Dronamraju
#11 lore raw
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.