30

C++11 supports pseudo-random number generation through the <random> library.

I've seen multiple books which mention that it is quite expensive to keep constructing and destroying std::random_device, std::uniform_int_distribution<>, std::uniform_real_distribution<> objects, and they recommend to keep a single copy of these objects in the application.

Why is it expensive to create/destroy these objects? What exactly is meant by expensive here? Is it expensive in terms of execution speed, or executable size, or something else?

Can someone please provide some explanation?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Aamir
  • 1,974
  • 1
  • 14
  • 18
  • 5
    I've not heard `std::uniform_*_distribution` be called *expensive* to construct in the same way as `std::random_device` – Caleth Jun 10 '22 at 16:25
  • 2
    Performance implications aside, you'll thank yourself down the road for using one random object when the time comes to test your application and you need to be able to reliably reproduce runs. – Silvio Mayolo Jun 10 '22 at 20:24
  • It certainly depends upon your hardware. And your trust in the hardware supplied by your vendor. You might buy [hardware random generators](https://en.wikipedia.org/wiki/Hardware_random_number_generator). – Basile Starynkevitch Jun 11 '22 at 10:12
  • 1
    Yes, Aamir… what exactly does "expensive" mean to you? Is it expensive in terms of execution speed, executable size, or what? I'm trying to turn that round because as it was, you seemed to Asking everyone else to do your homework… In the context of this Question , what difference do you see between "random" and any other kind of device creation? – Robbie Goodwin Jun 11 '22 at 20:55
  • @RobbieGoodwin, Yes, device creation might be expensive in term of execution speed, but for random number generation on a normal desktop PC, I never thought that it require access to the hardware. I thought it was done purely in software. – Aamir Jun 14 '22 at 07:28

2 Answers2

31
  • std::random_device may be expensive to create. It may open a device feeding it data, and that takes some time. It can also be expensive to call because it requires entropy to deliver a truly random number, not a pseudo random number.
  • uniform_int_distribution is never expensive to create. It's designed to be cheap. It does have internal state though, so in extreme situations, keep the same distribution between calls if you can.
  • Pseudo-random number generators (PRNGs), like default_random_engine or mt19937, are usually semi-cheap to create, but expensive to seed. How expensive this is largely depends on the size of the state they keep internally, and what the seeding procedure is. For example, the std::mersenne_twister_engine in the standard library keeps a "large" (leaning towards "huge") state which makes it very expensive to create.

Upside:

  • You usually only use one temporary random_device and call it once to seed one PRNG. So, one expensive creation and call to random_device and one expensive seeding of a PRNG.
Cody Gray - on strike
  • 239,200
  • 50
  • 490
  • 574
Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
  • I remember watching a talk, with a code snippet where `uniform_int_distribution` was actually slower when constructed upfront instead of in place. Although I couldn't find it and don't remember the exact example code. – camel-cdr Jun 10 '22 at 16:29
  • @camel-cdr Oh, that sounds bad. Well, `uniform_int_distribution` does have _state_ so it's not totally without cost, but still, the design goal is for it to be cheap. If you use the same distribution over and over, you could make it `static`/`thread_local`. – Ted Lyngmo Jun 10 '22 at 16:30
  • So it is expensive in terms of execution speed? If we keep on creating and destroying random device, it might slow down our application? – Aamir Jun 10 '22 at 16:39
  • 4
    @Aamir Yes. **1)** It's very very rare to actually use `random_device` as a source for random numbers (other than for seeding the fast PRNG:s). **2)** If you _do_ use it (more than to seed PRNG:s), just create one instance. That goes for all random number generators. Just create one instance. – Ted Lyngmo Jun 10 '22 at 16:40
  • @TedLyngmo I meant it the other way around, as in it was slower when you create a variable with it and faster if you just create and use it together. every time – camel-cdr Jun 10 '22 at 17:00
  • @camel-cdr Ok, I think I see what you mean. Like `dist d(low,high); number = d(generator);` vs. `number = dist(low,high){}(generator);` ? If the second one results in more effective code, I suspect that the compiler wasn't able to optimize away the state. It may depend on how you write it how obvious it becomes to the compiler that you don't care about the state. – Ted Lyngmo Jun 10 '22 at 17:12
  • 6
    @TedLyngmo -- another reason for keeping the same object is precisely because it can have internal state, designed to provide the proper distribution. Throwing away that state means there is no connection between previous and subsequent generated values, so there is no guarantee that the results satisfy the distribution. – Pete Becker Jun 10 '22 at 17:22
  • 1
    @PeteBecker Yes exactly so. I wish the standard library came with distributions without state and with names that revealed what not having a state implies. The stateless distributions should be fairly easy to standardize too as opposed to those we have now. – Ted Lyngmo Jun 10 '22 at 17:25
  • @PeteBecker Point being: We can create and test a system using a standardized PRNG, but as soon as we involve one of the standard distributions, all bets are off. At least for testing purposes, a `not_so_uniform_int_distribution`, with a standardized algorithm would do good. – Ted Lyngmo Jun 10 '22 at 17:41
  • Hmm, I thought it was a typo, so I fixed it in the answer, but after reading the comments, it seems you intentionally spell it "PRNG:s". Why? That's not standard or correct, as far as I know. PRNG is the acronym, and if you want to make it plural, the standard convention I'm familiar with is to just append an "s". Sometimes, people will do an apostrophe-s, presumably because they want there to be some visual separation, but this is wrong (unless it's possessive). I've definitely never seen the colon used here. – Cody Gray - on strike Jun 11 '22 at 09:14
  • @CodyGray Oh, I'm Swedish and we use `:s` to "pluralize" acronyms (unless I'm mistaken about that too) :-) I'm happy with your edit. – Ted Lyngmo Jun 11 '22 at 09:16
  • Oh, wow! Makes complete sense, then. Thanks for replying with an explanation. I took several years of Norwegian and Old Norse back in university, so I am vaguely familiar with Scandinavian languages, but I never specifically learned the grammar of Swedish, so I was completely unfamiliar with this convention. – Cody Gray - on strike Jun 11 '22 at 12:07
  • @CodyGray You're welcome! :) Norwegian you say? Nice! We're not used to people learning our languages "for fun" since we have a very little market share... :) When it comes to the pluralizing thing in swedish, I think I have misunderstood that too. It _is_ used, but not in all situations I thought it should be used. – Ted Lyngmo Jun 11 '22 at 12:18
  • @PeteBecker A good random source does not have any (observable) connection between previous and subsequent generated values *by definition*. What you want to avoid is regenerating the same sequence multiple times by repeatedly creating a PRNG with the same seed. – cmaster - reinstate monica Jun 12 '22 at 00:16
  • @cmaster-reinstatemonica as I understand, that's true for a random generator, but explicitly not so for PRNGs. A good PRNG should always give you the same sequence for the same seed for reproducible generation. This is important in scientific computing, e.g. for end-to-end testing after changing code. – GeckoGeorge Jun 15 '22 at 10:25
  • @GeckoGeorge Ok, we have two things munched together here: 1) Any PRNG is deterministic and will generate the exact same "random" sequence given the same seed value. 2) *Without knowledge of the seed and the count of "random" values that have already been generated*, the resulting "random" sequence should still look 100% random, i.e. you should not be able to deduce anything about the next value even if you have observed some length of the "random" sequence. The internal state of the PRNG should remain a mystery to you. I have been talking about 2) while you seem to have been talking about 1). – cmaster - reinstate monica Jun 15 '22 at 16:57
23

The short answer is: It depends on the system and library implementation

Types of standard libraries

  • In a fairytale world where you have the most shitty standard library implementation imaginable, random_device is nothing but a superfluous wrapper around std::rand(). I'm not aware of such an implementation but someone may correct me on this

  • On a bare-metal system, e.g. an embedded microcontroller, random_device may interact directly with a hardware random number generator or a corresponding CPU feature. That may or may not require an expensive setup, e.g. to configure the hardware, open communication channels, or discard the first N samples

  • Most likely you are on a hosted platform, meaning a modern operating system with a hardware abstraction level. Let's consider this case for the rest of this post

Types of random_device

Your system may have a real hardware random number generator, for example the TPM module can act as one. See How does the Trusted Platform Module generate its true random numbers? Any access to this hardware has to go through the operating system, for example on Windows this would likely be a Cryptographic Service Provider (CSP).

Or your CPU may have some built in, such as Intel's rdrand and rdseed instruction. In this case a random_device that maps directly to these just has to discover that they are available and check that they are operational. rdrand for example can detect hardware failure at which point the implementation may provide a fallback. See What are the exhaustion characteristics of RDRAND on Ivy Bridge?

However, since these features may not be available, operating systems generally provide an entropy pool to generate random numbers. If these hardware features are available, your OS may use them to feed this pool or provide a fallback once the pool is exhausted. Your standard library will most likely just access this pool through an OS-specific API.

That is what random_device is on all mainstream library implementations at the moment: an access point to the OS facilities for random number generation. So what is the setup overhead of these?

System APIs

  • A traditional POSIX (UNIX) operating system provides random numbers through the pseudo-devices /dev/random and /dev/urandom. So the setup cost is the same as opening and closing this file. I assume this is what your book refers to

  • Since this API has some downsides, new APIs have popped up, such as Linux's getrandom. This one would not have any setup cost but it may fail if the kernel does not support it, at which point a good library may try /dev/urandom again

  • Windows libraries likely go through its crypto API. So either the old CSP API CryptGenRandom or the new BCryptGenRandom. Both require a handle to a service or algorithm provider. So this may be similar to the /dev/urandom approach

Consequences

In all these cases you will need at least one system call to access the RNG and these are significantly slower than normal function calls. See System calls overhead And even the rdrand instruction is around 150 cycles per instruction. See What is the latency and throughput of the RDRAND instruction on Ivy Bridge? Or worse, see RDRAND and RDSEED intrinsics on various compilers?

A library (or user) may be tempted to reduce the number of system calls by buffering a larger number random bytes, e.g. with buffered file I/O. This again would make opening and closing the random_device unwise, assuming this discards the buffer.

Additionally, the OS entropy pool has a limited size and can be exhausted, potentially causing the whole system to suffer (either by working with sub-par random numbers or by blocking until entropy is available again). This and the slow performance mean that you should not usually feed the random_device directly into a uniform_int_distribution or something like this. Instead use it to initialize a pseudo random number generator.

Of course this has exceptions. If your program needs just 64 random bytes over the course of its entire runtime, it would be foolish to draw the 2.5 kiB random state to initialize a mersenne twister, for example. Or if you need the best possible entropy, e.g. to generate cryptographic keys, then by all means, use it (or better yet, use a library for this; never reinvent crypto!)

Homer512
  • 9,144
  • 2
  • 8
  • 25
  • *random_device has to interact with the operating system* I'd rework this statement because it's not true. I know where you are going, that you need to leave the confines of C++ to get at some non-algorithmic deep magic, but there is no need for an OS to be involved. – user4581301 Jun 10 '22 at 16:32
  • 1
    @user4581301 in a hosted implementation I surely need OS support to access any actual device or pseudo-device, right? Unless I have a non-privileged CPU instruction to draw from a hardware RNG. – Homer512 Jun 10 '22 at 16:47
  • If the hardware exists, there is going to be a way to get at it with a bare metal system. Someone just has to write the code to do it. – user4581301 Jun 10 '22 at 17:03
  • 4
    @Homer512 -- the issue here is that `random_device` is not formally required to use a system-specific source of random numbers. It can be anything at all. You're right that it **should** get something from the OS, which, presumably, provides some sort of hardware support. But it's not actually required to; an implementation that calls `rand()` conforms to the standard. +1. – Pete Becker Jun 10 '22 at 17:19
  • 3
    @Homer512: x86 `rdrand` and [`rdseed`](https://www.felixcloutier.com/x86/rdseed) are precisely that: unprivileged instructions to pull "true" randomness from an on-chip entropy source. But most people consider it unwise to use directly in cryptographically sensitive cases, for possible backdoor / unverifiable black-box reasons. So mainstream C++ implementations don't use it directly even if you compile with `g++ -march=skylake` or something (a CPU which has rdrand and rdseed). – Peter Cordes Jun 11 '22 at 08:36
  • 1
    @PeteBecker: See my previous comment re: new-enough x86 not needing OS support for HW TRNG. https://www.intel.com/content/dam/develop/external/us/en/documents/drng-software-implementation-guide-2-1-185467.pdf is what Intel has to say about the internals, and https://en.wikipedia.org/wiki/RDRAND has some stuff including comments about security concerns. Of course a C++ implementation on a microcontroller might not have an OS, but might still have a HW RNG that can be accessed directly via an IO port. ISO C++ is not limited to hosted implementations. – Peter Cordes Jun 11 '22 at 09:14
  • 1
    @PeterCordes I substantially rewrote the answer to cover more ground.It's still a bit speculative on what a library *might* do but since OP didn't mention an OS, i think this is enough for the moment – Homer512 Jun 11 '22 at 10:06
  • 2
    Yup, nice edit. Note that `rdrand` is [much slower](https://stackoverflow.com/a/72265912/224132) on some CPUs with microcode updates that work around a potential info exposure, like thousands of cycles. (https://www.phoronix.com/scan.php?page=news_item&px=RdRand-3-Percent / https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/) But if a C++ implementation were to use it *directly*, constructing a `std::random_device` should have no overhead, same as if it optimistically expects to be able to use `getrandom`. – Peter Cordes Jun 11 '22 at 10:23
  • 5
    Just to be clear, mainstream `std::random_device` implementations *don't* use `rdrand` directly, and I wouldn't expect that in the future, for trust reasons as much as lack of guaranteed support. Although they *may* at some point use Linux `getrandom` (equivalent to reading from /dev/urandom) and thus not have any overhead to construct, only to actually use. (Or maybe some state like an `fd` that's initialized to `-1` to indicate that it should try `getrandom` before falling back to opening `/dev/urandom`.) – Peter Cordes Jun 11 '22 at 20:52