diff options
author | Josh Bleecher Snyder <josharian@gmail.com> | 2017-02-13 12:46:17 -0800 |
---|---|---|
committer | Josh Bleecher Snyder <josharian@gmail.com> | 2017-02-14 00:01:22 +0000 |
commit | 46a75870ad5b9b9711e69ffce3738a3ab2057789 (patch) | |
tree | 56cb970b704a126287c469112d2bf6c5d7b27c74 /src/runtime/stubs.go | |
parent | 83c58ac710517e0b3fb2654cdba187e45900cca2 (diff) | |
download | go-46a75870ad5b9b9711e69ffce3738a3ab2057789.tar.gz go-46a75870ad5b9b9711e69ffce3738a3ab2057789.zip |
runtime: speed up fastrand() % n
This occurs a fair amount in the runtime for non-power-of-two n.
Use an alternative, faster formulation.
name old time/op new time/op delta
Fastrandn/2-8 4.45ns ± 2% 2.09ns ± 3% -53.12% (p=0.000 n=14+14)
Fastrandn/3-8 4.78ns ±11% 2.06ns ± 2% -56.94% (p=0.000 n=15+15)
Fastrandn/4-8 4.76ns ± 9% 1.99ns ± 3% -58.28% (p=0.000 n=15+13)
Fastrandn/5-8 4.96ns ±13% 2.03ns ± 6% -59.14% (p=0.000 n=15+15)
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)
Updates #16213
Change-Id: Ib555a4d7da2042a25c3976f76a436b536487d5b7
Reviewed-on: https://go-review.googlesource.com/36932
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Diffstat (limited to 'src/runtime/stubs.go')
-rw-r--r-- | src/runtime/stubs.go | 7 |
1 files changed, 7 insertions, 0 deletions
diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go index e839c59d55..ff230b8e55 100644 --- a/src/runtime/stubs.go +++ b/src/runtime/stubs.go @@ -103,6 +103,13 @@ func fastrand() uint32 { return fr } +//go:nosplit +func fastrandn(n uint32) uint32 { + // This is similar to fastrand() % n, but faster. + // See http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ + return uint32(uint64(fastrand()) * uint64(n) >> 32) +} + //go:linkname sync_fastrand sync.fastrand func sync_fastrand() uint32 { return fastrand() } |