Performance of std::generate_canonical and std::uniform_real_distribution

[Gilberto Noronha]

Hi all,

I think I might know a way to, in certain cases, speed up the
generation of uniform floating point numbers in the unit interval, and
I was wondering if my suggestion could possibly be implemented if the
standard allows it. Any comments are very much appreciated (even if
you tell me that I am completely wrong)!

Here is the main argument. For sake of simplicity, I will focus in the
case when the random engine is std::mt19937_64 and we want to generate
doubles. I'm also assuming that doubles are 64 bits long.

In this case, the current implementation of std::generate_canonical
(in random.tcc) does something like (excluding the rejection of 1.0,
which is not important for my argument):

  double result = (rng() - rng.min()) / (static_cast<long
double>(rng.max()) - static_cast<long double>(rng.min()) + 1);

My suggestion is to take advantage of the fact that the range of
std::mt19937_64 (like the range of most popular rngs) is a power of
two and do (keeping in mind the 53 significant binary digits of
standard doubles, as suggested by: http://xoshiro.di.unimi.it/):

 double result = (rng() >> 11) * (1.0 / (static_cast<std::uint64_t>(1) << 53));

Similar tricks can be applied with other combinations of rng/float
type (like std::mt19937/32 bits float, for example).

I am attaching code that does a few regarding the performance and
accuracy of this technique.
It can be compiled with (I tested this using Arch Linux):
g++ -std=c++11 -O3 -Wall -Wextra -pedantic -Wconversion -march=native main.cpp

The code compares (both for double/std::mt19937_64, and
float/std::mt19937) 4 ways of generating random numbers on [0, 1):

1) using std::uniform_real_distribution
2) using std::generate_canonical directly
3) using my implementation of generate_canonical (I added this mostly
to make sure I could            replicate libstdc++'s implementation
4) using the approach discussed above (I called it
fast_generate_canonical for lack of a better name).

Here's a sample output (tested using a laptop with an i7 8750h processor):

Results (Double Precision):
Cycles per Random Number:
std::uniform_real_distribution: 14.174
std::generate_canonical: 14.023
::generate_canonical: 13.8942
fast_generate_canonical: 5.5942
Max Difference: 1.11022e-16
Machine Epsilon: 2.22045e-16

Results (Single Precision):
Cycles per Random Number:
std::uniform_real_distribution: 5.8468
std::generate_canonical: 5.6288
::generate_canonical: 6.0972
fast_generate_canonical: 5.3858
Max Difference: 5.96046e-08
Machine Epsilon: 1.19209e-07

This is with gcc version 8.2. With doubles (and std::mt19937_64),
there is speedup of more than 2.5.
With 32 bits floats (and std::mt19937), the performance improvement is
much smaller.

(I also tested this with Clang and/or with the Intel compiler, and the
single precision speedup seems to be much higher.

The number "Max Difference" is the maximum absolute difference between
the output of fast_generate_canonical and the output of libstdc++
(methods 1, 2, and 3 mentioned above produce exactly the same result).
This is based on 10000 runs, with each run having 10000 random numbers
generated (each run using a different seed).

Let me know if you have any thoughts on this. I'd be happy to work on
a patch if people think this could be useful. But I'm not an expert
regarding the exact requirements of the standard, and I am not sure if
this transformation is acceptable, especially for
std::generate_canonical (my understanding is that the standard does
allow distributions to not use generate_canonical, but I am not 100%
sure about that either).

Gilberto

PS: I am aware that my benchmarks/tests are far from perfect. The
attached code is not meant to be production ready by any stretch of
the imagination.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.cpp
Type: text/x-c++src
Size: 9886 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20180925/93fbbde3/attachment.bin>