code review 10042044: runtime: improve scheduler fairness

runtime: improve scheduler fairness
Currently global runqueue is starved if a group of goroutines
constantly respawn each other (local runqueue never becomes empty).
Fixes issue 5639.

[dvyukov, 2013-06-05 12:22:18]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://dvyukov%40google.com@code.google.com/p/go/

[iant, 2013-06-06 23:56:10]

https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:1164: if((int32)(p->tick - p->tickglobcheck) > 0)  // be
careful with overflow
I don't really see the point of tickglobcheck.  Pulling in another goroutine
every so often shouldn't be too expensive, and it's hard for me to believe that
adjusting tickglobcheck based on the size of the P's run queue will matter very
much.  Suppose you just say something like
    if ((p->tick & 0x3f) == 0)

https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:2209: // Try get one G from the global queue.
s/Try get/Try to get/

https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:2213: gp = runtime·sched.runqhead;
This introduces another spot that needs to manage this list, but it's not
performance critical at all.  Suppose we just call globrunqget here.  Or, if you
really don't want that many g's (though I don't know why that would matter), add
an argument to globrunqget: the maximum number of g's to move.  For the other
calls pass, I don't know, 32 or something.  Here, pass 1.

[dvyukov, 2013-06-07 14:42:06]

https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:1164: if((int32)(p->tick - p->tickglobcheck) > 0)  // be
careful with overflow
On 2013/06/06 23:56:10, iant wrote:
> I don't really see the point of tickglobcheck.  Pulling in another goroutine
> every so often shouldn't be too expensive, and it's hard for me to believe
that
> adjusting tickglobcheck based on the size of the P's run queue will matter
very
> much.  Suppose you just say something like
>     if ((p->tick & 0x3f) == 0)


That's probably fine. But this it too simple check, I was actually able to
exploit it with the following program, so that the global queue is never polled.
Is it possible to do a less exploitable check w/o using division?

func TestTimerFairness2(t *testing.T) {
	done := make(chan bool)
	c := make(chan bool)
	for i := 0; i < 2; i++ {
		go func() {
			timer := time.After(20 * time.Millisecond)
			var buf [1]byte
			for {
				syscall.Read(0, buf[0:0])
				select {
				case c <- true:
				case <-c:
				case <-timer:
					done <- true
					return
				}
			}
		}()
	}
	<-done
	<-done
}

[dvyukov, 2013-06-07 15:10:57]

Added a comment explaining why we don't want to poll global queue too often.

https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:2213: gp = runtime·sched.runqhead;
On 2013/06/06 23:56:10, iant wrote:
> This introduces another spot that needs to manage this list, but it's not
> performance critical at all.  Suppose we just call globrunqget here.  Or, if
you
> really don't want that many g's (though I don't know why that would matter),
add
> an argument to globrunqget: the maximum number of g's to move.  For the other
> calls pass, I don't know, 32 or something.  Here, pass 1.

Done.

[dvyukov, 2013-06-07 15:12:10]

On 2013/06/07 14:42:06, dvyukov wrote:
> https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c
> File src/pkg/runtime/proc.c (right):
> 
>
https://codereview.appspot.com/10042044/diff/11001/src/pkg/runtime/proc.c#new...
> src/pkg/runtime/proc.c:1164: if((int32)(p->tick - p->tickglobcheck) > 0)  //
be
> careful with overflow
> On 2013/06/06 23:56:10, iant wrote:
> > I don't really see the point of tickglobcheck.  Pulling in another goroutine
> > every so often shouldn't be too expensive, and it's hard for me to believe
> that
> > adjusting tickglobcheck based on the size of the P's run queue will matter
> very
> > much.  Suppose you just say something like
> >     if ((p->tick & 0x3f) == 0)
> 
> 
> That's probably fine. But this it too simple check, I was actually able to
> exploit it with the following program, so that the global queue is never
polled.
> Is it possible to do a less exploitable check w/o using division?

A good check would be something like (tick%59)==0 || (tick%61)==0 (both prime
numbers), but I don't want 2 divisions on scheduler fast path.


> func TestTimerFairness2(t *testing.T) {
> 	done := make(chan bool)
> 	c := make(chan bool)
> 	for i := 0; i < 2; i++ {
> 		go func() {
> 			timer := time.After(20 * time.Millisecond)
> 			var buf [1]byte
> 			for {
> 				syscall.Read(0, buf[0:0])
> 				select {
> 				case c <- true:
> 				case <-c:
> 				case <-timer:
> 					done <- true
> 					return
> 				}
> 			}
> 		}()
> 	}
> 	<-done
> 	<-done
> }

[iant, 2013-06-10 17:38:25]

On Fri, Jun 7, 2013 at 8:12 AM,  <dvyukov@google.com> wrote:
>
> A good check would be something like (tick%59)==0 || (tick%61)==0 (both
> prime numbers), but I don't want 2 divisions on scheduler fast path.

Well, how would you feel about some multiplications on the fast path?
Division by an unsigned constant is equivalent to multiplication by a
large unsigned constant.  Look at the code that GCC -O2 generates for
x % 59.

Ian

[dvyukov, 2013-06-13 11:43:16]

Hello golang-dev@googlegroups.com, iant@golang.org (cc:
golang-dev@googlegroups.com),

Please take another look.

[dvyukov, 2013-06-13 11:45:35]

On 2013/06/13 11:43:16, dvyukov wrote:
> Hello mailto:golang-dev@googlegroups.com, mailto:iant@golang.org (cc:
> mailto:golang-dev@googlegroups.com),
> 
> Please take another look.

OK, let's try MUL, it's a bit better than DIV:

with DIV:
      4.22%  runtime.test  runtime.test       [.] schedule       
3.78 :          418fa8:       xor    %edx,%edx                                  
                                                                                
                            0.00 :          418faa:       movl   $0x3d,0xc(%rsp)
                                                                                
                                                        0.00 :          418fb2: 
     divl   0xc(%rsp)                                                           
                                
37.11:          418fb6:       cmp    $0x0,%edx                                  
                                                     
0.00 :          418fb9:       jne    418fe0 <schedule+0xa0>  	
      
with MUL:
      3.39%  runtime.test  runtime.test       [.] schedule     
8.19 :          418fa8:       mov    %edx,%eax                                  
                                                                                
                            1.72 :          418faa:       imul  
$0x4325c53f,%rax,%rax                                                           
                     
1.29 :          418fb1:       shr    $0x24,%rax                                 
                                                      
2.16 :          418fb5:       imul   $0x3d,%rax,%rax                            
                                                      
7.76 :          418fb9:       mov    %edx,%ecx                                  
                                                      
0.00 :          418fbb:       sub    %rax,%rcx                                  
                                                      
0.00 :          418fbe:       cmp    $0x0,%rcx                                  
                                                      
0.00 :          418fc2:       jne    418fe9 <schedule+0xa9>

[iant, 2013-06-14 15:40:37]

LGTM

Thanks.

https://codereview.appspot.com/10042044/diff/33001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/10042044/diff/33001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:1027: gp = globrunqget(m->p, -1);
Since nobody is ever going to pass a max of 0, it might be infinitesimally more
efficient to pass 0 rather than -1 when there is no max.

https://codereview.appspot.com/10042044/diff/33001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:1164: // it uses 2 MUL instructions instead of a single
DIV and so faster on modern processors.
s/so faster/so is faster/

[dvyukov, 2013-06-15 12:03:03]

https://codereview.appspot.com/10042044/diff/33001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/10042044/diff/33001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:1027: gp = globrunqget(m->p, -1);
On 2013/06/14 15:40:37, iant wrote:
> Since nobody is ever going to pass a max of 0, it might be infinitesimally
more
> efficient to pass 0 rather than -1 when there is no max.

Done.

https://codereview.appspot.com/10042044/diff/33001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:1164: // it uses 2 MUL instructions instead of a single
DIV and so faster on modern processors.
On 2013/06/14 15:40:37, iant wrote:
> s/so faster/so is faster/

Done.

[dvyukov, 2013-06-15 12:06:39]

*** Submitted as https://code.google.com/p/go/source/detail?r=81e554ab7787 ***

runtime: improve scheduler fairness
Currently global runqueue is starved if a group of goroutines
constantly respawn each other (local runqueue never becomes empty).
Fixes issue 5639.

R=golang-dev, iant
CC=golang-dev
https://codereview.appspot.com/10042044