math/rand: use a sharded lock for the default shared Source #20387
Comments
|
Recently: |
|
Maybe a cheap intermediate fix would be to have lockedSource be (say) type lockedSource struct {
n uint64
lks [64]sync.Mutex
srcs [64]Source64
}where n is updated with atomic.AddUint64 on each use, and used (%64) as an index into lks and srcs. There's only one of them, so the size increase shouldn't be too bad. |
|
Do we care about changing the generated numbers users see? I thought we did, but I might be thinking of something else. |
|
There have been a slew of cases (#12290, #16124, #8731). I have been unable to discern a coherent explanation for when we can change it and when we can't. Discussion in #8013 and #14416 seems to indicate that none will be forthcoming soon. (I'd still like to see a "big break" release in which we fix a bunch of bugs and inefficiencies that have been blocked by this constraint, including using a much better PRNG, and publish a backwards-compat golang.org/x package usable by those that still really need the original stream.) However, I think with some care and extra overhead I could write this such that the random stream is unaltered when not called concurrently. When called concurrently, all bets for reproducibility are off anyway, and that's the case in which we'd want to shard locks. I'll give it a try. |
|
CL https://golang.org/cl/43611 mentions this issue. |
|
With some brain-hurting/scary atomic fairy dust, I managed to get these performance numbers for "only shard locks when concurrent": I'm not sure that this is worth it. If others disagree, I'm happy to do a documentation pass over the CL to make it reviewable. |
|
IMHO, the current behaviour of |
|
@valyala not changing the behavior for users that depend on it is exactly what @josharian's patch attempts to do. |
DO NOT REVIEW [needs careful docs, not sure we want to do it] demo for golang#20387 name old time/op new time/op delta Int63Threadsafe 23.4ns ± 5% 35.9ns ± 9% +52.92% (p=0.000 n=10+10) Int63Threadsafe-2 22.2ns ±13% 34.9ns ± 3% +57.08% (p=0.000 n=10+10) Int63Threadsafe-4 20.9ns ±16% 34.9ns ± 2% +67.26% (p=0.000 n=10+10) Int63Threadsafe-8 20.1ns ± 2% 34.9ns ± 1% +74.10% (p=0.000 n=8+8) Int63Threadsafe-16 21.2ns ±18% 34.9ns ± 2% +64.15% (p=0.000 n=10+10) Int63Threadsafe-32 20.9ns ± 2% 34.8ns ± 1% +66.45% (p=0.000 n=9+9) Int63Threadsafe-64 22.1ns ±15% 34.6ns ± 1% +56.38% (p=0.000 n=10+9) Int63ThreadsafeParallel 21.2ns ± 3% 35.2ns ± 1% +65.65% (p=0.000 n=10+8) Int63ThreadsafeParallel-2 28.1ns ± 2% 66.3ns ± 4% +135.54% (p=0.000 n=10+10) Int63ThreadsafeParallel-4 45.9ns ± 1% 43.9ns ± 1% -4.31% (p=0.000 n=9+10) Int63ThreadsafeParallel-8 60.1ns ± 2% 34.1ns ± 4% -43.23% (p=0.000 n=9+10) Int63ThreadsafeParallel-16 70.4ns ± 2% 33.9ns ± 3% -51.75% (p=0.000 n=9+10) Int63ThreadsafeParallel-32 78.3ns ±17% 33.5ns ± 3% -57.18% (p=0.000 n=10+10) Int63ThreadsafeParallel-64 105ns ± 5% 33ns ± 1% -68.63% (p=0.000 n=10+9) Change-Id: I02f036c4c80e41df3065446be36840992b1c978e
DO NOT REVIEW [needs careful docs, not sure we want to do it] demo for golang#20387 name old time/op new time/op delta Int63Threadsafe 23.4ns ± 5% 35.9ns ± 9% +52.92% (p=0.000 n=10+10) Int63Threadsafe-2 22.2ns ±13% 34.9ns ± 3% +57.08% (p=0.000 n=10+10) Int63Threadsafe-4 20.9ns ±16% 34.9ns ± 2% +67.26% (p=0.000 n=10+10) Int63Threadsafe-8 20.1ns ± 2% 34.9ns ± 1% +74.10% (p=0.000 n=8+8) Int63Threadsafe-16 21.2ns ±18% 34.9ns ± 2% +64.15% (p=0.000 n=10+10) Int63Threadsafe-32 20.9ns ± 2% 34.8ns ± 1% +66.45% (p=0.000 n=9+9) Int63Threadsafe-64 22.1ns ±15% 34.6ns ± 1% +56.38% (p=0.000 n=10+9) Int63ThreadsafeParallel 21.2ns ± 3% 35.2ns ± 1% +65.65% (p=0.000 n=10+8) Int63ThreadsafeParallel-2 28.1ns ± 2% 66.3ns ± 4% +135.54% (p=0.000 n=10+10) Int63ThreadsafeParallel-4 45.9ns ± 1% 43.9ns ± 1% -4.31% (p=0.000 n=9+10) Int63ThreadsafeParallel-8 60.1ns ± 2% 34.1ns ± 4% -43.23% (p=0.000 n=9+10) Int63ThreadsafeParallel-16 70.4ns ± 2% 33.9ns ± 3% -51.75% (p=0.000 n=9+10) Int63ThreadsafeParallel-32 78.3ns ±17% 33.5ns ± 3% -57.18% (p=0.000 n=10+10) Int63ThreadsafeParallel-64 105ns ± 5% 33ns ± 1% -68.63% (p=0.000 n=10+9) Change-Id: I02f036c4c80e41df3065446be36840992b1c978e
|
This happened as part of #54880. |
Benchmarks and performance sensitive code that use the top-level functions in the math/rand package (
rand.Intnand so forth) will have hidden lock contention on the default sharedSource. This can be a surprise to people, as they see unexpectedly poor performance without realizing clearly that the problem is in their code.. If we had a sharded lock of some sort, this would be a good place to use it.The text was updated successfully, but these errors were encountered: