[PATCH] libstdc++: Prevent hanging of uniform_int_distribution for non-conforming engines [PR118665]

[Tomasz Kaminski]

On Wed, Jul 22, 2026 at 4:02 PM Tomasz Kamiński <tkaminsk@redhat.com> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260722/77818207/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: benchmark.cpp
Type: text/x-c++src
Size: 1187 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260722/77818207/attachment-0001.bin>