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

Commit Message

René Scharfe Oct. 8, 2021, 4:04 a.m. UTC

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 <[e-mail]>
---
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(-)

--
2.33.0

Comments

Jeff King Oct. 8, 2021, 4:17 a.m. UTC | #1

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

Ævar Arnfjörð Bjarmason Oct. 8, 2021, 7:23 a.m. UTC | #2

On Fri, Oct 08 2021, 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.
>
> Signed-off-by: René Scharfe <[e-mail]>
> ---
> 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 }

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.

René Scharfe Oct. 8, 2021, 5:30 p.m. UTC | #3

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é

Ævar Arnfjörð Bjarmason Oct. 8, 2021, 7 p.m. UTC | #4

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

> Am 08.10.21 um 09:23 schrieb Ævar Arnfjörð Bjarmason:
>> 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()...

Patch

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 }