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
