[PATCH] libstdc++: Prevent hanging of uniform_int_distribution for non-conforming engines [PR118665]
Jonathan Wakely
jwakely@redhat.com
Thu Aug 27 15:11:01 GMT 2026
On Wed, 22 Jul 2026 at 15:53 +0200, Tomasz Kamiński 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.
"prior to GCC 11 or with other 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.
Strictly speaking, it's not only the number of values that are
rejected, it has to be correctly distributed values. For example,
given a 2-bit URBG and range 3 we have product=x*3 and so for x in
[0,3] we get these {low,high} pairs:
{0,0}, {3,0}, {2,1}, {1,2}
We need to reject *one* of the pairs with high=0 because that way our
outputs will be 0,1,2 with equal probability. But it's important that
we reject either {0,0} or {3,0}, not {2,1} or {1,2}. So it's not
*only* the number of values that get rejected that matters.
Maybe say something like "The output remains uniform, as the same
number of values are rejected and the distribution of high-word values
is preserved even though different low-word values are rejected".
I don't have a proof that the distribution is preserved, but it's true
for the examples I've worked through with pencil and paper.
>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:
>-- 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
With fixed spelling+grammar:
// The algorithm is modified to alternate between rejecting
// from the beginning and end of the range. This guarantees
// that we stop for non-uniform engines that always result
// in values below the threshold.
I removed the mentions of (__low) and (__high) since those names
do not refer to where in the range the value occurs (see below).
>+ // in __low value.
>+ __product = _Wp(__g()) * _Wp(__range);
>+ _Up __high = _Up(__product);
The name __high is misleading, this is taking the low N/2 bits of
__product, not the high N/2 bits. It's exactly the same as the
assignment to __low further down. Should we just reuse __low here?
I don't think we need a second local variable.
i.e. I don't think the name "low" refers to rejecting values at the
low end of the range, I think it refers to the low word from
__product.
>+ if (__high <= _Up_traits::__max - __threshold)
I know we currently only use Lemire for uint32 and uint64, but if we
used it with _Up == uint16_t then __max - __threshold would promote to
signed int, and we could get a -Wsign-compare warning here.
Could you use <= _Up(_Up_traits::__max - __threshold) instead. Or
declare it where we declare __threshold above:
_Up __upper_threshold = _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
>
>
More information about the Libstdc++
mailing list