[PATCH, libstdc++] Improve the performance of std::uniform_int_distribution (fewer divisions)
Even on recent processors, integer division is relatively expensive.
The current implementation of std::uniform_int_distribution typically
requires two divisions by invocation:
const __uctype __uerange = __urange + 1; // __urange can be zero
const __uctype __scaling = __urngrange / __uerange;
const __uctype __past = __uerange * __scaling;
__ret = __uctype(__urng()) - __urngmin;
while (__ret >= __past);
__ret /= __scaling;
We can achieve the same algorithmic result with at most one division,
no division at all without requiring more calls to the random number generator.
This was recently added to Swift (https://github.com/apple/swift/pull/25286)
The main challenge is that we need to be able to compute the "full"
given two 64-bit integers, we want the 128-bit result; given two 32-bit integers
we want the 64-bit result. This is fast on common processors. The
is not natively supported in C/C++ but can be achieved with the
which is widely supported by GCC. The patch checks for __uint128_t support; when
support is lacking, we fallback on the existing approach.
For example, if we replace the above code by the following, we get a substantial
performance boost on skylake microarchitectures. E.g., it can
be twice as fast to shuffle arrays of 1 million elements (e.g., using
benchmark: https://github.com/lemire/simple_cpp_shuffle_benchmark )