Generating random numbers using C++ standard library: the problems
codingnest.com
codingnest.com
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.
Distributions are dog slow.
Look at the "Conclusion" section of this article:
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.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.
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.
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.)
References? I'm not being snide. I need to save those for future arguments.
In short:
* It has a huge state (~2kB per instance); compare 128-bit LCG at 128 bits or even a cryptographic PRF like Chacha at 64 bytes. This is a factor of 128x larger overhead (or 32x bigger than Chacha!) and hurts, say, L1 cache of more important data, especially with multiple instances.
* It has mediocre statistical properties (fails TestU01 BigCrush, fails PractRand). (128-bit LCG passes both.)
* And it has mediocre performance. (In the PCG benchmark, pg. 35: ~2.17 ns/op vs 128/64 LCG at ~1.05 ns/op. In that diagram, labelled "MCG" — but MCGs are just a subset of LCGs.)
Ref: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
See also: https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages
It too has a 128bit state and has a hard to beat speed for such a naive implementation
Yes and no. There are a lot of different functions in the PCG umbrella and that adds some mental complexity IMO. Some of the functions are very simple, including the 128-bit LCG I am referring to above ("pcg64_fast", IIRC). It is almost trivial; basically a single LoC to generate the next state and a single LoC to produce the output from that state:
https://github.com/imneme/pcg-c/blob/master/include/pcg_vari...
https://github.com/imneme/pcg-c/blob/master/include/pcg_vari...
https://github.com/imneme/pcg-c/blob/master/include/pcg_vari...
https://github.com/imneme/pcg-c/blob/master/include/pcg_vari...
Or condensed from several composed inline functions:
uint64_t
my_pcg64_fast(uint128_t *state)
{
// Multiplier: (2549297995355413924ULL << 64) + 4865540595714422341ULL
*state *= PCG_DEFAULT_MULTIPLIER_128;
// Output is XOR-condensed state rotated right by the high 6 bits of state.
return pcg_rotr_64(((uint64_t)(*state >> 64u)) ^ (uint64_t)*state,
*state >> 122u);
}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
C++ standard PRNG's, on top of all the brokenness listed in the article are very inefficient, especially if you use distributions.
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.
> 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.
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.
I wouldn't say so. Even object initialization is atrociously complex in C++.
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.
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.
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.