On Mon, Sep 21, 2026 at 4:37 PM Jonathan Wakely <[email protected]> wrote:
> On Mon, 21 Sep 2026 at 15:28 +0100, Jonathan Wakely wrote:
> >On Tue, 28 Jul 2026 at 11:33 +0200, Tomasz Kamiński wrote:
> >>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.
> >
> >We use both __UINT32_TYPE__ and __UINT64_TYPE__ unconditionally
> >elsewhere, so we could have just dropped the #ifdef preprocessor
> >checks for them. They're always defined.
> >
> >But I agree that the change makes the code clearer anyway.
> >
> >>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
> >
> >Thanks for checking it.
> >
> >>Tested on x86_64 linux. Additionally all *random* tested with all
> >>standard modes, -m32 and debug. OK for trunk?
> >
> >OK with fixes for the grammar and spelling issues noted below.
> >
> >>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.
> >
> >"Primary"
> >
> >>+#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");
>
> These static assertions don't seem useful now. They are guaranteed to
> be true, unless _Select_uint_least_t is completely broken.
>
Thanks removed them and _Wp_traits that are no longer used locally, and
will commit without them.
The last one is technically incorrect, as _Select_uint_least_t<2 * _Bits>
may
have more than two time of _Select_uint_least_t<2 * _Bits>. That's what
least means,
so good catch.
>
> >>+
> >> 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,
> >
> >"that use no more than 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,
> >
> >"that use no more than 64 bits,"
> >
> >>+ // so use 128-bit integer is sufficeint to downscale to
> desired range.
> >
> >"so use" -> "so"
> >
> >"sufficient"
> >
> >>+ __ret = __extension__ _S_nd<__bits>(__urng, __uerange);
> >># endif
> >> else
> >>#endif
> >>--
> >>2.55.0
> >>
> >>
>
>
