For some reason, I became concerned about the amount of time being spent by random number generators, so I took a look into them. I wrote a program which compares the speed of std::mt19937 ( mersenne twister ), a custom “twister loop”, a custom “pcg”, and custom “xorshift” generators. The standard twister was the slowest, though I’m unsure if it matters since they’re all quite fast. The fastest turned out to be my “twister loop”, though, this is also the least random, and it’s barely the fastest.
This code shows how to write a custom random number generator that can be used with std functions such as shuffle and distributions. Here are the results, followed by the code.
It turns out that std::twister is pretty fast compared to the custom “faster” generators I discovered online. The fastest generator, twister_loop, is just an array filled with twister values being referenced rather than an actual generator.
Here is the code:
#include <random>
#include <iostream>
#include <chrono>
class TwisterLoop{
public:
using result_type = uint32_t;
static constexpr result_type(min)() { return 0; }
static constexpr result_type(max)() { return UINT32_MAX; }
//
std::mt19937 mTwister;
std::size_t mCurrentIdx{ 0 };
std::vector< result_type > mValues;
result_type generateOne() {
return mTwister();
}
void refreshLoop() {
std::generate(mValues.begin(), mValues.end(), [&]() {
return generateOne();
});
}
TwisterLoop(result_type rdseed, std::size_t loopSize=1000){
seed(rdseed);
mValues.resize(loopSize);
refreshLoop();
}
void seed(result_type rdseed){
mTwister.seed(rdseed);
}
result_type operator()(){
if (mCurrentIdx >= mValues.size()) mCurrentIdx = 0;
return mValues[mCurrentIdx++];
}
void discard(unsigned long long n){
for (unsigned long long i = 0; i < n; ++i)
operator()();
}
};
class pcg{
public:
using result_type = uint32_t;
static constexpr result_type(min)() { return 0; }
static constexpr result_type(max)() { return UINT32_MAX; }
pcg()
: m_state(0x853c49e6748fea9bULL)
, m_inc(0xda3e39cb94b95bdbULL)
{}
pcg(std::random_device& rd){
seed(rd);
}
void seed(std::random_device& rd){
uint64_t s0 = uint64_t(rd()) << 31 | uint64_t(rd());
uint64_t s1 = uint64_t(rd()) << 31 | uint64_t(rd());
m_state = 0;
m_inc = (s1 << 1) | 1;
(void)operator()();
m_state += s0;
(void)operator()();
}
result_type operator()(){
uint64_t oldstate = m_state;
m_state = oldstate * 6364136223846793005ULL + m_inc;
uint32_t xorshifted = uint32_t(((oldstate >> 18u) ^ oldstate) >> 27u);
int rot = oldstate >> 59u;
return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}
void discard(unsigned long long n){
for (unsigned long long i = 0; i < n; ++i)
operator()();
}
private:
uint64_t m_state;
uint64_t m_inc;
};
class xorshift{
public:
using result_type = uint32_t;
static constexpr result_type(min)() { return 0; }
static constexpr result_type(max)() { return UINT32_MAX; }
xorshift() : m_seed(0xc1f651c67c62c6e0ull) {}
xorshift(std::random_device& rd){
seed(rd);
}
void seed(std::random_device& rd){
m_seed = uint64_t(rd()) << 31 | uint64_t(rd());
}
result_type operator()(){
uint64_t result = m_seed * 0xd989bcacc137dcd5ull;
m_seed ^= m_seed >> 11;
m_seed ^= m_seed << 31;
m_seed ^= m_seed >> 18;
return uint32_t(result >> 32ull);
}
void discard(unsigned long long n){
for (unsigned long long i = 0; i < n; ++i)
operator()();
}
private:
uint64_t m_seed;
};
int main() {
std::random_device rd;
std::mt19937 twister(rd());
TwisterLoop twisterLoop(rd(), 10000);
pcg pcg1(rd);
xorshift shift(rd);
std::uniform_real_distribution<float> reals(-100.0f, 100.0f);
std::vector<float> results; results.resize(1000);
auto time = [&](auto& generator) -> std::size_t{
auto start = std::chrono::high_resolution_clock::now();
std::generate(results.begin(), results.end(), [&]() { return reals(generator); });
std::shuffle(results.begin(), results.end(), generator);
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
};
auto test = [&](const std::string& caption, auto& generator) {
std::size_t testCount = 100;
std::size_t avg = 0;
std::cout << "testing: " << caption << " " << testCount << " times" << std::endl;
for (std::size_t i = 0; i < testCount; ++i) {
avg += time(generator);
}
avg /= testCount;
std::cout << "took: " << avg << " nanoseconds"
<< std::endl << std::endl;
};
test("std::twister", twister );
test("twister_loop", twisterLoop);
test("pcg", pcg1);
test("shift", shift);
std::cout << "\nprogram finished, press enter";
std::cin.get();
std::cin.get();
return 0;
}
The pcg and xorshift generators are credited to /* Copyright (c) 2018 Arvid Gerstmann. https://gist.github.com/Leandros */
Spot C++ 