https://gcc.gnu.org/g:675b6856ca66366632598cb0f5ccedbb337ccc0b
commit r17-4533-g675b6856ca66366632598cb0f5ccedbb337ccc0b Author: Tomasz Kamiński <[email protected]> Date: Tue Jul 28 11:13:26 2026 +0200 libstdc++: Use of Lemire's algorithm for targets that do not provide __UINT32_TYPE__ && __UINT64_TYPE__. 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. Reviewed-by: Jonathan Wakely <[email protected]> Diff: --- libstdc++-v3/include/bits/random.h | 34 ++-------------- libstdc++-v3/include/bits/uniform_int_dist.h | 61 +++++++++++++++++++++------- 2 files changed, 51 insertions(+), 44 deletions(-) diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h index 1a2900e2b9d8..e2b29961bd92 100644 --- a/libstdc++-v3/include/bits/random.h +++ b/libstdc++-v3/include/bits/random.h @@ -569,36 +569,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) \ +// Primary 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 f19f051b8052..554a82cd72ee 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,14 @@ _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); @@ -324,23 +358,22 @@ _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 no more than 32-bits, - // so use 64-bit integers to downscale to desired range. + // so 64-bit integer is sufficient to downscale to desired range. __UINT32_TYPE__ __u32erange = __uerange; - __ret = _S_nd<__bits, __UINT64_TYPE__>(__urng, __u32erange); + __ret = _S_nd<__bits>(__urng, __u32erange); } # if __SIZEOF_INT128__ else if constexpr (__detail::_Power_of_2(__urngrange + 1) && __bits <= 64) { // __urng produces values that use no more than 64-bits, - // so use 128-bit integers to downscale to desired range. + // so 128-bit integer is sufficient to downscale to desired range. __UINT64_TYPE__ __u64erange = __uerange; - __ret = __extension__ _S_nd<__bits, unsigned __int128>( - __urng, __u64erange); + __ret = _S_nd<__bits>(__urng, __u64erange); } # endif else
