硬核 – Java 隨機數相關 API 的演進與思考（下）
- 2022 年 1 月 11 日
- 筆記
- JAVA, Java & JDK
本系列將 Java 17 之前的隨機數 API 以及 Java 17 之後的統一 API 都做了比較詳細的說明，並且將隨機數的特性以及實現思路也做了一些簡單的分析，幫助大家明白為何會有這麼多的隨機數演算法，以及他們的設計思路是什麼。
本系列會分為兩篇，第一篇講述 Java 隨機數演算法的演變思路以及底層原理與考量，之後介紹 Java 17 之前的隨機演算法 API 以及測試性能，第二篇詳細分析 Java 17 之後的隨機數生成器演算法以及 API 和底層實現類以及他們的屬性，性能以及使用場景，如何選擇隨機演算法等等，並對 Java 的隨機數對於 Java 的一些未來特性的適用進行展望
這是第二篇
Java 17 之後的變化
之前的 API 的缺點
- 沒有統一的介面：之前的
Random還有SplittableRandom沒有統一的繼承類，以及統一的抽象介面，雖然 他們內部方法基本一致，互相替換的麻煩並不多，但是這樣我們要想實現自己的隨機演算法也比較麻煩，因為沒有統一的介面。 - ThreadLocalRandom 與未來的 Project Loom 的虛擬執行緒相性比較差。虛擬執行緒是可以不斷創建的資源，在大量虛擬執行緒中如果還是用 ThreadLocalRandom 一一對應的話，會有隨機性減弱的問題。所以，我們需要尋找新的實現方法，並且從現在開始為 Project Loom 鋪路。
新的 API 定義
在 Java 17 中的 JEP 356: Enhanced Pseudo-Random Number Generators 中，統一了隨機數生成器的介面，即 RandomGenerator：
其中，針對我們前面提到的可跳躍性（可以通過簡單計算，跳過序列環中的很多元素）抽象了對應的介面 JumpableGenerator，如果跳躍的步長希望更大一些的話，對應的就是 LeapableGenerator。
針對我們前面提到的可拆分性（可以通過簡單計算，拆分出生成完全不同序列的隨機數生成器）也抽象了介面 SplitableGenerator
前面提到的演算法，與對應的實現類是：
統一抽象後，我們就可以這樣創建不同實現類型的隨機數字生成器：
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();
每種演算法實現的隨機數生成器類的屬性
1.Random：底層是基於線性同餘演算法生成的是一個 48 位的數字，選擇的參數保證了每個數字都能隨機出來，所以 Period 為 2^48。nextInt 和 nextLong 都不能做到完全均勻隨機分布，因為生成的數字是 48 位的數字，nextInt 即取其中的 32 位，nextLong 是取兩次組合在一起。之前的演算法分析我們提到過，這種演算法不能跳躍，不能分割。
2.SplittableRandom: 底層基於 SplitMix 演算法生成的一個 64 位的數字，通過 MurMurhash 保證了區間內每個數字都會出現（所以 Period 是 2^64），並且是完全均勻分布的。對於 nextInt 是一個 Period 內每個結果都會出現兩次，對於 nextLong 是一個 Period 內每個結果都會出現一次。之前的演算法分析我們提到過，這種演算法不能跳躍，可以分割。
3.Xoroshiro128PlusPlus：底層基於 Xoroshiro128++ 演算法，使用兩個 64 位數字記錄狀態，這兩個數字不會同時為 0，這兩個數字經過計算組合成為一個 64 位隨機數。由於是兩個 64 位數字組合而成，那麼就有 2^64 * 2^64 = 2^128 種不同組合，兩個數字不會同時為 0，那麼就少了一種情況，所以一共是 2^128 - 1 種情況，所以 Period 是 2^128 - 1。之前的演算法分析我們提到過，這種演算法可以跳躍，不能分割。
4.Xoshiro256PlusPlus：底層基於 Xoshiro256++ 演算法，使用四個 64 位數字記錄狀態，這四個數字不會同時為 0，這四個數字經過計算組合成為一個 64 位隨機數。由於是四個 64 位數字組合而成，那麼就有 2^64 * 2^64 * 2^64 * 2^64 = 2^256 種不同組合，兩個數字不會同時為 0，那麼就少了一種情況，所以一共是 2^256 - 1 種情況，所以 Period 是 2^256 - 1。之前的演算法分析我們提到過，這種演算法可以跳躍，不能分割。
5. L64X256MixRandom：底層基於 LXM 演算法，使用一個 64 位數字保存線性同餘的結果，4 個 64 位數字記錄 Xoshiro 組合，線性同餘有 2^64 種不同組合，Xoshiro 有 2^256 - 1 種組合，一共 2^64(2^256 - 1) 種組合，所以 Period 是 2^64(2^256 - 1)。之前的演算法分析我們提到過，這種演算法可以分割，不能跳躍。
其他的 LXM 實現類是類似的。
其實可以從每個演算法的實現類的 “ 註解上，看出他們的這些屬性：
@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.TYPE)
public @interface RandomGeneratorProperties {
/**
* 演算法名稱
*/
String name();
/**
* 演算法類別
*/
String group() default "Legacy";
/**
* period 大小，由 i, j, k 三個數字描述，即：
* period = (2^i - j) * 2^k
*/
int i() default 0;
int j() default 0;
int k() default 0;
/**
* 均勻分布性，0 或者最大值則不是均勻分布，這個值描述在一個 Period 內每個數字出現多少次，但是不是那麼精準的，會忽略一些小的偏差，例如 Xoroshiro128++ 認為每個數字出現 2^64 次而不是 2^64 - 1 次。
*/
int equidistribution() default Integer.MAX_VALUE;
/**
* 是否是基於系統 Entropy（參考前面的 SEED 來源章節）的演算法
*/
boolean isStochastic() default false;
/**
* 是否是硬體輔助的演算法
*/
boolean isHardware() default false;
}
我們還可以通過下面的程式碼，查看每種實現的屬性，同樣的，也可以通過這些 API 對演算法進行過濾，找到適合我們業務的實現類：
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);
輸出是：
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 }
哪種演算法最快（不用測也很明顯）
這個根據之前的分析，應該還是 SplittableRandom 在單執行緒環境下最快，多執行緒環境下使用 ThreadLocalRandom 最快。新增的隨機演算法實現類，Period 約大需要的計算越多， LXM 的實現需要更多計算，加入這些演算法是為了適應更多的隨機應用，而不是為了更快。不過為了滿足大家的好奇心，還是寫了如下的程式碼進行測試，從下面的程式碼也可以看出，新的 RandomGenerator API 使用更加簡便：
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;
//測試指標為吞吐量
@BenchmarkMode(Mode.Throughput)
//需要預熱，排除 jit 即時編譯以及 JVM 採集各種指標帶來的影響，由於我們單次循環很多次，所以預熱一次就行
@Warmup(iterations = 1)
//執行緒個數
@Threads(10)
@Fork(1)
//測試次數，我們測試50次
@Measurement(iterations = 50)
//定義了一個類實例的生命周期，所有測試執行緒共享一個實例
@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 {
//注意不取 2^n 這種數字，因為這種數字一般不會作為實際應用的範圍，但是底層針對這種數字有優化
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();
}
}
測試結果：
Benchmark (name) Mode Cnt Score Error Units
TestRandomGenerator.testRandomInt Random thrpt 50 276250026.985 ± 240164319.588 ops/s
TestRandomGenerator.testRandomInt SecureRandom thrpt 50 2362066.269 ± 1277699.965 ops/s
TestRandomGenerator.testRandomInt SplittableRandom thrpt 50 365417656.247 ± 377568150.497 ops/s
TestRandomGenerator.testRandomInt Xoroshiro128PlusPlus thrpt 50 341640250.941 ± 287261684.079 ops/s
TestRandomGenerator.testRandomInt Xoshiro256PlusPlus thrpt 50 343279172.542 ± 247888916.092 ops/s
TestRandomGenerator.testRandomInt L64X256MixRandom thrpt 50 317749688.838 ± 245196331.079 ops/s
TestRandomGenerator.testRandomInt L64X128StarStarRandom thrpt 50 294727346.284 ± 283056025.396 ops/s
TestRandomGenerator.testRandomInt L64X128MixRandom thrpt 50 314790625.909 ± 257860657.824 ops/s
TestRandomGenerator.testRandomInt L64X1024MixRandom thrpt 50 315040504.948 ± 101354716.147 ops/s
TestRandomGenerator.testRandomInt L32X64MixRandom thrpt 50 311507435.009 ± 315893651.601 ops/s
TestRandomGenerator.testRandomInt L128X256MixRandom thrpt 50 187922591.311 ± 137220695.866 ops/s
TestRandomGenerator.testRandomInt L128X128MixRandom thrpt 50 218433110.870 ± 164229361.010 ops/s
TestRandomGenerator.testRandomInt L128X1024MixRandom thrpt 50 220855813.894 ± 47531327.692 ops/s
TestRandomGenerator.testRandomIntWithBound Random thrpt 50 248088572.243 ± 206899706.862 ops/s
TestRandomGenerator.testRandomIntWithBound SecureRandom thrpt 50 1926592.946 ± 2060477.065 ops/s
TestRandomGenerator.testRandomIntWithBound SplittableRandom thrpt 50 334863388.450 ± 92778213.010 ops/s
TestRandomGenerator.testRandomIntWithBound Xoroshiro128PlusPlus thrpt 50 252787781.866 ± 200544008.824 ops/s
TestRandomGenerator.testRandomIntWithBound Xoshiro256PlusPlus thrpt 50 247673155.126 ± 164068511.968 ops/s
TestRandomGenerator.testRandomIntWithBound L64X256MixRandom thrpt 50 273735605.410 ± 87195037.181 ops/s
TestRandomGenerator.testRandomIntWithBound L64X128StarStarRandom thrpt 50 291151383.164 ± 192343348.429 ops/s
TestRandomGenerator.testRandomIntWithBound L64X128MixRandom thrpt 50 217051928.549 ± 177462405.951 ops/s
TestRandomGenerator.testRandomIntWithBound L64X1024MixRandom thrpt 50 222495366.798 ± 180718625.063 ops/s
TestRandomGenerator.testRandomIntWithBound L32X64MixRandom thrpt 50 305716905.710 ± 51030948.739 ops/s
TestRandomGenerator.testRandomIntWithBound L128X256MixRandom thrpt 50 174719656.589 ± 148285151.049 ops/s
TestRandomGenerator.testRandomIntWithBound L128X128MixRandom thrpt 50 176431895.622 ± 143002504.266 ops/s
TestRandomGenerator.testRandomIntWithBound L128X1024MixRandom thrpt 50 198282642.786 ± 24204852.619 ops/s
在之前的結果驗證中，我們已經知道了 SplittableRandom 的在單執行緒中的性能最好，多執行緒環境下表現最好的是演算法與它類似但是做了多執行緒優化的 ThreadLocalRandom.
如何選擇隨機演算法
原則是，看你的業務場景，所有的隨機組合到底有多少個，在什麼範圍內。然後找大於這個範圍的 Period 中，性能最好的演算法。例如，業務場景是一副撲克除了大小王 52 張牌，通過隨機數決定發牌順序：
- 第一張牌：
randomGenerator.nextInt(0, 52)，從剩餘的 52 張牌選 - 第二張牌：
randomGenerator.nextInt(0, 51)，從剩餘的 51 張牌選 - 以此類推
那麼一共有 52! 這麼多結果，範圍在 2^225 ~ 2^226 之間。如果我們使用的隨機數生成器的 Period 小於這個結果集，那麼某些牌的順序，我們可能永遠生成不了。所以，我們需要選擇一個 Period > 54! 的隨機數生成器。
未來展望
Project Loom 中的隨機數生成器
如果 Project Loom 中沒有針對 ThreadLocal 的優化，那麼 ThreadLocalRandom 的隨機性表現也會變差，因為虛擬執行緒是一個可以不斷生成回收的類似於對象的東西，ThreadLocalRandom 並不能無限枚舉下去。這時候我們可能需要使用固定的多個隨機數生成器給所有的虛擬執行緒使用，而不是使用 ThreadLocalRandom：
ExecutorService vte = Executors.newVirtualThreadExecutor();
SplittableGenerator source = RandomGeneratorFactory.<SplittableGenerator>of("L128X1024MixRandom").create();
//分割出 128 個不同的隨機數生成器
List<RandomGenerator> rngs = source.splits(128);
AtomicInteger i = new AtomicInteger(0);
vte.submit(() -> {
long random = rngs.get(Math.abs(i.incrementAndGet() & 127)).nextLong();
...
});
Scoped Local 特性下的隨機數生成器
Scoped Local 是一種更通用的域變數（例如 ThreadLocal 即當前執行緒域本地，Scoped Local 可以支援不同的域，包括虛擬執行緒，執行緒，方法域，包域等等），目前還沒公布哪個版本會計劃開發，不過按現在的爆料來看，我們可以使用下面這種方式更好的給每個執行緒分配隨機數生成器：
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);
}
}
微信搜索「我的編程喵」關注公眾號，每日一刷，輕鬆提升技術，斬獲各種offer：
