runtime: select on a shared channel is slow with many Ps

[bradfitz]

@tombergan and I have been debugging a severe performance regression that Kubernetes observed when switching from Go 1.7 to Go 1.8. The problem ended up being the addition of net/http.Server.Shutdown that's currently implemented by closing a channel that all the open connections select on.

(Details in kubernetes/kubernetes#45216 and #20302)

But the short summary is:

package selbench
        
import "testing"
        
func BenchmarkSelectShared(b *testing.B) {
        idleShared := make(chan struct{})
        b.RunParallel(func(pb *testing.PB) {
                ch := make(chan int, 1)
                for pb.Next() {
                        select {
                        case ch <- 1:
                        case <-ch:
                        case <-idleShared:
                        }
                }
        })      
}       

func BenchmarkSelectPrivate(b *testing.B) {
        b.RunParallel(func(pb *testing.PB) {
                ch := make(chan int, 1)
                idlePrivate := make(chan struct{})
                for pb.Next() {
                        select {
                        case ch <- 1:
                        case <-ch:
                        case <-idlePrivate:
                        }
                }
        })
} 

Note that the idle channels below are never closed and are never selectable, but the other two are, and stay busy.

But when the channel is private to the goroutine (uncontended), things are fast. When it's a shared channel, things are slow.

$ go test -v -bench=Select -cpu=1,2,4,8,16,32,64
BenchmarkSelectShared           10000000               194 ns/op
BenchmarkSelectShared-2         10000000               147 ns/op
BenchmarkSelectShared-4          5000000               395 ns/op
BenchmarkSelectShared-8          3000000               449 ns/op
BenchmarkSelectShared-16         5000000               354 ns/op
BenchmarkSelectShared-32         5000000               320 ns/op
BenchmarkSelectShared-64         5000000               296 ns/op
BenchmarkSelectPrivate          10000000               192 ns/op
BenchmarkSelectPrivate-2        20000000                98.0 ns/op
BenchmarkSelectPrivate-4        30000000                49.3 ns/op
BenchmarkSelectPrivate-8        50000000                25.5 ns/op
BenchmarkSelectPrivate-16       100000000               13.8 ns/op
BenchmarkSelectPrivate-32       200000000                7.07 ns/op
BenchmarkSelectPrivate-64       200000000                6.31 ns/op

Are there any optimizations to be done here?

We'll work around it in the meantime and generally keep this in mind as an anti-pattern for performance.

/cc @aclements @randall77 @ianlancetaylor @rsc @josharian @mdempsky

[tombergan]

The root problem is lock contention in runtime.sellock and runtime.selunlock. One idea is to replace runtime.mutex with a scalable lock, such as an MCS lock.

[ianlancetaylor]

An MCS lock can scale a spinlock, but that's not what this is. Though I suppose maybe it could be, it's not long we ever hold channels locked.

One thing that might speed up this test case would be to scan all the channels without locking them to see if they are ready. Then lock only the ones that are ready, and check them again. But that will only help the real code if there is usually some ready channel. If the select usually has to wait, it won't help, because we need to queue the goroutine on each channel. Even if we use a spinlock that queuing step is going to be a point of contention.

[josharian]

I think the usage pattern is a bit more accurately described with this benchmark:

package selbench

import (
	"fmt"
	"math/rand"
	"testing"
	"time"
)

func BenchmarkSelectContended(b *testing.B) {
	for workers := 1; workers <= 100000; workers *= 10 {
		b.Run(fmt.Sprintf("workers=%d", workers), func(b *testing.B) {
			done := make(chan struct{})
			// Spin up workers, each with their own work channel.
			wc := make([]chan struct{}, workers)
			for i := range wc {
				c := make(chan struct{})
				go func() {
					for {
						select {
						case <-done:
							return
						case <-c:
						}
					}
				}()
				wc[i] = c
			}
			b.ResetTimer()
			// Have the workers do b.N units of work.
			b.RunParallel(func(pb *testing.PB) {
				src := rand.New(rand.NewSource(time.Now().UnixNano()))
				for pb.Next() {
					wc[src.Intn(len(wc))] <- struct{}{}
				}
			})
			b.StopTimer()
			close(done)
		})
	}
}

For this, I see a total lack of scaling at small numbers of workers and a performance cliff as the number of workers grows large.

$ go test -bench=. -cpu=1,2,4,8,16,32,64 -benchtime=100ms x_test.go 
goos: darwin
goarch: amd64
BenchmarkSelectContended/workers=1            	  500000	       350 ns/op
BenchmarkSelectContended/workers=1-2          	  300000	       417 ns/op
BenchmarkSelectContended/workers=1-4          	  300000	       487 ns/op
BenchmarkSelectContended/workers=1-8          	  300000	       561 ns/op
BenchmarkSelectContended/workers=1-16         	  200000	       623 ns/op
BenchmarkSelectContended/workers=1-32         	  200000	       628 ns/op
BenchmarkSelectContended/workers=1-64         	  200000	       594 ns/op
BenchmarkSelectContended/workers=10           	  500000	       376 ns/op
BenchmarkSelectContended/workers=10-2         	  300000	       513 ns/op
BenchmarkSelectContended/workers=10-4         	  300000	       620 ns/op
BenchmarkSelectContended/workers=10-8         	  300000	       575 ns/op
BenchmarkSelectContended/workers=10-16        	  300000	       533 ns/op
BenchmarkSelectContended/workers=10-32        	  300000	       508 ns/op
BenchmarkSelectContended/workers=10-64        	  300000	       461 ns/op
BenchmarkSelectContended/workers=100          	  300000	       385 ns/op
BenchmarkSelectContended/workers=100-2        	  300000	       443 ns/op
BenchmarkSelectContended/workers=100-4        	  300000	       439 ns/op
BenchmarkSelectContended/workers=100-8        	  300000	       539 ns/op
BenchmarkSelectContended/workers=100-16       	  200000	       594 ns/op
BenchmarkSelectContended/workers=100-32       	  200000	       601 ns/op
BenchmarkSelectContended/workers=100-64       	  200000	       696 ns/op
BenchmarkSelectContended/workers=1000         	  300000	       452 ns/op
BenchmarkSelectContended/workers=1000-2       	  300000	       426 ns/op
BenchmarkSelectContended/workers=1000-4       	  300000	       412 ns/op
BenchmarkSelectContended/workers=1000-8       	  200000	       563 ns/op
BenchmarkSelectContended/workers=1000-16      	  200000	       551 ns/op
BenchmarkSelectContended/workers=1000-32      	  200000	       606 ns/op
BenchmarkSelectContended/workers=1000-64      	  300000	       601 ns/op
BenchmarkSelectContended/workers=10000        	  200000	       894 ns/op
BenchmarkSelectContended/workers=10000-2      	  200000	       691 ns/op
BenchmarkSelectContended/workers=10000-4      	  200000	       597 ns/op
BenchmarkSelectContended/workers=10000-8      	  200000	       788 ns/op
BenchmarkSelectContended/workers=10000-16     	  100000	      1174 ns/op
BenchmarkSelectContended/workers=10000-32     	  200000	       792 ns/op
BenchmarkSelectContended/workers=10000-64     	  100000	      1070 ns/op
BenchmarkSelectContended/workers=100000       	    1000	    157938 ns/op
BenchmarkSelectContended/workers=100000-2     	     200	   1044491 ns/op
BenchmarkSelectContended/workers=100000-4     	      50	   2425451 ns/op
BenchmarkSelectContended/workers=100000-8     	     300	    848236 ns/op
BenchmarkSelectContended/workers=100000-16    	     500	    201122 ns/op
BenchmarkSelectContended/workers=100000-32    	      20	   9354451 ns/op
BenchmarkSelectContended/workers=100000-64    	       1	 187918798 ns/op
PASS
ok  	command-line-arguments	18.974s

[bradfitz]

@josharian, that rand.Intn call in there has a mutex (var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})). I'd remove that and use a goroutine-local math/rand.Rand instead.

[josharian]

@bradfitz sheesh. Thanks. Updated in situ above. Results are unchanged, though.

$ go test -bench=. -cpu=1,2,4,8,16,32,64 -benchtime=100ms x_test.go 
BenchmarkSelectContended/workers=1            	  300000	       358 ns/op
BenchmarkSelectContended/workers=1-2          	  300000	       526 ns/op
BenchmarkSelectContended/workers=1-4          	  300000	       552 ns/op
BenchmarkSelectContended/workers=1-8          	  300000	       600 ns/op
BenchmarkSelectContended/workers=1-16         	  200000	       713 ns/op
BenchmarkSelectContended/workers=1-32         	  200000	       674 ns/op
BenchmarkSelectContended/workers=1-64         	  200000	       701 ns/op
BenchmarkSelectContended/workers=10           	  500000	       399 ns/op
BenchmarkSelectContended/workers=10-2         	  300000	       551 ns/op
BenchmarkSelectContended/workers=10-4         	  300000	       585 ns/op
BenchmarkSelectContended/workers=10-8         	  200000	       660 ns/op
BenchmarkSelectContended/workers=10-16        	  300000	       574 ns/op
BenchmarkSelectContended/workers=10-32        	  300000	       551 ns/op
BenchmarkSelectContended/workers=10-64        	  300000	       498 ns/op
BenchmarkSelectContended/workers=100          	  500000	       439 ns/op
BenchmarkSelectContended/workers=100-2        	  300000	       481 ns/op
BenchmarkSelectContended/workers=100-4        	  300000	       494 ns/op
BenchmarkSelectContended/workers=100-8        	  300000	       569 ns/op
BenchmarkSelectContended/workers=100-16       	  200000	       733 ns/op
BenchmarkSelectContended/workers=100-32       	  200000	       650 ns/op
BenchmarkSelectContended/workers=100-64       	  200000	       645 ns/op
BenchmarkSelectContended/workers=1000         	  200000	       583 ns/op
BenchmarkSelectContended/workers=1000-2       	  300000	       467 ns/op
BenchmarkSelectContended/workers=1000-4       	  300000	       492 ns/op
BenchmarkSelectContended/workers=1000-8       	  200000	       633 ns/op
BenchmarkSelectContended/workers=1000-16      	  200000	       651 ns/op
BenchmarkSelectContended/workers=1000-32      	  200000	       645 ns/op
BenchmarkSelectContended/workers=1000-64      	  200000	       708 ns/op
BenchmarkSelectContended/workers=10000        	  100000	      1056 ns/op
BenchmarkSelectContended/workers=10000-2      	  200000	       756 ns/op
BenchmarkSelectContended/workers=10000-4      	  200000	       691 ns/op
BenchmarkSelectContended/workers=10000-8      	  200000	       795 ns/op
BenchmarkSelectContended/workers=10000-16     	  200000	       810 ns/op
BenchmarkSelectContended/workers=10000-32     	  200000	       804 ns/op
BenchmarkSelectContended/workers=10000-64     	  200000	       889 ns/op
BenchmarkSelectContended/workers=100000       	    1000	    134482 ns/op
BenchmarkSelectContended/workers=100000-2     	     500	    208302 ns/op
BenchmarkSelectContended/workers=100000-4     	     100	   1339142 ns/op
BenchmarkSelectContended/workers=100000-8     	       1	 170459942 ns/op
BenchmarkSelectContended/workers=100000-16    	     100	   1204770 ns/op
BenchmarkSelectContended/workers=100000-32    	     300	    573343 ns/op
BenchmarkSelectContended/workers=100000-64    	       1	 188693577 ns/op
PASS
ok  	command-line-arguments	19.280s

[valyala]

Cc @dvyukov

[dvyukov]

Running a benchmark with fast iterations and heavy setup for 1 iteration does not make sense. The numbers at the bottom is setup cost, not the cost of chan operation. Run them for more iterations.

[bradfitz]

@dvyukov, see also the original benchmark at top. But ignoring specific benchmarks (flawed or not), do you have any thoughts?

[huguesb]

@josharian @dvyukov the addition of a waitgroup fixes the 100k worker case:

package selbench

import (
	"fmt"
	"math/rand"
	"sync"
	"testing"
	"time"
)

func BenchmarkSelectContended(b *testing.B) {
	for workers := 1; workers <= 100000; workers *= 10 {
		b.Run(fmt.Sprintf("workers=%d", workers), func(b *testing.B) {
			done := make(chan struct{})
			// Spin up workers, each with their own work channel.
			wc := make([]chan struct{}, workers)
			var wg sync.WaitGroup
			wg.Add(workers)
			for i := range wc {
				c := make(chan struct{})
				go func() {
					wg.Done()
					for {
						select {
						case <-done:
							return
						case <-c:
						}
					}
				}()
				wc[i] = c
			}
			wg.Wait()
			b.ResetTimer()
			// Have the workers do b.N units of work.
			b.RunParallel(func(pb *testing.PB) {
				src := rand.New(rand.NewSource(time.Now().UnixNano()))
				for pb.Next() {
					wc[src.Intn(len(wc))] <- struct{}{}
				}
			})
			b.StopTimer()
			close(done)
		})
	}
}

This gives me the following on a 4 core i7 (w/ hyper threading):

name                              time/op
SelectContended/workers=1          408ns ± 1%
SelectContended/workers=1-2        483ns ± 0%
SelectContended/workers=1-4        528ns ± 2%
SelectContended/workers=1-8        595ns ± 4%
SelectContended/workers=10         454ns ± 0%
SelectContended/workers=10-2       536ns ± 1%
SelectContended/workers=10-4       634ns ± 3%
SelectContended/workers=10-8       880ns ±10%
SelectContended/workers=100        490ns ± 2%
SelectContended/workers=100-2      522ns ± 2%
SelectContended/workers=100-4      596ns ± 3%
SelectContended/workers=100-8      855ns ± 6%
SelectContended/workers=1000       582ns ± 2%
SelectContended/workers=1000-2     510ns ± 5%
SelectContended/workers=1000-4     563ns ± 3%
SelectContended/workers=1000-8     838ns ± 5%
SelectContended/workers=10000      913ns ± 5%
SelectContended/workers=10000-2    542ns ± 2%
SelectContended/workers=10000-4    533ns ± 4%
SelectContended/workers=10000-8    911ns ± 4%
SelectContended/workers=100000    1.70µs ± 7%
SelectContended/workers=100000-2   915ns ± 7%
SelectContended/workers=100000-4   685ns ±12%
SelectContended/workers=100000-8  1.15µs ± 3%

[dvyukov]

Lock-free channels help to some degree (#8899):

tip:
BenchmarkSelectContended10000-64 2000000 1985 ns/op
BenchmarkSelectContended10000-64 2000000 1929 ns/op
BenchmarkSelectContended10000-64 2000000 2031 ns/op

3c3be62 (base for lock-free chans):
BenchmarkSelectContended10000-64 50000 110105 ns/op
BenchmarkSelectContended10000-64 50000 110315 ns/op
BenchmarkSelectContended10000-64 50000 113208 ns/op

3c3be62 with lock-free chans:
BenchmarkSelectContended10000-64 5000000 1141 ns/op
BenchmarkSelectContended10000-64 5000000 1150 ns/op
BenchmarkSelectContended10000-64 5000000 1208 ns/op

[dvyukov]

@bradfitz What is that shared chan in http? srv.closeDoneChanLocked? I don't see where it is checked during connection serving.
The select is slow, but it does not seem to be too slow. Also numbers does not seem to depend too much on number of goroutines (I guess it is that you just mostly need enough of them to create contention from multiple CPUs).

Shouldn't Served.Shutdown do closeDoneChanLocked before closeListenersLocked? Otherwise error handling logic in Server.Serve is broken. I am not sure if there will a temp error on listener close or not, but bad both ways.