Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

math/rand: no non-default concurrency-safe Source #21393

Open
krancour opened this issue Aug 11, 2017 · 8 comments

Comments

@krancour
Copy link

commented Aug 11, 2017

I apologize if this is a duplicate issue. I looked and couldn't quite find this one...

According to math/rand package documentation, the following is not concurrency safe:

var seededRand = rand.New(rand.NewSource(time.Now().UnixNano()))

NewSource returns a new pseudo-random Source seeded with the given value. Unlike the default Source used by top-level functions, this source is not safe for concurrent use by multiple goroutines.

The aforementioned "default source," is (rightfully) not exported by the math/rand package. So the only way to generate random numbers in a concurrency-safe fashion (with this package, at least) is to resort to using package level functions that rely on the default, concurrency-safe source.

To seed that, one must make a call similar to the following:

rand.Seed(time.Now().UnixNano())

But this is equally a problem! Why? Because nothing prevents any other bit of code from also seeding/re-seeding the math/rand package-level default source. Consider the possibility that some third party package that is initialized after one has seeded the source re-seeds the source with a constant-- bye, bye, psuedo-randomness; hello determinism.

The bottom line here is that achieving concurrency safety with math/rand forces one down a path that's dependent on package-level globals and that introduces its own problems. It's out of the frying pan and into the fryer, and that is (for me at least) making the package nearly unusable.

@ianlancetaylor ianlancetaylor changed the title math/rand usability issues math/rand: no non-default concurrency-safe Source Aug 11, 2017

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Aug 11, 2017

It seems straightforward to wrap a mutex around your calls to a Source.

That said, do you have a suggestion for how the package should be changed?

@ianlancetaylor ianlancetaylor added this to the Unplanned milestone Aug 11, 2017

@josharian

This comment has been minimized.

Copy link
Contributor

commented Aug 11, 2017

In Go 2 world, we could have the default source be non-concurrency-safe, and provide a convenience wrapper that accepts a Source and returns a concurrency-safe Source. (There may be some subtleties and/or optimizations that just throwing a mutex won't help with, like batching core PRNG calls for rand.Read.)

(I have a partially written Go 2 math/rand proposal. I had in mind this being a part of it, but I hadn't gotten to working this part of it yet.)

@krancour

This comment has been minimized.

Copy link
Author

commented Aug 11, 2017

It seems straightforward to wrap a mutex around your calls to a Source

I suppose I could and probably will. But, should I have to? imho if something in the standard library implicitly requires me to wrap something in a mutex just to use it safely, then it should have done that for me. (This is, in fact how the package level default source works. It's a locking source that utilizes a mutex. At minimum, it would be nice if that source impl or something similar to it were exported so I could use it.)

@gopherbot

This comment has been minimized.

Copy link

commented Sep 4, 2017

Change https://golang.org/cl/10161 mentions this issue: x/exp/rand: new rand package

gopherbot pushed a commit to golang/exp that referenced this issue Sep 4, 2017
x/exp/rand: new rand package
This is an approximately compatible new implementation of math/rand.
The differences are:

Source emits uint64s rather than positive int64s.
The method is now
	Uint64() uint64; not
	Int63() int64
There are corresponding new methods on Rand:
	func (r *Rand) Uint64() uint64
	func (r *Rand) Uint64n(n uint64) uint64
The default Source is now an exported type, PCGSource.

The default Source holds 128 bits of state for a 64-bit
result. This has good statistical properties but is slower,
largely because the multiplication step is inefficient.
That can be improved with assembler.

Thus the default Source has a two 64-bit words of state (in
math/rand it has 607 words). It is thus practical to have
millions of Sources in the address space, making it well
suited to lock-free simulations using random numbers.

Benchmarks:

benchmark                        old ns/op     new ns/op     delta
BenchmarkInt63Threadsafe-4       20.0          24.4          +22.00%
BenchmarkInt63Unthreadsafe-4     6.32          13.0          +105.70%
BenchmarkIntn1000-4              16.4          23.8          +45.12%
BenchmarkInt63n1000-4            25.5          23.8          -6.67%
BenchmarkInt31n1000-4            14.2          23.8          +67.61%
BenchmarkFloat32-4               11.8          21.0          +77.97%
BenchmarkFloat64-4               8.76          18.3          +108.90%
BenchmarkPerm3-4                 80.3          94.3          +17.43%
BenchmarkPerm30-4                627           814           +29.82%

The new generator is PCG XSL RR 128/64 (LCG) from
http://www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.pdf
It has been tested against the C version and generates the same
output if initialized to the same value.
See also http://www.pcg-random.org/.

TODO: Improve performance, make initialization better.

Independently, this fixes a bug in the bias-prevention code that
appears, in this package, in Uint64n.

This also exports LockedSource:
Update golang/go#21393.

Change-Id: I48a410fade5d78b8ec993cc1210b96b7a9ab462f
Reviewed-on: https://go-review.googlesource.com/10161
Reviewed-by: Rob Pike <r@golang.org>
@dr2chase

This comment has been minimized.

Copy link
Contributor

commented Feb 26, 2018

Would a deterministic parallel random number generator work for you?
E.g., http://supertech.csail.mit.edu/papers/dprng.pdf

@andybons

This comment has been minimized.

Copy link
Member

commented Mar 26, 2018

I suppose I could and probably will. But, should I have to? imho if something in the standard library implicitly requires me to wrap something in a mutex just to use it safely, then it should have done that for me. (This is, in fact how the package level default source works. It's a locking source that utilizes a mutex. At minimum, it would be nice if that source impl or something similar to it were exported so I could use it.)

There are a lot of constructs in the standard library (and language) that require you to wrap them in a mutex or use channels in order to avoid creating race conditions.

It would be helpful to have your desired change in a proposal format (https://golang.org/s/proposal) so that we can better understand what exact changes we’d make along with motivating examples on why the status quo is unusable for you.

@krancour

This comment has been minimized.

Copy link
Author

commented Mar 27, 2018

I think I've stated the case clearly and succinctly. I'm not sure what information is missing (warranting the "WaitingForInfo" label) or what the benefit of a more elaborate proposal would be.

@andybons

This comment has been minimized.

Copy link
Member

commented Mar 27, 2018

There is precedent with the log package. Moving this to a NeedsDecision.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
6 participants
You can’t perform that action at this time.