Replace rnd macros with STL alternatives

[voidanix]

Should address #191

Picked ranlux because it seems faster (and is less predictable) but any PRNG should do

EDIT: mt19937 is back again

[robalni]

I don't think we should include c++ standard library headers in common header files like tools.h because it makes the build time slow. I don't even think this is needed in this pull request because <random> is not used in tools.h.

[TheAssassin]

We could introduce a random.h, for instance, and include that wherever needed.

Re. ranlux48, I guess it makes sense not to hardcode an implementation (we never know where the game will be compiled) but rather use default_random_engine. OTOH, picking one will ensure results are reproducible. Regarding its performance, I don't think the overhead of an MT is really critical, but we're not using these for serious cryptographic work anyway, so I think that one's fine, too.

[TheAssassin]

Regarding ranlux48 vs. MT19937, I've come to another conclusion than you, performance wise. I've put together some (very shady but good enough) "benchmark".

#include <random>

int main() {
    std::random_device rndseed;
    //std::ranlux48 rndalg(rndseed());
    std::mt19937 rndalg(rndseed());
    for (uint64_t i = 0; i < (1ULL << 24); ++i) {
        rndalg();
    } 
}

With 1 << 24 samples, ranlux48 takes around 8.5 seconds in average (~20 passes), whereas MT needs around 0.3 seconds. So, on my computer, the MT implementation outperforms ranlux easily. (Just for comparison, ranlux24 takes around 2.6 seconds.) Hooking up an std::uniform_int_distribution<> dist(0, (1ULL << 15));, I get around 0.75 seconds for MT, 2.95 seconds for ranlux24, and 9.15 seconds for ranlux48. The slowdown seems somewhat constant, which means we can exclude it for our assessment. These results seem to confirm some way better analyses on the Internet, which all confirm that performance wise, the MT is faster by some orders of magnitude.

We should discuss what we want. In games, I think "no predictability" (which is actually just a security property) isn't necessarily the goal. Performance, however, is. We should not use any of these PRNGs for serious work, as they're just not good at it (boost-random is significantly different, but also a lot better than what you get in the STL). We just need a reasonably well-distributed random number generation. MT19937 will provide that, but, looking at some Internet suggestions, it might even be overkill (many games just use xor shift algorithms for tasks like randomizing spawns or weapons). Given that we've been using MT so far, I think we should just continue to do so.

I am eager to see how that (shady) benchmark performs on @voidanix's computer. I can't reproduce that ranlux should run faster than MT.

[voidanix]

We could introduce a random.h, for instance, and include that wherever needed.

Re. ranlux48, I guess it makes sense not to hardcode an implementation (we never know where the game will be compiled) but rather use default_random_engine. OTOH, picking one will ensure results are reproducible. Regarding its performance, I don't think the overhead of an MT is really critical, but we're not using these for serious cryptographic work anyway, so I think that one's fine, too.

The problem with default_random_engine is that it's implementation defined, so it could as well go and pick the slowest of the bunch.

As for a random.h, I guess it's fine just to define <random> in tools.cpp? It shaves around 6 seconds on my machine and it's used only there

[voidanix]

Regarding ranlux48 vs. MT19937, I've come to another conclusion than you, performance wise. I've put together some (very shady but good enough) "benchmark".

#include <random>

int main() {
    std::random_device rndseed;
    //std::ranlux48 rndalg(rndseed());
    std::mt19937 rndalg(rndseed());
    for (uint64_t i = 0; i < (1ULL << 24); ++i) {
        rndalg();
    } 
}

With 1 << 24 samples, ranlux48 takes around 8.5 seconds in average (~20 passes), whereas MT needs around 0.3 seconds. So, on my computer, the MT implementation outperforms ranlux easily. (Just for comparison, ranlux24 takes around 2.6 seconds.) Hooking up an std::uniform_int_distribution<> dist(0, (1ULL << 15));, I get around 0.75 seconds for MT, 2.95 seconds for ranlux24, and 9.15 seconds for ranlux48. The slowdown seems somewhat constant, which means we can exclude it for our assessment. These results seem to confirm some way better analyses on the Internet, which all confirm that performance wise, the MT is faster by some orders of magnitude.

We should discuss what we want. In games, I think "no predictability" (which is actually just a security property) isn't necessarily the goal. Performance, however, is. We should not use any of these PRNGs for serious work, as they're just not good at it (boost-random is significantly different, but also a lot better than what you get in the STL). We just need a reasonably well-distributed random number generation. MT19937 will provide that, but, looking at some Internet suggestions, it might even be overkill (many games just use xor shift algorithms for tasks like randomizing spawns or weapons). Given that we've been using MT so far, I think we should just continue to do so.

I am eager to see how that (shady) benchmark performs on @voidanix's computer. I can't reproduce that ranlux should run faster than MT.

# mt19937
./a.out  0.25s user 0.00s system 99% cpu 0.253 total

# ranlux48
./a.out  7.49s user 0.37s system 97% cpu 8.075 total

Here I'm guessing that my way of testing this was stupid: I moved std::random_device inside rnd and tested both mt19937 and ranlux48; ranlux48 gave me ~60fps more but that could be because it didn't call /dev/urandom as frequently.

So yes, I will switch back to std::mt19937

[TheAssassin]

As for a random.h, I guess it's fine just to define in tools.cpp? It shaves around 6 seconds on my machine and it's used only there.

Given your current implementation, yeah, that'll do. It's anyway best practice to include headers only where needed, in the smallest possible unit.