On Thu, Aug 27, 2026 at 5:11 PM Jonathan Wakely <[email protected]> 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 > > > > > >
