Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1562814 > unrolled thread

[PATCH] sched: Optimize pick_next_task for idle_sched_class too

Back to article view | Back to linux.kernel

Contents

  [PATCH] sched: Optimize pick_next_task for idle_sched_class too Steven Rostedt <rostedt@goodmis.org> - 2017-01-19 16:20 +0100
    Re: [PATCH] sched: Optimize pick_next_task for idle_sched_class too Peter Zijlstra <peterz@infradead.org> - 2017-01-19 22:00 +0100
      Re: [PATCH] sched: Optimize pick_next_task for idle_sched_class too Steven Rostedt <rostedt@goodmis.org> - 2017-01-20 17:20 +0100
      Re: [PATCH] sched: Optimize pick_next_task for idle_sched_class too Steven Rostedt <rostedt@goodmis.org> - 2017-01-20 17:20 +0100
        Re: [PATCH] sched: Optimize pick_next_task for idle_sched_class too Peter Zijlstra <peterz@infradead.org> - 2017-01-20 18:00 +0100
      [tip:sched/core] sched/core: Optimize pick_next_task() for  idle_sched_class tip-bot for Peter Zijlstra <tipbot@zytor.com> - 2017-01-30 13:00 +0100

#1562814 — [PATCH] sched: Optimize pick_next_task for idle_sched_class too

When running my likely/unlikely profiler, I noticed that the
SCHED_DEADLINE's pick_next_task_dl() unlikely case of
(!dl_rq->dl_nr_running) was always being hit. There's two cases where
this can happen.

First, there's an optimization in pick_next_task() for the likely case
that the only tasks running on the run queue are SCHED_OTHER tasks. In
a normal system, this is the case most of the time. When this is true,
only the pick_next_task() of the fair_sched_class is called. If an RT or
DEADLINE task is queued, then the other pick_next_task()s of the other
sched classes are called in sequence.

The SCHED_DEADLINE pick_next_task() is called first, and that
unlikely() case is hit if there's no deadline tasks available. This
happens when an RT task is queued (first case). But tracing revealed
that this happens in another very common case. The case where the
system goes from idle to running any task, including SCHED_OTHER. This
is because the idle task has a different sched class than the
fair_sched_class.

The optimization has:

	if (prev->sched_class == fair_sched_class &&
	    rq->nr_running == rq->cfs.h_nr_running) {

When going from SCHED_OTHER to idle, this optimization is hit, because
the SCHED_OTHER task is of the fair_sched_class, and rq->nr_running and
rq->cfs.h_nr_running are both zero. But when we go from idle to
SCHED_OTHER, the first test fails. prev->sched_class is equal to
idle_sched_class, and this causes both the pick_next_task() of deadline
and RT sched classes to be called unnecessarily.

Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 154fd68..e2c6d3b 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3259,13 +3259,15 @@ static inline struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct pin_cookie cookie)
 {
 	const struct sched_class *class = &fair_sched_class;
+	const struct sched_class *idle_class = &idle_sched_class;
 	struct task_struct *p;
 
 	/*
 	 * Optimization: we know that if all tasks are in
 	 * the fair class we can call that function directly:
 	 */
-	if (likely(prev->sched_class == class &&
+	if (likely((prev->sched_class == class ||
+		    prev->sched_class == idle_class) &&
 		   rq->nr_running == rq->cfs.h_nr_running)) {
 		p = fair_sched_class.pick_next_task(rq, prev, cookie);
 		if (unlikely(p == RETRY_TASK))

[toc] | [next] | [standalone]

#1563082

On Thu, Jan 19, 2017 at 10:17:03AM -0500, Steven Rostedt wrote:
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 154fd68..e2c6d3b 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3259,13 +3259,15 @@ static inline struct task_struct *
>  pick_next_task(struct rq *rq, struct task_struct *prev, struct pin_cookie cookie)
>  {
>  	const struct sched_class *class = &fair_sched_class;
> +	const struct sched_class *idle_class = &idle_sched_class;
>  	struct task_struct *p;
>  
>  	/*
>  	 * Optimization: we know that if all tasks are in
>  	 * the fair class we can call that function directly:
>  	 */
> -	if (likely(prev->sched_class == class &&
> +	if (likely((prev->sched_class == class ||
> +		    prev->sched_class == idle_class) &&
>  		   rq->nr_running == rq->cfs.h_nr_running)) {

OK, so I hate this patch because it makes the condition more complex,
and while staring at what it does for code generation I couldn't for the
life of me figure out why we care about prev->sched_class to begin with.

(we used to, but the current code not so much)

So I simply removed that entire clause, like below, and lo and behold,
the system booted...

Could you give it a spin to see if anything comes apart?


diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 49ce1cb..51ca21e 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3321,15 +3321,14 @@ static inline void schedule_debug(struct task_struct *prev)
 static inline struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	const struct sched_class *class = &fair_sched_class;
+	const struct sched_class *class;
 	struct task_struct *p;
 
 	/*
 	 * Optimization: we know that if all tasks are in
 	 * the fair class we can call that function directly:
 	 */
-	if (likely(prev->sched_class == class &&
-		   rq->nr_running == rq->cfs.h_nr_running)) {
+	if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
 		p = fair_sched_class.pick_next_task(rq, prev, rf);
 		if (unlikely(p == RETRY_TASK))
 			goto again;

[toc] | [prev] | [next] | [standalone]

#1563746

On Fri, 20 Jan 2017 11:14:25 -0500
Steven Rostedt <rostedt@goodmis.org> wrote:
> 
> > 
> > Could you give it a spin to see if anything comes apart?  
> 
> Yeah this works. You can add:
> 
> Reported-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
> Tested-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
> 

You can also add that my likely profiler on a normal box showed this
likely case go from 78% correct to 98% correct.

-- Steve

[toc] | [prev] | [next] | [standalone]

#1563747

On Thu, 19 Jan 2017 18:44:08 +0100
Peter Zijlstra <peterz@infradead.org> wrote:
-	if (likely(prev->sched_class == class &&
> > +	if (likely((prev->sched_class == class ||
> > +		    prev->sched_class == idle_class) &&
> >  		   rq->nr_running == rq->cfs.h_nr_running)) {  
> 
> OK, so I hate this patch because it makes the condition more complex,
> and while staring at what it does for code generation I couldn't for the
> life of me figure out why we care about prev->sched_class to begin with.

I was thinking it would save on checking the rq at all, but rq is used
by pick_next_task_*() anyway, so I doubt it's much savings.

> 
> (we used to, but the current code not so much)
> 
> So I simply removed that entire clause, like below, and lo and behold,
> the system booted...

I thought about doing this too, but decided against it because I was
thinking that since class (and now idle_class) are constants, it would
help the non cfs case. Checking prev->sched_class against a constant I
thought would be quick. But yeah, I doubt it matters much in the grand
scale of things.


> 
> Could you give it a spin to see if anything comes apart?

Yeah this works. You can add:

Reported-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
Tested-by: Steven Rostedt (VMware) <rostedt@goodmis.org>

Thanks,

-- Steve

> 
> 
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 49ce1cb..51ca21e 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3321,15 +3321,14 @@ static inline void schedule_debug(struct task_struct *prev)
>  static inline struct task_struct *
>  pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>  {
> -	const struct sched_class *class = &fair_sched_class;
> +	const struct sched_class *class;
>  	struct task_struct *p;
>  
>  	/*
>  	 * Optimization: we know that if all tasks are in
>  	 * the fair class we can call that function directly:
>  	 */
> -	if (likely(prev->sched_class == class &&
> -		   rq->nr_running == rq->cfs.h_nr_running)) {
> +	if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
>  		p = fair_sched_class.pick_next_task(rq, prev, rf);
>  		if (unlikely(p == RETRY_TASK))
>  			goto again;

[toc] | [prev] | [next] | [standalone]

#1563788

On Fri, Jan 20, 2017 at 11:14:25AM -0500, Steven Rostedt wrote:
> > OK, so I hate this patch because it makes the condition more complex,
> > and while staring at what it does for code generation I couldn't for the
> > life of me figure out why we care about prev->sched_class to begin with.
> 
> I was thinking it would save on checking the rq at all, but rq is used
> by pick_next_task_*() anyway, so I doubt it's much savings.

fwiw, code generation adds something like:

	CMP imm32, reg
	JE imm8

So the overhead is not immense, something like 7-8 bytes, but still,
less is more :-)

[toc] | [prev] | [next] | [standalone]

#1569641 — [tip:sched/core] sched/core: Optimize pick_next_task() for idle_sched_class

Commit-ID:  49ee576809d837442624ac18804b07943267cd57
Gitweb:     http://git.kernel.org/tip/49ee576809d837442624ac18804b07943267cd57
Author:     Peter Zijlstra <peterz@infradead.org>
AuthorDate: Thu, 19 Jan 2017 18:44:08 +0100
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Mon, 30 Jan 2017 11:46:34 +0100

sched/core: Optimize pick_next_task() for idle_sched_class

Steve noticed that when we switch from IDLE to SCHED_OTHER we fail to
take the shortcut, even though all runnable tasks are of the fair
class, because prev->sched_class != &fair_sched_class.

Since I reworked the put_prev_task() stuff, we don't really care about
prev->class here, so removing that condition will allow this case.

This increases the likely case from 78% to 98% correct for Steve's
workload.

Reported-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
Tested-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Mike Galbraith <efault@gmx.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/20170119174408.GN6485@twins.programming.kicks-ass.net
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/sched/core.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 49ce1cb..51ca21e 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3321,15 +3321,14 @@ static inline void schedule_debug(struct task_struct *prev)
 static inline struct task_struct *
 pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	const struct sched_class *class = &fair_sched_class;
+	const struct sched_class *class;
 	struct task_struct *p;
 
 	/*
 	 * Optimization: we know that if all tasks are in
 	 * the fair class we can call that function directly:
 	 */
-	if (likely(prev->sched_class == class &&
-		   rq->nr_running == rq->cfs.h_nr_running)) {
+	if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
 		p = fair_sched_class.pick_next_task(rq, prev, rf);
 		if (unlikely(p == RETRY_TASK))
 			goto again;

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web