Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Show HN: Fast Random Library for C++17 (github.com/dmitribogdanov)
52 points by GeorgeHaldane 37 days ago | hide | past | favorite | 58 comments
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/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.




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();
    }


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.


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.


You mean creating the generator with a deterministic seed is shorter code than creating it with entropy? Well yes, because the entropy source is std::random_device so it's an extra line for an extra variable.

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.


> You mean creating the generator with a deterministic seed is shorter code than creating it with entropy?

No, it was more like: it's easy to write code that appears to fully seed a RNG with entropy, but in fact only seeds a tiny part of its state. Making it seed the whole lot, especially in a portable way, is surprisingly hard to get right. But I now can't find the article that explains this.

I seem to remember I had to use Boost.Random instead of the C++ standard library to do this in a real program, but this was a few years ago and the latest standard that was available in most implementations was C++11. Perhaps things have improved since.


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.


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. ;)


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.


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


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.)


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.


For a more full featured Xoshiro/Xoroshiro implementation see

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.


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.


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


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

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.


By far the vast majority of RNG calls in use need to be non-crypto. They are so many orders of magnitude too slow for so many uses that it's ludicrous to claim there are " vanishingly few use cases for non-crypto RNGs," unless you're trying to scare people into using your work.

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.


> They are so many orders of magnitude too slow for so many uses

On hardware with AES primitives this is simply false. Yes, embedded cases are different. There's some neat work on probabilistic computing that uses a xorshift RNG in hardware. These are specialized use cases that probably aren't your use case. Use the right tool for the job and try to be less condescending.


> On hardware with AES primitives this is simply false.

????

Do you even code these things?

I'm unaware of any CPU with AES hardware that lets you compute SIMD under AES, and AES instructions on every CPU I've used (quite a few) are again slower even for single data paths. Once you switch to PRNGs using SIMD that alone is an order of magnitude faster than any AES method. It's not hard to check (say via Agner Fog's CPU instruction tables if you want Intel/AMD) that no AES method is going to beat the fastest non-crypto RNGS. Or simply code and profile a few.

AES primitives are generally used for AES, and even for RNG, they are slow. No one is using crypto rand, even with AES, for all the uses I mentioned, which is orders of magnitude more rands than all the crypto in the world. Between physical simulation, video game uses, and no data centers and AI running PRNGs up the wazoo, all the crypto rand in the world is a tiny, tiny, fraction of the uses - and even there they're used a handful of times to set up a private key system with no more PRNGs needed (and this is why AES instructions were built into CPUs in the first place - for symmetric key encryption - no PRNGS there...)

And once you stop with the simple single rng call mentality, the world runs on GPUs and parallel HW where you get 1000 to ~20,000+ cores, all of which are doing non-crypto rand a lot for the uses above.

There's a reason places like CERN publish RNG algorithms suitable for their needs, which are often adopted in many industries that need actual high speed, high quality PRNGs, and none of them are crypto RNGs. Not one.

So go ahead and show me this fast AES PRNG that is as fast as the fastest non-crpyto RNGs. I'll wait......

I've worked in this space a long time, done DARPA HPC projects, written articles on PRNGs, designed specialized PRNGs, have a math PhD (my advisor did crypto, so I've done quite a bit of that), and have written numerical software for just about every application mentioned above. Read my posting history. I know what I'm taking about.

> Use the right tool for the job ....

Yes, indeed.

> ... and try to be less condescending.

Then don't make false claims, then double down with more. I'm not the only one calling you out on your claims in this thread; probably there's a reason.


> I think there are vanishingly few use cases for non-crypto RNGs.

There are quite a few applications:

- audio applications

- computer games

- simulations

- etc.


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.


Out of curiosity, how do audio applications use RNG?


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


Ah, ok. I was thinking playback. Noise makes total sense. Thanks!


I guess I should have pointed out the noise shaping could be useful if you're doing 16bit playback of a 24bit source, so possibly useful during playback as well.


So I'm a bit confused, the paper says "'Randen' ... outperforming ... PCG" but now you wrote "though slower than pcg64"? In the paper itself, PCG is faster but "these microbenchmark results are quite irrelevant in practice — which actual application repeatedly calls a random generator and ignores the results?" I wonder, was the paper peer-reviewed? (I'm not saying it should have been..., just wondering.)

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.


If you look inside Abseil it seems that the authors generally agree on performance. The default random in Abseil is Randen, but the faster variant the use of which is discouraged is PCG.


The paper doesn't seem peer reviewed or published. It doesn't show up as published anywhere on Google scholar, and papers that are published years later still reference the arxiv link, not a publication link. This is pretty strong evidence of not being reviewed or published.

You can check via: google scholar, search randen random number, note there is no version with a journal, click citations and look through the few articles mentioning it, you can see which of those are published, can see a few, not one has a journal ref to it.


I was citing the micro benchmarks because they provide a pessimistic comparison in favor of other RNGs. My recollection is that it appeared as a conference paper, but I'd need to ask the author.


> the micro benchmarks because they provide a pessimistic comparison in favor of other RNGs

Why would one claim they're fast, then simply fiddle with benchmarks so they find a place where they look fast?

When someone wants a fast RNG, they're not calling it 10 times per sec. They're hammering it for actual needs.


Every time you use a hash map you use a (PR)RNG. There are an abundant number of use cases for non-CS RNGs.


Well, when you use the Abseil hash maps the "random" number is actually a thread-local variable that monotonically increments, and the Abseil hash functions use static "random" data.


That would be a very strange hash map :) Could it be that you are confusing hash functions with PRNGs?


Why do you think they are different? That's what a hash function is--mapping input to outputs with a pseudo-random distribution. Different words for literally the same thing.


> That's what a hash function is--mapping input to outputs with a pseudo-random distribution

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.


When used as a hasher, the 'seed' is the input. When used as a PRNG tool, the seed is an incrementing counter or something. It's the same function though.


I see what you mean. You can use a hash function to build a PRNG, but the hash function itself it not a PRNG.

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.


A many hash tables use PRNG sequences for collision resolution by moving around to other buckets. That PRNG seed comes from the hash value. PRNGs are chosen for good uniform spread and repeatable sequence and speed.

The naive collision resolution ideas start like this: chained items (slow, memory costs), linear probing (results in clustering), quadratic probing (better, still has problems), double hashing (good), PRNG sequences with good properties (so any item hitting the same spot checks the same seq of overflow slots. One can alternate linear and PRNG or other combos.

Start with the basic wiki article https://en.wikipedia.org/wiki/Hash_table, check through many of the modern has table types linked from there.


You've made yourself susceptible to hash flooding.


I mean the only use case for cryptographically secure RNGs is cryptography. I can't think of non-crypto use cases that need it, but all of those need performance (and determinism is sometimes desirable!).


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


Std::minstd at 100pct and std::mt19997 at 105pct?!?

Not quite believable...


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


That seems to be linux/glibc specific.


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.


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.


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.


Linus merged it on July 24, 2024, so about a year I guess. Kernel is released ~8 weeks after the merge window, so I suppose September or so.

I think neither are unbelievably slow. I dunno, take some measurements and see, maybe it suits you.


[flagged]


> 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].


weirdly enough, the provided implementation of rand_float() actually generates numbers in the interval [0, 1).

I haven't read the implementation of _generate_canonical_generic(), but the following special case in generate_canonical() applies here:

  if constexpr (prng_is_bit_uniform && sizeof(T) == 4 && sizeof(generated_type) == 8) {
    return (static_cast<std::uint32_t>(gen()) >> exponent_bits_32) * mantissa_hex_32;
  }
which boils down to:

  return (static_cast<std::uint32_t>(gen()) >> 8) * 0x1.p-24;
that is, a number in the interval [0, 2^24) divided by 2^24.


Thank you for noticing! Turns out [0, 1] is an artifact of the old documentation carried back from the time where generic GCC / clang approach used to produce occasional 1's due to some issues in N4958 specification. This is fixed in a new commit.

For floats there are essentially 3 approaches that are selected based on the provided range & PRNG:

  1) Shift + multiply (like `(rng >> 11) * 0x1.0p-53`)
  2) "Low-high" from the paper by J. Doornik
  https://www.doornik.com/research/randomdouble.pdf
  3) Canonical GCC implementation
All of these generate values in [0, 1) range which is now reflected in the docs properly. For most actual cases 1st method is the one selected.


In this case I would suggest using the high bits of the RNG output when generating a float, since some generators have better entropy around the high bits.

So when you're generating floats with a 64-bit generator, instead of masking out the high bits with the static_cast, you may want to use the following:

  return (gen() >> 40) * 0x1.0p-24;


This article shows how to generate perfectly-distributed random floats: https://specbranch.com/posts/fp-rand/


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

[2] https://github.com/camel-cdr/cauldron/blob/a673553dd7925b0f1...


Downey published a (big-endian, SPARC) method in 2007:

https://allendowney.com/research/rand/

And Lemire in 2017 asked the question

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).


Now that I've actually looked at the "utl::random" code in the OP, I see that its UniformRealDistribution is a wrapper around std::generate_canonical, so the juicy bits about turning a random into into a random float are not exposed here at all. But the utl::random code does include an pointer* to an informative C++ working group note.

* https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p09...


Thanks for the additional pointers!

I like the idea of looking at the histogram of exponents: incrementing (by 1) the exponent doubles the width of the interval so should double the number of hits. Conversely the histogram of the significand (or any subset of its bits) should be flat.


Beebe publishes a lengthy bibliography.

https://www.netlib.org/tex/bib/prng.pdf

758 pages and counting....


Lengthy indeed. Do you have advice for how to find amongst these the first paper on correctly sampling [0,1) with real-world floating point?




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: