[PATCH 2/2] libstdc++: Use of Lemire's algorithm for targets that do not provide __UINT32_TYPE__ && __UINT64_TYPE__.
Jonathan Wakely
jwakely@redhat.com
Mon Sep 21 14:28:41 GMT 2026
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");
>+
> 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
>
>
More information about the Libstdc++
mailing list