What is performance-wise the best way to generate random bools?

Question

I need to generate random Boolean values on a performance-critical path.

The code which I wrote for this is

std::random_device   rd;
std::uniform_int_distribution<> randomizer(0, 1);
const int val randomizer(std::mt19937(rd()));
const bool isDirectionChanged = static_cast<bool>(val);

But do not think that this is the best way to do this as I do not like doing static_cast<bool>.

On the web I have found a few more solutions

1. std::bernoulli_distribution

2. bool randbool = rand() & 1; Remember to call srand() at the beginning.

Answer 1

For the purpose of performance, at a price of less "randomness" than e.g. std::mt19937_64, you can use Xorshift+ to generate 64-bit numbers and then use the bits of those numbers as pseudo-random booleans.

Quoting the Wikipedia:

This generator is one of the fastest generators passing BigCrush

Details: http://xorshift.di.unimi.it/ . There is a comparison table in the middle of the page, showing that mt19937_64 is 2 times slower and is systematic.

Below is sample code (the real code should wrap it in a class):

#include <cstdint>
#include <random>
using namespace std;

random_device rd;
/* The state must be seeded so that it is not everywhere zero. */
uint64_t s[2] = { (uint64_t(rd()) << 32) ^ (rd()),
    (uint64_t(rd()) << 32) ^ (rd()) };
uint64_t curRand;
uint8_t bit = 63;

uint64_t xorshift128plus(void) {
    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;
}

bool randBool()
{
    if(bit >= 63)
    {
        curRand = xorshift128plus();
        bit = 0;
        return curRand & 1;
    }
    else
    {
        bit++;
        return curRand & (1<<bit);
    }
}

Answer 2

Some quick benchmarks (code):

   647921509 RandomizerXorshiftPlus
   821202158 BoolGenerator2 (reusing the same buffer)
  1065582517 modified Randomizer
  1130958451 BoolGenerator2 (creating a new buffer as needed)
  1140139042 xorshift128plus
  2738780431 xorshift1024star
  4629217068 std::mt19937
  6613608092 rand()
  8606805191 std::bernoulli_distribution
 11454538279 BoolGenerator
 19288820587 std::uniform_int_distribution

For those who want ready-to-use code, I present XorShift128PlusBitShifterPseudoRandomBooleanGenerator, a tweaked version of RandomizerXorshiftPlus from the above link. On my machine, it is about as fast as @SergeRogatch's solution, but consistently about 10-20% faster when the loop count is high (≳100,000), and up to ~30% slower with smaller loop counts.

class XorShift128PlusBitShifterPseudoRandomBooleanGenerator {
public:
  bool randBool() {
    if (counter == 0) {
      counter = sizeof(GeneratorType::result_type) * CHAR_BIT;
      random_integer = generator();
    }
    return (random_integer >> --counter) & 1;
  }

private:
  class XorShift128Plus {
  public:
    using result_type = uint64_t;

    XorShift128Plus() {
      std::random_device rd;
      state[0] = rd();
      state[1] = rd();
    }

    result_type operator()() {
      auto x = state[0];
      auto y = state[1];
      state[0] = y;
      x ^= x << 23;
      state[1] = x ^ y ^ (x >> 17) ^ (y >> 26);
      return state[1] + y;
    }

  private:
    result_type state[2];
  };

  using GeneratorType = XorShift128Plus;

  GeneratorType generator;
  GeneratorType::result_type random_integer;
  int counter = 0;
};

Answer 3

A way would be to just generate a unsigned long long for every 64 random calls as stated in the comments. An example:

#include <random>
class Randomizer
{
public:
    Randomizer() : m_rand(0), counter(0), randomizer(0, std::numeric_limits<unsigned long long>::max()) {}

    bool RandomBool()
    {
        if (!counter)
        {
            m_rand = randomizer(std::mt19937(rd()));
            counter = sizeof(unsigned long long) * 8;

        }
        return (m_rand >> --counter) & 1;
    }
private:
    std::random_device  rd;
    std::uniform_int_distribution<unsigned long long> randomizer;
    unsigned long long m_rand;
    int counter;
};