libstdc++: Allow Lemire's algorithm to be used in more cases
authorJonathan Wakely <jwakely@redhat.com>
Thu, 29 Oct 2020 14:47:18 +0000 (14:47 +0000)
committerJonathan Wakely <jwakely@redhat.com>
Thu, 29 Oct 2020 14:47:18 +0000 (14:47 +0000)
commit822c1d21a3c710831af65a6e3bc83f558fb39044
treec3161acd5372b06acd519e99876ba93ce15f2c2c
parentd067bd72936aaaa7e947e919fc869143539ae023
libstdc++: Allow Lemire's algorithm to be used in more cases

This extends the fast path to also work when the URBG's range of
possible values is not the entire range of its result_type. Previously,
the slow path would be used for engines with a uint_fast32_t result type
if that type is actually a typedef for uint64_t rather than uint32_t.
After this change, the generator's result_type is not important, only
the range of possible value that generator can produce. If the
generator's range is exactly UINT64_MAX then the calculation will be
done using 128-bit and 64-bit integers, and if the range is UINT32_MAX
it will be done using 64-bit and 32-bit integers.

In practice, this benefits most of the engines and engine adaptors
defined in [rand.predef] on x86_64-linux and other 64-bit targets. This
is because std::minstd_rand0 and std::mt19937 and others use
uint_fast32_t, which is a typedef for uint64_t.

The code now makes use of the recently-clarified requirement that the
generator's min() and max() functions are usable in constant
expressions (see LWG 2154).

libstdc++-v3/ChangeLog:

* include/bits/uniform_int_dist.h (_Power_of_two): Add
constexpr.
(uniform_int_distribution::_S_nd): Add static_assert to ensure
the wider type is twice as wide as the result type.
(uniform_int_distribution::__generate_impl): Add static_assert
and declare variables as constexpr where appropriate.
(uniform_int_distribution:operator()): Likewise. Only consider
the uniform random bit generator's range of possible results
when deciding whether _S_nd can be used, not the __uctype type.
libstdc++-v3/include/bits/uniform_int_dist.h