Utility class implementing functions for random number generation

Issue #29 resolved
geisserf
created an issue

Currently random numbers are generated by calling the rand() method, which is terrible.

Besides implementing the generation of random numbers by using <random>, we want a utility class to generate random numbers. The baseline implementation should use the common c++11 way to generate random numbers, but we want to be able to insert some "fake" random engine. This may be useful for testing or for other experimental stuff.

Comments (13)

  1. geisserf reporter

    I've identified a bunch of issues with the current implementation, unfortunately this is a result of the c++11/14 random library.

    • Using std::random_device{}() to seed the rng engine: First, the standard allows to return non-random data with random_device, i.e. there exist platforms where this will be not random. Fast-Downwards solution to this issue is to seed the engine with time and process id instead. This is not a perfect solution, but it may be better than having some platforms where the output is the same for each run.

    • Second, using random_device{}() to seed the engine returns a single 32 bit integer, but engines may use more than a single integer. For example, the mt19937 engine uses 624 32-bit integers for its internal state. By using a single integer for seeding, it only has 2^32 possible output sequences, instead of 2^19937 possible ones. This makes it predictable and introduces bias. Obviously, seeding via time+pid has the same issues.

    A proper way to seed the mt19937 engine (but still using std::random_device) would be:

    std::array<int, std::mt19937::state_size> seed_data;
    std::random_device r;
    std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
    std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
    std::mt19937 gen(seq);
    

    This is easy to implement if we fix the generator of RandomImpl to being a mt19937 engine (instead of being a template); after all I doubt we ever need another of the currently available engines and if we do so we can just create another random implementation derived from Random. Unfortunately, even this approach is not perfect.

    The problem here is that the c++11/14 implementation of <random> has several issues, which unfortunately does not seem get fixed in c++17, more discussion on that topic is here. A good choice would therefore have to last several years.

    I see the following options:

    • Use the solution Fast-Downward uses, reducing the number of possible output sequences of the engine, but making sure that the random number generation is (at least somewhat) random on every platform.
    • Seed the mt19937 properly, the most important issue here is probably that this still uses random_device (i.e. may not be random on some platforms.)
    • Use the header-only rand-utils c++11 library, which is written by Melissa O'Neil and provides utility functions that handle proper seeding (and probably more).
    • Use the PCG Generator, a generator also written by Melissa O'Neil which fixes all the issues the current c++11 generators have, recommended by several people.

    The last option is probably the best option in terms of efficiency and scientific correctness, but also the one with the most overhead. After all, do we even need strong unpredicatbility. The header only library seems like a fair compromise, but we have to take the license into account (although MIT license is easy to include and we should maybe start to think about licenses anyway some day?). The first two approaches are easy to implement and may be enough for our application. We should probably still document the issues, as these likely won't change for several years.

  2. geisserf reporter

    Answer by tkeller:

    I would prefer a solution that doesn't blow up things unnecessarily, i.e. one where we do not need to include 3rd party code and other licenses. Therefore, I'd prefer your second option if it is possible to implement it such that the seed it truly random on Linux and Windows systems. Is that possible?

  3. geisserf reporter

    I don't think the second approach works if we want to seed truly random on Linux and Windows for all possible compilers. However, we could restrict us to the most common Linux/Windows compilers; I think that would be GCC and Clang for Linux and Mingw, Cygwin and VC for Windows. At least for GCC, Clang and VC std::random_device is non-deterministic, I would have to check it for the other compilers.

    The FD approach would also work for our purposes, i.e. use std::chrono::high_resolution_clock and std::this_thread::get_id() for entropy. After all, we only initialize the RNG once, so as long as PROST is not called every millisecond this should also work quite well. But, once again, different compilers may have different implementations of high_resolution_clock:

    There are some issues with using C++11's high_resolution_clock. One is that libraries lie. The GNU libstdc++ library claims that its high-resolution clock ticks every nanosecond, but on some platforms, including OS X, the underlying implementation uses a POSIX gettimeofday system call which only has microsecond resolution. And even if your C++ library tells the truth, there is no requirement that the high-resolution clock be especially high resolution. You could be using a C++ library where the clock only ticks once a second (or even once a year!).

    Again, I think this does not really matter for common compilers.

    That being said, I prefer the second approach. I don't think one should use a compiler where random_device is not implemented non-deterministically - if they do, they might be happy to know about that issue. For common compilers it is a cleaner solution and might avoid future issues, if someone decides to initialize multiple RNGs at the same time (e.g. using multiple planners at once).

  4. tkeller repo owner

    Have you looked into some specific instances and compared the number of trials that are performed in a fixed amount of time? I am asking because the results are slightly weakerif UnsolvedMCOutcomeSelection is used, and I'd like to know if that is due to the usual uncertainty in the results or if significantly less trials are performed in the same time

  5. geisserf reporter

    I only compared the trials in the first step for several instances of the IPPC2014 benchmark. No significant differences there (rev223 is even slightly ahead). I could start some runs with increased time limit for the first step and compare the number of trials after the first step with a script, would that be sufficient?

  6. tkeller repo owner

    I tested this myself with 3 runs each on elevators 2 and sysadmin 5 and these are the number of trials in 1s (r223 | r222)

    elev2: 194057 | 198257 200749 | 207270 200177 | 201342

    -> avg: 198327,67 | 202289,67 2% more with rev 222

    sysadmin5: 49827 | 48445 45832 | 48567 46837 | 49615

    -> avg: 47498,67 | 48875,67 2,89% more with rev 222

    I don't think this is critical so I'd merge this as it is.

  7. tkeller repo owner

    I wrote my post before I read yours, but my conclusion still holds: I would just merge it, I don't think the difference matters much (the difference between two runs with the same revision is larger than the average difference between the revisions).

  8. Log in to comment