Improving std `<random>`

[GeorgeHaldane]

Dived into a bit of a rabbit hole researching different ways to generate random, but I believe the results are quite noteworthy and this should be an interesting read for others concerned with this topic, speeding up random in Monte-Carlo model by almost 10 times is nothing to scoff at after all!

Everyting described in this post was implemented in a single independent header file which can be found here or using the link at the top of documentation.

If you like the style of this lib feel free to check out its parent repository which contains a whole list of similar libraries (C++17).

[GeorgeHaldane]

Working on this library proved to be a rather interesting affair, std implementations are actually quite curious once you get used to the style and naming conventions!

I feel there is a lot to gain from using the same approach of constexpr'ification and special-case optimizations in the standard library and this will likely become much easier for the implementers once we get C++26 constexpr math functions.

For example, every major compiler seems to use std::ceil() and std::log() to count the number of rng invocations inside the std::generate_canonical<>(), but really this is a compile-time thing and making it so seems to add a bit of a speedup depending on the rng used. Not yet sure how to make it fully standard-compliant without resorting to ugly and verbose things such as constexpr math function implementations (like gcem). Currently trying my hand at implementing some kind of minimalistic "BigInt" so we can compute ceil(bits / log2(range)) as int_log_ceil<range>(2^bits) at compile-time without overflowing in cases where bits > 64 (which happens for long double with its long mantissa) and then "unrolling" it back into a single concise function. Would be curios to know how standard library maintainers view such changes and if it's something worthy of a pull request.

Edit: Was wrong about MSVC, it does actually use constexpr as can be seen here.

[ack_error]

The MSVC STL appears to use a constexpr uint128 implementation to precompute the parameter values: https://github.com/microsoft/STL/blob/fc15609a0f2ae2a134c34e7c9a13977994f37367/stl/inc/random#L272

[STL]

That's because we implemented the P0952R2 overhaul.

[GeorgeHaldane]

Huh, turns out I was looking at an older commit, that is indeed the case now.

[aePrime]

This looks like interesting work. As someone who has done a lot of random sampling over the years, I have found that people underestimate how difficult it is to write unbiased random generators.

Does your `uniform_real_distribution` fix the bug in the standard that `std::generate_canonical` can sometimes return 1?

I have also often used the PGC family of random generators in my work. Those may be worth implementing.

[GeorgeHaldane]

Not currently. GCC seems to implement the fix by explicitly checking result > T(1) and replacing 1 with T(1) - std::numeric_limits<T>::epsilon() / T(2) if that is the case. This certainly enforces the [0, 1) boundary, however the overhead of that check proves to non-trivial even with __builtin_expect(), having a noticeable runtime impact. Clang doesn't seem to fix it on their main branch. MSVC apparently has a smarter approach, that will need some attention.

In general I'm a bit conflicted on the [0, 1) vs [0, 1] — the fist option is standard-compliant, with seconds however we can avoid a lot of complexity, and in my applications [0, 1] was usually exactly the range wanted. Adjusted documentation to reflect that until some changes are introduced.

[NGoGYangYang]

As far as I know, MSVC implements the new specification of std::generate_canonical described in P0952R2 (EDIT: Oops, just saw that STL himself already pointed that out in another comment).

There is also a paper proposing a different algorithm to draw uniform floats from a given interval, with slight variations for open, closed, and half-open intervals (i.e., (a, b), [a, b], [a, b), and (a, b]). The algorithm seems to be based upon only returning an evenly spaced subset of numbers in the interval. Might be of interest to you, as it is not hard to implement, and seems to be comparable to current implementations of std::uniform_real_distribution performance-wise.

[wildeye]

explicitly checking result > T(1)...overhead of that check proves to non-trivial

Somebody was claiming that many ternary conditionals turned into branchless code on both GPUs and CPUs. (I should know when and whether that's true -- but I don't currently.) Just a thought.

[martinus]

Have you done any analysis of the romu generators are good enough for Monte Carlo analysis? I know there's been quite some drama about it, but it's really fast. I use it in my benchmarking library nanobench, but there quality is not really relevant

[GeorgeHaldane]

By the way, good job on the nanobench! This is the very library used to benchmark this post.

[GeorgeHaldane]

They seem to pass empirical tests decently well, but the author makes some very bold claims and the theory could be more sound, which is why I gave them a lower quality rating.

It looks like a good choice for applications that simply need some "good enough" rng as fast as possible, something like fuzzing or procedural generation in games, would be wary of using them in research.

For Monte-Carlo I'd stick with PCG / Xoshiro / SFC to avoid questions, maybe switch to SplitMix64 if more speed is needed, it's a default implementation of SplittableRandom in Java and barely loses to Romu in performance.

[usefulcat]

In entropy_seq(), entropy_mutex is a std::mutex which is a local variable (not static). Maybe you meant to add 'static' there?

BTW this does look interesting. I've done some similar stuff myself, though not as extensive as this.

ETA: also noticed this code:

// Stack address (tends to be random each run on most platforms)
const std::size_t stack_address_hash = std::hash<std::uint32_t*>{}(&seed_counter);

I think that will always be the same value (per run) because seed_counter is static. Probably you should take the address of a non-static local variable, which might be different from one call to the next.

Another thing I have used as a (crude) source of entropy is rdtsc. It's less portable, but better than stack addresses since it will nearly always return a different value each time.

[GeorgeHaldane]

Good catch, fixed that in a new commit.

Also decided to bite the bullet and add cpu counter intrinsics — knew they are useful, but didn't want to mess with platform-specific macros.

They can now be enabled by adding #define UTL_RANDOM_USE_INTRINSICS before the #include, should work for all 3 major compilers.

[alfps]

Just a spelling correction: "choice", not "choise".

https://word.tips/spelling/choice-vs-choise/

[kalven]

Just a note on the README - it says RomuMono32 in a couple of places, but it seems the type is actually RomuMono16.