On Wed, Jul 22, 2026 at 4:02 PM Tomasz Kamiński <[email protected]> wrote:
> Since r11-3757-g98c37d3bacbb2f the uniform_int_distribution uses Lemire's
> algorithm for engines outputting power of two range. As this algorithm
> (in-contrast to other) rejects low outputs from incoming generator, this
> change lead to hangs (due infinite loop) when distribution was mixed
> with non-uniform generator, that returned 0 constantly. Such usage has
> undefined behavior according to standard, however didn't lead to hangs
> prior GCC 11 or (reportedly) standard libraries.
>
> This patch, addresses above by changing the (slower) rejection path of the
> algorithm, to alternate between rejecting low/high value of the range. The
> output remains uniform, as only number of values rejected from span is
> important. In consequence, of above the algorithm finishes successfully
> for any generator that returns same value constantly.
>
> While, it is possible to create an generator that would still lead to
> infinite loop, by alternating between low and high values, I believe
> this is inherent property on any algorithm that rejects some of the
> engine's outputs.
>
> PR libstdc++/118665
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/uniform_int_dist.h
> (uniform_int_distribution::_S_nd): Alternate between rejecting
> from beginning/end of the range.
> *
> testsuite/26_numerics/random/uniform_int_distribution/operators/pr118665.cc:
> New test.
> ---
> I have benchmarked this locally, measuring time required to generate
> 1000 values from distribution. OLD is before the change, NEW is after:
>
Attaching the benchmark code.
> -- NEW
> --------------------------------------------------------
> Benchmark Time CPU Iterations
> --------------------------------------------------------
> BM_mt19937 2778 ns 2762 ns 241094
> BM_philox4x32 4175 ns 4151 ns 183153
> BM_Constant 343 ns 342 ns 2009755
> -- OLD
> --------------------------------------------------------
> Benchmark Time CPU Iterations
> --------------------------------------------------------
> BM_mt19937 2982 ns 2970 ns 233294
> BM_philox4x32 4181 ns 4167 ns 167653
> BM_Constant 337 ns 336 ns 2070099
>
> The Constant is engine that returns a value of volatile
> variable (otherwise it was optimized to constant by compiler).
>
> Tested onx x86_64 linux locally. Additionally *random* test passed
> in all standard modes, debug, -m32. OK for trunk?
>
> Should we backport ths (after letting it bake for sometime) up to 13?
> This was reported as regression. It will impact the result observed
> from distribution, but not as much as introducing Lemiere's algoritghm
> did.
>
> libstdc++-v3/include/bits/uniform_int_dist.h | 9 ++++++
> .../operators/pr118665.cc | 28 +++++++++++++++++++
> 2 files changed, 37 insertions(+)
> create mode 100644
> libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/pr118665.cc
>
> diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h
> b/libstdc++-v3/include/bits/uniform_int_dist.h
> index 9c5514c7c13..8ffce793482 100644
> --- a/libstdc++-v3/include/bits/uniform_int_dist.h
> +++ b/libstdc++-v3/include/bits/uniform_int_dist.h
> @@ -273,6 +273,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> _Up __threshold = -__range % __range;
> while (__low < __threshold)
> {
> + // Algorithm is modified to alternate between rejecting
> from
> + // begining (__low) and end (__high) of the range. This
> + // guarantee stop for non-uniform engines that always
> results
> + // in __low value.
> + __product = _Wp(__g()) * _Wp(__range);
> + _Up __high = _Up(__product);
> + if (__high <= _Up_traits::__max - __threshold)
> + break;
> +
> __product = _Wp(__g()) * _Wp(__range);
> __low = _Up(__product);
> }
> diff --git
> a/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/pr118665.cc
> b/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/pr118665.cc
> new file mode 100644
> index 00000000000..979d5fdfca9
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/pr118665.cc
> @@ -0,0 +1,28 @@
> +// { dg-do run { target c++11 } }
> +// { dg-require-cstdint "" }
> +
> +#include <random>
> +#include <testsuite_hooks.h>
> +
> +class Constant {
> +public:
> + using result_type = unsigned;
> + static constexpr result_type min() { return 0u; }
> + static constexpr result_type max() { return ~0u; }
> +
> + // always return 0
> + result_type operator()() {
> + ++calls;
> + VERIFY( calls < 1000 );
> + return 0;
> + }
> +
> + unsigned calls = 0;
> +};
> +
> +int main()
> +{
> + Constant gen;
> + std::uniform_int_distribution<int> dist(0, 42);
> + dist(gen);
> +}
> --
> 2.55.0
>
>
#include <benchmark/benchmark.h>
#include <random>
// ~/gcc/17/bin/g++ benchmark.cpp -std=c++26 -lbenchmark -O2 -DUSE_PROXY -o a.proxy
class Constant {
public:
using result_type = unsigned;
static constexpr result_type min() { return 0u; }
static constexpr result_type max() { return ~0u; }
// always return 0
result_type operator()() { return val; }
static volatile unsigned val;
};
#ifdef CONSTANT
volatile unsigned Constant::val = CONSTANT;
#else
volatile unsigned Constant::val = 13;
#endif
template<typename URBG>
static void Benchmark(URBG& urbg, benchmark::State& state)
{
std::uniform_int_distribution<int> dist(0, 42);
for (auto _ : state) {
int sum = 0;
for (int i = 0; i < 1000; ++i)
sum += dist(urbg);
benchmark::DoNotOptimize(sum);
}
}
static void BM_mt19937(benchmark::State& state) {
std::mt19937 gen;
Benchmark(gen, state);
}
BENCHMARK(BM_mt19937);
static void BM_philox4x32(benchmark::State& state) {
std::philox4x32 gen;
Benchmark(gen, state);
}
BENCHMARK(BM_philox4x32);
static void BM_Constant(benchmark::State& state) {
Constant gen;
Benchmark(gen, state);
}
BENCHMARK(BM_Constant);
BENCHMARK_MAIN();
