[PATCH] schedule: use unlikely()

[PATCH] schedule: use unlikely()

[Mikulas Patocka]

A small patch for schedule(), so that the code goes straght in the common
case.

Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>

---
 include/linux/blkdev.h |    2 +-
 kernel/sched/core.c    |    2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

Index: linux-2.6/include/linux/blkdev.h
===================================================================
--- linux-2.6.orig/include/linux/blkdev.h
+++ linux-2.6/include/linux/blkdev.h
@@ -1308,7 +1308,7 @@ static inline bool blk_needs_flush_plug(
 {
 	struct blk_plug *plug = tsk->plug;
 
-	return plug &&
+	return unlikely(plug != NULL) &&
 		(!list_empty(&plug->list) ||
 		 !list_empty(&plug->mq_list) ||
 		 !list_empty(&plug->cb_list));
Index: linux-2.6/kernel/sched/core.c
===================================================================
--- linux-2.6.orig/kernel/sched/core.c
+++ linux-2.6/kernel/sched/core.c
@@ -3405,7 +3405,7 @@ void __noreturn do_task_dead(void)
 
 static inline void sched_submit_work(struct task_struct *tsk)
 {
-	if (!tsk->state || tsk_is_pi_blocked(tsk))
+	if (!tsk->state || unlikely(tsk_is_pi_blocked(tsk)))
 		return;
 	/*
 	 * If we are going to sleep and we have plugged IO queued,

Re: [PATCH] schedule: use unlikely()

[Ingo Molnar]

* Mikulas Patocka <mpatocka@redhat.com> wrote:

> A small patch for schedule(), so that the code goes straght in the common
> case.
> 
> Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> 
> ---
>  include/linux/blkdev.h |    2 +-
>  kernel/sched/core.c    |    2 +-
>  2 files changed, 2 insertions(+), 2 deletions(-)
> 
> Index: linux-2.6/include/linux/blkdev.h
> ===================================================================
> --- linux-2.6.orig/include/linux/blkdev.h
> +++ linux-2.6/include/linux/blkdev.h
> @@ -1308,7 +1308,7 @@ static inline bool blk_needs_flush_plug(
>  {
>  	struct blk_plug *plug = tsk->plug;
>  
> -	return plug &&
> +	return unlikely(plug != NULL) &&
>  		(!list_empty(&plug->list) ||
>  		 !list_empty(&plug->mq_list) ||
>  		 !list_empty(&plug->cb_list));

That's an unrelated change.

> Index: linux-2.6/kernel/sched/core.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched/core.c
> +++ linux-2.6/kernel/sched/core.c
> @@ -3405,7 +3405,7 @@ void __noreturn do_task_dead(void)
>  
>  static inline void sched_submit_work(struct task_struct *tsk)
>  {
> -	if (!tsk->state || tsk_is_pi_blocked(tsk))
> +	if (!tsk->state || unlikely(tsk_is_pi_blocked(tsk)))
>  		return;
>  	/*
>  	 * If we are going to sleep and we have plugged IO queued,

Do these changes actually change the generated assembly code?

Thanks,

	Ingo

Re: [PATCH] schedule: use unlikely()

[Mikulas Patocka]

On Fri, 24 Nov 2017, Ingo Molnar wrote:

> * Mikulas Patocka <mpatocka@redhat.com> wrote:
> 
> > A small patch for schedule(), so that the code goes straght in the common
> > case.
> > 
> > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> > 
> > ---
> >  include/linux/blkdev.h |    2 +-
> >  kernel/sched/core.c    |    2 +-
> >  2 files changed, 2 insertions(+), 2 deletions(-)
> > 
> > Index: linux-2.6/include/linux/blkdev.h
> > ===================================================================
> > --- linux-2.6.orig/include/linux/blkdev.h
> > +++ linux-2.6/include/linux/blkdev.h
> > @@ -1308,7 +1308,7 @@ static inline bool blk_needs_flush_plug(
> >  {
> >  	struct blk_plug *plug = tsk->plug;
> >  
> > -	return plug &&
> > +	return unlikely(plug != NULL) &&
> >  		(!list_empty(&plug->list) ||
> >  		 !list_empty(&plug->mq_list) ||
> >  		 !list_empty(&plug->cb_list));
> 
> That's an unrelated change.

It is related, because this function gets inlined into schedule().

> > Index: linux-2.6/kernel/sched/core.c
> > ===================================================================
> > --- linux-2.6.orig/kernel/sched/core.c
> > +++ linux-2.6/kernel/sched/core.c
> > @@ -3405,7 +3405,7 @@ void __noreturn do_task_dead(void)
> >  
> >  static inline void sched_submit_work(struct task_struct *tsk)
> >  {
> > -	if (!tsk->state || tsk_is_pi_blocked(tsk))
> > +	if (!tsk->state || unlikely(tsk_is_pi_blocked(tsk)))
> >  		return;
> >  	/*
> >  	 * If we are going to sleep and we have plugged IO queued,
> 
> Do these changes actually change the generated assembly code?
> 
> Thanks,
> 
> 	Ingo

Yes. It saves two jumps because the compiler falsely assumes that 
tsk_is_pi_blocked would return true. Likewise, the compiler falsely 
assumes that tsk->plug would be true.

The static branch prediction in gcc assumes that pointers are usually not 
NULL, but in this case tsk->pi_blocked_on and tsk->plug are usually NULL.

Mikulas

Re: [PATCH] schedule: use unlikely()

[Ingo Molnar]

* Mikulas Patocka <mpatocka@redhat.com> wrote:

> 
> 
> On Fri, 24 Nov 2017, Ingo Molnar wrote:
> 
> > * Mikulas Patocka <mpatocka@redhat.com> wrote:
> > 
> > > A small patch for schedule(), so that the code goes straght in the common
> > > case.
> > > 
> > > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> > > 
> > > ---
> > >  include/linux/blkdev.h |    2 +-
> > >  kernel/sched/core.c    |    2 +-
> > >  2 files changed, 2 insertions(+), 2 deletions(-)
> > > 
> > > Index: linux-2.6/include/linux/blkdev.h
> > > ===================================================================
> > > --- linux-2.6.orig/include/linux/blkdev.h
> > > +++ linux-2.6/include/linux/blkdev.h
> > > @@ -1308,7 +1308,7 @@ static inline bool blk_needs_flush_plug(
> > >  {
> > >  	struct blk_plug *plug = tsk->plug;
> > >  
> > > -	return plug &&
> > > +	return unlikely(plug != NULL) &&
> > >  		(!list_empty(&plug->list) ||
> > >  		 !list_empty(&plug->mq_list) ||
> > >  		 !list_empty(&plug->cb_list));
> > 
> > That's an unrelated change.
> 
> It is related, because this function gets inlined into schedule().

That needs to be in the changelog and the patch needs to be Cc:-ed to the 
affected maintainer as well.

> > > Index: linux-2.6/kernel/sched/core.c
> > > ===================================================================
> > > --- linux-2.6.orig/kernel/sched/core.c
> > > +++ linux-2.6/kernel/sched/core.c
> > > @@ -3405,7 +3405,7 @@ void __noreturn do_task_dead(void)
> > >  
> > >  static inline void sched_submit_work(struct task_struct *tsk)
> > >  {
> > > -	if (!tsk->state || tsk_is_pi_blocked(tsk))
> > > +	if (!tsk->state || unlikely(tsk_is_pi_blocked(tsk)))
> > >  		return;
> > >  	/*
> > >  	 * If we are going to sleep and we have plugged IO queued,
> > 
> > Do these changes actually change the generated assembly code?
> > 
> > Thanks,
> > 
> > 	Ingo
> 
> Yes. It saves two jumps because the compiler falsely assumes that 
> tsk_is_pi_blocked would return true. Likewise, the compiler falsely 
> assumes that tsk->plug would be true.
> 
> The static branch prediction in gcc assumes that pointers are usually not 
> NULL, but in this case tsk->pi_blocked_on and tsk->plug are usually NULL.

That too should be in the changelog.

Thanks,

	Ingo

Re: [PATCH] schedule: use unlikely()

[Mikulas Patocka]

On Sat, 25 Nov 2017, Ingo Molnar wrote:

> 
> * Mikulas Patocka <mpatocka@redhat.com> wrote:
> 
> > On Fri, 24 Nov 2017, Ingo Molnar wrote:
> > 
> > > > +	return unlikely(plug != NULL) &&
> > > >  		(!list_empty(&plug->list) ||
> > > >  		 !list_empty(&plug->mq_list) ||
> > > >  		 !list_empty(&plug->cb_list));
> > > 
> > > That's an unrelated change.
> > 
> > It is related, because this function gets inlined into schedule().
> 
> That needs to be in the changelog and the patch needs to be Cc:-ed to the 
> affected maintainer as well.
> 
> > The static branch prediction in gcc assumes that pointers are usually not 
> > NULL, but in this case tsk->pi_blocked_on and tsk->plug are usually NULL.
> 
> That too should be in the changelog.
> 
> Thanks,
> 
> 	Ingo
> 

OK - here I resend it with more verbose message:

Mikulas



From: Mikulas Patocka <mpatocka@redhat.com>
Subject: [PATCH] schedule: add unlikely()

A small patch for schedule(), so that the code goes straght in the common 
case. This patch saves two jumps in the assembler listing. The static 
branch prediction in GCC assumes that pointers are usually non-NULL when 
they are compared against NULL, but in theis case, tsk->plug is usually 
NULL (the function blk_needs_flush_plug gets inlined into schedule()) and 
tsk->pi_blocked_on is also usually NULL (that is checked by 
tsk_is_pi_blocked). This patch adds the macro unlikely() to override the 
static prediction.

Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>

---
 include/linux/blkdev.h |    2 +-
 kernel/sched/core.c    |    2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

Index: linux-2.6/include/linux/blkdev.h
===================================================================
--- linux-2.6.orig/include/linux/blkdev.h
+++ linux-2.6/include/linux/blkdev.h
@@ -1308,7 +1308,7 @@ static inline bool blk_needs_flush_plug(
 {
 	struct blk_plug *plug = tsk->plug;
 
-	return plug &&
+	return unlikely(plug != NULL) &&
 		(!list_empty(&plug->list) ||
 		 !list_empty(&plug->mq_list) ||
 		 !list_empty(&plug->cb_list));
Index: linux-2.6/kernel/sched/core.c
===================================================================
--- linux-2.6.orig/kernel/sched/core.c
+++ linux-2.6/kernel/sched/core.c
@@ -3405,7 +3405,7 @@ void __noreturn do_task_dead(void)
 
 static inline void sched_submit_work(struct task_struct *tsk)
 {
-	if (!tsk->state || tsk_is_pi_blocked(tsk))
+	if (!tsk->state || unlikely(tsk_is_pi_blocked(tsk)))
 		return;
 	/*
 	 * If we are going to sleep and we have plugged IO queued,

Re: [PATCH] schedule: use unlikely()

[Greg KH]

On Mon, Nov 13, 2017 at 02:00:45PM -0500, Mikulas Patocka wrote:
> A small patch for schedule(), so that the code goes straght in the common
> case.
> 
> Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>

Was this a measurable difference?  If so, great, please provide the
numbers and how you tested in the changelog.  If it can't be measured,
then it is not worth it to add these markings as the CPU/compiler almost
always knows better.

thanks,

greg k-h

Re: [PATCH] schedule: use unlikely()

[Mikulas Patocka]

On Sat, 25 Nov 2017, Greg KH wrote:

> On Mon, Nov 13, 2017 at 02:00:45PM -0500, Mikulas Patocka wrote:
> > A small patch for schedule(), so that the code goes straght in the common
> > case.
> > 
> > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> 
> Was this a measurable difference?  If so, great, please provide the
> numbers and how you tested in the changelog.  If it can't be measured,
> then it is not worth it to add these markings

It is much easier to make microoptimizations (such as using likely() and 
unlikely()) than to measure their effect.

If a programmer were required to measure performance every time he uses 
likely() or unlikely() in his code, he wouldn't use them at all.

> as the CPU/compiler almost always knows better.
> 
> thanks,
> 
> greg k-h

The compiler assumes that pointers are usually not NULL - but in this 
case, they are usually NULL. The compiler can't know better (unless 
profile feedback is used).

Mikulas

Re: [PATCH] schedule: use unlikely()

[Greg KH]

On Mon, Nov 27, 2017 at 07:05:22PM -0500, Mikulas Patocka wrote:
> 
> 
> On Sat, 25 Nov 2017, Greg KH wrote:
> 
> > On Mon, Nov 13, 2017 at 02:00:45PM -0500, Mikulas Patocka wrote:
> > > A small patch for schedule(), so that the code goes straght in the common
> > > case.
> > > 
> > > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> > 
> > Was this a measurable difference?  If so, great, please provide the
> > numbers and how you tested in the changelog.  If it can't be measured,
> > then it is not worth it to add these markings
> 
> It is much easier to make microoptimizations (such as using likely() and 
> unlikely()) than to measure their effect.
> 
> If a programmer were required to measure performance every time he uses 
> likely() or unlikely() in his code, he wouldn't use them at all.

If you can not measure it, you should not use it.  You are forgetting
about the testing that was done a few years ago that found that some
huge percentage (80? 75? 90?) of all of these markings were wrong and
harmful or did absolutely nothing.

> > as the CPU/compiler almost always knows better.
> > 
> > thanks,
> > 
> > greg k-h
> 
> The compiler assumes that pointers are usually not NULL - but in this 
> case, they are usually NULL. The compiler can't know better (unless 
> profile feedback is used).

If you think so, great, but prove it, otherwise you are adding markup
that is not needed or could be harmful. :)

thanks,

greg k-h

Re: [PATCH] schedule: use unlikely()

[Mikulas Patocka]

On Tue, 28 Nov 2017, Greg KH wrote:

> On Mon, Nov 27, 2017 at 07:05:22PM -0500, Mikulas Patocka wrote:
> > 
> > 
> > On Sat, 25 Nov 2017, Greg KH wrote:
> > 
> > > On Mon, Nov 13, 2017 at 02:00:45PM -0500, Mikulas Patocka wrote:
> > > > A small patch for schedule(), so that the code goes straght in the common
> > > > case.
> > > > 
> > > > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> > > 
> > > Was this a measurable difference?  If so, great, please provide the
> > > numbers and how you tested in the changelog.  If it can't be measured,
> > > then it is not worth it to add these markings
> > 
> > It is much easier to make microoptimizations (such as using likely() and 
> > unlikely()) than to measure their effect.
> > 
> > If a programmer were required to measure performance every time he uses 
> > likely() or unlikely() in his code, he wouldn't use them at all.
> 
> If you can not measure it, you should not use it.  You are forgetting
> about the testing that was done a few years ago that found that some
> huge percentage (80? 75? 90?) of all of these markings were wrong and
> harmful or did absolutely nothing.

The whole kernel has 19878 likely/unlikely tags.

Do you have benchmark proving efficiency for each of them? :-)

Mikulas

Re: [PATCH] schedule: use unlikely()

[Greg KH]

On Thu, Nov 30, 2017 at 02:04:01AM -0500, Mikulas Patocka wrote:
> 
> 
> On Tue, 28 Nov 2017, Greg KH wrote:
> 
> > On Mon, Nov 27, 2017 at 07:05:22PM -0500, Mikulas Patocka wrote:
> > > 
> > > 
> > > On Sat, 25 Nov 2017, Greg KH wrote:
> > > 
> > > > On Mon, Nov 13, 2017 at 02:00:45PM -0500, Mikulas Patocka wrote:
> > > > > A small patch for schedule(), so that the code goes straght in the common
> > > > > case.
> > > > > 
> > > > > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> > > > 
> > > > Was this a measurable difference?  If so, great, please provide the
> > > > numbers and how you tested in the changelog.  If it can't be measured,
> > > > then it is not worth it to add these markings
> > > 
> > > It is much easier to make microoptimizations (such as using likely() and 
> > > unlikely()) than to measure their effect.
> > > 
> > > If a programmer were required to measure performance every time he uses 
> > > likely() or unlikely() in his code, he wouldn't use them at all.
> > 
> > If you can not measure it, you should not use it.  You are forgetting
> > about the testing that was done a few years ago that found that some
> > huge percentage (80? 75? 90?) of all of these markings were wrong and
> > harmful or did absolutely nothing.
> 
> The whole kernel has 19878 likely/unlikely tags.

And most of them are wrong.  Don't add new ones unless you can prove it
is correct.

> Do you have benchmark proving efficiency for each of them? :-)

Yes, people have done this work in the past, see the archives.

greg k-h

Re: [PATCH] schedule: use unlikely()

[Pavel Machek]

[-- Attachment #1: Type: text/plain, Size: 1775 bytes --]

On Thu 2017-11-30 08:07:44, Greg KH wrote:
> On Thu, Nov 30, 2017 at 02:04:01AM -0500, Mikulas Patocka wrote:
> > 
> > 
> > On Tue, 28 Nov 2017, Greg KH wrote:
> > 
> > > On Mon, Nov 27, 2017 at 07:05:22PM -0500, Mikulas Patocka wrote:
> > > > 
> > > > 
> > > > On Sat, 25 Nov 2017, Greg KH wrote:
> > > > 
> > > > > On Mon, Nov 13, 2017 at 02:00:45PM -0500, Mikulas Patocka wrote:
> > > > > > A small patch for schedule(), so that the code goes straght in the common
> > > > > > case.
> > > > > > 
> > > > > > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> > > > > 
> > > > > Was this a measurable difference?  If so, great, please provide the
> > > > > numbers and how you tested in the changelog.  If it can't be measured,
> > > > > then it is not worth it to add these markings
> > > > 
> > > > It is much easier to make microoptimizations (such as using likely() and 
> > > > unlikely()) than to measure their effect.
> > > > 
> > > > If a programmer were required to measure performance every time he uses 
> > > > likely() or unlikely() in his code, he wouldn't use them at all.
> > > 
> > > If you can not measure it, you should not use it.  You are forgetting
> > > about the testing that was done a few years ago that found that some
> > > huge percentage (80? 75? 90?) of all of these markings were wrong and
> > > harmful or did absolutely nothing.
> > 
> > The whole kernel has 19878 likely/unlikely tags.
> 
> And most of them are wrong.  Don't add new ones unless you can prove it
> is correct.

_Most_ of them wrong? Really? Where is your data for _that_?

									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: [PATCH] schedule: use unlikely()

[Greg KH]

On Fri, Dec 08, 2017 at 03:30:18PM +0100, Pavel Machek wrote:
> On Thu 2017-11-30 08:07:44, Greg KH wrote:
> > On Thu, Nov 30, 2017 at 02:04:01AM -0500, Mikulas Patocka wrote:
> > > 
> > > 
> > > On Tue, 28 Nov 2017, Greg KH wrote:
> > > 
> > > > On Mon, Nov 27, 2017 at 07:05:22PM -0500, Mikulas Patocka wrote:
> > > > > 
> > > > > 
> > > > > On Sat, 25 Nov 2017, Greg KH wrote:
> > > > > 
> > > > > > On Mon, Nov 13, 2017 at 02:00:45PM -0500, Mikulas Patocka wrote:
> > > > > > > A small patch for schedule(), so that the code goes straght in the common
> > > > > > > case.
> > > > > > > 
> > > > > > > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> > > > > > 
> > > > > > Was this a measurable difference?  If so, great, please provide the
> > > > > > numbers and how you tested in the changelog.  If it can't be measured,
> > > > > > then it is not worth it to add these markings
> > > > > 
> > > > > It is much easier to make microoptimizations (such as using likely() and 
> > > > > unlikely()) than to measure their effect.
> > > > > 
> > > > > If a programmer were required to measure performance every time he uses 
> > > > > likely() or unlikely() in his code, he wouldn't use them at all.
> > > > 
> > > > If you can not measure it, you should not use it.  You are forgetting
> > > > about the testing that was done a few years ago that found that some
> > > > huge percentage (80? 75? 90?) of all of these markings were wrong and
> > > > harmful or did absolutely nothing.
> > > 
> > > The whole kernel has 19878 likely/unlikely tags.
> > 
> > And most of them are wrong.  Don't add new ones unless you can prove it
> > is correct.
> 
> _Most_ of them wrong? Really? Where is your data for _that_?

Andi Kleen ran tests about 5 years ago or so which showed this.  It's in
the archives somewhere...

greg k-h

Re: [PATCH] schedule: use unlikely()

[Pavel Machek]

[-- Attachment #1: Type: text/plain, Size: 1435 bytes --]

On Tue 2017-11-28 08:22:50, Greg KH wrote:
> On Mon, Nov 27, 2017 at 07:05:22PM -0500, Mikulas Patocka wrote:
> > 
> > 
> > On Sat, 25 Nov 2017, Greg KH wrote:
> > 
> > > On Mon, Nov 13, 2017 at 02:00:45PM -0500, Mikulas Patocka wrote:
> > > > A small patch for schedule(), so that the code goes straght in the common
> > > > case.
> > > > 
> > > > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> > > 
> > > Was this a measurable difference?  If so, great, please provide the
> > > numbers and how you tested in the changelog.  If it can't be measured,
> > > then it is not worth it to add these markings
> > 
> > It is much easier to make microoptimizations (such as using likely() and 
> > unlikely()) than to measure their effect.
> > 
> > If a programmer were required to measure performance every time he uses 
> > likely() or unlikely() in his code, he wouldn't use them at all.
> 
> If you can not measure it, you should not use it.  You are forgetting
> about the testing that was done a few years ago that found that some
> huge percentage (80? 75? 90?) of all of these markings were wrong and
> harmful or did absolutely nothing.

If Mikulas has enough data that particular if() is usually taken or
not, that should be enough.
								Pavel
								-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]