JEP 356: Enhanced Pseudo-Random Number Generators

AuthorGuy Steele
OwnerJim Laskey
TypeFeature
ScopeSE
StatusIntegrated
Release17
Componentcore-libs / java.util
Discussioncore dash libs dash dev at openjdk dot java dot net
EffortM
DurationM
Reviewed byBrian Goetz
Endorsed byBrian Goetz
Created2017/12/07 19:09
Updated2021/04/05 19:07
Issue8193209

Summary

Provide new interface types and implementations for pseudorandom number generators (PRNGs), including jumpable PRNGs and an additional class of splittable PRNG algorithms (LXM).

Goals

Non-Goals

It is not a goal to provide implementations of numerous other PRNG algorithms, only to provide a framework that can accommodate other PRNG algorithms. However, we have added three common algorithms that have already been widely deployed in other programming language environments.

Success Metrics

The output of the new LXM algorithms passes the existing well-known TestU01 and PractRand test suites.

Jumpable and leapable PRNG algorithms pass tests that verify the commutativity of certain operations.

Motivation

We focus on five areas for improvement in the area of pseudorandom number generators in Java:

Description

We provide a new interface, RandomGenerator, which supplies a uniform API for all existing and new PRNGs. RandomGenerators provide methods named ints, longs, doubles, nextBoolean, nextInt, nextLong, nextDouble, and nextFloat, with all their current parameter variations.

We provide four new specialized RandomGenerator interfaces:

We provide a new class RandomGeneratorFactory which is used to locate and construct instances of RandomGenerator implementations. The RandomGeneratorFactory uses the ServiceLoader.Provider API to register RandomGenerator implementations.

We have refactored Random, ThreadLocalRandom, and SplittableRandom so as to share most of their implementation code and, furthermore, make that code reusable by other algorithms as well. This refactoring creates underlying non-public abstract classes AbstractRandomGenerator, AbstractSplittableRandomGenerator, AbstractJumpableRandomGenerator, AbstractLeapableRandomGenerator, and AbstractArbitrarilyJumpableRandomGenerator, each provide only implementations for methods nextInt(), nextLong(), and (if relevant) either split(), or jump(), or jump() and leap(), or jump(distance). After this refactoring, Random, ThreadLocalRandom, and SplittableRandom inherit the RandomGenerator interface. Note that because SecureRandom is a subclass of Random, all instances of SecureRandom also automatically support the RandomGenerator interface, with no need to recode the SecureRandom class or any of its associated implementation engines.

We also added underlying non-public classes that extend AbstractSplittableRandomGenerator (and therefore implement SplittableRandomGenerator and RandomGenerator) to support six specific members of the LXM family of PRNG algorithms:

The structure of the central nextLong (or nextInt) method of an LXM algorithm follows a suggestion in December 2017 by Sebastiano Vigna that using one LCG subgenerator and one xor-based subgenerator (rather than two LCG subgenerators) would provide a longer period, superior equidistribution, scalability, and better quality. Each of the specific implementations here combines one of the best currently known xor-based generators (xoroshiro or xoshiro, described by Blackman and Vigna in "Scrambled Linear Pseudorandom Number Generators", ACM Trans. Math. Softw., 2021) with an LCG that uses one of the best currently known multipliers (found by a search for better multipliers in 2019 by Steele and Vigna), and then applies a mixing function identified by Doug Lea. Testing has confirmed that the LXM algorithm is far superior in quality to the SplitMix algorithm (2014) used by SplittableRandom.

We also provide implementations of these widely-used PRNG algorithms:

The non-public abstract implementations mentioned above may be supplied as part of a random number implementor SPI in the future.

This suite of algorithms provide Java programmers with a reasonable range of tradeoffs among space, time, quality, and compatibility with other languages.

Alternatives

We considered simply introducing new interfaces while leaving the implementations of Random, ThreadLocalRandom, and SplittableRandom as is. This would help to make PRNG objects more easily interchangeable but would not make it any easier to implement them.

We considered refactoring Random, ThreadLocalRandom, and SplittableRandom without changing their functionality or adding any new interfaces. We believe this would reduce their overall memory footprint, but do nothing to make future PRNG algorithms easier to implement or use.

Testing

Risks and Assumptions

We believe this is a medium project and the risks are minimal. Probably
the largest burden has been crafting the specification and the second-largest has been testing.

Care has been give to ensure the behaviour of legacy random number generators has not been affected.