[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:37:46 GMT 2026
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.
>>+
>> 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