Repository navigation
proposal: use PCG Source in math/rand for Go 2 #21835
Description
The original math/rand package had a number of flaws. Some of the flaws in the API have been addressed, such as the addition of the Source64 interface, but the most important issue remains: the default Source is poor.
The Source has several problems.
- It has no clear provenance (it came from Plan 9, but its history before that is unknown).
- It is a linear feedback shift register, which is known to have flaws uncovered by various empirical tests.
- It is difficult and expensive to seed.
- It is enormous! The shift register itself comprises 607 64-bit words, a total of 4856 bytes.
This last point is not fatal if there is only one instance, but it couples poorly with another fundamental and perhaps unfixable problem: bad behavior when accessed concurrently. It must be protected with a mutex, but if it were much smaller (and cheaper to seed) it would be practical instead to have each client in the address space access a separate instance, seeded uniquely.
To put it another way, with a separate Source for each goroutine, no locking would be required, but the current implementation is impractically large for such an approach.
The proposal here is in several parts.
First, we create an alternate Source implementation. Our choice is the Permuted Congruential Generator (PCG) designed and thoroughly tested by O'Neill in:
PCG: A Family of Simple Fast Space-Efficient Statistically Good
Algorithms for Random Number Generation
Melissa E. O’Neill, Harvey Mudd College
http://www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.pdf
A 128-bit PCG generator producing a 64-bit output is only two words of memory but provably has a period of 2**128, is cheap to seed, and efficient. (A 64-bit generator would be noticeably cheaper, but a period of only 2**64 is deemed too small for modern hardware). It is practical and reasonable for every goroutine to have a local Source (a simple seeding algorithm is to use the address of the Source as the seed).
An implementation of this generator, specifically PCG XSL RR 128/64 (LCG), is checked in to golang.org/x/exp/rand as its default Source.
Second, we work on the compiler, possibly through math/bits, to make it a little more efficient. The current implementation, in pure Go, is somewhat slower than math/rand, but could be comparably fast or even faster given compiler support for the 128-bit multiply inside.
The third part is the critical piece.
We propose to make this generator the default one in math/rand for Go 2. The Go 1 compatibility decree could allow it to happen today, but we have chosen in the past to take the guarantee more literally than is expressed by also requiring that the generated stream of bits will never change. This decision was made when a fix was done, but enough tests in production were discovered that depended on the exact stream that it was deemed simpler to lock down the implementation rather than to fix all the tests.
However, with Go 2 on the horizon, there is enough time and understanding and process to offer an opportunity to use rolling out an improved, API-compatible version of math/rand as an early test case for Go 2. Changing math/rand to use PCG is strictly incompatible, but not in a way that the Go 1 decree actually prohibits. A soft breakage at this level would be an excellent step on the way to understanding what it takes to roll out a breaking change for Go 2.
In essence, the proposal is to use the fixing of math/rand as a test case for introducing breaking changes in Go 2. And a much better random number generator would result, too: the breaking change is worth making.
The precise sequence of steps to roll it out needs discussion, but one possible outline is like this:
- Add PCG as a secondary source to
math/rand, but not as the default. - Make it available under an alternate name;
PCGSourceis the obvious. - Provide an alias for the current source, say
LFSRSource. - Optional: Provide a gofix that updates existing code to use
LFSRSourcerather thanSource. SinceSourceis usually hidden, accessed throughRand, this may be ineffectual unless we also provide PCG functions explicitly forInt32, etc. Or perhaps provide LFSR versions and rotate towards those in legacy code. - Make announcements of what's to come.
- At some point, flip the alias so
Sourcepoints toPCGSourceandLFSRSourceis no longer the default. - In parallel with this work, make
math/bitssupport its operations more efficiently through the compiler. - Just prior to Go 2, delete
LFSRSource.
At some point along the way, Source64 should become the default, under a similar sequence of events. Minor cleanups could occur too, tidying up the API and fixing some old-style names like Intn not IntN.
There is much detail that remains to be worked out; this proposal is only an outline.
Activity
[-]proposal: fix math/rand for Go 2[/-][+]proposal: use PCG source in math/rand for Go 2[/+][-]proposal: use PCG source in math/rand for Go 2[/-][+]proposal: use PCG Source in math/rand for Go 2[/+]odeke-em commentedon Sep 11, 2017
@MichaelTJones perhaps you might be interested in this issue, as you already have an implementation of Melissa O'Neill's PCG generator at https://github.com/MichaelTJones/pcg.
MichaelTJones commentedon Sep 12, 2017
I would very much support this change. In fact my careful PCG implementation is because of the weaknesses mentioned here. I long ago switched to this code and will not use the present library PRNG. In addition to being technically excellent, a new generator can be created in 2.72ns, makes new 64-bit values in 5.56ns, and has small state. Examine the tests in my implementation for details.
dongweigogo commentedon Sep 12, 2017
why not bring it to Go 1
mvdan commentedon Sep 12, 2017
@dongweigogo please read the proposal text carefully, it is explained.
btracey commentedon Oct 24, 2017
For some random generators, generating a bunch of new streams is worse statistically for once stream. Section 4.3.2 of the paper suggests that this is not a problem with PCG if the seeding is done properly. Just wanted to comment for anyone curious.
MichaelTJones commentedon Oct 24, 2017
lemire commentedon Jan 10, 2018
@MichaelTJones Notice how the bounded functions are significantly slower, that's because of the divisions. You can follow the new implementation at go/src/math/rand/rand.go and avoid divisions (with high probability) and get something faster...
MichaelTJones/pcg#2
Once Go gets something like a full 64-bit multiplication (outputting both the high and low 64-bit values), then we will be able to similarly speed up Bounded64.
27 remaining items
lemire commentedon Dec 4, 2020
@zephyrtronium I was under the impression that wasm did have 64-bit integer support universally today? Is this not the case? Or do you mean to refer to something else with the remark "especially as Wasm becomes more prominent". Or is there a particular issue with how Go generate wasm outputs?
cc @jfbastien
imneme commentedon Dec 4, 2020
It's worth noting that I responded to his critiques here.
zephyrtronium commentedon Dec 4, 2020
So it does, my mistake. I must have misread something about Wasm at some point.
imneme commentedon Dec 4, 2020
Also, as observed by some of the commentators here, more recently Vigna has raised concerns about self-similarity in PCG. If we interleave outputs from carefully chosen seedings of PCG, although the outputs are superficially different, the closer scrutiny applied by sensitive PRNG tests will reveal correlations of some kind indicating that the generator exhibits self-similarity between distant parts of its output.
I think this kind of self-similarity is interesting (and well known for the LCGs that underlie PCG), but Vigna's apparent grave concern about this issue was rather undercut when, on the NumPy mailing list, Tyge Løvset pointed out that similar issues affected Vigna's own most-recent PRNG, xoshift** (comment, code).
If users follow good practice for seeding PRNGs (which they should for a wide variety of other reasons), these kinds of issues won't arise (or rather, they are vanishingly unlikely). An alternative is to scramble the output more aggressively, but the trade-off is execution time. PCG's newest output permutation, DXSM, does represent an attempt to scramble better at no added cost on many platforms, but it is still making a trade off in this space.
Plazmaz commentedon Dec 5, 2020
I wasn't sure of the impact of the claims made, but the general tone was harsh enough it made it more difficult to take his critiques seriously, although I felt there was some interesting points mentioned. I'm happy you took the time to address them, and thank you for providing that information here. His post was certainly at best unintentionally misleading.
jfbastien commentedon Jan 28, 2021
@lemire sorry for missing this, I don't look at github notifications often.
Yes, wasm supports 64-bit integers universally as a first-class type. The initial discussion in 2016 hedged a bit in case there were JS-based implementations in some browsers, but now all relevant browsers support wasm natively (that's 92% of all users on the web). Non-browser implementations of wasm also support 64-bit integers natively.
Maybe the confusion is around "32-bit platforms"? wasm is currently ILP32, thought there's a proposal for wasm64 with 64-bit address spaces. Limiting the address space to 32 bits doesn't limit the use of 64-bit integers.
trafalmuffti commentedon Apr 2, 2021
There is no mention of a multiply-with-carry generator in these discussions. Unlike many of these other algorithms, it is listed on wikipedia and is simply a LCG with less constants.
If the multiply-with-carry generator had a lag of at least 2 (according to the parlance used), it would be parallelizable by typical cpu dispatch units as there would be less dependencies.
Hopefully whatever the generator used, it will allow for 64-bit seeds or at least frequent reseeding.
This AES-NI accelerated RNG is faster and has performance nearly that of a CPU's memory transfer limit: dragontamer/aesrand
Adding an extra AES round might make it cryptographic.
rkern commentedon May 5, 2021
Hi everyone! I'm a numpy developer with a particular focus on our PRNG capabilities. For some background, the older PCG64 with the XSL-RR output function is our current default PRNG for the past couple of years. The next release will have an optional implementation with the stronger DXSM output function. We expect we will make it the default some undetermined time down the road.
I have written up a what I hope to be an accessible explanation of the consequences so you don't have to reconstruct everything from those long digressing threads. My prose style is prone to long, complicated sentences, so please ask if anything needs to be clarified; that will help me edit this down for my own audience. I hope to provide a point of view as a PRNG library maintainer that is helpfully complementary to those of our PRNG algorithm authors. To be clear about where I'm writing from, numpy is an anchor library for scientific computing and machine learning, so we have a particular risk profile that is driving our decisions. The extreme conditions that would make this weakness non-negligibly likely are not really a practical use case right now, but you can see it on the horizon, at least for my audience. This is likely a different risk profile for you, but I try to give the information needed to evaluate things for yourself rather than boil everything down to a universal safe/unsafe declaration.
If I were still asked my opinion for what you should do, if you do decide to use a PCG algorithm, I would recommend using the DXSM variant over the XSL-RR. While the risks of XSL-RR are rare outside of extreme use cases and usually inconsequential, I think they are still worth documenting. And it's a pain to document and a pain for the user to work through the math to determine that yes, they are safe using it. DXSM provides an extra safety margin that renders those computations (and my article) unnecessary. I can think about the DXSM variant with a mental model that is a lot less complicated than one I would now use for XSL-RR. As a library maintainer and documenter, that's golden.
lemire commentedon May 5, 2021
@rkern
You sir have no idea what long and complicated sentences are... :-)
imneme commentedon May 5, 2021
Thanks for the write up! Nicely done.
(It might be too tangential to include, but the only thing I'd add is that detectable self-similarity is not unique to LCGs (and PCG); it's findable in a number of non-cryptographic PRNGs.)
rsc commentedon Jun 13, 2023
See #60751 for a GitHub Discussion that I hope will lead to a math/rand/v2. Closing as duplicate of that.