Re: [PATCH 10/9 v2] test-mergesort: use repeatable random numbers

From: René Scharfe <l.s.r@web.de>
Date: Oct 8, 2021, 17:30 UTC
Message-ID: <c43ce422-0eba-0c7e-af01-a85cd948b0bb@web.de>
In-Reply-To: <87tuhsez93.fsf@evledraar.gmail.com>

Am 08.10.21 um 09:23 schrieb Ævar Arnfjörð Bjarmason:

Show 14 quoted lines

>
> Just to your upthread:
>
>     "Right, so we'd need to ship our own random number generator."
>
> I don't really think this matters in either case here, and if anything a
> flaky failure in this test would quickly point us in the right
> direction, as opposed to say having the N test_expect_success being run
> in rand() order or whatever.
>
> If we'd like results we can compare across platforms we're surely better
> of here running this in a loop with different per-platform srand()
> values N times for some high value of N, than we are in picking one
> "golden" distribution.

A mergesort bug that only causes invalid results for certain RNG seeds is not impossible, but unlikely. Portability of results is more useful for comparing the number of operations needed for different types of input, i.e. for performance work, not so much for correctness checking. (And those results need to be taken with enough salt to avoid micro- optimizing for specific distributions.)

Adding more rand and shuffle distributions, parameterized with different seeds, is certainly possible. Not sure what it would prove, though. We would visit a bigger part of the permutation space, but that thing is so huge (N!) that any reasonable sample is still small. That's why I added the unriffle modes, to find maxima.

Show 6 quoted lines

> But just on srand() and rand() use more generally in the test suite: I
> think it's fine to just assume that we can call srand()/rand() and get
> "predictable" results, because what we're really after in most cases is
> to avoid hard-to-diagnose flakyness. If as a result of random
> distribution we'll get a consistent failure on one OS (or the flakyness
> is just OpenBSD...).

I can't find any current use of rand() in t/, except perhaps t/helper/test-genrandom.c, which open-codes it to get reproducible results. I don't see how calling rand() instead would improve it.

Show 20 quoted lines

> Also generally: If you'd like "portable" rand() for a test just shell
> out to perl. I ran this on various Perl versions (oldest 5.12) on Debian
> Linux, OSX, Solaris & OpenBSD, all returned the same number for both:
>
>     ruby -e 'srand(1); puts rand'; perl -E 'srand(1); say $^V; say rand'
>
> Whereas a C program doing the same:
>
>     #include <stdio.h>
>     #include <stdlib.h>
>
>     int main(void)
>     {
>             srand(1);
>             printf("rand = %d\n", rand());
>             return 0;
>     }
>
> Returns different numbers an all, and on OpenBSD the number is different
> each time, per their well-known non-standard srand()/rand() behavior.

For test shell code that needs only a few random numbers this would be fine.

For test-genrandom it would also work, but I don't see any benefit in converting it to a scripting language.

Shelling out to a script to avoid a multiplication and a modulo in test-mergesort is not interesting, to put it mildly. A mode that sorts input from stdin like the sort subcommand, but returns the operation counts, might be useful if you want to test distributions generated by a Perl script or other data source of your choice.

René