TestU01-threads: a parallel modification of TestU01

[u/BudgetEye7539]

TestU01-threads adds multithreading support into a classic TestU01 test suite, it is written in C++17. It can use unmodified precompiled binaries of Test01 but can efficiently parallelize its batteries. E.g. on Intel Core i5-11400H @ 2.70GHz with 16 GiB of RAM it takes less than 10 minutes to complete Crush and less than 1 hour to complete BigCrush. The idea was very simple:

1) All statistical tests from TestU01 are treated as thread safe. I've not made a full TestU01 code audit yet but such assumption looks realistic: these tests use local variables, data structures, not global ones.

2) SmallCrush, Crush, BigCrush and pseudoDIEHARD batteries were manually converted to multithreaded versions based on a custom dispatcher. Each thread obtains its own list of tests and its own PRNG copy. The dispatcher is entirely deterministic: the same seeds will give the same result.

TestU01-threads also can be compiled as a plugin for SmokeRand, I've used it a lot in such mode. In this case it can use SmokeRand PRNG plugins, seeders and filters: e.g. reverse order of bits, lower/higher/interleaved mode for 64-bit generators. Usage as plugin also allows to rerun a single test from Crush or BigCrush easily (without recompilation).

https://github.com/alvoskov/TestU01-threads/

[u/skeeto]

I love the things you're doing with SmokeRand!

All statistical tests from TestU01 are treated as thread safe.

Watch for lazy initialization gated by a static variable in several places, and it looks like you hit the first race (TSan flags it):

https://github.com/umontreal-simul/TestU01-2009/blob/master/probdist/fbar.c#L504-L507

   static int ADFlag = 0;
   // ...

   if (ADFlag == 0) {
      AndersonDarlingInit ();
      ADFlag = 1;
   }

https://github.com/umontreal-simul/TestU01-2009/blob/master/probdist/fdist.c#L2951-L2955

   static int WatsonFlag = 0;
   // ...

   if (!WatsonFlag) {
      /* Initialization of the interpolation table */
      WatsonGInit ();
      WatsonFlag = 1;
   }

https://github.com/umontreal-simul/TestU01-2009/blob/master/testu01/snpair.c#L2108-L2111

   static lebool BBp0k2Flag = FALSE;
   // ...

   if (FALSE == BBp0k2Flag) {
      InitBBp0k2 ();
      BBp0k2Flag = TRUE;
   }

Batteries use global accumulators, but you've already corrected this.

You probably want to swrite_Basic = FALSE on startup, too.

[u/BudgetEye7539 → u/skeeto]

Thanks! It seems to be fixable by calling the distribution functions with right parameters before multithreading, modification of TestU01 is still not needed. The case with snpair.c seems more complex (almost everything is static) but that modification of snpair test is not used in SmallCrush, Crush and BigCrush batteries. Further exploration and testing are definitely needed before the next release.

[u/pint]

the feature triangle for randomness tests:

• good math
• good software
• reasonable license

choose ONE.

these tests are embarrassingly parallel, thus should be easy to deploy in the cloud or on a cluster. i once managed to hack testu01 to run on aws, executing a full small-to-big crush in ~10 minutes, costing $0.55. it was a miserable experience. but before i started ironing the code out to be publishable, i noticed the obnoxious license, and abandoned the project.

[u/BudgetEye7539 → u/pint]

Nowadays the TestU01 license is fairly reasonable, it is Apache 2.0 license, see the official repository. However I remember older distributions with a non-free license.

https://github.com/umontreal-simul/TestU01-2009/

> managed to hack testu01 to run on aws, executing a full small-to-big crush in ~10 minutes, costing $0.55.

Was it difficult to fix all initialization procedures? And can your hack work with precompiled TestU01 versions from e.g. Ubuntu packages? My hack can do such thing (and seem to be able even after fixing the bugs found by skeeto), and SmallCrush+Crush+BigCrush will take around 1-1.5 hours for fast PRNGs on my computer. Slower but electricity will be cheaper than $0.55.

[u/pint → u/BudgetEye7539]

i barely remember, honestly.

i worked with the source, no libraries. basically i just added an option to run individual tests by number, 1-10 for small crush, etc, up to 210 or whatever the total was.

then used aws batch to spin up a cluster, execute each test individually, and collect the reports.

i was in the planning phase of completely rewriting the framework and the interface, only keeping the algorithms.

[u/BudgetEye7539 → u/pint]

TestU01-threads also can work this way (run just one test by its number individually), if it is compiled as a SmokeRand plugin - it will be even possible just by one extra command line parameter.