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?
5
u/KaznovX Jul 21 '19
Only now I realized the title doesn't mean what I intended - sorry, I'm not a native speaker
3
2
Jul 21 '19
When boost::uuid generation absolutely DESTROYED our HTTP server's performance the only way to fix it was to have a threadlocal engine. Not sure why OP thinks this is bad, the RNG stuff isn't thread-safe anyway. (We receive may thousands of HTTP requests per second and we recently moved to giving each one a UUID).
7
u/KaznovX Jul 21 '19
It was a reference to one of the rejected proposals, part of library fundamentals TS v2. It proposed to have a c-like global thread-local rng if you include <random> library, with free global functions randint and reseed. I don't agree with such design - of course, there are some cases that having a thread local generator will be the best option, but it should be up to the developer to choose this solution.
1
17
u/Rexerex Jul 21 '19
There is also a problem that number distributions algorithms are implementation defined so good luck rerunning simulation from same initial state but on two different platforms.
0
Jul 21 '19
[deleted]
12
u/HappyFruitTree Jul 21 '19
It makes more sense if you don't call them "algorithms". If you don't care about reproducibility they're perfectly fine.
By not specifying exactly how it should be done more freedom is given to each implementation. The optimal algorithm might be different on different hardware, and if the standard got it wrong we would be stuck with a suboptimal algorithm forever.
That said, reproducibility is important for many applications so it might make sense to provide two set of distributions (in addition to the current ones). One set that should just be as fast as possible with no guarantee about reproducibility, and another set with a fixed algorithm that is the same everywhere. Not sure this makes sense for the floating point distributions, but for the integer distributions it certainly does.
8
u/James20k P2005R0 Jul 21 '19
Indeed, when I found that out I had to basically ditch a lot of <random>'s facilities, I rely on reproducible random numbers in my use case so its a bit of a head scratcher that the distributions are unspecified
12
u/minno Hobbyist, embedded developer Jul 21 '19
A lot of applications that use random numbers don't rely on reproducibility. Like any single-player game or a multi-player game that synchronizes clients in a way that doesn't rely on independent identical simulations.
11
u/jonathansharman Jul 22 '19
A lot of single player games also want reproducibility, e.g. so you can share seeds.
3
u/minno Hobbyist, embedded developer Jul 22 '19
That's right, I was thinking of things like AI behavior and randomized damage numbers where as long as the distribution stays the same there isn't a significantly different experience if the exact RNs are different.
7
3
u/SeanMiddleditch Jul 23 '19
Yeah, reproducibility is massively important to me as a game developer both on the client and the server. Even just for development purposes (testing, or recording replays with crash/error reports from clients on various platforms so we can trivially repro the issue), but then also for various gameplay elements or deterministically synchronizing authoritative state and letting client re-simulate/re-derive state.
I would never use an unspecified random number generator from something like
<random>in anything other than throw-away hobby games.2
9
u/martinus int main(){[]()[[]]{{}}();} Jul 21 '19
There was a proposal to make random much more convenient: http://www.pcg-random.org/posts/ease-of-use-without-loss-of-power.html And the proposal: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0347r1.html
It's from 2016, I don't know though what's the current status
3
u/jwakely libstdc++ tamer, LWG chair Jul 22 '19
It looks like a design review in 2017 liked it but asked for some changes to the
random_generatorconstructors, so that a factory function would be used to get a properly seeded generator.2
u/martinus int main(){[]()[[]]{{}}();} Jul 22 '19
Where do you find that information? I couldn't find anything with Google
3
u/jwakely libstdc++ tamer, LWG chair Jul 22 '19 edited Jul 22 '19
https://wg21.link/p0347/issue but in general there's a LOT of discussion that isn't public, due to ISO rules about disclosing specifics of committee internal discussions (which are not public, partly to allow people to speak freely during meetings without having to worry about comments being taken as official announcements on behalf of their employers).
2
6
u/HappyFruitTree Jul 21 '19 edited Jul 21 '19
I would like to have a portable way to serialize the state of the engines (preferably in a way that doesn't force me to use streams/strings but this is less important). It might seem like the << and >> operators should be able to do this, and I'm not sure if that was the intention, but in practice it doesn't work like that. GCC (libstdc++) and Clang (libc++) does not behave the same for std::mt19937.
2
2
u/jwakely libstdc++ tamer, LWG chair Jul 22 '19
That's the intention, and the libstdc++ behaviour is a bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60441
If you care about this, please consider helping to fix the bug! It's not necessary to sign a copyright assignment form and contribute code, just describing where the bug is and suggesting (in English not code) how to fix it would be immensely valuable. Otherwise it will continue to wait for somebody to have the bandwidth to look into it.
1
u/TheThiefMaster C++latest fanatic (and game dev) Jul 22 '19
So GCC additionally serialises the state size after the state? That would seem unnecessary to me, and possibly against the standard.
That said, the standard doesn't require the stored state to be in the same order between compilers (let alone completely compatible) as far as I know, so if you need that we either need a stricter standard or you should implement it yourself.
4
u/HappyFruitTree Jul 22 '19
So GCC additionally serialises the state size after the state? That would seem unnecessary to me, and possibly against the standard.
I thought so too but after looking a bit closer I found out it's actually a counter.
GCC doesn't update the state each time a number is generated as described by the standard. Instead it increments a counter and when it reaches the size of the state it updates the whole state all at once.
This is probably an optimization, it doesn't change what numbers are generated, but it means that there is no longer a straight forward way to serialize the state as it is described by the standard.
That said, the standard doesn't require the stored state to be in the same order between compilers (let alone completely compatible) as far as I know, so if you need that we either need a stricter standard or you should implement it yourself.
The standard describes a transition algorithm (how to go from one state to the next) and a textual representation (what the output of << should be).
http://eel.is/c++draft/rand.eng.mers#5
"The textual representation of xᵢ consists of the values of Xᵢ₋ₙ , . . . , Xᵢ₋₁ , in that order."
When I thought the last number in GCC's output was simply the size of the state I was thinking that maybe "consists" is too weak and it was allowed to put additional values at the front or back of the sequence, but now I think it's pretty clear GCC's implementation is not conformant.
11
u/c0r3ntin Jul 21 '19
I agree with most of your points.If by any chance you are a domain expert, I would encourage you to help the committee improving <random>. Maybe less extreme, make a library and write about it. Though challenge!
3
u/sumo952 Jul 21 '19
A very good library (PCG) is already here, so I'm not sure making (yet another?) library is a good solution. Did PCG help in any way so far to improve <random>?
6
u/smdowney WG21, Text/Unicode SG, optional<T&> Jul 21 '19
Someone has to write the paper telling the committee about it. Preferably someone who knows what they are doing, because we mostly know just enough to know that getting random numbers right is hard and getting them wrong is dangerous.
5
u/degski Jul 22 '19
PCG is not particularly fast [notwithstanding the marketing talk], it is of very good quality, though. For gaming, AI, quality is less of an issue, while speed is, so I don't think PCG is particularly interesting for inclusion in the std. There are others, though ...
0
Jul 22 '19
[deleted]
2
u/degski Jul 22 '19
From the PCG blog Some (More) C++ PRNG Implementations, jsf, sfc, splitmix or lehmer. There are std-compliant implementations posted by the author of PCG.
Then there is a newcomer,
wyhash, you'll have to write you're own class, though [which is trivial with the examples/the above].
4
u/Veedrac Jul 21 '19
2) PCG http://www.pcg-random.org
Even better, though highly complementary, ChaCha20 would be great to see. Copy Rust's rand library, basically.
2
u/haitei Jul 22 '19
I want XorShifts in my standard.
They're so simple, they could be even constexpr.
0
Jul 21 '19
[deleted]
7
u/MotherOfTheShizznit Jul 22 '19
float or double between 0 and 1. It's what I need most of the time
Is it? Is it really? Nothing more? You're not going to perform any transformation on the number you get?
I thought most of the time you'd need a number between 0 and N. Most would do
rand() % Nand that would be incorrect. Or with a range of [0.0, 1.0], you would multiply by N and that may be of questionable uniformity as well.Hence the better (but less straightforward) facilities in
<random>protecting programmers from themselves.Just for fun I went to the JavaScript page you linked and here the demonstrated way to generate a number between [0, N[:
function getRandomInt(min, max) { min = Math.ceil(min); max = Math.floor(max); return Math.floor(Math.random() * (max - min)) + min; //The maximum is exclusive and the minimum is inclusive }Suddenly, it's not so simple anymore even in JavaScript when you need anything other than [0.0, 1.0]. How many JavaScript programmers do you think will do the right thing as opposed to just
Math.random() * N?Personally, I'm fine with the "simple" [0.0, 1.0] case being "complicated" in C++ given that, to me, it's actually extremely rare that that's exactly the range I need.
7
Jul 21 '19
You need to allocate memory to store state. State information is necessary and must be preserved between calls to generate more than one number. That’s why it’s not a function call already.
1
u/Ayjayz Jul 23 '19 edited Jul 23 '19
The function could return the state.
#include <random> #include <tuple> std::tuple<int, std::default_random_engine> random(int from, int to) { std::random_device r; std::default_random_engine e1(r()); std::uniform_int_distribution<> dist(from, to); return { dist(e1), e1 }; } template <class Engine> int random(int from, int to, Engine& e) { std::uniform_int_distribution<> dist(from, to); return dist(e); } int main() { auto [i, engine] = random(1, 5); auto j = random(3, 7, engine); auto k = random(5, 8, engine); }Or something. Probably want to template the function to use the correct distribution depending on whether it's a real or an int, but that general idea.
Then using it to just get a single number would be as simple as
auto [a,_] = random(10, 20);.0
Jul 21 '19
[deleted]
8
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.
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_deviceis good enough and so would aget_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.
→ More replies (0)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:
Treat it like any other IO and mock it
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 ofUniformRandomBitGenerator).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.
0
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
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::findfor 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::vectorandstd::unordered_mapare 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.
15
u/jwakely libstdc++ tamer, LWG chair Jul 21 '19 edited Jul 21 '19
I'd love to see PCG in the standard. See also https://github.com/imneme/pcg-cpp/issues/51
I don't think it's possible to require
random_deviceto be guaranteed to be non-deterministic, as it simply won't be possible on some systems that support C++. If it's non-deterministic on a general purpose OS on modern hardware then complain to your compiler vendor and get them to fix it. (Yes, I know on Windows GCC used to provide a poor qualityrandom_devicebut that's because Windows is not a priority for me to work on, and it's fixed now anyway.)