[PATCH] libstdc++: Prevent hanging of uniform_int_distribution for non-conforming engines [PR118665]
Tomasz Kaminski
tkaminsk@redhat.com
Thu Aug 27 17:06:26 GMT 2026
On Thu, Aug 27, 2026 at 5:11 PM Jonathan Wakely <jwakely@redhat.com> wrote:
> 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.
>
I really like explanation from here:
https://github.com/colmmacc/s2n/blob/7ad9240c8b9ade0cc3a403a732ba9f1289934abd/utils/s2n_random.c#L188
.
> 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}
>
And indeed, we need to leave a contingous range, so dropping from
begining or end of range mod size of generator (2^N) is required, but
it does not matter from which size. Maybe I should link above in commit
description.
> 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.
>
I recommend reading the link I mentioned above; it helped me to come
up with this solution.
>
> >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;
>
Good catch.
>
> >+ 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
> >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260827/0f8e079b/attachment-0001.htm>
More information about the Libstdc++
mailing list