Skip to content

runtime: select is not fair #21806

Closed
Closed

Description

@bench

What version of Go are you using (go version)?

$ go version
go version go1.9 linux/amd64

Does this issue reproduce with the latest release?

yes, on 1.9

What operating system and processor architecture are you using (go env)?

GOARCH="amd64"
GOBIN=""
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/bchenebault/DEV/git-oab.si.fr.intraorange/BU900102/ceo-be"
GORACE=""
GOROOT="/usr/local/go"
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build913166031=/tmp/go-build -gno-record-gcc-switches"
CXX="g++"
CGO_ENABLED="1"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"

What did you do?

A Go select statement with reflect package function reflect.Select(...) should block until at least one of the cases can proceed and make a uniform pseudo-random choice. It appears that the behavior has changed since returned values are no longer pseudo-random in specific cases only.

Our case is the following : 2 signaling channels preceding 2 "logic" channels
https://play.golang.org/p/0TiMtsRk03

But the same version with only one channel preceding the 2 others works
https://play.golang.org/p/sy4RjEEjdg

This case perfectly works on go1.8.3 and below.

What did you expect to see?

A pseudo random distribution

What did you see instead?

A strange distribution, surely not pseudo random

Activity

  1. changed the title [-]reflect.select() no longer pseudo-random choices[/-] [+]reflect.Select(...) no longer pseudo-random choices[/+] on Sep 8, 2017
  2. changed the title [-]reflect.Select(...) no longer pseudo-random choices[/-] [+]reflect.Select(...) no longer pseudo-random selects[/+] on Sep 8, 2017
  3. changed the title [-]reflect.Select(...) no longer pseudo-random selects[/-] [+]runtime: reflect.Select(...) no longer pseudo-random selects[/+] on Sep 8, 2017
  4. changed the title [-]runtime: reflect.Select(...) no longer pseudo-random selects[/-] [+]runtime: select is not fair[/+] on Sep 8, 2017
  5. ianlancetaylor commented on Sep 8, 2017

    @ianlancetaylor
    Contributor

    This is not just using reflect. This similar program shows the same problem using an ordinary select statement.

    package main
    
    import (
    	"fmt"
    )
    
    func main() {
    	in1 := make(chan int, 15000)
    	in2 := make(chan int, 15000)
    
    	for i := 0; i < 15000; i++ {
    		in1 <- 1
    	}
    
    	for i := 0; i < 15000; i++ {
    		in2 <- 2
    	}
    	out := make(chan int)
    
    	go func() {
    		c1 := make(chan struct{})
    		c2 := make(chan struct{})
    		for {
    			var v int
    			select {
    			case <-c1:
    			case <-c2:
    			case v = <-in2:
    			case v = <-in1:
    			}
    			out <- v
    		}
    	}()
    	
    	var nb1, nb2 int = 0, 0
    
    ConsumerLoop:
    	for {
    		select {
    		case d := <-out:
    			switch d {
    			case 1:
    				nb1++
    				if nb1 > 5000 { // stop consume. At this point, messages should be the equidistribution
    					break ConsumerLoop
    				}
    			case 2:
    				nb2++
    			default:
    				panic(d)
    			}
    		}
    	}
    
    	print(nb1, "\n")
    	print(nb2, "\n")
    
    	if !areSameOrder(nb1, nb2) {
    		fmt.Printf("Should have as many nb1 as nb2, got %d nb1 and %d nb2\n", nb1, nb2)
    	}
    }
    
    func areSameOrder(a, b int) bool {
    	ratio := float32(a) / float32(b)
    	return ratio < 1.3 && ratio > 0.7
    }
    
  6. added this to the Go1.9.1 milestone on Sep 8, 2017
  7. ianlancetaylor commented on Sep 8, 2017

    @ianlancetaylor
    Contributor

    It seems to be a problem with fastrandn. If I replace this line in runtime/select.go:

    		j := fastrandn(uint32(i + 1))
    

    with the line that was in 1.8:

    		j := int(fastrand()) % (i + 1)
    

    then the program runs correctly.

    CC @josharian

  8. zigo101 commented on Sep 8, 2017

    @zigo101
    Contributor

    also not fair for

    			select {
    			case v = <-in2:
    			case v = <-in1:
    			case v = <-in2:
    			case v = <-in1:
    			}

    the ratio is constantly larger than 1.08.

    The ratio for the following is even worse, about 2.0

    			select {
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in1:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			case v = <-in2:
    			}
  9. randall77 commented on Sep 8, 2017

    @randall77
    Contributor

    The problem is one of correlation.

    package main
    
    import "fmt"
    
    var state uint32 = 1
    
    func fastrand() uint32 {
    	fr := state
    	mx := uint32(int32(fr)>>31) & 0xa8888eef
    	fr = fr<<1 ^ mx
    	state = fr
    	return fr
    }
    
    func fastrandn(n uint32) uint32 {
    	return uint32(uint64(fastrand()) * uint64(n) >> 32)
    }
    
    func main() {
    	const N = 4
    	var hist [N][N]int
    	for i := 0; i < 1000000; i++ {
    		x := fastrandn(N)
    		y := fastrandn(N)
    		hist[x][y]++
    	}
    	for i := 0; i < N; i++ {
    		for j := 0; j < N; j++ {
    			fmt.Printf("%6d ", hist[i][j])
    		}
    		fmt.Println()
    	}
    }
    

    Outputs:

    124831 124610      0      0 
         0      0 125374 125232 
         0      0 124870 124900 
    125083 125100      0      0 
    

    So if we get a 0 from fastrandn(4), the next output is guaranteed to be a 0 or a 1.
    I think this is fundamentally a problem with this RNG when N is a power of two, because the values we return are highly predictive of whether we end up xoring in the feedback or not.

    Maybe if we did the feedback in the other direction (shift right, xor based on the low bit), it would help. Or maybe we have to go back to using modulo so we can depend on the low bits.

  10. randall77 commented on Sep 8, 2017

    @randall77
    Contributor
  11. funny-falcon commented on Sep 8, 2017

    @funny-falcon
    Contributor

    @randall77 looks like it is flaw of LFSR. Old version were not better:

    var state uint32 = 1
    func fastrand() uint32 {
        fr := state
        fr <<= 1
        fr ^= uint32(int32(fr)>>31) & 0x88888eef
        state = fr
        return fr
    }                                                    
    func fastrandn(n uint32) uint32 {
            return uint32(uint64(fastrand()) * uint64(n) >> 31)
    }
    125097 124561      0      0
         0      0 124738 125274
    125113 125123      0      0
         0      0 124721 125373
    

    I'm thinking what could be done with.

  12. rasky commented on Sep 8, 2017

    @rasky
    Member

    What about using xorshift instead?

    var state uint32 = 2463534242
    
    func fastrand() uint32 {
    	fr := state
    	fr ^= fr<<13
    	fr ^= fr>>17
    	fr ^= fr<<5
    	state = fr
    	return fr
    }

    Outputs:

     62797  62420  62588  62303 
     62401  62408  61990  62399 
     62207  62601  62742  62515 
     62916  62716  62655  62342 
    

    (https://play.golang.org/p/sD9jmKGWJy)

  13. funny-falcon commented on Sep 8, 2017

    @funny-falcon
    Contributor

    @rasky , xorshift is slower. Otherwise it is good because it gives almost same randomness for high and low bits.

    I have other variant for fastrandn:

    func fastrandn(n uint32) uint32 {
        // some constants with random bit pattern
        // (this are from hash32.go)
        const m1 = 3168982561
        const m2 = 3339683297
        fr := fastrand()
        fr ^= m1
        fr *= m2
        return uint32(uint64(fr) * uint64(n) >> 32)
    }

    It also gives fair distribution

    100192 100322  99857 100461
     99535 100347 100216 100209
     99533 100023  99899 100376
     99678  99796  99982  99574
    

    And it is faster than xorshift.
    But it uses multiplication, and doesn't fix cases when raw fastrand used.

    https://play.golang.org/p/29n_4OfVQq

  14. funny-falcon commented on Sep 8, 2017

    @funny-falcon
    Contributor

    Benchmark:

    • master
    $ GOMAXPROCS=1 ../bin/go test runtime -run 'foo' -bench '.*astrand.*'
    BenchmarkFastrand               1000000000               2.35 ns/op
    BenchmarkFastrandHashiter       50000000                27.3 ns/op
    BenchmarkFastrandn/2            1000000000               2.39 ns/op
    BenchmarkFastrandn/3            1000000000               2.39 ns/op
    BenchmarkFastrandn/4            1000000000               2.39 ns/op
    BenchmarkFastrandn/5            1000000000               2.39 ns/op
    
    • xorshift
    BenchmarkFastrand               500000000                3.16 ns/op
    BenchmarkFastrandHashiter       50000000                33.9 ns/op
    BenchmarkFastrandn/2            500000000                3.34 ns/op
    BenchmarkFastrandn/3            500000000                3.34 ns/op
    BenchmarkFastrandn/4            500000000                3.34 ns/op
    BenchmarkFastrandn/5            500000000                3.34 ns/op
    
    • fastrand in this way:
    func fastrand() uint32 {
        mp := getg().m
        fr := mp.fastrand
        mx := uint32(int32(fr)>>31) & 0xa8888eef
        fr = fr<<1 ^ mx
        mp.fastrand = fr
        fr ^= 3168982561
        fr *= 3339683297
        return fr ^ (fr >> 16)
    }
    BenchmarkFastrand               1000000000               2.34 ns/op
    BenchmarkFastrandHashiter       50000000                34.3 ns/op
    BenchmarkFastrandn/2            1000000000               2.56 ns/op
    BenchmarkFastrandn/3            1000000000               2.56 ns/op
    BenchmarkFastrandn/4            1000000000               2.56 ns/op
    BenchmarkFastrandn/5            1000000000               2.56 ns/op
    
  15. 20 remaining items

  16. randall77 commented on Sep 16, 2017

    @randall77
    Contributor

    I like the CL as is.

  17. gopherbot commented on Sep 17, 2017

    @gopherbot
    Contributor

    Change https://golang.org/cl/64193 mentions this issue: [release-branch.go1.9] runtime: improve fastrand with a better generator

  18. funny-falcon commented on Oct 4, 2017

    @funny-falcon
    Contributor
  19. modified the milestones: Go1.9.1, Go1.9.2 on Oct 4, 2017
  20. gopherbot commented on Oct 4, 2017

    @gopherbot
    Contributor

    Change https://golang.org/cl/68050 mentions this issue: runtime: fix using fastrand in sema.go

  21. rsc commented on Oct 13, 2017

    @rsc
    Contributor

    If we cherry-pick CL 64193 then we must also cherry-pick CL 68050, because CL 64193 breaks a different property of fastrand.

    I'm pretty skeptical of wholesale-replacing the random number generator and then putting it into a point release when we just found a serious problem with it 9 days ago.

    Maybe for Go 1.9.2 we should just fix fastrandn to use a % again. The move away from % got this performance win:

        name                    old time/op  new time/op  delta
        SelectUncontended-8     33.7ns ± 2%  33.9ns ± 2%  +0.70%  (p=0.000 n=49+50)
        SelectSyncContended-8   1.68µs ± 4%  1.65µs ± 4%  -1.54%  (p=0.000 n=50+45)
        SelectAsyncContended-8   282ns ± 1%   277ns ± 1%  -1.50%  (p=0.000 n=48+43)
        SelectNonblock-8        5.31ns ± 1%  5.32ns ± 1%    ~     (p=0.275 n=45+44)
        SelectProdCons-8         585ns ± 3%   577ns ± 2%  -1.35%  (p=0.000 n=50+50)
        GoroutineSelect-8       1.59ms ± 2%  1.59ms ± 1%    ~     (p=0.084 n=49+48)
    

    I'm happy to give that back for Go 1.9.2. The uses of fastrandn elsewhere in the runtime also look like they would appreciate not having terrible correlations, so I don't think we should change only select's use.

  22. rsc commented on Oct 13, 2017

    @rsc
    Contributor

    Closing this and remilestoning Go 1.10. The fix for Go 1.9.2 is #22253.

  23. modified the milestones: Go1.9.2, Go1.10 on Oct 13, 2017
  24. locked and limited conversation to collaborators on Oct 13, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions