On Tue, Jul 28, 2026 at 11:35 AM Tomasz Kamiński <[email protected]>
wrote:
> 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.
>
Attached an benchmark file.
>
> 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
>
>
#include <benchmark/benchmark.h>
#include <random>
#include <cstdint>
// ~/gcc/17/bin/g++ benchmark.cpp -std=c++26 -lbenchmark -O2 -DUSE_PROXY -o a.proxy
template<typename T>
class Constant {
public:
using result_type = T;
static constexpr result_type min() { return T(0); }
static constexpr result_type max() { return ~T(0); }
// always return 0
result_type operator()() { return val; }
static volatile unsigned val;
};
#ifndef CONSTANT
# define CONSTANT 2050
#endif
template<typename T>
volatile unsigned Constant<T>::val = CONSTANT;
template<size_t Bits, typename Gen>
struct Trimmed {
using result_type = typename Gen::result_type;
static constexpr result_type mask = (result_type(1) << Bits) - 1u;
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return mask; }
result_type operator()() { return gen() & mask; }
Gen gen{};
};
template<typename URBG>
static void Benchmark(URBG& urbg, benchmark::State& state)
{
std::uniform_int_distribution<int> dist(0, 42);
for (auto _ : state) {
benchmark::DoNotOptimize(dist(urbg));
}
}
static void BM_mt19937(benchmark::State& state) {
std::mt19937 gen;
Benchmark(gen, state);
}
BENCHMARK(BM_mt19937);
static void BM_t20_mt19937(benchmark::State& state) {
Trimmed<20, std::mt19937> gen;
Benchmark(gen, state);
}
BENCHMARK(BM_t20_mt19937);
static void BM_philox4x32(benchmark::State& state) {
std::philox4x32 gen;
Benchmark(gen, state);
}
BENCHMARK(BM_philox4x32);
static void BM_ranlux24(benchmark::State& state) {
std::ranlux24 gen;
Benchmark(gen, state);
}
BENCHMARK(BM_ranlux24);
static void BM_Constant32(benchmark::State& state) {
Constant<std::uint32_t> gen;
Benchmark(gen, state);
}
BENCHMARK(BM_Constant32);
static void BM_mt19937_64(benchmark::State& state) {
std::mt19937_64 gen;
Benchmark(gen, state);
}
BENCHMARK(BM_mt19937_64);
static void BM_t40_mt19937_64(benchmark::State& state) {
Trimmed<40, std::mt19937_64> gen;
Benchmark(gen, state);
}
BENCHMARK(BM_t40_mt19937_64);
static void BM_philox4x64(benchmark::State& state) {
std::philox4x64 gen;
Benchmark(gen, state);
}
BENCHMARK(BM_philox4x64);
static void BM_ranlux48(benchmark::State& state) {
std::ranlux48 gen;
Benchmark(gen, state);
}
BENCHMARK(BM_ranlux48);
static void BM_Constant64(benchmark::State& state) {
Constant<std::uint64_t> gen;
Benchmark(gen, state);
}
BENCHMARK(BM_Constant64);
static void BM_minstd_rand(benchmark::State& state) {
std::minstd_rand gen;
Benchmark(gen, state);
}
BENCHMARK(BM_minstd_rand);
static void BM_knuth_b(benchmark::State& state) {
std::knuth_b gen;
Benchmark(gen, state);
}
BENCHMARK(BM_knuth_b);
BENCHMARK_MAIN();
