C++ fast random bool generation benchmarks

fast_random_bool_benchmarks.cpp

#include <random>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <functional>

using namespace std;
using namespace chrono;

const int Count = 1000'000'000;

#define BM_START(number)              \
auto bm##number() {                   \
  std::random_device rd;              \
  auto start = steady_clock::now();

#define BM_END                        \
  return steady_clock::now() - start; \
}

#define BM_RESULT(number, name)       \
cout << std::right << std::setw(12) << bm##number().count() << ' ' << name << endl

BM_START(1)
  auto gen = mt19937(rd());
  std::uniform_int_distribution<> dist(0, 1);
  
  for (int idx = 0; idx < Count; ++idx) {
    const int val = dist(gen);
    const bool isDirectionChanged = static_cast<bool>(val);
  }
BM_END

BM_START(2)
  srand(rd());
  
  for (int idx = 0; idx < Count; ++idx) {
    const int val = rand();
    const bool isDirectionChanged = val & 1;
  }
BM_END

BM_START(3)
  auto gen = mt19937(rd());
  std::bernoulli_distribution dist;

  for (int idx = 0; idx < Count; ++idx) {
    const bool isDirectionChanged = dist(gen);
  }
BM_END

uint64_t s[2];

uint64_t xorshift128plus() {
  uint64_t x = s[0];
  uint64_t const y = s[1];
  s[0] = y;
  x ^= x << 23; // a
  s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
  return s[1] + y;
}

BM_START(4)
  // Seed xorshift128plus taking into account that random_device may return 32-bit values
  s[0] = (uint64_t(rd()) << 32) | (rd() & 0xffffffff);
  s[1] = (uint64_t(rd()) << 32) | (rd() & 0xffffffff);
  
  for (int idx = 0; idx < Count; ++idx) {
    const auto val = xorshift128plus();
    const bool isDirectionChanged = val & 1;
  }
BM_END

uint64_t s2[16];
int p;

uint64_t xorshift1024star(void) {
   const uint64_t s0 = s2[p];
   uint64_t s1 = s2[p = (p + 1) & 15];
   s1 ^= s1 << 31; // a
   s2[p] = s1 ^ s0 ^ (s1 >> 11) ^ (s0 >> 30); // b,c
   return s2[p] * UINT64_C(1181783497276652981);
}

BM_START(5)
  for (int idx = 0; idx < 16; ++idx) {
    // Seed xorshift1024star taking into account that random_device may return 32-bit values
    s2[0] = (uint64_t(rd()) << 32) | (rd() & 0xffffffff);
    s2[1] = (uint64_t(rd()) << 32) | (rd() & 0xffffffff);
  }
  
  for (int idx = 0; idx < Count; ++idx) {
    const auto val = xorshift1024star();
    const bool isDirectionChanged = val & 1;
  }
BM_END

class BoolGenerator {
  private:
  static const int BUFFER_SIZE = Count / 64;
  uint64_t randomBuffer[BUFFER_SIZE];
  uint64_t mask;
  int counter;

  void advanceCounter() {
    counter++;
    if (counter == BUFFER_SIZE) {
        counter = 0;
    }
  }

  public:
  BoolGenerator(std::random_device& rd) {
    for (int idx = 0; idx < BUFFER_SIZE; ++idx)
      randomBuffer[idx] = rd();
    mask = 1;
    counter = 0;
  }

  bool generate() {
    mask <<= 1;
    if (!mask) { //After 64 shifts the mask becomes zero
        mask = 1;//reset mask
        advanceCounter();//get the next value in the buffer
    }
    return randomBuffer[counter] & mask;
  }
};

BM_START(6)
  auto gen = BoolGenerator(rd);
  
  for (int idx = 0; idx < Count; ++idx) {
    const bool isDirectionChanged = gen.generate();
  }
BM_END

class Randomizer
{
public:
    Randomizer(std::random_device& rd)
    : m_rand(0),
      counter(0),
      gen(rd()),
      randomizer(0, std::numeric_limits<unsigned long long>::max())
    {}

    bool RandomBool()
    {
        if (!counter)
        {
            m_rand = randomizer(gen);
            counter = sizeof(unsigned long long) * CHAR_BIT;
        }
        return (m_rand >> --counter) & 1;
    }
private:
    unsigned long long m_rand;
    int counter;
    std::mt19937 gen;
    std::uniform_int_distribution<unsigned long long> randomizer;
};

BM_START(7)
  auto gen = Randomizer(rd);
  
  for (int idx = 0; idx < Count; ++idx) {
    const bool isDirectionChanged = gen.RandomBool();
  }
BM_END

class RandomizerXorshiftPlus
{
public:
    RandomizerXorshiftPlus(std::random_device& rd)
    : m_rand(0),
      counter(0),
      randomizer(0, std::numeric_limits<uint64_t>::max())
    {
      // Seed xorshift128plus taking into account that random_device may return 32-bit values
      s[0] = (uint64_t(rd()) << 32) | (rd() & 0xffffffff);
      s[1] = (uint64_t(rd()) << 32) | (rd() & 0xffffffff);
    }

    bool RandomBool()
    {
        if (!counter)
        {
            m_rand = randomizer(gen);
            counter = sizeof(uint64_t) * CHAR_BIT;
        }
        return (m_rand >> --counter) & 1;
    }
private:
    struct generator {
        using result_type = uint64_t;
        static constexpr result_type max() { return std::numeric_limits<result_type>::max(); }
        static constexpr result_type min() { return std::numeric_limits<result_type>::min(); }
        result_type operator()() { return xorshift128plus(); }
    } gen;
    uint64_t m_rand;
    int counter;
    std::uniform_int_distribution<uint64_t> randomizer;
};

BM_START(8)
  auto gen = RandomizerXorshiftPlus(rd);

  for (int idx = 0; idx < Count; ++idx) {
    const bool isDirectionChanged = gen.RandomBool();
  }
BM_END

class BoolGenerator2 {
  private:
  static const int BUFFER_SIZE = 65536;
  uint64_t randomBuffer[BUFFER_SIZE];
  uint64_t currValue;
  int bufferCounter;
  int bitCounter;

  void advanceBufferCounter() {
    bufferCounter++;
    if (bufferCounter == BUFFER_SIZE) {
        bufferCounter = 0;
    }
  }

  void getNextValue() {
      currValue = randomBuffer[bufferCounter];
      bitCounter = sizeof(uint64_t) * 8;
      advanceBufferCounter();
  }
  
  //HERE FILL YOUR BUFFER WITH A RANDOM GENERATOR
  void initializeBuffer() {
  //Anything will do, taken from here: http://stackoverflow.com/a/19728404/2436175
      std::random_device rd;
      std::mt19937 rng(rd());
      std::uniform_int_distribution<uint64_t> uni(0,std::numeric_limits<uint64_t>::max());
      for (int i = 0; i < BUFFER_SIZE; i++ ) {
           randomBuffer[i] = uni(rng);
      }
  }

  public:
  BoolGenerator2() {
      initializeBuffer();
      bufferCounter = 0;
      getNextValue();
  }

  bool generate() {
      if (!bitCounter) {
           getNextValue();
      }
      //A variation of other methods seen around
      bitCounter--;
      bool retVal = currValue & 0x01;
      currValue >>= 1;
      return retVal;
  }
};

BM_START(9)
  auto gen = BoolGenerator2();
  
  for (int idx = 0; idx < Count; ++idx) {
    const bool isDirectionChanged = gen.generate();
  }
BM_END

class BoolGenerator2WithReinitialization {
  private:
  static const int BUFFER_SIZE = 65536;
  uint64_t randomBuffer[BUFFER_SIZE];
  uint64_t currValue;
  int bufferCounter;
  int bitCounter;

  void advanceBufferCounter() {
    bufferCounter++;
    if (bufferCounter == BUFFER_SIZE) {
        bufferCounter = 0;
        // Reinitialize buffer to not get the same numbers again.
        initializeBuffer();
    }
  }

  void getNextValue() {
      currValue = randomBuffer[bufferCounter];
      bitCounter = sizeof(uint64_t) * 8;
      advanceBufferCounter();
  }
  
  //HERE FILL YOUR BUFFER WITH A RANDOM GENERATOR
  void initializeBuffer() {
  //Anything will do, taken from here: http://stackoverflow.com/a/19728404/2436175
      std::random_device rd;
      std::mt19937 rng(rd());
      std::uniform_int_distribution<uint64_t> uni(0,std::numeric_limits<uint64_t>::max());
      for (int i = 0; i < BUFFER_SIZE; i++ ) {
           randomBuffer[i] = uni(rng);
      }
  }

  public:
  BoolGenerator2WithReinitialization() {
      initializeBuffer();
      bufferCounter = 0;
      getNextValue();
  }

  bool generate() {
      if (!bitCounter) {
           getNextValue();
      }
      //A variation of other methods seen around
      bitCounter--;
      bool retVal = currValue & 0x01;
      currValue >>= 1;
      return retVal;
  }
};

BM_START(10)
  auto gen = BoolGenerator2WithReinitialization();
  
  for (int idx = 0; idx < Count; ++idx) {
    const bool isDirectionChanged = gen.generate();
  }
BM_END

BM_START(11)
  auto gen = mt19937(rd());
  
  for (int idx = 0; idx < Count; ++idx) {
    const bool isDirectionChanged = gen() & 1;
  }
BM_END

int main() {
  BM_RESULT(8, "RandomizerXorshiftPlus");
  BM_RESULT(9, "BoolGenerator2 (reusing the same buffer)");
  BM_RESULT(7, "modified Randomizer");
  BM_RESULT(10,"BoolGenerator2 (creating a new buffer as needed)");
  BM_RESULT(4, "xorshift128plus");
  BM_RESULT(5, "xorshift1024star");
  BM_RESULT(11,"std::mt19937");
  BM_RESULT(2, "rand()");
  BM_RESULT(3, "std::bernoulli_distribution");
  BM_RESULT(6, "BoolGenerator1");
  BM_RESULT(1, "std::uniform_int_distribution");
}