Bitcoin Core  0.20.99
P2P Digital Currency
Public Types | Public Member Functions | Static Public Member Functions | Static Private Member Functions | Private Attributes | List of all members
ankerl::nanobench::Rng Class Referencefinal

An extremely fast random generator. More...

#include <nanobench.h>

Public Types

using result_type = uint64_t
 This RNG provides 64bit randomness. More...
 

Public Member Functions

 Rng (Rng const &)=delete
 As a safety precausion, we don't allow copying. More...
 
Rngoperator= (Rng const &)=delete
 Same as Rng(Rng const&), we don't allow assignment. More...
 
 Rng (Rng &&) noexcept=default
 
Rngoperator= (Rng &&) noexcept=default
 
 ~Rng () noexcept=default
 
 Rng ()
 Creates a new Random generator with random seed. More...
 
 Rng (uint64_t seed) noexcept
 
 Rng (uint64_t x, uint64_t y) noexcept
 
 ANKERL_NANOBENCH (NODISCARD) Rng copy() const noexcept
 Creates a copy of the Rng, thus the copy provides exactly the same random sequence as the original. More...
 
uint64_t operator() () noexcept
 Produces a 64bit random value. More...
 
uint32_t bounded (uint32_t range) noexcept
 Generates a random number between 0 and range (excluding range). More...
 
double uniform01 () noexcept
 Provides a random uniform double value between 0 and 1. More...
 
template<typename Container >
void shuffle (Container &container) noexcept
 Shuffles all entries in the given container. More...
 

Static Public Member Functions

static constexpr uint64_t() min ()
 
static constexpr uint64_t() max ()
 

Static Private Member Functions

static constexpr uint64_t rotl (uint64_t x, unsigned k) noexcept
 

Private Attributes

uint64_t mX
 
uint64_t mY
 

Detailed Description

An extremely fast random generator.

Currently, this implements RomuDuoJr, developed by Mark Overton. Source: http://www.romu-random.org/

RomuDuoJr is extremely fast and provides reasonable good randomness. Not enough for large jobs, but definitely good enough for a benchmarking framework.

This random generator is a drop-in replacement for the generators supplied by <random>. It is not cryptographically secure. It's intended purpose is to be very fast so that benchmarks that make use of randomness are not distorted too much by the random generator.

Rng also provides a few non-standard helpers, optimized for speed.

Definition at line 453 of file nanobench.h.

Member Typedef Documentation

◆ result_type

This RNG provides 64bit randomness.

Definition at line 458 of file nanobench.h.

Constructor & Destructor Documentation

◆ Rng() [1/5]

ankerl::nanobench::Rng::Rng ( Rng const &  )
delete

As a safety precausion, we don't allow copying.

Copying a PRNG would mean you would have two random generators that produce the same sequence, which is generally not what one wants. Instead create a new rng with the default constructor Rng(), which is automatically seeded from std::random_device. If you really need a copy, use copy().

◆ Rng() [2/5]

ankerl::nanobench::Rng::Rng ( Rng &&  )
defaultnoexcept

◆ ~Rng()

ankerl::nanobench::Rng::~Rng ( )
defaultnoexcept

◆ Rng() [3/5]

ankerl::nanobench::Rng::Rng ( )

Creates a new Random generator with random seed.

Instead of a default seed (as the random generators from the STD), this properly seeds the random generator from std::random_device. It guarantees correct seeding. Note that seeding can be relatively slow, depending on the source of randomness used. So it is best to create a Rng once and use it for all your randomness purposes.

Here is the caller graph for this function:

◆ Rng() [4/5]

ankerl::nanobench::Rng::Rng ( uint64_t  seed)
explicitnoexcept

Creates a new Rng that is seeded with a specific seed. Each Rng created from the same seed will produce the same randomness sequence. This can be useful for deterministic behavior.

embed:rst
.. note::

   The random algorithm might change between nanobench releases. Whenever a faster and/or better random
   generator becomes available, I will switch the implementation.

As per the Romu paper, this seeds the Rng with splitMix64 algorithm and performs 10 initial rounds for further mixing up of the internal state.

Parameters
seedThe 64bit seed. All values are allowed, even 0.

◆ Rng() [5/5]

ankerl::nanobench::Rng::Rng ( uint64_t  x,
uint64_t  y 
)
noexcept

Member Function Documentation

◆ ANKERL_NANOBENCH()

ankerl::nanobench::Rng::ANKERL_NANOBENCH ( NODISCARD  ) const
noexcept

Creates a copy of the Rng, thus the copy provides exactly the same random sequence as the original.

◆ bounded()

uint32_t ankerl::nanobench::Rng::bounded ( uint32_t  range)
inlinenoexcept

Generates a random number between 0 and range (excluding range).

The algorithm only produces 32bit numbers, and is slightly biased. The effect is quite small unless your range is close to the maximum value of an integer. It is possible to correct the bias with rejection sampling (see here, but this is most likely irrelevant in practices for the purposes of this Rng.

See Daniel Lemire's blog post A fast alternative to the modulo reduction

Parameters
rangeUpper exclusive range. E.g a value of 3 will generate random numbers 0, 1, 2.
Returns
uint32_t Generated random values in range [0, range(.

Definition at line 1081 of file nanobench.h.

◆ max()

static constexpr uint64_t() ankerl::nanobench::Rng::max ( )
static

◆ min()

static constexpr uint64_t() ankerl::nanobench::Rng::min ( )
static

◆ operator()()

uint64_t ankerl::nanobench::Rng::operator() ( )
inlinenoexcept

Produces a 64bit random value.

This should be very fast, thus it is marked as inline. In my benchmark, this is ~46 times faster than std::default_random_engine for producing 64bit random values. It seems that the fastest std contender is std::mt19937_64. Still, this RNG is 2-3 times as fast.

Returns
uint64_t The next 64 bit random value.

Definition at line 1071 of file nanobench.h.

◆ operator=() [1/2]

Rng& ankerl::nanobench::Rng::operator= ( Rng const &  )
delete

Same as Rng(Rng const&), we don't allow assignment.

If you need a new Rng create one with the default constructor Rng().

◆ operator=() [2/2]

Rng& ankerl::nanobench::Rng::operator= ( Rng &&  )
defaultnoexcept

◆ rotl()

constexpr uint64_t ankerl::nanobench::Rng::rotl ( uint64_t  x,
unsigned  k 
)
staticprivatenoexcept

Definition at line 1106 of file nanobench.h.

◆ shuffle()

template<typename Container >
void ankerl::nanobench::Rng::shuffle ( Container &  container)
noexcept

Shuffles all entries in the given container.

Although this has a slight bias due to the implementation of bounded(), this is preferable to std::shuffle because it is over 5 times faster. See Daniel Lemire's blog post Fast random shuffling.

Parameters
containerThe whole container will be shuffled.

Definition at line 1097 of file nanobench.h.

◆ uniform01()

double ankerl::nanobench::Rng::uniform01 ( )
inlinenoexcept

Provides a random uniform double value between 0 and 1.

This uses the method described in Generating uniform doubles in the unit interval, and is extremely fast.

Returns
double Uniformly distributed double value in range [0,1(, excluding 1.

Definition at line 1087 of file nanobench.h.

Here is the call graph for this function:

Member Data Documentation

◆ mX

uint64_t ankerl::nanobench::Rng::mX
private

Definition at line 564 of file nanobench.h.

◆ mY

uint64_t ankerl::nanobench::Rng::mY
private

Definition at line 565 of file nanobench.h.


The documentation for this class was generated from the following file: