@@ -4521,15 +4521,39 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
- if (__first != __last)
- for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
- {
- // XXX rand() % N is not uniformly distributed
- _RandomAccessIterator __j = __first
- + std::rand() % ((__i - __first) + 1);
- if (__i != __j)
- std::iter_swap(__i, __j);
- }
+ if (__first == __last)
+ return;
+
+#if RAND_MAX < __INT_MAX__
+ if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
+ {
+ // Use a xorshift implementation seeded by two calls to rand()
+ // instead of using rand() for all the random numbers needed.
+ unsigned __xss
+ = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
+ for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+ {
+ __xss += !__xss;
+ __xss ^= __xss << 13;
+ __xss ^= __xss >> 17;
+ __xss ^= __xss << 5;
+ _RandomAccessIterator __j = __first
+ + (__xss % ((__i - __first) + 1));
+ if (__i != __j)
+ std::iter_swap(__i, __j);
+ }
+ return;
+ }
+#endif
+
+ for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+ {
+ // XXX rand() % N is not uniformly distributed
+ _RandomAccessIterator __j = __first
+ + (std::rand() % ((__i - __first) + 1));
+ if (__i != __j)
+ std::iter_swap(__i, __j);
+ }
}
/**
new file mode 100644
@@ -0,0 +1,24 @@
+// { dg-do run }
+// { dg-options "-Wno-deprecated-declarations" }
+
+// Bug 88935 std::random_shuffle does not work if the sequence
+// is longer than RAND_MAX elements
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+int main()
+{
+ const std::size_t N = 30000;
+ std::vector<unsigned char> v(N, (unsigned char)0);
+ std::fill(v.begin() + (N / 5 * 4), v.end(), (unsigned char)1);
+ std::random_shuffle(v.begin(), v.end());
+ double sum = 0;
+ for (std::size_t i = 0; i < v.size(); ++i)
+ {
+ sum += v[i];
+ if (i > 0 && i % (N / 100) == 0)
+ VERIFY( (sum / i) < 0.3 );
+ }
+}
This is a revised version of a patch Giovanni submitted some years ago, which has been unreviewed until recently. Tested x86_64-linux. I would like to push this to trunk. -- >8 -- When RAND_MAX is small and the number of elements being shuffled is close to it, we get very uneven distributions in std::random_shuffle. This uses a simple xorshift generator seeded by std::rand if we can't rely on std::rand itself. libstdc++-v3/ChangeLog: PR libstdc++/88935 * include/bits/stl_algo.h (random_shuffle) [RAND_MAX < INT_MAX]: Use xorshift instead of rand(). * testsuite/25_algorithms/random_shuffle/88935.cc: New test. Co-authored-by: Jonathan Wakely <jwakely@redhat.com> Signed-off-by: Giovanni Bajo <rasky@develer.com> --- libstdc++-v3/include/bits/stl_algo.h | 42 +++++++++++++++---- .../25_algorithms/random_shuffle/88935.cc | 24 +++++++++++ 2 files changed, 57 insertions(+), 9 deletions(-) create mode 100644 libstdc++-v3/testsuite/25_algorithms/random_shuffle/88935.cc