runtime: speed up cheaprand and cheaprand64
The current cheaprand performs 128-bit multiplication on 64-bit numbers
and truncate the result to 32 bits, which is inefficient.
A 32-bit specific implementation is more performant because it performs
64-bit multiplication on 32-bit numbers instead.
The current cheaprand64 involves two cheaprand calls.
Implementing it as 64-bit wyrand is significantly faster.
Since cheaprand64 discards one bit, I have preserved this behavior.
The underlying uint64 function is made available as cheaprandu64.
│ old │ new │
│ sec/op │ sec/op vs base │
Cheaprand-8 1.358n ± 0% 1.218n ± 0% -10.31% (n=100)
Cheaprand64-8 2.424n ± 0% 1.391n ± 0% -42.62% (n=100)
Blocksampled-8 8.347n ± 0% 2.022n ± 0% -75.78% (n=100)
Fixes #77149
Change-Id: Ib0b5da4a642cd34d0401b03c1d343041f8230d11
GitHub-Last-Rev:
549d8d407e2bbcaecdee0b52cbf3a513dda637fb
GitHub-Pull-Request: golang/go#77150
Reviewed-on: https://go-review.googlesource.com/c/go/+/735480
Auto-Submit: Keith Randall <khr@golang.org>
Reviewed-by: Carlos Amedee <carlos@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>