Re: [PATCH 3/9] test-mergesort: add test subcommand

René Scharfe [off-list ref] writes:

Repeatable tests are not essential (the original paper didn't mention
seeding), but shouldn't be much trouble to implement and would simplify
comparisons across versions, systems and among testers.

The only downside I can think of is that it may perhaps also simplify
over-fitting, i.e. I might find micro-tweaks that only work for our
specific rand() sequence and then misinterpret them as general
improvements..

Yup, I think you summarized the pros-and-cons nicely.

Am 03.10.21 um 19:33 schrieb Junio C Hamano:

René Scharfe [off-list ref] writes:

quoted

Repeatable tests are not essential (the original paper didn't mention
seeding), but shouldn't be much trouble to implement and would simplify
comparisons across versions, systems and among testers.

The only downside I can think of is that it may perhaps also simplify
over-fitting, i.e. I might find micro-tweaks that only work for our
specific rand() sequence and then misinterpret them as general
improvements..

Yup, I think you summarized the pros-and-cons nicely.

Seeing that the series is in next already, here's a bonus patch for
that.

--- >8 ---

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

Use MINSTD to generate pseudo-random numbers consistently instead of
using rand(3), whose output can vary from system to system, and reset
its seed before filling in the test values.  This gives repeatable
results across versions and systems, which simplifies sharing and
comparing of results between developers.

Signed-off-by: René Scharfe <redacted>
---
 t/helper/test-mergesort.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 43ec74e2d3..8d128ae437 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c

@@ -2,6 +2,12 @@
 #include "cache.h"
 #include "mergesort.h"

+static unsigned int minstd_rand(unsigned int *state)
+{
+	*state = (uint64_t)*state * 48271 % 2147483647;
+	return *state;
+}
+
 struct line {
 	char *text;
 	struct line *next;

@@ -60,8 +66,9 @@ static void dist_sawtooth(int *arr, int n, int m)
 static void dist_rand(int *arr, int n, int m)
 {
 	int i;
+	unsigned int seed = 1;
 	for (i = 0; i < n; i++)
-		arr[i] = rand() % m;
+		arr[i] = minstd_rand(&seed) % m;
 }

 static void dist_stagger(int *arr, int n, int m)

@@ -81,8 +88,9 @@ static void dist_plateau(int *arr, int n, int m)
 static void dist_shuffle(int *arr, int n, int m)
 {
 	int i, j, k;
+	unsigned int seed = 1;
 	for (i = j = 0, k = 1; i < n; i++)
-		arr[i] = (rand() % m) ? (j += 2) : (k += 2);
+		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
 }

 #define DIST(name) { #name, dist_##name }
--

2.33.0

Use MINSTD to generate pseudo-random numbers consistently instead of
using rand(3), whose output can vary from system to system, and reset
its seed before filling in the test values.  This gives repeatable
results across versions and systems, which simplifies sharing and
comparing of results between developers.

Signed-off-by: René Scharfe <redacted>
---
Change: Use uint32_t to avoid relying on unsigned int being exactly
4 bytes wide.  D'oh!

 t/helper/test-mergesort.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 29758cf89b..c6fa816be3 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c

@@ -2,6 +2,12 @@
 #include "cache.h"
 #include "mergesort.h"

+static uint32_t minstd_rand(uint32_t *state)
+{
+	*state = (uint64_t)*state * 48271 % 2147483647;
+	return *state;
+}
+
 struct line {
 	char *text;
 	struct line *next;

@@ -60,8 +66,9 @@ static void dist_sawtooth(int *arr, int n, int m)
 static void dist_rand(int *arr, int n, int m)
 {
 	int i;
+	uint32_t seed = 1;
 	for (i = 0; i < n; i++)
-		arr[i] = rand() % m;
+		arr[i] = minstd_rand(&seed) % m;
 }

 static void dist_stagger(int *arr, int n, int m)

@@ -81,8 +88,9 @@ static void dist_plateau(int *arr, int n, int m)
 static void dist_shuffle(int *arr, int n, int m)
 {
 	int i, j, k;
+	uint32_t seed = 1;
 	for (i = j = 0, k = 1; i < n; i++)
-		arr[i] = (rand() % m) ? (j += 2) : (k += 2);
+		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
 }

 #define DIST(name) { #name, dist_##name }
--

2.33.0

On Fri, Oct 08, 2021 at 06:04:42AM +0200, René Scharfe wrote:

Use MINSTD to generate pseudo-random numbers consistently instead of
using rand(3), whose output can vary from system to system, and reset
its seed before filling in the test values.  This gives repeatable
results across versions and systems, which simplifies sharing and
comparing of results between developers.

Nice. As a bonus, I noticed that Coverity complains about the use of
rand() as a security red-flag (even though of course we don't care about
its quality here). This should get rid of it by hiding the same thing in
a custom implementation. ;)

We have a similar LCG in t/helper/test-genrandom.c, but I don't think
there's any reason this needs to be factored into a shared one. And in
particular, I'd be loathe to change the genrandom one, as it may create
small bugs in the test suite (cases where we rely on hashes of the data
having particular attributes).

-Peff

On Fri, Oct 08 2021, René Scharfe wrote:

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.

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...).

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.

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

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.

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.

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é

On Fri, Oct 08 2021, René Scharfe wrote:

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

quoted

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.

Yes, it has zero applicablility here.

It was just an aside/FYI since we were on the topic of the
cross-platformness of rand().

I.e. one might assume that for the general problem of seeding something
randomly cross-platform one had to ship a rand(), but usually at least
perl is there ahead of you, and since it has its own rand()...