This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Fix random_sample_n and random_shuffle when RAND_MAX is small


Il giorno mar 15 gen 2019 alle ore 03:38 Jonathan Wakely <jwakely@redhat.com>
ha scritto:

> On 12/12/18 22:31 +0100, Giovanni Bajo wrote:
> >Hello,
> >
> >we hit a bug today while cross-compiling a C++ program with mingw32:
> >if random_shuffle or random_sample_n are called with a sequence of
> >elements whose length is higher than RAND_MAX, the functions don't
> >behave as expected because they ignore elements beyond RAND_MAX. This
> >does not happen often on Linux where glibc defines RAND_MAX to 2**31,
> >but mingw32 (all released versions) relies on the very old msvcrt.lib,
> >where RAND_MAX is just 2**15.
> >
> >I found mentions of this problem in 2011
> >(
> http://mingw-users.1079350.n2.nabble.com/RAND-MAX-still-16bit-td6299546.html
> )
> >and 2006 (
> https://mingw-users.narkive.com/gAIO4G5V/rand-max-problem-why-is-it-only-16-bit
> ).
> >
> >I'm attaching a proof-of-concept patch that fixes the problem by
> >introducing an embedded xorshift generator, seeded with std::rand (so
> >that the functions still depend on srand — it looks like this is not
> >strictly required by the standard, but it sounds like a good thing to
> >do for backward compatibility with existing programs). I was wondering
> >if this approach is OK or something else is preferred.
>
> I'd prefer not to introduce that change unconditionally. The existing
> code works fine when std::distance(first, last) < RAND_MAX, and as we
> have random access iterators we can check that cheaply.
>
> We'd prefer a bug report in Bugzilla with a testcase that demonstrates
> the bug. A portable regression test for our testsuite might not be
> practical if it needs more than RAND_MAX elements, but one that runs
> for mingw and verifies the fix there would be needed.
>
> See https://gcc.gnu.org/contribute.html#patches for guidelines for
> submitting patches (and the rest of the page for other requirements,
> like copyright assignment or disclaimers).
>

Thanks Jonathan. We have opened a Bugzilla report here:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

In the bug, we highlighted that the current algorithm is also (less
severely) broken when the number of elements is less but close to RAND_MAX;
the farther you move away from RAND_MAX, the better it becomes. Would you
still prefer to have a different version of the algorithm, gated by a
comparison to RAND_MAX? Our patch fixes everything by switching to an
inline 64-bit PRNG which is seeded by std::rand().
-- 
Giovanni Bajo   ::  rasky@develer.com
Develer S.r.l.  ::  http://www.develer.com


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]