[PATCH] sched: recover sched_yield task running time increase

[PATCH] sched: recover sched_yield task running time increase

[Alex Shi]

commit ac53db596cc08ecb8040c removed the sched_yield task running
time increase, so the yielded task get more opportunity to be launch
again. That may not the caller want to be. And this also causes
volano benchmark drop 50~80 percent performance on core2/NHM/WSM
machines. This patch recover the sched_yield task vruntime up.

Signed-off-by: alex.shi@intel.com
---
 kernel/sched_fair.c |   18 +++++++++++++++++-
 1 files changed, 17 insertions(+), 1 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index 3f7ec9e..04d58bb 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -1956,7 +1956,7 @@ static void yield_task_fair(struct rq *rq)
 {
 	struct task_struct *curr = rq->curr;
 	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
-	struct sched_entity *se = &curr->se;
+	struct sched_entity *se = &curr->se, *rightmost;
 
 	/*
 	 * Are we the only task in the tree?
@@ -1975,6 +1975,22 @@ static void yield_task_fair(struct rq *rq)
 	}
 
 	set_skip_buddy(se);
+	/*
+	 * Find the rightmost entry in the rbtree:
+	 */
+	rightmost = __pick_last_entity(cfs_rq);
+	/*
+	 * Already in the rightmost position?
+	 */
+	if (unlikely(!rightmost || entity_before(rightmost, se)))
+		return;
+
+	/*
+	 * Minimally necessary key value to be last in the tree:
+	 * Upon rescheduling, sched_class::put_prev_task() will place
+	 * 'current' within the tree based on its new key value.
+	 */
+	se->vruntime = rightmost->vruntime + 1;
 }
 
 static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preempt)
-- 
1.6.0

Re: [PATCH] sched: recover sched_yield task running time increase

[Rik van Riel]

On 04/05/2011 06:33 PM, Alex Shi wrote:
> commit ac53db596cc08ecb8040c removed the sched_yield task running
> time increase, so the yielded task get more opportunity to be launch
> again. That may not the caller want to be. And this also causes
> volano benchmark drop 50~80 percent performance on core2/NHM/WSM
> machines. This patch recover the sched_yield task vruntime up.
>
> Signed-off-by: alex.shi@intel.com

NACK

This was switched off by default and under
the sysctl sched_compat_yield for a reason.

Reintroducing it under that sysctl option
may be acceptable, but by default it would
be doing the wrong thing for other workloads.

Re: [PATCH] sched: recover sched_yield task running time increase

[Alex,Shi]

On Wed, 2011-04-06 at 13:07 +0800, Rik van Riel wrote:
> On 04/05/2011 06:33 PM, Alex Shi wrote:
> > commit ac53db596cc08ecb8040c removed the sched_yield task running
> > time increase, so the yielded task get more opportunity to be launch
> > again. That may not the caller want to be. And this also causes
> > volano benchmark drop 50~80 percent performance on core2/NHM/WSM
> > machines. This patch recover the sched_yield task vruntime up.
> >
> > Signed-off-by: alex.shi@intel.com
> 
> NACK
> 
> This was switched off by default and under
> the sysctl sched_compat_yield for a reason.
> 
> Reintroducing it under that sysctl option
> may be acceptable, but by default it would
> be doing the wrong thing for other workloads.

I can implement this as sysctl option. But when I checked again the man
page of sched_yield. I have some concerns on this. 

----
       int sched_yield(void);

DESCRIPTION
       A  process  can  relinquish  the processor voluntarily without blocking by calling sched_yield().
       The process will then be moved to the end of the queue for its static priority and a new  process
       gets to run.
----

If a application calls sched_yield system call, most of time it is not
want to be launched again right now. so the man page said "the caller
process will then be moved to the _end_ of the queue..."

Re: [PATCH] sched: recover sched_yield task running time increase

[Mike Galbraith]

On Wed, 2011-04-06 at 14:15 +0800, Alex,Shi wrote:
> On Wed, 2011-04-06 at 13:07 +0800, Rik van Riel wrote:
> > On 04/05/2011 06:33 PM, Alex Shi wrote:
> > > commit ac53db596cc08ecb8040c removed the sched_yield task running
> > > time increase, so the yielded task get more opportunity to be launch
> > > again. That may not the caller want to be. And this also causes
> > > volano benchmark drop 50~80 percent performance on core2/NHM/WSM
> > > machines. This patch recover the sched_yield task vruntime up.
> > >
> > > Signed-off-by: alex.shi@intel.com
> > 
> > NACK
> > 
> > This was switched off by default and under
> > the sysctl sched_compat_yield for a reason.
> > 
> > Reintroducing it under that sysctl option
> > may be acceptable, but by default it would
> > be doing the wrong thing for other workloads.
> 
> I can implement this as sysctl option. But when I checked again the man
> page of sched_yield. I have some concerns on this. 
> 
> ----
>        int sched_yield(void);
> 
> DESCRIPTION
>        A  process  can  relinquish  the processor voluntarily without blocking by calling sched_yield().
>        The process will then be moved to the end of the queue for its static priority and a new  process
>        gets to run.
> ----
> 
> If a application calls sched_yield system call, most of time it is not
> want to be launched again right now. so the man page said "the caller
> process will then be moved to the _end_ of the queue..."

Moving a yielding nice 0 task behind a SCHED_IDLE (or nice 19) task
could be incredibly painful.

	-Mike

Re: [PATCH] sched: recover sched_yield task running time increase

[Peter Zijlstra]

On Wed, 2011-04-06 at 06:33 +0800, Alex Shi wrote:
> commit ac53db596cc08ecb8040c removed the sched_yield task running
> time increase, so the yielded task get more opportunity to be launch
> again. That may not the caller want to be. And this also causes
> volano benchmark drop 50~80 percent performance on core2/NHM/WSM
> machines. This patch recover the sched_yield task vruntime up.

You do know that any app that relies on sched_yield behaviour is more
than broken? Using sched_yield() for anything other than SCHED_FIFO
tasks is well outside spec.

Furthermore, apparently you used sysctl_sched_compat_yield, which was
bound to disappear some time, since with the default settings the yield
semantics didn't actually change.

So no, I'm not much inclined to accept this. The Java people have had
every opportunity to go fix their crap, them not doing so will
eventually (preferably now) stop being my problem.

RE: [PATCH] sched: recover sched_yield task running time increase

[Shi, Alex]

>> > NACK
>> >
>> > This was switched off by default and under
>> > the sysctl sched_compat_yield for a reason.
>> >
>> > Reintroducing it under that sysctl option
>> > may be acceptable, but by default it would
>> > be doing the wrong thing for other workloads.
>>
>> I can implement this as sysctl option. But when I checked again the man
>> page of sched_yield. I have some concerns on this.
>>
>> ----
>>        int sched_yield(void);
>>
>> DESCRIPTION
>>        A  process  can  relinquish  the processor voluntarily without blocking by calling sched_yield().
>>        The process will then be moved to the end of the queue for its static priority and a new  process
>>        gets to run.
>> ----
>>
>> If a application calls sched_yield system call, most of time it is not
>> want to be launched again right now. so the man page said "the caller
>> process will then be moved to the _end_ of the queue..."
>
>Moving a yielding nice 0 task behind a SCHED_IDLE (or nice 19) task
>could be incredibly painful.

Good reminder! Do you have more detailed idea on this? 

Re: [PATCH] sched: recover sched_yield task running time increase

[Rik van Riel]

On 04/06/2011 04:04 AM, Peter Zijlstra wrote:
> On Wed, 2011-04-06 at 06:33 +0800, Alex Shi wrote:
>> commit ac53db596cc08ecb8040c removed the sched_yield task running
>> time increase, so the yielded task get more opportunity to be launch
>> again. That may not the caller want to be. And this also causes
>> volano benchmark drop 50~80 percent performance on core2/NHM/WSM
>> machines. This patch recover the sched_yield task vruntime up.
>
> You do know that any app that relies on sched_yield behaviour is more
> than broken? Using sched_yield() for anything other than SCHED_FIFO
> tasks is well outside spec.
>
> Furthermore, apparently you used sysctl_sched_compat_yield, which was
> bound to disappear some time, since with the default settings the yield
> semantics didn't actually change.
>
> So no, I'm not much inclined to accept this. The Java people have had
> every opportunity to go fix their crap, them not doing so will
> eventually (preferably now) stop being my problem.

It appears they might not have figured out how to fix
their stuff :)

Would you have any hints on what the Java folks should
replace their calls to sched_yield with?

Proper use of futexes from inside the JVM perhaps?

Or should we export yield_to to userspace and have
them use that? :)   *runs*

Re: [PATCH] sched: recover sched_yield task running time increase

[Peter Zijlstra]

On Wed, 2011-04-06 at 10:42 -0400, Rik van Riel wrote:

> It appears they might not have figured out how to fix
> their stuff :)

As far as I can tell they're totally not interested in fixing their
crap, it comes up every time we touch sched_yield() but nobody ever
steps up and fixes things.

> Would you have any hints on what the Java folks should
> replace their calls to sched_yield with?
> 
> Proper use of futexes from inside the JVM perhaps?

Yeah, Darren was working on making adaptive spinning futexes, but still
even without that, syscalls on x86 are so cheap there's really hardly
any point in actually spinning in userspace.

> Or should we export yield_to to userspace and have
> them use that? :)   *runs*

Hehe, no, yield_to() is an absolute abomination (much like yield itself
but worse), they have proper locks and should thus use proper
primitives.

RE: [PATCH] sched: recover sched_yield task running time increase

[Mike Galbraith]

On Wed, 2011-04-06 at 21:28 +0800, Shi, Alex wrote:
> >> > NACK
> >> >
> >> > This was switched off by default and under
> >> > the sysctl sched_compat_yield for a reason.
> >> >
> >> > Reintroducing it under that sysctl option
> >> > may be acceptable, but by default it would
> >> > be doing the wrong thing for other workloads.
> >>
> >> I can implement this as sysctl option. But when I checked again the man
> >> page of sched_yield. I have some concerns on this.
> >>
> >> ----
> >>        int sched_yield(void);
> >>
> >> DESCRIPTION
> >>        A  process  can  relinquish  the processor voluntarily without blocking by calling sched_yield().
> >>        The process will then be moved to the end of the queue for its static priority and a new  process
> >>        gets to run.
> >> ----
> >>
> >> If a application calls sched_yield system call, most of time it is not
> >> want to be launched again right now. so the man page said "the caller
> >> process will then be moved to the _end_ of the queue..."
> >
> >Moving a yielding nice 0 task behind a SCHED_IDLE (or nice 19) task
> >could be incredibly painful.
> 
> Good reminder! Do you have more detailed idea on this?

Other than 'don't do that'?  Nope.  sched_yield() semantics suck.

	-Mike

Re: [PATCH] sched: recover sched_yield task running time increase

[Alex,Shi]

On Wed, 2011-04-06 at 16:04 +0800, Peter Zijlstra wrote:
> On Wed, 2011-04-06 at 06:33 +0800, Alex Shi wrote:
> > commit ac53db596cc08ecb8040c removed the sched_yield task running
> > time increase, so the yielded task get more opportunity to be launch
> > again. That may not the caller want to be. And this also causes
> > volano benchmark drop 50~80 percent performance on core2/NHM/WSM
> > machines. This patch recover the sched_yield task vruntime up.
> 
> You do know that any app that relies on sched_yield behaviour is more
> than broken? Using sched_yield() for anything other than SCHED_FIFO
> tasks is well outside spec.
> 
> Furthermore, apparently you used sysctl_sched_compat_yield, which was
> bound to disappear some time, since with the default settings the yield
> semantics didn't actually change.

Yes, I used sched_compat_yield, otherwise volano will become extremely
slow in my single machine testing. We may reconsider our testing
setting. 

On the other side, after scheduler change to CFS, the task priority was
converted into load.weight and calculated into vruntime, the originally
meaningful of sched_yield system call is very hard to implement.
Considering this, I understand your decision on this. 
> 
> So no, I'm not much inclined to accept this. The Java people have had
> every opportunity to go fix their crap, them not doing so will
> eventually (preferably now) stop being my problem.
> 

Re: [PATCH] sched: recover sched_yield task running time increase

[Rik van Riel]

On 04/06/2011 11:08 PM, Alex,Shi wrote:
> On Wed, 2011-04-06 at 16:04 +0800, Peter Zijlstra wrote:
>> On Wed, 2011-04-06 at 06:33 +0800, Alex Shi wrote:

>> You do know that any app that relies on sched_yield behaviour is more
>> than broken? Using sched_yield() for anything other than SCHED_FIFO
>> tasks is well outside spec.
>>
>> Furthermore, apparently you used sysctl_sched_compat_yield, which was
>> bound to disappear some time, since with the default settings the yield
>> semantics didn't actually change.
>
> Yes, I used sched_compat_yield, otherwise volano will become extremely
> slow in my single machine testing. We may reconsider our testing
> setting.

With what JVM is this happening?

Surely not every JVM uses user space spinlocks and
yield, when we have futexes available?

Re: [PATCH] sched: recover sched_yield task running time increase

[Alex,Shi]

On Thu, 2011-04-07 at 14:13 +0800, Rik van Riel wrote:
> On 04/06/2011 11:08 PM, Alex,Shi wrote:
> > On Wed, 2011-04-06 at 16:04 +0800, Peter Zijlstra wrote:
> >> On Wed, 2011-04-06 at 06:33 +0800, Alex Shi wrote:
> 
> >> You do know that any app that relies on sched_yield behaviour is more
> >> than broken? Using sched_yield() for anything other than SCHED_FIFO
> >> tasks is well outside spec.
> >>
> >> Furthermore, apparently you used sysctl_sched_compat_yield, which was
> >> bound to disappear some time, since with the default settings the yield
> >> semantics didn't actually change.
> >
> > Yes, I used sched_compat_yield, otherwise volano will become extremely
> > slow in my single machine testing. We may reconsider our testing
> > setting.
> 
> With what JVM is this happening?

I used openjdk from fedora 10~13 and jrockit-R27.3.1-jre1.5.0_11, both
of them use sched_yield much. And I just did a quick try with
jrockit-R27.4.0-jre1.6.0_02.x86_64, it had same problem.

> 
> Surely not every JVM uses user space spinlocks and
> yield, when we have futexes available?

No, just 7 times futex called in testing, so I think the JVM did not use
it. 
> 
> 
> 

Re: [PATCH] sched: recover sched_yield task running time increase

[Ingo Molnar]

* Alex,Shi <alex.shi@intel.com> wrote:

> On Thu, 2011-04-07 at 14:13 +0800, Rik van Riel wrote:
> > On 04/06/2011 11:08 PM, Alex,Shi wrote:
> > > On Wed, 2011-04-06 at 16:04 +0800, Peter Zijlstra wrote:
> > >> On Wed, 2011-04-06 at 06:33 +0800, Alex Shi wrote:
> > 
> > >> You do know that any app that relies on sched_yield behaviour is more
> > >> than broken? Using sched_yield() for anything other than SCHED_FIFO
> > >> tasks is well outside spec.
> > >>
> > >> Furthermore, apparently you used sysctl_sched_compat_yield, which was
> > >> bound to disappear some time, since with the default settings the yield
> > >> semantics didn't actually change.
> > >
> > > Yes, I used sched_compat_yield, otherwise volano will become extremely
> > > slow in my single machine testing. We may reconsider our testing
> > > setting.
> > 
> > With what JVM is this happening?
> 
> I used openjdk from fedora 10~13 and jrockit-R27.3.1-jre1.5.0_11, both
> of them use sched_yield much. And I just did a quick try with
> jrockit-R27.4.0-jre1.6.0_02.x86_64, it had same problem.

Well, switching openjdk to futexes would be a nice performance optimization for 
sure - especially if you can show the speedups with VolanoMark.

It would also put all the performance claims to rest. If indeed yield() is 
faster then this would give us an opportunity to improve futex performance to 
the point (or beyond) yield() based locks.

Thanks,

	Ingo