PCG Random Number Generation, Java Edition

PCG is a family of simple fast space-efficient statistically good algorithms for random number generation. Unlike many general-purpose RNGs, they are also hard to predict.

This implementation is based on Melissa E. O'Neill C code and paper PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation.

You are highly advised to check out her website for further information: www.pcg-random.org Java implementation featuring a 64 bit state RNG with 32 bit output.

Table taken from http://www.pcg-random.org/.

Features

• High quality number generator
• Thread safe
• Quick advance and rewind allowing to reset the generator to a previous state or to skip the next k numbers
• Calculate the distance between different generator instances
• Extends the random interface to conveniently uses methods like Collection.sort
• Allows to split instances like SplittableRandom

Note: The PCG family is not cryptographically secure!

Usage

1. Either download the pre build jar files and add them to your build path manually
2. Use Maven, gradle or ivy via maven central

<!-- Java 10 Version -->
<dependency>
  <groupId>dev.brachtendorf</groupId>
  <artifactId>pcg-java-10</artifactId>
  <version>1.0.1</version>
</dependency>

<!-- Java 8 Version -->
<dependency>
  <groupId>dev.brachtendorf</groupId>
  <artifactId>pcg-java-8</artifactId>
  <version>1.0.1</version>
</dependency>

Several different random number generators are bundled in this package. Pick one which suits your needs

// Uniquely seed
PcgRR rng = new PcgRR();

int randomInt = rng.nextInt();
double nextGaus = rng.nextGaus();

Choose the correct generator

• 3 separate implementations with different synchronization approaches were implemented and benchmarked with synchronization outperforming locks and cas instructions by far. ** when speaking about less statistical performance we are still way beyond everything generated by java random or mt!

Benchmark

Statistical and performance benchmarks were performed using pract rand and Oracle's jmh harness respectively

Statistical Quality (performed on nextInt only)

PractRand Test Suite

rng=PcgRSUFast stdin32, seed=Random
length= 64 gigabytes (2^36 bytes), time= 2351 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+0,13-0,T)                  R=  +1.0  p = 0.335     normal           
  BCFN(2+1,13-0,T)                  R=  -2.7  p = 0.865     normal           
  BCFN(2+2,13-0,T)                  R=  +0.7  p = 0.386     normal           

PracRand was advertised by pcg-random.com and according to it's docs outperforms dieharder and testu01 in it's analysis. I mainly choose it because it was already prebuild for windows and I did not have to switch to linux to build the other tools myself. You are more than welcome to go ahead and run benchmarks using TestU01 or Dieharder and report back.

Performance

Performed with OpenJDKs jmh benchmark harness testing the throughput of nextInt. Higher numbers are better Jmh parameters

• Single: java -jar benchmarks.jar -f 5 -tu us -w15
• Multi:  java -jar benchmarks.jar -f 5 -tu us -w15 -t 4 -e "Fast|Splittable"

wmic:root\cli>cpu get caption, name, numberofcores, maxclockspeed
Caption                               MaxClockSpeed  Name                                     NumberOfCores
Intel64 Family 6 Model 94 Stepping 3  3301           Intel(R) Core(TM) i5-6600 CPU @ 3.30GHz  4

Single threading

Be aware of the axis scales. The PCG family performs really well in single threaded environments. In multithreading the CAS instruction is capping the execution speed. Note that while JdkRandom and PCU's are thread safe they rely on Compare And Swap instructions which, if contested (higher contention) result in a lower throughput (In other words the more threads try to access a thread safe instance the slower it will overall get).

Multi threading

Next take a look at the thread safe implementation under high congestion (the synchronized block, lock or cas instructions are constantly contested). As you can see under really high stress the locked version performs the best, but does it really warrant the trade off to be more than 4 times slower if it does not get raced? Probably not but it has to be decided on a case by case basis.

To avoid object creation overhead a good way to implement high throughput rngs for multi threaded environments is to use make use of the PcgRSFast implementation combined with the Threadlocal class instance to be used within executor pools. (TODO link to GA for example)

Note

The code is provided as is with no guarantee on correct implementation or liability. Please check it for yourself and if you find any errors open an issue and optionally a pull request. It would be nice if you let me know if the code was to use for your.