From 510ad4561f859f66e5a2d22a73ce8253d19ede3e Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Tue, 7 Dec 2021 09:22:33 -0800 Subject: [PATCH] runtime: improve work stealing randomness For certain values of GOMAXPROCS, the current code is less random than it looks. For example with GOMAXPROCS=12, there are 4 coprimes: 1 5 7 11. That's bad, as 12 and 4 are not relatively prime. So if pos == 2, then we always pick 7 as the inc. We want to pick pos and inc independently at random. Change-Id: I5c7e4f01f9223cbc2db12a685dc0bced2cf39abf Reviewed-on: https://go-review.googlesource.com/c/go/+/369976 Run-TryBot: Keith Randall Trust: Keith Randall TryBot-Result: Gopher Robot Reviewed-by: Dmitry Vyukov --- src/runtime/proc.go | 2 +- src/runtime/proc_runtime_test.go | 17 +++++++++++++++++ 2 files changed, 18 insertions(+), 1 deletion(-) diff --git a/src/runtime/proc.go b/src/runtime/proc.go index b997a467ba..df16e0f9b6 100644 --- a/src/runtime/proc.go +++ b/src/runtime/proc.go @@ -6138,7 +6138,7 @@ func (ord *randomOrder) start(i uint32) randomEnum { return randomEnum{ count: ord.count, pos: i % ord.count, - inc: ord.coprimes[i%uint32(len(ord.coprimes))], + inc: ord.coprimes[i/ord.count%uint32(len(ord.coprimes))], } } diff --git a/src/runtime/proc_runtime_test.go b/src/runtime/proc_runtime_test.go index a7bde2c6df..90aed83d46 100644 --- a/src/runtime/proc_runtime_test.go +++ b/src/runtime/proc_runtime_test.go @@ -30,4 +30,21 @@ func RunStealOrderTest() { } } } + // Make sure that different arguments to ord.start don't generate the + // same pos+inc twice. + for procs := 2; procs <= 64; procs++ { + ord.reset(uint32(procs)) + checked := make([]bool, procs*procs) + // We want at least procs*len(ord.coprimes) different pos+inc values + // before we start repeating. + for i := 0; i < procs*len(ord.coprimes); i++ { + enum := ord.start(uint32(i)) + j := enum.pos*uint32(procs) + enum.inc + if checked[j] { + println("procs:", procs, "pos:", enum.pos, "inc:", enum.inc) + panic("duplicate pos+inc during enumeration") + } + checked[j] = true + } + } } -- 2.50.0