This patch apply's the Lemire's algorithm to all generators that emit values
in range which size is power of two (2^_Bits), instead only 2^32 and 2^64.
This is achieved by masking the result of conversion of __product to lowest
_Bits. If _Bits is equal to bitwidth of _Up type, the bitand with all set
mask is optimized out by compilers.
libstdc++-v3/ChangeLog:
* include/bits/uniform_int_dist.h
(uniform_int_distribution::operator()): Use _S_nd (Lemire's
algorithm) if __urngrange is power of two.
(uniform_int_distribution::_S_nd): Add _Bits parameter. Mask
the result of conversion of __product to _Up to lowest _Bits.
*
testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc:
Add testDiscreteDist for ranlux24 and ranlux48 engines.
---
This does not show much improvment for the standard ranlux enginies,
as the uniform_int_operations are dwarfed by the cost of running the
engine. However, for synthetic version of engines that reduces output
to 20 (BM_t20_mt19937) and 40 (BM_t40_mt19937_64) we see an expected
improvment. So this is not totally lost case.
Benchmark Trunk Fixes Patch
--------------------------------------
BM_mt19937 2.51 2.53 2.53
BM_t20_mt19937 4.89 4.9 2.66
BM_philox4x32 3.57 3.58 3.62
BM_ranlux24 39.4 39.5 39.4
BM_Constant32 0.322 0.323 0.323
BM_mt19937_64 1.61 1.62 1.61
BM_t40_mt19937_64 4.92 4.98 3.17
BM_philox4x64 3.13 3.12 3.19
BM_ranlux48 116 121 121
BM_Constant64 0.214 0.216 0.217
BM_minstd_rand 4.28 4.29 4.31
BM_knuth_b 7.85 7.88 7.91
* Fixes in the char above is trunk with following patches applied,
and this patch is measured on top of them.
https://gcc.gnu.org/pipermail/libstdc++/2026-July/067310.html
https://gcc.gnu.org/pipermail/libstdc++/2026-July/067350.html
Tested on powerpc64le and x86_64 linux. Additionally all *random*
tested with all standard modes, -m32 and debug. OK for trunk?
libstdc++-v3/include/bits/uniform_int_dist.h | 46 ++++++++++---------
.../operators/values.cc | 24 ++++++----
2 files changed, 40 insertions(+), 30 deletions(-)
diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h
b/libstdc++-v3/include/bits/uniform_int_dist.h
index 1b472e7b93a..6f29bd0a98c 100644
--- a/libstdc++-v3/include/bits/uniform_int_dist.h
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -252,7 +252,7 @@ _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<typename _Wp, typename _Urbg, typename _Up>
+ template<size_t _Bits, typename _Wp, typename _Urbg, typename _Up>
static _Up
_S_nd(_Urbg& __g, _Up __range)
{
@@ -263,15 +263,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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);
// reference: Fast Random Integer Generation in an Interval
// ACM Transactions on Modeling and Computer Simulation 29 (1), 2019
// https://arxiv.org/abs/1805.10941
_Wp __product = _Wp(__g() - __min) * _Wp(__range);
- _Up __low = _Up(__product);
+ _Up __low = _Up(__product) & __mask;
if (__low < __range)
{
- _Up __threshold = -__range % __range;
+ _Up __threshold = (-__range & __mask) % __range;
while (__low < __threshold)
{
// Algorithm is modified to alternate between rejecting from
@@ -279,15 +281,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// guarantee stop for non-uniform engines that always results
// in __low value.
__product = _Wp(__g() - __min) * _Wp(__range);
- _Up __high = _Up(__product);
- if (__high <= _Up_traits::__max - __threshold)
+ _Up __high = _Up(__product) & __mask;
+ if (__high <= __mask - __threshold)
break;
__product = _Wp(__g() - __min) * _Wp(__range);
- __low = _Up(__product);
+ __low = _Up(__product) & __mask;
}
}
- return __product >> _Up_traits::__digits;
+ return _Up(__product >> _Bits) & __mask;
}
};
@@ -320,25 +322,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
-#if defined __UINT64_TYPE__ && defined __UINT32_TYPE__
-#if __SIZEOF_INT128__
- if constexpr (__urngrange == __UINT64_MAX__)
+#if defined __UINT64_TYPE__ && defined __UINT32_TYPE__ &&
__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 exactly 64-bits,
- // so use 128-bit integers to downscale to desired range.
- __UINT64_TYPE__ __u64erange = __uerange;
- __ret = __extension__ _S_nd<unsigned __int128>(__urng,
- __u64erange);
- }
- else
-#endif
- if constexpr (__urngrange == __UINT32_MAX__)
- {
- // __urng produces values that use exactly 32-bits,
+ // __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<__UINT64_TYPE__>(__urng, __u32erange);
+ __ret = _S_nd<__bits, __UINT64_TYPE__>(__urng, __u32erange);
+ }
+# 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);
}
+# endif
else
#endif
{
diff --git
a/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc
b/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc
index fce14944d88..ebb02aa4912 100644
---
a/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc
+++
b/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc
@@ -50,27 +50,35 @@ void test01()
{
using namespace __gnu_test;
- std::mt19937 eng;
+ std::mt19937 mteng;
std::uniform_int_distribution<> uid1(0, 2);
- auto buid1 = std::bind(uid1, eng);
+ auto buid1 = std::bind(uid1, mteng);
testDiscreteDist<ARGS>(buid1, [](int n) { return uniform_int_pdf(n, 0, 2); }
);
std::uniform_int_distribution<> uid2(3, 7);
- auto buid2 = std::bind(uid2, eng);
+ auto buid2 = std::bind(uid2, mteng);
testDiscreteDist<ARGS>(buid2, [](int n) { return uniform_int_pdf(n, 3, 7); }
);
std::uniform_int_distribution<> uid3(1, 20);
- auto buid3 = std::bind(uid3, eng);
+ auto buid3 = std::bind(uid3, mteng);
testDiscreteDist<ARGS>(buid3, [](int n) { return uniform_int_pdf(n, 1, 20);
} );
- shifted<(std::uint64_t(1) << 16)> s16e;
- auto buid4 = std::bind(uid3, s16e);
+ std::ranlux24 r24eng;
+ auto buid4 = std::bind(uid3, r24eng);
testDiscreteDist<ARGS>(buid4, [](int n) { return uniform_int_pdf(n, 1, 20);
} );
- shifted<(std::uint64_t(1) << 32)> s32e;
- auto buid5 = std::bind(uid3, s32e);
+ std::ranlux48 r48eng;
+ auto buid5 = std::bind(uid3, r48eng);
testDiscreteDist<ARGS>(buid5, [](int n) { return uniform_int_pdf(n, 1, 20);
} );
+
+ shifted<(std::uint64_t(1) << 16)> s16e;
+ auto buid6 = std::bind(uid3, s16e);
+ testDiscreteDist<ARGS>(buid6, [](int n) { return uniform_int_pdf(n, 1, 20);
} );
+
+ shifted<(std::uint64_t(1) << 32)> s32e;
+ auto buid7 = std::bind(uid3, s32e);
+ testDiscreteDist<ARGS>(buid7, [](int n) { return uniform_int_pdf(n, 1, 20);
} );
}
int main()
--
2.55.0
