[PATCH] sched/fair: Optimize select_idle_core

[PATCH] sched/fair: Optimize select_idle_core

[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 <srikar@linux.vnet.ibm.com>
---
 kernel/sched/fair.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 69a81a5709ff..b9d628128cfc 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -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

Re: [PATCH] sched/fair: Optimize select_idle_core

[Vincent Guittot]

Hi Srikar,

On Thu, 5 Dec 2019 at 18:23, Srikar Dronamraju
<srikar@linux.vnet.ibm.com> wrote:
>
> 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

>
> Signed-off-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
> ---
>  kernel/sched/fair.c | 6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 69a81a5709ff..b9d628128cfc 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -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
>

Re: [PATCH] sched/fair: Optimize select_idle_core

[Srikar Dronamraju]

* Vincent Guittot <vincent.guittot@linaro.org> [2019-12-05 18:27:51]:

> Hi Srikar,
> 
> On Thu, 5 Dec 2019 at 18:23, Srikar Dronamraju
> <srikar@linux.vnet.ibm.com> wrote:
> >
> > 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
> 
> >

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.

> > Signed-off-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
> > ---
> >  kernel/sched/fair.c | 6 ++++--
> >  1 file changed, 4 insertions(+), 2 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 69a81a5709ff..b9d628128cfc 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -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
> >

-- 
Thanks and Regards
Srikar Dronamraju

Re: [PATCH] sched/fair: Optimize select_idle_core

[Vincent Guittot]

On Thu, 5 Dec 2019 at 18:52, Srikar Dronamraju
<srikar@linux.vnet.ibm.com> wrote:
>
> * Vincent Guittot <vincent.guittot@linaro.org> [2019-12-05 18:27:51]:
>
> > Hi Srikar,
> >
> > On Thu, 5 Dec 2019 at 18:23, Srikar Dronamraju
> > <srikar@linux.vnet.ibm.com> wrote:
> > >
> > > 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
> >
> > >
>
> 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

>
> > > Signed-off-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
> > > ---
> > >  kernel/sched/fair.c | 6 ++++--
> > >  1 file changed, 4 insertions(+), 2 deletions(-)
> > >
> > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > > index 69a81a5709ff..b9d628128cfc 100644
> > > --- a/kernel/sched/fair.c
> > > +++ b/kernel/sched/fair.c
> > > @@ -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
> > >
>
> --
> Thanks and Regards
> Srikar Dronamraju
>

Re: [PATCH] sched/fair: Optimize select_idle_core

[Srikar Dronamraju]

* Vincent Guittot <vincent.guittot@linaro.org> [2019-12-05 19:52:40]:

> On Thu, 5 Dec 2019 at 18:52, Srikar Dronamraju
> <srikar@linux.vnet.ibm.com> wrote:
> >
> > * Vincent Guittot <vincent.guittot@linaro.org> [2019-12-05 18:27:51]:
> >
> > > Hi Srikar,
> > >
> > > On Thu, 5 Dec 2019 at 18:23, Srikar Dronamraju
> > > <srikar@linux.vnet.ibm.com> wrote:
> > > >
> > > > 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
> > >
> > > >
> >
> > 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%

-- 
Thanks and Regards
Srikar Dronamraju

Re: [PATCH] sched/fair: Optimize select_idle_core

[Valentin Schneider]

On 05/12/2019 17:23, Srikar Dronamraju wrote:
> 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 <srikar@linux.vnet.ibm.com>
> ---
>  kernel/sched/fair.c | 6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 69a81a5709ff..b9d628128cfc 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -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));
>  

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.

Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>


>  		if (idle)
>  			return core;
> 

Re: [PATCH] sched/fair: Optimize select_idle_core

[Peter Zijlstra]

On Fri, Dec 06, 2019 at 12:00:00PM +0000, Valentin Schneider wrote:

> 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; 

See here:

  https://lkml.kernel.org/r/20180530142236.667774973@infradead.org

Re: [PATCH] sched/fair: Optimize select_idle_core

[Srikar Dronamraju]

Hi Valentin,

> 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:
> 

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.

>   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.
> 
> Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> 

Thanks for the review.

-- 
Thanks and Regards
Srikar Dronamraju

Re: [PATCH] sched/fair: Optimize select_idle_core

[Vincent Guittot]

On Fri, 6 Dec 2019 at 09:17, Srikar Dronamraju
<srikar@linux.vnet.ibm.com> wrote:
>
> * Vincent Guittot <vincent.guittot@linaro.org> [2019-12-05 19:52:40]:
>
> > On Thu, 5 Dec 2019 at 18:52, Srikar Dronamraju
> > <srikar@linux.vnet.ibm.com> wrote:
> > >
> > > * Vincent Guittot <vincent.guittot@linaro.org> [2019-12-05 18:27:51]:
> > >
> > > > Hi Srikar,
> > > >
> > > > On Thu, 5 Dec 2019 at 18:23, Srikar Dronamraju
> > > > <srikar@linux.vnet.ibm.com> wrote:
> > > > >
> > > > > 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
> > > >
> > > > >
> > >
> > > 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%

Thanks for the figures. Might be good to include them in the commit message

Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>


>
> --
> Thanks and Regards
> Srikar Dronamraju
>

Re: [PATCH] sched/fair: Optimize select_idle_core

[Srikar Dronamraju]

Hi Vincent,

> >
> > 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%
> 
> 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.

> Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>
>

Thanks.

-- 
Thanks and Regards
Srikar Dronamraju

Re: [PATCH] sched/fair: Optimize select_idle_core

[Vincent Guittot]

On Fri, 6 Dec 2019 at 14:39, Srikar Dronamraju
<srikar@linux.vnet.ibm.com> wrote:
>
> Hi Vincent,
>
> > >
> > > 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%
> >
> > 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

>
> > Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>
> >
>
> Thanks.
>
> --
> Thanks and Regards
> Srikar Dronamraju
>

Re: [PATCH] sched/fair: Optimize select_idle_core

[Valentin Schneider]

On 06/12/2019 12:53, Srikar Dronamraju wrote:
> 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.