In this series, we will explain the pre-Java 17 random number API and the post-Java 17 unified API in detail. We will also analyze the random number characteristics and implementation ideas to help you understand why there are so many random number algorithms, and what their design ideas are.
This series will be divided into two parts. The first part will describe the evolution of Java random number algorithm and the underlying principles and considerations, and then introduce the RANDOM algorithm API and test performance before Java 17. The second part will analyze the random number generator algorithm after Java 17, API and the underlying implementation classes and their attributes in detail. Performance and usage scenarios, how to choose random algorithms, etc., and the application of Java random numbers to some future features of Java
This is the second one
Changes since Java 17
Disadvantages of the previous API
- No unified interface: previous
RandomThere areSplittableRandomThere is no unified inheritance class and unified abstract interface. Although their internal methods are basically the same, there is not much trouble to replace each other, but it is also more trouble for us to implement our own random algorithm, because there is no unified interface. - ThreadLocalRandom doesn’t match the virtual threads of the future Project Loom. Virtual threads are resources that can be created continuously, and if ThreadLocalRandom is used one-to-one in a large number of virtual threads, the randomness will be reduced. So we need to find a new way to do it and pave the way for Project Loom right now.
New API definitions
In JEP 356: Enhanced pseudo-random Number Generators in Java 17, the Random Number generator interface is unified:
The corresponding interface JumpableGenerator is abstracted for the leapability we mentioned earlier (you can skip many elements in a sequence loop by simply calculating it), which is LeapableGenerator if the jump step size is desired.
The interface SplitableGenerator is also abstracted for the separability we mentioned earlier (you can simply compute to split random number generators into completely different sequences)
The algorithm mentioned above, and the corresponding implementation class are:
After unifying the abstraction, we can create random number generators with different implementation types as follows:
RandomGenerator random = RandomGeneratorFactory.of("Random").create();
RandomGenerator secureRandom = RandomGeneratorFactory.of("SecureRandom").create();
RandomGenerator splittableRandom = RandomGeneratorFactory.of("SplittableRandom").create();
RandomGenerator xoroshiro128PlusPlus = RandomGeneratorFactory.of("Xoroshiro128PlusPlus").create();
RandomGenerator xoshiro256PlusPlus = RandomGeneratorFactory.of("Xoshiro256PlusPlus").create();
RandomGenerator l64X256MixRandom = RandomGeneratorFactory.of("L64X256MixRandom").create();
RandomGenerator l64X128StarStarRandom = RandomGeneratorFactory.of("L64X128StarStarRandom").create();
RandomGenerator l64X128MixRandom = RandomGeneratorFactory.of("L64X128MixRandom").create();
RandomGenerator l64X1024MixRandom = RandomGeneratorFactory.of("L64X1024MixRandom").create();
RandomGenerator l32X64MixRandom = RandomGeneratorFactory.of("L32X64MixRandom").create();
RandomGenerator l128X256MixRandom = RandomGeneratorFactory.of("L128X256MixRandom").create();
RandomGenerator l128X128MixRandom = RandomGeneratorFactory.of("L128X128MixRandom").create();
RandomGenerator l128X1024MixRandom = RandomGeneratorFactory.of("L128X1024MixRandom").create();
Copy the codeProperties of the random number generator class that each algorithm implements
1.Random: The bottom layer is a 48-digit number generated based on the linear congruence algorithm. The selected parameter ensures that each number can be randomly generated, so the Period is 2^48. Neither nextInt nor nextLong can achieve a completely uniform and random distribution, because the generated number is a 48-digit number. NextInt takes 32 bits of the number, and nextLong takes two times and combines them together. In the previous analysis of the algorithm we talked about, this algorithm can’t jump, it can’t split.
2.SplittableRandom: A 64-bit number generated by the underlying SplitMix algorithm, using MurMurhash to ensure that every number in the interval (so the Period is 2^64) is completely evenly distributed. For nextInt, every result occurs twice in a Period, and for nextLong, every result occurs once in a Period. As we mentioned in the previous analysis of the algorithm, this algorithm can’t jump, it can split.
3.Xoroshiro128PlusPlus: The bottom layer is based on Xoroshiro128++ algorithm, which uses two 64-bit digits to record the state. These two digits will not be 0 at the same time, and these two digits are combined into a random 64-bit number after calculation. There are 2^64 * 2^64 = 2^128 different combinations, so there is one less case, so there are 2^ 128-1 cases, so Period is 2^ 128-1. In the previous analysis of the algorithm, we mentioned that this algorithm can jump, it can’t split.
4.Xoshiro256PlusPlus: The bottom layer is based on Xoshiro256++ algorithm, which uses four 64-bit digits to record the state. These four digits will not be 0 at the same time, and these four digits are combined into a 64-bit random number after calculation. Because it is a combination of four 64-bit digits, there are 2^64 * 2^64 * 2^64 * 2^64 * 2^64 = 2^256 different combinations, the two digits can not be 0 at the same time, so there is one less case, so there are 2^ 256-1 cases, So Period is 2^ 256-1. In the previous analysis of the algorithm, we mentioned that this algorithm can jump, it can’t split.
5. L64X256MixRandom: The bottom layer is based on the LXM algorithm, using a 64-bit number to store the results of linear congruence, 4 64-bit numbers to record Xoshiro combinations, linear congruence has 2^64 different combinations, Xoshiro has 2^ 256-1 combinations, There are 2^64(2^ 256-1) combinations, so Period is 2^64(2^ 256-1). As we mentioned in the previous analysis of the algorithm, this algorithm can be split, can’t jump.
The other LXM implementation classes are similar.
In fact, you can see these attributes in the annotation of each algorithm implementation class:
@ Retention (RetentionPolicy RUNTIME) @ Target (ElementType. TYPE) public @ interface RandomGeneratorProperties {/ * * * algorithm name */ String name(); /** * Algorithm category */ String group() default "Legacy"; * period = (2^ i-j) * 2^k */ int I () default 0; int j() default 0; int k() default 0; /** * Uniform distribution, 0 or maximum is not uniform distribution, this value describes how many times each number occurs in a Period, but is not precise enough to ignore small deviations, Xoroshilo 128++, for example, thinks that each number occurs 2^64 times instead of 2^ 64-1 times. */ int equidistribution() default Integer.MAX_VALUE; /** * Is an algorithm based on the system Entropy (see the previous section on SEED sources) */ Boolean isStochastic() default false; /** * is a hardware assisted algorithm */ Boolean isHardware() default false; }Copy the codeWe can also use the following code to view the properties of each implementation, and we can also use these apis to filter algorithms to find implementation classes suitable for our business:
RandomGeneratorFactory.all()
.map(fac -> fac.group()+":"+fac.name()
+ " {"
+ (fac.isSplittable()?" splitable":"")
+ (fac.isStreamable()?" streamable":"")
+ (fac.isJumpable()?" jumpable":"")
+ (fac.isLeapable()?" leapable":"")
+ (fac.isHardware()?" hardware":"")
+ (fac.isStatistical()?" statistical":"")
+ (fac.isStochastic()?" stochastic":"")
+ " stateBits: "+fac.stateBits()
+ " }"
)
.sorted().forEach(System.out::println);
Copy the codeThe output is:
LXM:L128X1024MixRandom { splitable streamable statistical stateBits: 1152 }
LXM:L128X128MixRandom { splitable streamable statistical stateBits: 256 }
LXM:L128X256MixRandom { splitable streamable statistical stateBits: 384 }
LXM:L32X64MixRandom { splitable streamable statistical stateBits: 96 }
LXM:L64X1024MixRandom { splitable streamable statistical stateBits: 1088 }
LXM:L64X128MixRandom { splitable streamable statistical stateBits: 192 }
LXM:L64X128StarStarRandom { splitable streamable statistical stateBits: 192 }
LXM:L64X256MixRandom { splitable streamable statistical stateBits: 320 }
Legacy:Random { statistical stateBits: 48 }
Legacy:SecureRandom { stochastic stateBits: 2147483647 }
Legacy:SplittableRandom { splitable streamable statistical stateBits: 64 }
Xoroshiro:Xoroshiro128PlusPlus { streamable jumpable leapable statistical stateBits: 128 }
Xoshiro:Xoshiro256PlusPlus { streamable jumpable leapable statistical stateBits: 256 }
Copy the codeWhich algorithm is the fastest (it’s obvious without testing)
SplittableRandom is the fastest in a single-threaded environment, and ThreadLocalRandom is the fastest in a multi-threaded environment. The new random algorithm implementation class, Period about large need more computation, LXM implementation needs more computation, these algorithms are added to adapt to more random applications, rather than for faster. The new RandomGenerator API is much easier to use:
package prng; import java.util.random.RandomGenerator; import java.util.random.RandomGeneratorFactory; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.BenchmarkMode; import org.openjdk.jmh.annotations.Fork; import org.openjdk.jmh.annotations.Measurement; import org.openjdk.jmh.annotations.Mode; import org.openjdk.jmh.annotations.Param; import org.openjdk.jmh.annotations.Scope; import org.openjdk.jmh.annotations.Setup; import org.openjdk.jmh.annotations.State; import org.openjdk.jmh.annotations.Threads; import org.openjdk.jmh.annotations.Warmup; import org.openjdk.jmh.infra.Blackhole; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; // The Throughput index is @benchmarkmode (mode.throughput) // The Throughput index is @benchmarkmode (mode.throughput) // The Throughput index is @benchmarkmode (mode.throughput) So you can change your iterations to @warmup (iterations = 1) // Number of Threads @threads (10) @fork (1) // Number of iterations, We go through 50 iterations @Measurement(Iterations = 50) // to define the life cycle of a class instance, @state (value = scope.benchmark) Public class TestRandomGenerator {@param ({"Random", "SecureRandom", "SplittableRandom", "Xoroshiro128PlusPlus", "Xoshiro256PlusPlus", "L64X256MixRandom", "L64X128StarStarRandom", "L64X128MixRandom", "L64X1024MixRandom", "L32X64MixRandom", "L128X256MixRandom", "L128X128MixRandom", "L128X1024MixRandom" }) private String name; ThreadLocal<RandomGenerator> randomGenerator; @Setup public void setup() { final String finalName = this.name; randomGenerator = ThreadLocal.withInitial(() -> RandomGeneratorFactory.of(finalName).create()); } @Benchmark public void testRandomInt(Blackhole blackhole) throws Exception { blackhole.consume(randomGenerator.get().nextInt()); } @benchmark public void testRandomIntWithBound(Blackhole Blackhole) throws Exception { Blackhole.consume (randomGenerator.get().nextint (1, 100)); } public static void main(String[] args) throws RunnerException { Options opt = new OptionsBuilder().include(TestRandomGenerator.class.getSimpleName()).build(); new Runner(opt).run(); }}Copy the codeTest results:
Benchmark (name) Mode Cnt Score Error Units TestRandomGenerator. TestRandomInt Random THRPT 50 + / - 276250026.985 240164319.588 ops/s TestRandomGenerator. TestRandomInt SecureRandom THRPT 50 to 2362066.269 + 1277699.965 ops/s TestRandomGenerator. TestRandomInt SplittableRandom THRPT 50 to 365417656.247 + 377568150.497 ops/s TestRandomGenerator. TestRandomInt Xoroshiro128PlusPlus THRPT 50 to 341640250.941 + 287261684.079 ops/s TestRandomGenerator. TestRandomInt Xoshiro256PlusPlus THRPT 50 to 343279172.542 + 247888916.092 ops/s TestRandomGenerator. TestRandomInt L64X256MixRandom THRPT 50 to 317749688.838 + 245196331.079 ops/s TestRandomGenerator. TestRandomInt L64X128StarStarRandom THRPT 50 to 294727346.284 + 283056025.396 ops/s TestRandomGenerator. TestRandomInt L64X128MixRandom THRPT 50 to 314790625.909 + 257860657.824 ops/s TestRandomGenerator. TestRandomInt L64X1024MixRandom THRPT 50 to 315040504.948 + 101354716.147 ops/s TestRandomGenerator. TestRandomInt L32X64MixRandom THRPT 50 to 311507435.009 + 315893651.601 ops/s TestRandomGenerator. TestRandomInt L128X256MixRandom THRPT 50 to 187922591.311 + 137220695.866 ops/s TestRandomGenerator. TestRandomInt L128X128MixRandom THRPT 50 to 218433110.870 + 164229361.010 ops/s TestRandomGenerator. TestRandomInt L128X1024MixRandom THRPT 50 to 220855813.894 + 47531327.692 ops/s TestRandomGenerator. TestRandomIntWithBound Random THRPT 50 to 248088572.243 + 206899706.862 ops/s TestRandomGenerator. TestRandomIntWithBound SecureRandom THRPT 50 to 1926592.946 + 2060477.065 ops/s TestRandomGenerator. TestRandomIntWithBound SplittableRandom THRPT 50 to 334863388.450 + 92778213.010 ops/s TestRandomGenerator. TestRandomIntWithBound Xoroshiro128PlusPlus THRPT 50 to 252787781.866 + 200544008.824 ops/s TestRandomGenerator. TestRandomIntWithBound Xoshiro256PlusPlus THRPT 50 to 247673155.126 + 164068511.968 ops/s TestRandomGenerator. TestRandomIntWithBound L64X256MixRandom THRPT 50 to 273735605.410 + 87195037.181 ops/s TestRandomGenerator. TestRandomIntWithBound L64X128StarStarRandom THRPT 50 to 291151383.164 + 192343348.429 ops/s TestRandomGenerator. TestRandomIntWithBound L64X128MixRandom THRPT 50 to 217051928.549 + 177462405.951 ops/s TestRandomGenerator. TestRandomIntWithBound L64X1024MixRandom THRPT 50 to 222495366.798 + 180718625.063 ops/s TestRandomGenerator. TestRandomIntWithBound L32X64MixRandom THRPT 50 to 305716905.710 + 51030948.739 ops/s TestRandomGenerator. TestRandomIntWithBound L128X256MixRandom THRPT 50 to 174719656.589 + 148285151.049 ops/s TestRandomGenerator. TestRandomIntWithBound L128X128MixRandom THRPT 50 to 176431895.622 + 143002504.266 ops/s TestRandomGenerator. TestRandomIntWithBound L128X1024MixRandom THRPT 50 to 198282642.786 + 24204852.619 ops/sCopy the codeIn the previous result verification, we have known that SplittableRandom has the best performance in single thread, and ThreadLocalRandom with a similar algorithm but multi-thread optimization has the best performance in multi-thread environment.
How do I choose a random algorithm
The principle is, depending on your business scenario, how many of all the random combinations are there, and within what range. And then we look for the best algorithm over that Period. For example, the business scenario is a deck of poker with 52 cards in addition to the big and small wang, and the order of dealing is determined by random numbers:
- First card:
randomGenerator.nextInt(0, 52), from the remaining 52 cards - Second card:
randomGenerator.nextInt(0, 51), from the remaining 51 cards - And so on
So there’s 52! That’s a lot of results, between 2^225 and 2^226. If we use a random number generator whose Period is less than this result set, then we may never be able to generate certain card orders. So, we need to choose a Period > 54! Random number generator.
future
Random number generator in Project Loom
Without the optimization for ThreadLocal in Project Loom, ThreadLocalRandom’s randomness would also be worse because a virtual thread is an object that can be recycled over and over again, ThreadLocalRandom cannot enumerate indefinitely. Instead of using ThreadLocalRandom, we might want to use a fixed number of random generators for all virtual threads:
ExecutorService vte = Executors.newVirtualThreadExecutor(); SplittableGenerator source = RandomGeneratorFactory.<SplittableGenerator>of("L128X1024MixRandom").create(); // Our List<RandomGenerator> RNGS = source.Splits (62); AtomicInteger i = new AtomicInteger(0); vte.submit(() -> { long random = rngs.get(Math.abs(i.incrementAndGet() & 127)).nextLong(); . });Copy the codeRandom number generator under Scoped Local
Scoped Local is a more generic domain variable (ThreadLocal is Local to the current thread domain, Scoped Local supports different domains, including virtual threads, threads, method domains, packages, etc.). No version is planned yet, but as far as we know, We can better assign random number generators to each thread as follows:
private final static ScopeLocal<SplittableGenerator> rng_scope = ScopeLocal.inheritableForType(SplittableGenerator.class); public static void main(String[] args) throws InterruptedException { SplittableGenerator rng1 = RandomGeneratorFactory.<SplittableGenerator>of("L128X1024MixRandom").create(); SplittableGenerator rng2 = RandomGeneratorFactory.<SplittableGenerator>of("L32X64MixRandom").create(); try (ExecutorService vte = Executors.newVirtualThreadExecutor()) { for (int i = 0; i < 5; i++) { ScopeLocal.where(rng_scope, rng1.split(), () -> { vte.submit(new Task()); }); } for (int i = 0; i < 5; i++) { ScopeLocal.where(rng_scope, rng2.split(), () -> { vte.submit(new Task()); }); } } } private static class Task implements Runnable { @Override public void run() { SplittableGenerator rng = rng_scope.get(); System.out.println(rng); }}Copy the codeWechat search “my programming meow” public account, a daily brush, easy to improve skills, won a variety of offers:
