Show HN: Fast Random Library for C++17
Random number generation feels is a somewhat underrepresented topic in the C++ realm. There is a lot of questionable info about it found online and even the standard library is quite behind the times in terms of it's algorithms. It suffers from trying to accommodate sometimes impractical standard requirements and has several ways of getting significantly bad statistical results. This leaves a lot easily achievable performance & quality on the table.
So, being a mathematician who mostly works with stochastic models and wants these models to run fast and well, I embarked on a journey of trying to summarize "what is good and what is bad" and implement the "best stuff there currently is".
Thankfully, the design of C++ <random> is quite flexible and easy to extend. With some cleanup, generalization and compile-time logic all the different algorithms can be wrapped in a generic standard-compatible API.
A result of this work is single-header RNG library which has:
- <random>-compatible generators (PRNGSs) with 3x-6x better performance
- Cryptographically secure generators (CSPRNGs)
- Faster uniform / normal distributions that produce same sequences on every platform
- Quick approximations of some non-linear distributions
- More reliable entropy sources that std::random_device()
- rand()-like API for when we just want random numbers without the boilerplate of proper a <random> setup
Don't think there is anything else like it, so I would like to showcase the result here and hear some opinions on its improvement:
https://github.com/DmitriBogdanov/UTL/blob/master/docs/modul...
For those interested, there is a more detailed rundown of all the quirks of this topic at end of the docs, might prove an interesting read.
One note on API design: I think it's a FANTASTIC idea to have default `rand()` functions available, since very often, you don't really care about the generator and you're just like "just give me a random number, i don't care how". But if you do, you shouldn't have a `seed()` function, because that means you can then never upgrade it without breaking your API contract. It should always be seeded with entropy. This is why glibc's `rand()` is still using an LCG from the late neolithic, they can't ever update it without breaking a gazillion applications and tests. This is the classic example of "Hyrum's law". Doing this also helps with thread-safety: you can just make the seed/state thread-local and then it just works.
Basically, if you want the ability to seed your PRNG, you also need to specify the generator explicitly. The global one is for convenience only, and there should be no ability in the API to seed it.
EDIT: btw, this is a really nice thing about C++, doing this is dead easy:
Don't think it's a problem in practice because every online tutorial or Stack Overflow posts contain that multi-line snippet for real entropy. C++ programmers are somewhat used to verbosity anyways.
One caveat:
> Note 2: If no hardware randomness is available, std::random_device falls back onto an internal PRNG ....
> ...
> std::random_device has a critical deficiency in it's design — in case its implementation doesn't provide a proper source of entropy, it is free to fallback onto a regular PRNGs that don't change from run to run. The method std::random_device::entropy() which should be able to detect that information is notoriously unreliable and returns different things on every platform.
> entropy() samples several sources of entropy (including the std::random_device itself) and is (almost) guaranteed to change from run to run even if it can't provide a proper hardware-sourced entropy that would be suitable for cryptography.
Personally, I think it would be best if there was a way to communicate to the system (or here, to the library in specific) what is the use case. For cryptographic applications, I don't want the library to fall back gracefully to something insecure; I would want a dark red critical error message and immediate termination with an "insufficient entropy error" error code.
However, for a game graceful degradation might be quite okay, because nobody is going to die in the real world if a monster behaves a little less random.
I learned a lot about recent advances in pseudo-random number generators by reading your code and associated documentation, including some stuff that DEK has yet to incorporate into volume 2 of TAOCP. ;)
> How is it faster than std: It uses the fact that popcount of a uniformly distributed integer follows a binomial distribution. By rescaling that binomial distribution and adding some linear fill we can achieve a curve very similar to a proper normal distribution in just a few instructions. While that level of precision is not suitable for a general use, in instances where quality is not particularly important (gamedev, fuzzing) this is perhaps the fastest possible way of generating normally distributed floats.
- Faster uniform / normal distributions that produce same sequences on every platform
This is very useful if you want to reliably repeat simulations across platforms!
One question:
Isn't this returning a reference to a local variable? In my understanding, 'objects' is destroyed when rand_choice() returns.https://github.com/nessan/xoshiro
Documented at: https://nessan.github.io/xoshiro/
Handles the full family of these generators featuring arbitrary jump sizes, stream partitioning for parallel applications, and, like this library, a number of convenience sampling methods to shield the casual user from the complexities of using <random>.
Can be used with a companion `bit` library (https://github.com/nessan/bit) that performs efficient linear algebra and polynomial reduction over GF(2) for those that want to explore some of the mathematics behind these linear generators.
The algorithm is provably secure, so long as AES is secure. It is also backtracking resistant: an adversary with the current RNG state cannot step backwards.
On hardware with AES primitives, it's faster than MT, though slower than pcg64.
Science, neural networks, simulation, gaming, rendering, weather, nuclear, robotics, signal processing, engineering, finance, and more industries require fast rngs to get billions to trillions of them quickly.
Very few things actually need secure - only the things that need a secure endpoint, and most of those simply use the secure rng to do a private key transfer algo, after which there is no more rngs.
Use the right tool for the job. Widen your view of what things are used for. Etc.
There are quite a few applications:
- audio applications
- computer games
- simulations
- etc.
It can also be used to dither[1] the result when doing a final rendering, to improve the noise floor.
[1]: https://en.wikipedia.org/wiki/Noise_shaping
My guess is that yes, Randen is fast, but it is not quite as fast as PCG or other pseudo-random number generators.
Whether or not it is relevant, that's another story. I can not agree to your claim "there are vanishingly few use cases" for insecure random number generators.
That's not what a PRNG does. A PRNG produces a sequence of pseudo-random values (with a particular distribution) based on an initial seed value.
A hash function is stateless, a PRNG is not.
In a hash table, the hash function is not used to produce a series of random numbers, that's why it's a bit silly to call it a PRNG. Instead, the purpose is to reduce a (possibly larger) input value to a fixed size output value, often with the requirement that similar input values should result in very different output values to avoid clustering.
However, your hash table example is still useful as an analogy.
Did you guys get a chance compare with [1]. These seen to be the standard for high-performance not Crypto RNGs.
[1]: https://github.com/DEShawResearch/random123
No comments yet
arc4random has been provided by glibc 2.36 (2022), and is available on all the above-mentioned systems as well. If you don't want to make a syscall per request (outside Linux), just use arc4random; it'll be the fastest method available. musl libc lacks arc4random, unfortunately, but you can always ship a small wrapper.
Systems that support arc4random also support arc4random_uniform, which is a way to get an unbiased unsigned integer between 0 and N (up to 2^32-1). That's probably the most important reason to use the arc4random family.
I think neither are unbelievably slow. I dunno, take some measurements and see, maybe it suits you.
Not quite believable...