From e7e4a4ffa3330518250c4075e1f16a8ba62414df Mon Sep 17 00:00:00 2001 From: Giovanni Bajo Date: Sat, 9 Sep 2017 14:59:06 +0200 Subject: [PATCH] runtime: improve fastrand with a better generator MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The current generator is a simple LSFR, which showed strong correlation in higher bits, as manifested by fastrandn(). Change it with xorshift64+, which is slightly more complex, has a larger state, but has a period of 2^64-1 and is much better at statistical tests. The version used here is capable of passing Diehard and even SmallCrush. Speed is slightly worse but is probably insignificant: name old time/op new time/op delta Fastrand-4 0.77ns ±12% 0.91ns ±21% +17.31% (p=0.048 n=5+5) FastrandHashiter-4 13.6ns ±21% 15.2ns ±17% ~ (p=0.160 n=6+5) Fastrandn/2-4 2.30ns ± 5% 2.45ns ±15% ~ (p=0.222 n=5+5) Fastrandn/3-4 2.36ns ± 7% 2.45ns ± 6% ~ (p=0.222 n=5+5) Fastrandn/4-4 2.33ns ± 8% 2.61ns ±30% ~ (p=0.126 n=6+5) Fastrandn/5-4 2.33ns ± 5% 2.48ns ± 9% ~ (p=0.052 n=6+5) Fixes #21806 Change-Id: I013bb37b463fdfc229a7f324df8fe2da8d286f33 Reviewed-on: https://go-review.googlesource.com/62530 Run-TryBot: Michael Munday TryBot-Result: Gobot Gobot Reviewed-by: Keith Randall --- src/runtime/chan_test.go | 57 ++++++++++++++++++++++++++++++++++++++++ src/runtime/proc.go | 12 +++++---- src/runtime/runtime2.go | 18 ++++++------- src/runtime/stubs.go | 15 +++++++---- 4 files changed, 83 insertions(+), 19 deletions(-) diff --git a/src/runtime/chan_test.go b/src/runtime/chan_test.go index a09baf52e1..69c64b5f37 100644 --- a/src/runtime/chan_test.go +++ b/src/runtime/chan_test.go @@ -5,6 +5,7 @@ package runtime_test import ( + "math" "runtime" "sync" "sync/atomic" @@ -430,6 +431,62 @@ func TestSelectStress(t *testing.T) { wg.Wait() } +func TestSelectFairness(t *testing.T) { + const trials = 10000 + c1 := make(chan byte, trials+1) + c2 := make(chan byte, trials+1) + for i := 0; i < trials+1; i++ { + c1 <- 1 + c2 <- 2 + } + c3 := make(chan byte) + c4 := make(chan byte) + out := make(chan byte) + done := make(chan byte) + var wg sync.WaitGroup + wg.Add(1) + go func() { + defer wg.Done() + for { + var b byte + select { + case b = <-c3: + case b = <-c4: + case b = <-c1: + case b = <-c2: + } + select { + case out <- b: + case <-done: + return + } + } + }() + cnt1, cnt2 := 0, 0 + for i := 0; i < trials; i++ { + switch b := <-out; b { + case 1: + cnt1++ + case 2: + cnt2++ + default: + t.Fatalf("unexpected value %d on channel", b) + } + } + // If the select in the goroutine is fair, + // cnt1 and cnt2 should be about the same value. + // With 10,000 trials, the expected margin of error at + // a confidence level of five nines is 4.4172 / (2 * Sqrt(10000)). + r := float64(cnt1) / trials + e := math.Abs(r - 0.5) + t.Log(cnt1, cnt2, r, e) + if e > 4.4172/(2*math.Sqrt(trials)) { + t.Errorf("unfair select: in %d trials, results were %d, %d", trials, cnt1, cnt2) + } + close(done) + wg.Wait() +} + func TestChanSendInterface(t *testing.T) { type mt struct{} m := &mt{} diff --git a/src/runtime/proc.go b/src/runtime/proc.go index 0e58838c88..0a85986f6c 100644 --- a/src/runtime/proc.go +++ b/src/runtime/proc.go @@ -531,15 +531,17 @@ func mcommoninit(mp *m) { callers(1, mp.createstack[:]) } - mp.fastrand = 0x49f6428a + uint32(mp.id) + uint32(cputicks()) - if mp.fastrand == 0 { - mp.fastrand = 0x49f6428a - } - lock(&sched.lock) mp.id = sched.mcount sched.mcount++ checkmcount() + + mp.fastrand[0] = 1597334677 * uint32(mp.id) + mp.fastrand[1] = uint32(cputicks()) + if mp.fastrand[0]|mp.fastrand[1] == 0 { + mp.fastrand[1] = 1 + } + mpreinit(mp) if mp.gsignal != nil { mp.gsignal.stackguard1 = mp.gsignal.stack.lo + _StackGuard diff --git a/src/runtime/runtime2.go b/src/runtime/runtime2.go index 15adfc74ec..174a73bdb3 100644 --- a/src/runtime/runtime2.go +++ b/src/runtime/runtime2.go @@ -414,7 +414,9 @@ type m struct { newSigstack bool // minit on C thread called sigaltstack printlock int8 incgo bool // m is executing a cgo call - fastrand uint32 + fastrand [2]uint32 + needextram bool + traceback uint8 ncgocall uint64 // number of cgo calls in total ncgo int32 // number of cgo calls currently in progress cgoCallersUse uint32 // if non-zero, cgoCallers in use temporarily @@ -424,14 +426,12 @@ type m struct { schedlink muintptr mcache *mcache lockedg guintptr - createstack [32]uintptr // stack that created this thread. - freglo [16]uint32 // d[i] lsb and f[i] - freghi [16]uint32 // d[i] msb and f[i+16] - fflag uint32 // floating point compare flags - locked uint32 // tracking for lockosthread - nextwaitm uintptr // next m waiting for lock - needextram bool - traceback uint8 + createstack [32]uintptr // stack that created this thread. + freglo [16]uint32 // d[i] lsb and f[i] + freghi [16]uint32 // d[i] msb and f[i+16] + fflag uint32 // floating point compare flags + locked uint32 // tracking for lockosthread + nextwaitm uintptr // next m waiting for lock waitunlockf unsafe.Pointer // todo go func(*g, unsafe.pointer) bool waitlock unsafe.Pointer waittraceev byte diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go index 19cddc9f65..331fc0d518 100644 --- a/src/runtime/stubs.go +++ b/src/runtime/stubs.go @@ -96,11 +96,16 @@ var hashLoad = float32(loadFactorNum) / float32(loadFactorDen) //go:nosplit func fastrand() uint32 { mp := getg().m - fr := mp.fastrand - mx := uint32(int32(fr)>>31) & 0xa8888eef - fr = fr<<1 ^ mx - mp.fastrand = fr - return fr + // Implement xorshift64+: 2 32-bit xorshift sequences added together. + // Shift triplet [17,7,16] was calculated as indicated in Marsaglia's + // Xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf + // This generator passes the SmallCrush suite, part of TestU01 framework: + // http://simul.iro.umontreal.ca/testu01/tu01.html + s1, s0 := mp.fastrand[0], mp.fastrand[1] + s1 ^= s1 << 17 + s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16 + mp.fastrand[0], mp.fastrand[1] = s0, s1 + return s0 + s1 } //go:nosplit -- 2.48.1