As the implementation already mask lowest _Bits when converting __product
to _Up, it works for any integer with at least _Bits, and no longer
requires integers with exactly 32 (__UINT32_TYPE__) or 64 (__UINT64_TYPE__).
The type _Up and _Wp are now defined in _Select_uint_least_t of _Bits
and 2 * _Bits respectively. Thus primary _Select_uint_least_t primary
template and partial specializations are now extracted to uniform_int_dist.h
header. The measurments on x86_32 indicated that using Lemire algorithm
with __rand_uint128 leads to worse performance, we only forward declared
corresponding _Select_uint_least_t specialization in uniform_int_dist.h,
and keep it definition (and __rand_uint128) in much larger bits/random.h
header.
libstdc++-v3/ChangeLog:
* include/bits/random.h (_Select_uint_least_t): Move primary
template and most of partial specializations to...
* include/bits/uniform_int_dist.h (_Select_uint_least_t):
Extracted from bits/random.h.
(uniform_int_distribution::_S_nd): Replace _Up and _Wp template
paramteters with Select_uint_least_t of _Bits and 2 * _Bits
respectively.
(uniform_int_distribution::operator()): Adjust calls to _S_nd
to pass only _Bits, and remove checks for presence of
__UINT64_TYPE__ and __UINT32_TYPE__ types.
---
I do not have any specific target in mind (that does not have exactly
32/64 bits integer), but I think this makes the code easier to follow
and generally cleaner.
I have measured a change where Lemiere algorithm with be used with
__rand_uint128, where __int128 is not available. However, my test
of x86_64 linux, indicate that such change has negative effect on
performance for 2^64 range engines:
Benchmark/m32 Patch rand_uint128
------------------------------------------------------------
BM_mt19937 1.68 1.71
BM_t20_mt19937 3.07 2.81
BM_philox4x32 4.02 4.13
BM_ranlux24 44.3 42.5
BM_Constant32 0.428 0.429
BM_mt19937_64 12 16.1
BM_t40_mt19937_64 16 21.4
BM_philox4x64 36.3 42.1
BM_ranlux48 189 188
BM_Constant64 0.43 15.3
BM_minstd_rand 3.68 3.68
BM_knuth_b 9.98 9.86
Tested on x86_64 linux. Additionally all *random* tested with all
standard modes, -m32 and debug. OK for trunk?
libstdc++-v3/include/bits/random.h | 34 ++--------
libstdc++-v3/include/bits/uniform_int_dist.h | 66 +++++++++++++++-----
2 files changed, 53 insertions(+), 47 deletions(-)
diff --git a/libstdc++-v3/include/bits/random.h
b/libstdc++-v3/include/bits/random.h
index b01b92862cc..3b7e13cc52d 100644
--- a/libstdc++-v3/include/bits/random.h
+++ b/libstdc++-v3/include/bits/random.h
@@ -534,36 +534,10 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
struct _Shift<_UIntType, __w, true>
{ static constexpr _UIntType __value = _UIntType(1) << __w; };
- template<int __s,
- int __which = ((__s <= __CHAR_BIT__ * sizeof (int))
- + (__s <= __CHAR_BIT__ * sizeof (long))
- + (__s <= __CHAR_BIT__ * sizeof (long long))
- /* assume long long no bigger than __int128 */
- + (__s <= 128))>
- struct _Select_uint_least_t
- {
- static_assert(__which < 0, /* needs to be dependent */
- "sorry, would be too much trouble for a slow result");
- };
-
- template<int __s>
- struct _Select_uint_least_t<__s, 4>
- { using type = unsigned int; };
-
- template<int __s>
- struct _Select_uint_least_t<__s, 3>
- { using type = unsigned long; };
-
- template<int __s>
- struct _Select_uint_least_t<__s, 2>
- { using type = unsigned long long; };
-
-#if __SIZEOF_INT128__ > __SIZEOF_LONG_LONG__
- template<int __s>
- struct _Select_uint_least_t<__s, 1>
- { __extension__ using type = unsigned __int128; };
-#elif __has_builtin(__builtin_add_overflow) \
- && __has_builtin(__builtin_sub_overflow) \
+// Primiary template and other specializtions are defined in
bits/uniform_int_dist.h.
+#if __SIZEOF_INT128__ <= __SIZEOF_LONG_LONG__ \
+ && __has_builtin(__builtin_add_overflow) \
+ && __has_builtin(__builtin_sub_overflow) \
&& defined __UINT64_TYPE__
template<int __s>
struct _Select_uint_least_t<__s, 1>
diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h
b/libstdc++-v3/include/bits/uniform_int_dist.h
index 6f29bd0a98c..dfccb9c73f1 100644
--- a/libstdc++-v3/include/bits/uniform_int_dist.h
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -72,6 +72,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
return ((__x - 1) & __x) == 0;
}
+
+ template<int __s,
+ int __which = ((__s <= __CHAR_BIT__ * sizeof (int))
+ + (__s <= __CHAR_BIT__ * sizeof (long))
+ + (__s <= __CHAR_BIT__ * sizeof (long long))
+ /* assume long long no bigger than __int128 */
+ + (__s <= 128))>
+ struct _Select_uint_least_t
+ {
+ static_assert(__which < 0, /* needs to be dependent */
+ "sorry, would be too much trouble for a slow result");
+ };
+
+ template<int __s>
+ struct _Select_uint_least_t<__s, 4>
+ { using type = unsigned int; };
+
+ template<int __s>
+ struct _Select_uint_least_t<__s, 3>
+ { using type = unsigned long; };
+
+ template<int __s>
+ struct _Select_uint_least_t<__s, 2>
+ { using type = unsigned long long; };
+
+// Alternate specialization for
+#if __SIZEOF_INT128__ > __SIZEOF_LONG_LONG__
+ template<int __s>
+ struct _Select_uint_least_t<__s, 1>
+ { __extension__ using type = unsigned __int128; };
+#elif __has_builtin(__builtin_add_overflow) \
+ && __has_builtin(__builtin_sub_overflow) \
+ && defined __UINT64_TYPE__
+ template<int __s>
+ struct _Select_uint_least_t<__s, 1>; // Defined in bits/random.h
+#endif
}
/// @endcond
@@ -252,16 +288,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Lemire's nearly divisionless algorithm.
// Returns an unbiased random number from __g downscaled to [0,__range)
// using an unsigned type _Wp twice as wide as unsigned type _Up.
- template<size_t _Bits, typename _Wp, typename _Urbg, typename _Up>
- static _Up
- _S_nd(_Urbg& __g, _Up __range)
+ template<size_t _Bits, typename _Urbg>
+ static typename __detail::_Select_uint_least_t<_Bits>::type
+ _S_nd(_Urbg& __g, typename __detail::_Select_uint_least_t<_Bits>::type
__range)
{
+ using _Up = typename __detail::_Select_uint_least_t<_Bits>::type;
+ using _Wp = typename __detail::_Select_uint_least_t<2 * _Bits>::type;
using _Up_traits = __gnu_cxx::__int_traits<_Up>;
using _Wp_traits = __gnu_cxx::__int_traits<_Wp>;
static_assert(!_Up_traits::__is_signed, "U must be unsigned");
static_assert(!_Wp_traits::__is_signed, "W must be unsigned");
static_assert(_Wp_traits::__digits == (2 * _Up_traits::__digits),
"W must be twice as wide as U");
+
constexpr auto __min = _Urbg::min();
constexpr _Up __mask = (_Bits < _Up_traits::__digits)
? (_Up(1) << _Bits) - 1 : ~_Up(0);
@@ -322,24 +361,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
-#if defined __UINT64_TYPE__ && defined __UINT32_TYPE__ &&
__has_builtin(__builtin_popcountg)
+#if __has_builtin(__builtin_popcountg)
constexpr auto __bits = __builtin_popcountg(__urngrange);
if constexpr (__detail::_Power_of_2(__urngrange + 1) && __bits <=
32)
- {
- // __urng produces values that use less or equal to 32-bits,
- // so use 64-bit integers to downscale to desired range.
- __UINT32_TYPE__ __u32erange = __uerange;
- __ret = _S_nd<__bits, __UINT64_TYPE__>(__urng, __u32erange);
- }
+ // __urng produces values that use less or equal to 32-bits,
+ // so 64-bit integer is sufficient to downscale to desired range.
+ __ret = _S_nd<__bits>(__urng, __uerange);
# if __SIZEOF_INT128__
else if constexpr (__detail::_Power_of_2(__urngrange + 1) && __bits
<= 64)
- {
- // __urng produces values that use less or equal to 64-bits,
- // so use 128-bit integers to downscale to desired range.
- __UINT64_TYPE__ __u64erange = __uerange;
- __ret = __extension__ _S_nd<__bits, unsigned __int128>(
- __urng, __u64erange);
- }
+ // __urng produces values that use less or equal to 64-bits,
+ // so use 128-bit integer is sufficeint to downscale to desired
range.
+ __ret = __extension__ _S_nd<__bits>(__urng, __uerange);
# endif
else
#endif
--
2.55.0
