This thread happened…
Choose:
— Elan Ruskin (@despair) May 24, 2018
What is the type of x?
— Jonathan Adamczewski (@twoscomplement) May 24, 2018
std::optional<std::any>
— Andreas Fredriksson (@deplinenoise) May 24, 2018
I’ll see your C++17, and raise you C89:#define x rand()
— Jonathan Adamczewski (@twoscomplement) May 24, 2018
auto x = []() { return rand(); }
— Andreas Fredriksson (@deplinenoise) May 24, 2018
tsk tsk… that’s not mordern enough: auto x = []() { std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dis(0, 32767); return dis(gen); } <— FIXED IT FOR YOU!
— Bobby Anguelov (@BobbyAnguelov) May 24, 2018
So, rand() assembles to ‘jmp rand’. That abomination on the other hand.. My eyes! https://t.co/ujNkLrzavs
— Andreas Fredriksson (@deplinenoise) May 24, 2018
So I did a little digging to satisfy my own curiosity about the “modern C++” version, and have learned a few things that I didn’t know previously…
(this is a manual unrolled twitter thread that starts here, with slight modifications)
Nearly all of this I gleaned from the invaluable http://cppreference.com and http://godbolt.org . Comments about implementation refer specifically to the gcc-8.1 C++ standard library, examined using Compiler Explorer and the -E command line option.
std::random_device is a platform-specific source of entropy.
std: mt19937 is a parameterized typedef of std::mersenne_twister_engine
specifically:
std::mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7, 0x9d2c5680, 15, 0xefc60000, 18, 1812433253>
(What do those number mean? I don’t know.)
And std::uniform_int_distribution produces uniformly distributed random numbers over a specified range, from a provided generator.
The default constructor for std::random_device takes an implementation-defined argument, with a default value.
The meaning of the argument is implementation-defined – but the type is not: std::string. (I’m not sure why a dynamically modifiable string object was the right choice to be the configuration parameter for an entropy generator.)
There are out-of-line private functions for much of this implementation of std::random_device. The constructor that calls the out-of-line init function is itself inline – so the construction and destruction of the default std::string param is also generated inline.
Also, peeking inside std::random_generator, there is a union with two members:
void* _M_file, which I guess would be used to store a file handle for /dev/urandom or similar.
std::mt19937 _M_mt, which is a … parameterized std::mersenne_twister_engine object.
So it seems reasonable to me that if you can’t get entropy* from outside your program, generate your own approximation. It looks like it is possible that the entropy for the std::mersenne_twister_engine will be provided by a std::mersenne_twister_engine.
Unlike std::random_device, which has its implementation out of line, std::mersenne_twister_engine‘s implementation seems to be all inline. It is unclear what benefits this brings, but it results in a few hundred additional instructions generated.
And then there’s std::uniform_int_distribution, which seems mostly unsurprising. It is again fully inline, which (from a cursory eyeballing) may allow a sufficiently insightful compiler to avoid a couple of branches and function calls.
The code that got me started on this was presented in jest – but (std::random_device + std::mt19937 + std::uniform_int_distribution) is a commonly recommended pattern for generating random numbers using these modern C++ library features.
My takeaways:
std::random_device is potentially very expensive to use – and doesn’t provide strong cross-platform guarantees about the randomness it provides. It is configured with an std::string – the meaning of which is platform dependent. I am not compelled to use this type.
std::mt19937 adds a sizeable chunk of codegen via its inline implementation – and there are better options than Mersenne Twister.
Bottom line: I’m probably going to stick with rand(), and if I need something a little fancier, http://www.pcg-random.org/ or one of the other suggestions provided as replies to the twitter thread.
Addition: the code I was able to gather, representing some relevant parts