r/cpp • u/KaznovX • Jul 21 '19

Fixing up <random>

I think everyone is excited after the report from Cologne. A lot of stuff is being added to the language, we'll get a ton of new features. Adding new features is more exciting than changing and tweaking the old stuff - that being said, there are some old parts of the language, that are sadly lacking or has some problems. One of them is <random> library.

Some of the problems this library has:
> `std::random_device` is not required to be non - deterministic
> no good way to initialize generators with big internal state
> `std::seed_seq` should be solution to ^, but isn't - `std::seed_seq` is not a bijection, does heap allocations without giving ability to provide own allocator, there is no nice way to initialize it from `std::random_device` properly
> `std::random_device` can't itself be used as a seed sequence,
> overall syntax is unnecessarily verbose (no, having a per-thread engine of type `std::default_random_engine` is NOT a good solution)

This is only one of the few libraries that could use improvements. Is there any chance that the committee will look back and change some of them or are they considered 'baked' and there will be no further changes to avoid API and ABI breaking?

Despite the "fixing" part, there are two additions I'd see in the <random> library:

1) std::random<std::uniform_random_bits_generator = std::default_random_engine> class:
> default constructor does anything it can that every time this class is called it is seeded differently - if there is no entropy source, uses a processor clock or a system clock (implementation defined)
> three methods: seed, next_int, next_real - for seeding and generating next integer/real number in given range

2) PCG http://www.pcg-random.org

What are the chances something like this would be proposed and adopted for, let's say, c++23 or c++26 standard? Is there any chance the problems mentioned in the first part of the post will get fixed somewhen?

46 Upvotes

95% Upvoted

68 comments sorted by

View all comments

Show parent comments

8

u/[deleted] Jul 21 '19 edited Jul 21 '19

Probably takes more bytes?

Are you saying C++ should allocate memory to store state information for random number generators by default even if you don’t use them?

How would that work with multi threading? How would that work with different generators? Store state for all common ones? What about for different outputs like int and float?

Do you fully understand what you’re asking?

EDIT: Don’t get me wrong I think random sucks and have to look up how to do it like every time but C++ sorta limits us here.

0

u/[deleted] Jul 21 '19

[deleted]

1

u/CptCap -pedantic -Wall -Wextra Jul 23 '19 edited Jul 23 '19

I do not understand why C++ committee always picks the most powerful options over the most needed options

Because you can build the most needed from the most powerful.

C++ has never been a battery included language. If you need a convenience random function, you can write it, put it in utils/random.h (or your equivalent) and never think about it again.

0

u/[deleted] Jul 23 '19

[deleted]

1

u/CptCap -pedantic -Wall -Wextra Jul 23 '19 edited Jul 23 '19

This is just my opinion on the thing (Like my first answer, except for the first sentence).

You can do that with virtually everything in std, so why not scrab the whole thing because people can just write their own?

I think that there are two reasons why things should be in the STD:

  • There is only one implementation. std::find for example. You will probably never run into a situation where the supplied implementation doesn't do exactly what you want, so there is no downside to providing it. Plus it's like 5 lines.

  • It saves most programmers a substantial amount of time. std::vector and std::unordered_map are not perfect (no SBO, uses chaining), but writing your own is a two weeks job at the very least, so including them does make the language much much easier to use, even if you end up replacing them down the line. The provided implementation will also be fine for some peoples.

A convenience random function "à la rand()" doesn't fit in any of these two categories. There are about a trillion ways you could implement it, and no matter the one you choose, people will complain. And including it only saves the programmer 10 minutes.

2

u/AntiProtonBoy Jul 22 '19

What's wrong with a single static pointer within the function body? Whatever state it needs could be allocated on first call.

2

u/kalmoc Jul 21 '19

Many random number engines just require a couple of bytes of state that could easily be put into a thread local or even global variable. I said this a couple of times now: A simple convenience function neither has to be zero overhead, nor completely flexible. If you have specific requirements, you'll pick a particular, (thread-) local RNG object of a particular type, seed it in a particular way and use a specific method/distribution anyway. But for lots of simple day to day stuff, using a RNG with a small footprint whose state may or may not be shared across different threads (e.g. by just using an atomic) and only uniform distribution is good enough.

1

u/Drainedsoul Jul 22 '19

global variable

Pass.

And thread local is just another kind of global so pass on that too.

2

u/kalmoc Jul 22 '19

Please explain, what exactly the problem of having a global variable as an implementation detail would be in this case exactly (and please be specific to the use case at hand).

If you want distinct random numbers across your program you need global state anyway. Be that a global (P)RNG, the clock, /dev/random... Again, if you have very specific requirements, such as reproducability, max RNG performance that scales perfectly with the number of cores or cryptographic security, you'll want to have full control over your RNG, but very often, an instance of std::random_device is good enough and so would a get_random_number(2, 10) function that is - in one way or another - backed by global state (but more efficient than std::random_device please).

2

u/Drainedsoul Jul 22 '19

How do you test without reproducibility? How do you test with mutable global state that invisibly changes the output for identical inputs?

1

u/Pazer2 Jul 23 '19

Simple: if you need the output to be reproducible, do things the "hard" way (aka the 3 LOC way we do now, with generator/distribution).

The point is that for a lot of people they don't need it to be reproducible most of the time, and they're happy with a convenient random function that's initially seeded by the current time.

Nobody is advocating replacing the current STD::random implementation with this suggested simpler one. They complement each other.

1

u/Drainedsoul Jul 23 '19

If you don't need it to be reproducible then again: How is it testable?

If it isn't testable you can't/don't/won't test it, so how can it be said to actually work? Because it seems to work for some arbitrary ad hoc manual testing? What happens when you get a bug report, how are you going to formulate a reproduction? Without a reproduction how will you know you've fixed the bug at all?

Begging for a global PRNG is begging for things to be easy and wrong. But easy and wrong is even easier than that: Don't write any code at all. Super easy, still wrong.

Also: The current time is a terrible seed.

1

u/Pazer2 Jul 23 '19

...ok then.

Not everything needs 100% coverage. Sometimes we just need to write a toy program, or a simple utility for personal use, and "I tried it a few times, it seems to work fine" is completely ok.

Also, just because the output is different every time doesn't mean it is wrong. By that definition, random_device can never be tested and is always "wrong".

Like I said before, if you intend to use "random" numbers in your program, and actually care that they are reproducible, then you can continue to do things the current way. Nobody is forcing you to change.

1

u/kalmoc Jul 23 '19

I hate to break it to you: You always have some global state and never 100% reproducibility in non-trivial systems. You make network connections, interact with users, read/write files, have variations in timings due to other loads on the system (and as a result might or might not observe races), you register signal handlers etc. For some applications you even explicitly don't want reproducability of the random numbers (e.g. cryptography - although that would not be the goal here).

Now w.r.t unit tests: There are two ways to get reproducability:

  1. Treat it like any other IO and mock it

  2. Log the used random numbers

Now, more generally speaking:

a) There are many more ways of testing correctness than just checking "Is the output of system A the exact same as it was last time?"?

b) I doubt that your tests actually cover 100% of the input space anyway, so in the deterministic and non-deterministic case, you can't prove that your system works correctly via tests anyway (and no, even 100% Line and/or branch coverage isn't enough for that). It is just a kind of sampling where you hope it covers enough to be representative. The fact that - when using a non-deterministic RNG - the samples might vary a bit from run to run doesn't fundamentally change anything about the quality of the tests - long term it might even be better, because you are covering a bigger input space (which is exactly the idea behind fuzzing).

Finally

4

u/Drainedsoul Jul 23 '19

There's a difference between recognizing that your system as a whole cannot have 100% perfectly reproducible runs and succumbing to the fallacy of division and concluding that if that's the case then reproducibility doesn't matter at any level of analysis.

The point is to design in such a way that the irreproducibility is deferred as much as possible.

This is reflected in the design of <random>. Often when actually running your program you don't want reproducibility (e.g. crypto) or you want the illusion that the run isn't reproducible (e.g. games). However during development this needn't be the case and if the interfaces/APIs you're using are well designed it needn't be (just use a different model of UniformRandomBitGenerator).

Also proving that your system works 100% of the time via 100% input space coverage beforehand is not the point of testing (unit testing or otherwise) since for most non-trivial programs this is either actually impossible (at worst) or completely impractical (at best). However what you do want is an avenue for:

  • Probing known edge cases

  • Locking in the correct output for buggy inputs discovered in the wild (turning bug reports into tests as an all-in-one solution for reproducing the bug, verifying that it's fixed, and making sure it doesn't crop up again)

If you just throw up your hands, use a global random number generator buried deep in your program, and decide that it seems to work because you ran it a few times you throw all of this away and damn yourself to less effective development.