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:
-- 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
