6 ms·
Generating random numbers using C++ standard library: the problems
- self_awareness 6y agoPortability of random number generation in C++ is also described in this blog post: http://anadoxin.org/blog/c-shooting-yourself-in-the-foot-4.html http://anadoxin.org/blog/c-shooting-yourself-in-the-foot-4.h...
- steerablesafe 6y agostd::seed_seq and the SeedSeq concept look incredibly broken, also it looks way over-engineered. Why can't a random generator engine just get a Calleable as a constructor argument and call it as many times as it needs to seed itself? SeedSeq tries to be way more than it needs to be while failing its basic requirement.
- quietbritishjim 6y agoYes indeed. In Boost.Random (which the standard library random was based on), you can do exactly that: boost::mt19937 generator(boost::random_device()); You can also pass an appropriate length container (as two iterators) which are directly used as the seed without any intermediate object.
- Asooka 6y ago> every single part of it is deeply flawed, and the best solution is to avoid using it completely You can sadly say the same for a large part of C++ standard features. At least the core language is mostly sound, simple intuitive and performant, so having to file off some edges is not that big of a problem.
- MaxBarraclough 6y ago> the core language is mostly sound, simple intuitive and performant I wouldn't say so. Even object initialization is atrociously complex in C++. https://stackoverflow.com/a/620402/ https://stackoverflow.com/a/620402/ https://stackoverflow.com/a/54350350/ https://stackoverflow.com/a/54350350/
- quietbritishjim 6y agoOr move semantics including rvalue references. In retrospect, objects should have been moved by default (and destructors for moved-from objects not called), like Rust. Then copying can just be an explicit normal method (that returns its result by moving it!).
- Veedrac 6y ago> and destructors for moved-from objects not called This doesn't work entirely cleanly in cases the compiler can't track liveness, which is more of an issue for C++ than Rust, since you want to be able to move out of pointers. A simple solution is to replace move operators with an `invalidate` function the compiler calls after doing a shallow move, that sets the old value to a moved-from state. Copy constructors (as opposed to copy assignment operators) are already a fine way to copy a value, there's no real need to change that.
- deleted 6y ago[deleted]
- Asooka 6y agoObject initialisation complexity is a consequence of the design goals of C++. It's unavoidable complexity, but it's not surprising once you know about it, and it is required for consistency.
- leni536 6y agoIt's also a consequence of some unfortunate mistakes, like uniform initialization being screwed up by std::initializer_list.
- MaxBarraclough 6y ago> it's not surprising once you know about it I disagree. My first link shows subtle but important differences across versions of C++, and it is surprising. It's a foot-gun at the heart of the language. I agree with the author's comment: This is one of the dusty corners of C++ that can drive you crazy.
- tsimionescu 6y agoC++ is pretty performant, that much is true. But no aspect of C++ is simple, almost all C++ features have complex interactions with almost all other C++ features (I can back this up with examples, if you'd like). And there's always the specter of UB making your benign program have no semantics. There is no other language as complex as C++. Still, for its relatively larhe niche, there is nothing that beats well-written C++. Thankfully, that niche has been ever-shrinking, though very slowly. Perhaps Rust will stake a claim to another part of C++'s niche, like Java/C# did so successfully before.
- mark-r 6y agoYou can't even count on std::random_device doing something sane. https://stackoverflow.com/q/18880654/5987 https://stackoverflow.com/q/18880654/5987
- loeg 6y agoYes, this is one of the first things covered in the article.
- mark-r 6y agoThey spend a lot of time telling you std::random_device::entropy() is useless, but I don't see anywhere that it says std::random_device itself is bad. The point of my link was to show that random_device itself is unreliable, even if you use it correctly. It doesn't always work as advertised.
- loeg 6y agoI read this part as describing that flaw: > The problem is that std::random_device is poorly specified, and inscrutable. > In theory, it should serve as an abstraction over some external source of entropy. In practice, an implementation is allowed to use any deterministic random number engine to implement it, e.g. a Mersenne twister, and there is no way to find out. There is a member function std::random_device::entropy(), which is in theory there to detect such case, but it does not work in practice. They go on to discuss ::entropy()'s flaws after that.
- jeffbee 6y agoWouldn't stability of output with given initial conditions totally freeze any ability to change the implementation in the future?
- loeg 6y agoSort of. Yes, you can't change the results, and that is often desirable for simulations. Consider academic publication and replication. You could make optimizations that do not affect results.
- joosters 6y agoSo you need a large stream of random numbers to seed your random number generator? Seems like a bizarre chicken and egg problem... If I had a source for large quantities of random numbers, why would I even need the second random number generator?
- ChrisSD 6y agoIf you have a stream of random numbers it can be expanded it to a gigantic stream of random numbers. A good pseudo-random number generator can give you a ZiB of random data from a 128bit or 256bit number.
- gnulinux 6y agoBecause one of them can be slower than the other? Let's assume random.org gives true quantum randomness. Let's assume it's acceptable for my program to make an api call to random.org to get some random numbers. That doesn't mean I want to go to internet every time I need a random number. I'd much rather get something like 256 random bits from random.org and create the rest with Mersenne Twister which has an insanely large period.
- kevin_thibedeau 6y agoYou might want the second generator to be deterministic. Consider a fuzzing testcase that generates randomized inputs. When a failure is hit the seed is recorded and someone can reproduce it for debugging.
- _wldu 6y agoOn Unix systems, you can use /dev/urandom to do this.
- loeg 6y agoThe use case here is basically simulations, where cryptographic RNG quality is not needed but a lot of pseudo-random numbers are. Even the fastest CSPRNGs (e.g., bulk Chacha20 keystream) are much much slower than good non-cryptographic PRNGs such as PCG or a 128-bit LCG. (Note that Mersenne Twister is an awful PRNG despite its enduring popularity.) If you play around with Chacha rounds, the minimal number of rounds necessary to provide "good", but non-cryptographic, results is 4[1], and Chacha4 (with dolbeau AVX acceleration) is still substantially slower than PCG or 128-bit LCG with 4 rounds (something like 30-50% slower than pcg64_fast, as I measure it). (Full-round AES w/ AES-NI is about 30% slower than Chacha4 w/ AVX on my hardware, but I did not test a reduced-round AES with AES-NI acceleration; that might be interesting and competitive.) [1]: https://crypto.stackexchange.com/a/57672/51869 https://crypto.stackexchange.com/a/57672/51869
- Jyaif 6y agoMy anecdote with C++'s RNGS: I was getting different sequences of random values using std::minstd_rand on arm64 and arm32. Turns out it was because the seed type is uint_fast32_t and I was passing a 64 bit seed. On arm32 the seed was getting truncated to 32 bits, but not on arm64. It was my fault but it was still surprising.
- 29athrowaway 6y agoBy default with gcc and clang on Linux, random_engine will use /dev/urandom. I use /dev/random and configured it with rng-tools. With rng-tools you can configure the sources of entropy for rngd. You can add a hw random number as entropy source there. Just do not add more entropy than the size of the entropy pool or your system performance will suffer. Some people discard a number of generated values to make it harder to guess the internal state of the generator. discard_block_engine can be used for this too. Anyways, if you want to test your random numbers try https://webhome.phy.duke.edu/~rgb/General/dieharder.php https://webhome.phy.duke.edu/~rgb/General/dieharder.php
- tpolzer 6y agoThe generator/seeding design is gnarly, totally agreed. I do want to disagree with the author on distributions. In most scenarios it is totally sufficient for distributions to be deterministic and reproducible on a given implementation/architecture instead of ossifying them to one implementation mandated by the standard.
- ur-whale 6y ago>n most scenarios it is totally sufficient for distributions to be deterministic and reproducible on a given implementation/architecture instead of ossifying them to one implementation mandated by the standard. Distributions are dog slow.
- tpolzer 6y agoCompared to what? Taking rand()%n? Of course they're usually slower than that, because they provide better quality distribution of random numbers.
- ur-whale 6y ago>Compared to what? Look at the "Conclusion" section of this article: https://www.pcg-random.org/posts/bounded-rands.html https://www.pcg-random.org/posts/bounded-rands.html
- otabdeveloper4 6y agoGolly, what a dumb post. I'm pretty sure it's not the job of the C++ standard to force all RNG implementations to be the same.
- saagarjha 6y agoWhat makes you so sure that this is not something that belongs in the C++ standard?
- aelphssss 6y agoI wrote a 64 bit random number generator in C. I didn't think much of it, it's only pseudo random.
- ur-whale 6y agoOne thing that isn't mentioned in the article is performance. C++ standard PRNG's, on top of all the brokenness listed in the article are very inefficient, especially if you use distributions.
- gnulinux 6y agoI was curious why that'd be the case. I checked GCC's implementation. It seems to be here: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/uniform_int_dist.h#L238 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-... Looks like they had to make this very generic, generic enough to account for random number generators that return value in specific ranges. If you have a generator that guarantees to return a uniformly random 32 bit value, it seems much faster to do (r%(max-min)+min) instead.
- brandmeyer 6y agoTaking the modulus of the desired range isn't uniform.
- gnulinux 6y agoThat's true, and obviously so but I never realized it until now. I'm curious why r%(max-min)+min is widespread "common" way of doing this, maybe I just saw it in a few places and never questioned it.
- eska 6y agoSomewhere in the footnotes he mentions that Microsoft considers changing the implementation of its uniform int distribution for performance reasons (as a supporting argument for lack of portability).
- srg0 6y agoPCG is not the only game in town when it comes to high-quality reproducible and fast PRNGs: https://github.com/lemire/testingRNG#visual-summary https://github.com/lemire/testingRNG#visual-summary Notably, some newer PRNGs are faster, and still pass all statistical tests.