8 ms·

Show HN: Fast Random Library for C++17

52 points by GeorgeHaldane 1y ago

Morning HN. 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 Effectively all of this gets us 2x-8x speedups on many workloads while producing even better statistical quality. 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/module_random.md 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.

jeffbee 1y ago
This looks quite helpful. An especially useful feature is to have a stable uniform int distribution, even if it is just a copy of the GNU one. It is incredibly annoying that the standard dictates the output of the generators, but leaves the output of the distributions unspecified.
fluffyllemon 1y ago
How does this compare with Abseil's random library? https://abseil.io/docs/cpp/guides/random https://abseil.io/docs/cpp/guides/random
- bhickey 1y ago
  This library appears to be insecure by default. I think there are vanishingly few use cases for non-crypto RNGs. We made absl random secure by default using randen: https://arxiv.org/abs/1810.02227 https://arxiv.org/abs/1810.02227 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.
  - spacechild1 1y ago
    > I think there are vanishingly few use cases for non-crypto RNGs. There are quite a few applications: - audio applications - computer games - simulations - etc.
    - bhickey 1y ago
      Years ago a player figured out how to decode the RNG state in dungeon crawl. This allowed them to essentially God mode the game because they could determine when a monster would land a hit.
    - Night_Thastus 1y ago
      Out of curiosity, how do audio applications use RNG?
      - magicalhippo 1y ago
        Noise. Either directly as a source, which is then filtered to produce say a cymbal sound, or indirectly by creating timing variance, ie notes not playing exactly at the beat each time, which makes things sound less artificial and more pleasing. 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 https://en.wikipedia.org/wiki/Noise_shaping
pantalaimon 1y ago
Shouldn't getrandom() be plenty fast these days?
- ksherlock 1y ago
  That seems to be linux/glibc specific.
  - deleted 1y ago
    [deleted]
- zx2c4 1y ago
  If you don't need "predictable randomness", like for repeatable statistical simulations, then absolutely, you should only use getrandom(). On recent Linux, this is implemented in the vDSO and is super fast. Few excuses now to use anything different.
  - wahern 1y ago
    The portable API is getentropy, which glibc provides as a simple wrapper around getrandom. getentropy was added to POSIX, and is also available on most modern unix systems, including FreeBSD, Illumos, NetBSD, macOS, OpenBSD, and Solaris. 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.
  - jeffbee 1y ago
    vDSO getrandom has been in the kernel for what, two weeks? And it is only "super fast" compared to the unbelievably slow full syscall. Compared to PCG it is like watching rocks grow.
    - 1y ago
zx2c4 1y ago
Careful with the "chacha csprng" when the seed from the seed() function appears to be 32 or 64 bits. That's not enough for the cs part. (Also the output stream appears to wrap after 2**32 blocks. Could make this larger.)
OskarS 1y ago
I think it looks great! Might be using this in a future project. 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: int rand() { thread_local generator my_generator { seed_with_entropy() }; return my_generator.rand(); }
- quietbritishjim 1y ago
  I forget the details off hand, but I thought that C++ notoriously fails to include much entropy in the generator unless you go through some complex multiline dance that forces the seed sequence to actually include it.
  - SiempreViernes 1y ago
    I think Oskars point is that if you say "I just want a random number, I don't care how" you can't very well be upset the seed is bad as that would be caring.
  - OskarS 1y ago
    I’m assuming here that ”generator” has a decent enough constructor that seeds it properly. If it doesn’t, and you have to cycle it a few times to ”warm it up”, it’s not much more complicated, just factor out the initialization code into a function or lambda and use that to initialize the thread_local.
  - 1y ago
joiguru 1y ago
Very interesting work! 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 https://github.com/DEShawResearch/random123
spacechild1 1y ago
This looks nice! One thing I find particularly noteworthy: - 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: template<class T> constexpr T& rand_choice(std::initializer_list<T> objects) noexcept; Isn't this returning a reference to a local variable? In my understanding, 'objects' is destroyed when rand_choice() returns.
- GeorgeHaldane 1y ago
  Thanks, that is indeed the case when list doesn't consist of literals, fixed in the new commit.
j_not_j 1y ago
[flagged]
- cornstalks 1y ago
  > If it is not [0,1) then it's not useful. I can understand [0, 1) being useful in some use cases but saying it's entirely useless is a bit dramatic, don't you think? I've certainly had uses for [0, 1].
- HeliumHydride 1y ago
  This article shows how to generate perfectly-distributed random floats: https://specbranch.com/posts/fp-rand/ https://specbranch.com/posts/fp-rand/
  - glkindlmann 1y ago
    That page ends with "This is the first efficient algorithm for generating random uniform floating-point numbers that can access the entire range of floating point outputs with correct probabilities". I am very skeptical. The same basic idea is described here [1] (though without any pretty pictures, but with a link to working code), and I know others have implemented the same insight [2]. This seems like the kind of thing that is reinvented every time some who cares about random numbers learns how IEEE 754 works. [1] http://mumble.net/~campbell/2014/04/28/uniform-random-float http://mumble.net/~campbell/2014/04/28/uniform-random-float [2] https://github.com/camel-cdr/cauldron/blob/a673553dd7925b0f103c81f19a7ff6f2e509eada/cauldron/random.h#L1391C8-L1391C33 https://github.com/camel-cdr/cauldron/blob/a673553dd7925b0f1...
    - j_not_j 1y ago
      Downey published a (big-endian, SPARC) method in 2007: https://allendowney.com/research/rand/ https://allendowney.com/research/rand/ And Lemire in 2017 asked the question https://lemire.me/blog/2017/02/28/how-many-floating-point-numbers-are-in-the-interval-01/ https://lemire.me/blog/2017/02/28/how-many-floating-point-nu... The basic approach: collect top 60 bits of a 64-bit PRNG. (Assume the LSBs are corrupt or zero or nonrandom). Set exponent zero. If the top mantissa bit is zero, shift left, subtract one from exponent. Repeat. When you run out of bits, collect another PRNG from your generator and resume until you have 56 bits of mantissa. When done, your floating-point PRNG is 2^exponent * mantissa. My short explanation: Suppose you want a random distance. Multiplying a PR integer is the same as selecting a random tile in the distance, and measuring the distance to the (far) edge of the tile. This is the multiply method. But if you want a real-valued distance even for very near distances, you need to scale your random number and ensure you have random bits throughout the mantissa. So reduce the exponent for every leading zero in your PR integer and shift. Add more bits if needed. Test: the histogram of exponents for a large-enough set of samples is linear, give or take. Very small floating numbers (less than say 1/32768) are 1/16 as likely as numbers in [0.5,1).
deleted 1y ago
[deleted]
jll29 1y ago
Thanks for sharing, this is a very well-written and useful set of libraries, not just random, but also the other sub-libraries of utl. 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. ;)
nzzn 1y ago
For a more full featured Xoshiro/Xoroshiro implementation see https://github.com/nessan/xoshiro https://github.com/nessan/xoshiro Documented at: https://nessan.github.io/xoshiro/ 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 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.
zX41ZdbW 1y ago
Nice trick: > 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.
Iwan-Zotow 1y ago
Std::minstd at 100pct and std::mt19997 at 105pct?!? Not quite believable...

52 points by GeorgeHaldane 1y ago

jeffbee 1y ago

This looks quite helpful. An especially useful feature is to have a stable uniform int distribution, even if it is just a copy of the GNU one. It is incredibly annoying that the standard dictates the output of the generators, but leaves the output of the distributions unspecified.

fluffyllemon 1y ago

How does this compare with Abseil's random library? https://abseil.io/docs/cpp/guides/random https://abseil.io/docs/cpp/guides/random

bhickey 1y ago
This library appears to be insecure by default. I think there are vanishingly few use cases for non-crypto RNGs. We made absl random secure by default using randen: https://arxiv.org/abs/1810.02227 https://arxiv.org/abs/1810.02227 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.
- spacechild1 1y ago
  > I think there are vanishingly few use cases for non-crypto RNGs. There are quite a few applications: - audio applications - computer games - simulations - etc.
  - bhickey 1y ago
    Years ago a player figured out how to decode the RNG state in dungeon crawl. This allowed them to essentially God mode the game because they could determine when a monster would land a hit.
  - Night_Thastus 1y ago
    Out of curiosity, how do audio applications use RNG?
    - magicalhippo 1y ago
      Noise. Either directly as a source, which is then filtered to produce say a cymbal sound, or indirectly by creating timing variance, ie notes not playing exactly at the beat each time, which makes things sound less artificial and more pleasing. 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 https://en.wikipedia.org/wiki/Noise_shaping

pantalaimon 1y ago

Shouldn't getrandom() be plenty fast these days?

ksherlock 1y ago
That seems to be linux/glibc specific.
- deleted 1y ago
  [deleted]
zx2c4 1y ago
If you don't need "predictable randomness", like for repeatable statistical simulations, then absolutely, you should only use getrandom(). On recent Linux, this is implemented in the vDSO and is super fast. Few excuses now to use anything different.
- wahern 1y ago
  The portable API is getentropy, which glibc provides as a simple wrapper around getrandom. getentropy was added to POSIX, and is also available on most modern unix systems, including FreeBSD, Illumos, NetBSD, macOS, OpenBSD, and Solaris. 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.
- jeffbee 1y ago
  vDSO getrandom has been in the kernel for what, two weeks? And it is only "super fast" compared to the unbelievably slow full syscall. Compared to PCG it is like watching rocks grow.
  - 1y ago

zx2c4 1y ago

Careful with the "chacha csprng" when the seed from the seed() function appears to be 32 or 64 bits. That's not enough for the cs part. (Also the output stream appears to wrap after 2**32 blocks. Could make this larger.)

OskarS 1y ago

I think it looks great! Might be using this in a future project. 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: int rand() { thread_local generator my_generator { seed_with_entropy() }; return my_generator.rand(); }

quietbritishjim 1y ago
I forget the details off hand, but I thought that C++ notoriously fails to include much entropy in the generator unless you go through some complex multiline dance that forces the seed sequence to actually include it.
- SiempreViernes 1y ago
  I think Oskars point is that if you say "I just want a random number, I don't care how" you can't very well be upset the seed is bad as that would be caring.
- OskarS 1y ago
  I’m assuming here that ”generator” has a decent enough constructor that seeds it properly. If it doesn’t, and you have to cycle it a few times to ”warm it up”, it’s not much more complicated, just factor out the initialization code into a function or lambda and use that to initialize the thread_local.
- 1y ago

joiguru 1y ago

Very interesting work! 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 https://github.com/DEShawResearch/random123

spacechild1 1y ago

This looks nice! One thing I find particularly noteworthy: - 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: template<class T> constexpr T& rand_choice(std::initializer_list<T> objects) noexcept; Isn't this returning a reference to a local variable? In my understanding, 'objects' is destroyed when rand_choice() returns.

GeorgeHaldane 1y ago
Thanks, that is indeed the case when list doesn't consist of literals, fixed in the new commit.

j_not_j 1y ago

[flagged]

cornstalks 1y ago
> If it is not [0,1) then it's not useful. I can understand [0, 1) being useful in some use cases but saying it's entirely useless is a bit dramatic, don't you think? I've certainly had uses for [0, 1].
HeliumHydride 1y ago
This article shows how to generate perfectly-distributed random floats: https://specbranch.com/posts/fp-rand/ https://specbranch.com/posts/fp-rand/
- glkindlmann 1y ago
  That page ends with "This is the first efficient algorithm for generating random uniform floating-point numbers that can access the entire range of floating point outputs with correct probabilities". I am very skeptical. The same basic idea is described here [1] (though without any pretty pictures, but with a link to working code), and I know others have implemented the same insight [2]. This seems like the kind of thing that is reinvented every time some who cares about random numbers learns how IEEE 754 works. [1] http://mumble.net/~campbell/2014/04/28/uniform-random-float http://mumble.net/~campbell/2014/04/28/uniform-random-float [2] https://github.com/camel-cdr/cauldron/blob/a673553dd7925b0f103c81f19a7ff6f2e509eada/cauldron/random.h#L1391C8-L1391C33 https://github.com/camel-cdr/cauldron/blob/a673553dd7925b0f1...
  - j_not_j 1y ago
    Downey published a (big-endian, SPARC) method in 2007: https://allendowney.com/research/rand/ https://allendowney.com/research/rand/ And Lemire in 2017 asked the question https://lemire.me/blog/2017/02/28/how-many-floating-point-numbers-are-in-the-interval-01/ https://lemire.me/blog/2017/02/28/how-many-floating-point-nu... The basic approach: collect top 60 bits of a 64-bit PRNG. (Assume the LSBs are corrupt or zero or nonrandom). Set exponent zero. If the top mantissa bit is zero, shift left, subtract one from exponent. Repeat. When you run out of bits, collect another PRNG from your generator and resume until you have 56 bits of mantissa. When done, your floating-point PRNG is 2^exponent * mantissa. My short explanation: Suppose you want a random distance. Multiplying a PR integer is the same as selecting a random tile in the distance, and measuring the distance to the (far) edge of the tile. This is the multiply method. But if you want a real-valued distance even for very near distances, you need to scale your random number and ensure you have random bits throughout the mantissa. So reduce the exponent for every leading zero in your PR integer and shift. Add more bits if needed. Test: the histogram of exponents for a large-enough set of samples is linear, give or take. Very small floating numbers (less than say 1/32768) are 1/16 as likely as numbers in [0.5,1).

deleted 1y ago

[deleted]

jll29 1y ago

Thanks for sharing, this is a very well-written and useful set of libraries, not just random, but also the other sub-libraries of utl. 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. ;)

nzzn 1y ago

For a more full featured Xoshiro/Xoroshiro implementation see https://github.com/nessan/xoshiro https://github.com/nessan/xoshiro Documented at: https://nessan.github.io/xoshiro/ 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 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.

zX41ZdbW 1y ago

Nice trick: > 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.

Iwan-Zotow 1y ago

Std::minstd at 100pct and std::mt19997 at 105pct?!? Not quite believable...