1 /* 2 * Copyright (c) 2013, 2021, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package java.util; 26 27 import java.math.BigInteger; 28 import java.util.concurrent.atomic.AtomicLong; 29 import java.util.random.RandomGenerator; 30 import java.util.random.RandomGenerator.SplittableGenerator; 31 import java.util.stream.DoubleStream; 32 import java.util.stream.IntStream; 33 import java.util.stream.LongStream; 34 import java.util.stream.Stream; 35 import jdk.internal.util.random.RandomSupport; 36 import jdk.internal.util.random.RandomSupport.AbstractSplittableGenerator; 37 import jdk.internal.util.random.RandomSupport.RandomGeneratorProperties; 38 39 /** 40 * A generator of uniform pseudorandom values (with period 2<sup>64</sup>) 41 * applicable for use in (among other contexts) isolated parallel 42 * computations that may generate subtasks. Class {@code SplittableRandom} 43 * supports methods for producing pseudorandom numbers of type {@code int}, 44 * {@code long}, and {@code double} with similar usages as for class 45 * {@link java.util.Random} but differs in the following ways: 46 * 47 * <ul> 48 * 49 * <li>Series of generated values pass the DieHarder suite testing 50 * independence and uniformity properties of random number generators. 51 * (Most recently validated with <a 52 * href="http://www.phy.duke.edu/~rgb/General/dieharder.php"> version 53 * 3.31.1</a>.) These tests validate only the methods for certain 54 * types and ranges, but similar properties are expected to hold, at 55 * least approximately, for others as well. The <em>period</em> 56 * (length of any series of generated values before it repeats) is 57 * 2<sup>64</sup>. </li> 58 * 59 * <li> Method {@link #split} constructs and returns a new 60 * SplittableRandom instance that shares no mutable state with the 61 * current instance. However, with very high probability, the 62 * values collectively generated by the two objects have the same 63 * statistical properties as if the same quantity of values were 64 * generated by a single thread using a single {@code 65 * SplittableRandom} object. </li> 66 * 67 * <li>Instances of SplittableRandom are <em>not</em> thread-safe. 68 * They are designed to be split, not shared, across threads. For 69 * example, a {@link java.util.concurrent.ForkJoinTask 70 * fork/join-style} computation using random numbers might include a 71 * construction of the form {@code new 72 * Subtask(aSplittableRandom.split()).fork()}. 73 * 74 * <li>This class provides additional methods for generating random 75 * streams, that employ the above techniques when used in {@code 76 * stream.parallel()} mode.</li> 77 * 78 * </ul> 79 * 80 * <p>Instances of {@code SplittableRandom} are not cryptographically 81 * secure. Consider instead using {@link java.security.SecureRandom} 82 * in security-sensitive applications. Additionally, 83 * default-constructed instances do not use a cryptographically random 84 * seed unless the {@linkplain System#getProperty system property} 85 * {@code java.util.secureRandomSeed} is set to {@code true}. 86 * 87 * @author Guy Steele 88 * @author Doug Lea 89 * @since 1.8 90 */ 91 @RandomGeneratorProperties( 92 name = "SplittableRandom", 93 i = 64, j = 0, k = 0, 94 equidistribution = 1 95 ) 96 public final class SplittableRandom implements RandomGenerator, SplittableGenerator { 97 98 /* 99 * Implementation Overview. 100 * 101 * This algorithm was inspired by the "DotMix" algorithm by 102 * Leiserson, Schardl, and Sukha "Deterministic Parallel 103 * Random-Number Generation for Dynamic-Multithreading Platforms", 104 * PPoPP 2012, as well as those in "Parallel random numbers: as 105 * easy as 1, 2, 3" by Salmon, Morae, Dror, and Shaw, SC 2011. It 106 * differs mainly in simplifying and cheapening operations. 107 * 108 * The primary update step (method nextSeed()) is to add a 109 * constant ("gamma") to the current (64 bit) seed, forming a 110 * simple sequence. The seed and the gamma values for any two 111 * SplittableRandom instances are highly likely to be different. 112 * 113 * Methods nextLong, nextInt, and derivatives do not return the 114 * sequence (seed) values, but instead a hash-like bit-mix of 115 * their bits, producing more independently distributed sequences. 116 * For nextLong, the mix64 function is based on David Stafford's 117 * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html) 118 * "Mix13" variant of the "64-bit finalizer" function in Austin 119 * Appleby's MurmurHash3 algorithm (see 120 * http://code.google.com/p/smhasher/wiki/MurmurHash3). The mix32 121 * function is based on Stafford's Mix04 mix function, but returns 122 * the upper 32 bits cast as int. 123 * 124 * The split operation uses the current generator to form the seed 125 * and gamma for another SplittableRandom. To conservatively 126 * avoid potential correlations between seed and value generation, 127 * gamma selection (method mixGamma) uses different 128 * (Murmurhash3's) mix constants. To avoid potential weaknesses 129 * in bit-mixing transformations, we restrict gammas to odd values 130 * with at least 24 0-1 or 1-0 bit transitions. Rather than 131 * rejecting candidates with too few or too many bits set, method 132 * mixGamma flips some bits (which has the effect of mapping at 133 * most 4 to any given gamma value). This reduces the effective 134 * set of 64bit odd gamma values by about 2%, and serves as an 135 * automated screening for sequence constant selection that is 136 * left as an empirical decision in some other hashing and crypto 137 * algorithms. 138 * 139 * The resulting generator thus transforms a sequence in which 140 * (typically) many bits change on each step, with an inexpensive 141 * mixer with good (but less than cryptographically secure) 142 * avalanching. 143 * 144 * The default (no-argument) constructor, in essence, invokes 145 * split() for a common "defaultGen" SplittableRandom. Unlike 146 * other cases, this split must be performed in a thread-safe 147 * manner, so we use an AtomicLong to represent the seed rather 148 * than use an explicit SplittableRandom. To bootstrap the 149 * defaultGen, we start off using a seed based on current time 150 * unless the java.util.secureRandomSeed property is set. This 151 * serves as a slimmed-down (and insecure) variant of SecureRandom 152 * that also avoids stalls that may occur when using /dev/random. 153 * 154 * It is a relatively simple matter to apply the basic design here 155 * to use 128 bit seeds. However, emulating 128bit arithmetic and 156 * carrying around twice the state add more overhead than appears 157 * warranted for current usages. 158 * 159 * File organization: First the non-public methods that constitute 160 * the main algorithm, then the main public methods, followed by 161 * some custom spliterator classes needed for stream methods. 162 */ 163 164 /** 165 * The golden ratio scaled to 64bits, used as the initial gamma 166 * value for (unsplit) SplittableRandoms. 167 */ 168 private static final long GOLDEN_GAMMA = 0x9e3779b97f4a7c15L; 169 170 /** 171 * The seed. Updated only via method nextSeed. 172 */ 173 private long seed; 174 175 /** 176 * The step value. 177 */ 178 private final long gamma; 179 180 /** 181 * Internal constructor used by all others except default constructor. 182 */ SplittableRandom(long seed, long gamma)183 private SplittableRandom(long seed, long gamma) { 184 this.seed = seed; 185 this.gamma = gamma; 186 this.proxy = new AbstractSplittableGeneratorProxy(); 187 } 188 189 /** 190 * Computes Stafford variant 13 of 64bit mix function. 191 * http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html 192 */ mix64(long z)193 private static long mix64(long z) { 194 z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L; 195 z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL; 196 return z ^ (z >>> 31); 197 } 198 199 /** 200 * Returns the 32 high bits of Stafford variant 4 mix64 function as int. 201 * http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html 202 */ mix32(long z)203 private static int mix32(long z) { 204 z = (z ^ (z >>> 33)) * 0x62a9d9ed799705f5L; 205 return (int)(((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32); 206 } 207 208 /** 209 * Returns the gamma value to use for a new split instance. 210 * Uses the 64bit mix function from MurmurHash3. 211 * https://github.com/aappleby/smhasher/wiki/MurmurHash3 212 */ mixGamma(long z)213 private static long mixGamma(long z) { 214 z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; // MurmurHash3 mix constants 215 z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L; 216 z = (z ^ (z >>> 33)) | 1L; // force to be odd 217 int n = Long.bitCount(z ^ (z >>> 1)); // ensure enough transitions 218 return (n < 24) ? z ^ 0xaaaaaaaaaaaaaaaaL : z; 219 } 220 221 /** 222 * Proxy class to non-public RandomSupportAbstractSplittableGenerator. 223 */ 224 private class AbstractSplittableGeneratorProxy extends AbstractSplittableGenerator { 225 @Override nextInt()226 public int nextInt() { 227 return SplittableRandom.this.nextInt(); 228 } 229 230 @Override nextLong()231 public long nextLong() { 232 return SplittableRandom.this.nextLong(); 233 } 234 235 @Override split(SplittableGenerator source)236 public java.util.SplittableRandom split(SplittableGenerator source) { 237 return new SplittableRandom(source.nextLong(), mixGamma(source.nextLong())); 238 } 239 } 240 241 /** 242 * Proxy object to non-public RandomSupportAbstractSplittableGenerator. 243 */ 244 private AbstractSplittableGeneratorProxy proxy; 245 246 /** 247 * Adds gamma to seed. 248 */ nextSeed()249 private long nextSeed() { 250 return seed += gamma; 251 } 252 253 /** 254 * The seed generator for default constructors. 255 */ 256 private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed()); 257 258 /* ---------------- public methods ---------------- */ 259 260 /** 261 * Creates a new SplittableRandom instance using the specified 262 * initial seed. SplittableRandom instances created with the same 263 * seed in the same program generate identical sequences of values. 264 * 265 * @param seed the initial seed 266 */ SplittableRandom(long seed)267 public SplittableRandom(long seed) { 268 this(seed, GOLDEN_GAMMA); 269 } 270 271 /** 272 * Creates a new SplittableRandom instance that is likely to 273 * generate sequences of values that are statistically independent 274 * of those of any other instances in the current program; and 275 * may, and typically does, vary across program invocations. 276 */ SplittableRandom()277 public SplittableRandom() { // emulate defaultGen.split() 278 long s = defaultGen.getAndAdd(2 * GOLDEN_GAMMA); 279 this.seed = mix64(s); 280 this.gamma = mixGamma(s + GOLDEN_GAMMA); 281 this.proxy = new AbstractSplittableGeneratorProxy(); 282 } 283 284 /** 285 * Constructs and returns a new SplittableRandom instance that 286 * shares no mutable state with this instance. However, with very 287 * high probability, the set of values collectively generated by 288 * the two objects has the same statistical properties as if the 289 * same quantity of values were generated by a single thread using 290 * a single SplittableRandom object. Either or both of the two 291 * objects may be further split using the {@code split()} method, 292 * and the same expected statistical properties apply to the 293 * entire set of generators constructed by such recursive 294 * splitting. 295 * 296 * @return the new SplittableRandom instance 297 */ split()298 public SplittableRandom split() { 299 return new SplittableRandom(nextLong(), mixGamma(nextSeed())); 300 } 301 302 /** 303 * {@inheritDoc} 304 * @throws NullPointerException {@inheritDoc} 305 * @since 17 306 */ split(SplittableGenerator source)307 public SplittableRandom split(SplittableGenerator source) { 308 return new SplittableRandom(source.nextLong(), mixGamma(source.nextLong())); 309 } 310 311 @Override nextInt()312 public int nextInt() { 313 return mix32(nextSeed()); 314 } 315 316 @Override nextLong()317 public long nextLong() { 318 return mix64(nextSeed()); 319 } 320 321 /** 322 * {@inheritDoc} 323 * @throws NullPointerException {@inheritDoc} 324 * @since 10 325 */ 326 @Override nextBytes(byte[] bytes)327 public void nextBytes(byte[] bytes) { 328 proxy.nextBytes(bytes); 329 } 330 331 /** 332 * {@inheritDoc} 333 * @implSpec {@inheritDoc} 334 * @since 17 335 */ 336 @Override splits()337 public Stream<SplittableGenerator> splits() { 338 return proxy.splits(); 339 } 340 341 /** 342 * {@inheritDoc} 343 * @throws IllegalArgumentException {@inheritDoc} 344 * @implSpec {@inheritDoc} 345 * @since 17 346 */ 347 @Override splits(long streamSize)348 public Stream<SplittableGenerator> splits(long streamSize) { 349 return proxy.splits(streamSize, this); 350 } 351 352 /** 353 * {@inheritDoc} 354 * @throws NullPointerException {@inheritDoc} 355 * @implSpec {@inheritDoc} 356 * @since 17 357 */ 358 @Override splits(SplittableGenerator source)359 public Stream<SplittableGenerator> splits(SplittableGenerator source) { 360 return proxy.splits(Long.MAX_VALUE, source); 361 } 362 363 /** 364 * {@inheritDoc} 365 * @throws NullPointerException {@inheritDoc} 366 * @throws IllegalArgumentException {@inheritDoc} 367 * @implSpec {@inheritDoc} 368 * @since 17 369 */ 370 @Override splits(long streamSize, SplittableGenerator source)371 public Stream<SplittableGenerator> splits(long streamSize, SplittableGenerator source) { 372 return proxy.splits(streamSize, source); 373 } 374 375 /** 376 * Returns a stream producing the given {@code streamSize} number 377 * of pseudorandom {@code int} values from this generator and/or 378 * one split from it. 379 * 380 * @param streamSize the number of values to generate 381 * @return a stream of pseudorandom {@code int} values 382 * @throws IllegalArgumentException if {@code streamSize} is 383 * less than zero 384 */ 385 @Override ints(long streamSize)386 public IntStream ints(long streamSize) { 387 return proxy.ints(streamSize); 388 } 389 390 /** 391 * Returns an effectively unlimited stream of pseudorandom {@code int} 392 * values from this generator and/or one split from it. 393 * 394 * @implNote This method is implemented to be equivalent to {@code 395 * ints(Long.MAX_VALUE)}. 396 * 397 * @return a stream of pseudorandom {@code int} values 398 */ 399 @Override ints()400 public IntStream ints() { 401 return proxy.ints(); 402 } 403 404 /** 405 * Returns a stream producing the given {@code streamSize} number 406 * of pseudorandom {@code int} values from this generator and/or one split 407 * from it; each value conforms to the given origin (inclusive) and bound 408 * (exclusive). 409 * 410 * @param streamSize the number of values to generate 411 * @param randomNumberOrigin the origin (inclusive) of each random value 412 * @param randomNumberBound the bound (exclusive) of each random value 413 * @return a stream of pseudorandom {@code int} values, 414 * each with the given origin (inclusive) and bound (exclusive) 415 * @throws IllegalArgumentException if {@code streamSize} is 416 * less than zero, or {@code randomNumberOrigin} 417 * is greater than or equal to {@code randomNumberBound} 418 */ 419 @Override ints(long streamSize, int randomNumberOrigin, int randomNumberBound)420 public IntStream ints(long streamSize, int randomNumberOrigin, int randomNumberBound) { 421 return proxy.ints(streamSize, randomNumberOrigin, randomNumberBound); 422 } 423 424 /** 425 * Returns an effectively unlimited stream of pseudorandom {@code 426 * int} values from this generator and/or one split from it; each value 427 * conforms to the given origin (inclusive) and bound (exclusive). 428 * 429 * @implNote This method is implemented to be equivalent to {@code 430 * ints(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}. 431 * 432 * @param randomNumberOrigin the origin (inclusive) of each random value 433 * @param randomNumberBound the bound (exclusive) of each random value 434 * @return a stream of pseudorandom {@code int} values, 435 * each with the given origin (inclusive) and bound (exclusive) 436 * @throws IllegalArgumentException if {@code randomNumberOrigin} 437 * is greater than or equal to {@code randomNumberBound} 438 */ 439 @Override ints(int randomNumberOrigin, int randomNumberBound)440 public IntStream ints(int randomNumberOrigin, int randomNumberBound) { 441 return proxy.ints(randomNumberOrigin, randomNumberBound); 442 } 443 444 /** 445 * Returns a stream producing the given {@code streamSize} number 446 * of pseudorandom {@code long} values from this generator and/or 447 * one split from it. 448 * 449 * @param streamSize the number of values to generate 450 * @return a stream of pseudorandom {@code long} values 451 * @throws IllegalArgumentException if {@code streamSize} is 452 * less than zero 453 */ 454 @Override longs(long streamSize)455 public LongStream longs(long streamSize) { 456 return proxy.longs(streamSize); 457 } 458 459 /** 460 * Returns an effectively unlimited stream of pseudorandom {@code 461 * long} values from this generator and/or one split from it. 462 * 463 * @implNote This method is implemented to be equivalent to {@code 464 * longs(Long.MAX_VALUE)}. 465 * 466 * @return a stream of pseudorandom {@code long} values 467 */ 468 @Override longs()469 public LongStream longs() { 470 return proxy.longs(); 471 } 472 473 /** 474 * Returns a stream producing the given {@code streamSize} number of 475 * pseudorandom {@code long} values from this generator and/or one split 476 * from it; each value conforms to the given origin (inclusive) and bound 477 * (exclusive). 478 * 479 * @param streamSize the number of values to generate 480 * @param randomNumberOrigin the origin (inclusive) of each random value 481 * @param randomNumberBound the bound (exclusive) of each random value 482 * @return a stream of pseudorandom {@code long} values, 483 * each with the given origin (inclusive) and bound (exclusive) 484 * @throws IllegalArgumentException if {@code streamSize} is 485 * less than zero, or {@code randomNumberOrigin} 486 * is greater than or equal to {@code randomNumberBound} 487 */ 488 @Override longs(long streamSize, long randomNumberOrigin, long randomNumberBound)489 public LongStream longs(long streamSize, long randomNumberOrigin, long randomNumberBound) { 490 return proxy.longs(streamSize, randomNumberOrigin, randomNumberBound); 491 } 492 493 /** 494 * Returns an effectively unlimited stream of pseudorandom {@code 495 * long} values from this generator and/or one split from it; each value 496 * conforms to the given origin (inclusive) and bound (exclusive). 497 * 498 * @implNote This method is implemented to be equivalent to {@code 499 * longs(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}. 500 * 501 * @param randomNumberOrigin the origin (inclusive) of each random value 502 * @param randomNumberBound the bound (exclusive) of each random value 503 * @return a stream of pseudorandom {@code long} values, 504 * each with the given origin (inclusive) and bound (exclusive) 505 * @throws IllegalArgumentException if {@code randomNumberOrigin} 506 * is greater than or equal to {@code randomNumberBound} 507 */ 508 @Override longs(long randomNumberOrigin, long randomNumberBound)509 public LongStream longs(long randomNumberOrigin, long randomNumberBound) { 510 return proxy.longs(randomNumberOrigin, randomNumberBound); 511 } 512 513 /** 514 * Returns a stream producing the given {@code streamSize} number of 515 * pseudorandom {@code double} values from this generator and/or one split 516 * from it; each value is between zero (inclusive) and one (exclusive). 517 * 518 * @param streamSize the number of values to generate 519 * @return a stream of {@code double} values 520 * @throws IllegalArgumentException if {@code streamSize} is 521 * less than zero 522 */ 523 @Override doubles(long streamSize)524 public DoubleStream doubles(long streamSize) { 525 return proxy.doubles(streamSize); 526 } 527 528 /** 529 * Returns an effectively unlimited stream of pseudorandom {@code 530 * double} values from this generator and/or one split from it; each value 531 * is between zero (inclusive) and one (exclusive). 532 * 533 * @implNote This method is implemented to be equivalent to {@code 534 * doubles(Long.MAX_VALUE)}. 535 * 536 * @return a stream of pseudorandom {@code double} values 537 */ 538 @Override doubles()539 public DoubleStream doubles() { 540 return proxy.doubles(); 541 } 542 543 /** 544 * Returns a stream producing the given {@code streamSize} number of 545 * pseudorandom {@code double} values from this generator and/or one split 546 * from it; each value conforms to the given origin (inclusive) and bound 547 * (exclusive). 548 * 549 * @param streamSize the number of values to generate 550 * @param randomNumberOrigin the origin (inclusive) of each random value 551 * @param randomNumberBound the bound (exclusive) of each random value 552 * @return a stream of pseudorandom {@code double} values, 553 * each with the given origin (inclusive) and bound (exclusive) 554 * @throws IllegalArgumentException if {@code streamSize} is 555 * less than zero, or {@code randomNumberOrigin} 556 * is greater than or equal to {@code randomNumberBound} 557 */ 558 @Override doubles(long streamSize, double randomNumberOrigin, double randomNumberBound)559 public DoubleStream doubles(long streamSize, double randomNumberOrigin, double randomNumberBound) { 560 return proxy.doubles(streamSize, randomNumberOrigin, randomNumberBound); 561 } 562 563 /** 564 * Returns an effectively unlimited stream of pseudorandom {@code 565 * double} values from this generator and/or one split from it; each value 566 * conforms to the given origin (inclusive) and bound (exclusive). 567 * 568 * @implNote This method is implemented to be equivalent to {@code 569 * doubles(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}. 570 * 571 * @param randomNumberOrigin the origin (inclusive) of each random value 572 * @param randomNumberBound the bound (exclusive) of each random value 573 * @return a stream of pseudorandom {@code double} values, 574 * each with the given origin (inclusive) and bound (exclusive) 575 * @throws IllegalArgumentException if {@code randomNumberOrigin} 576 * is greater than or equal to {@code randomNumberBound} 577 */ 578 @Override doubles(double randomNumberOrigin, double randomNumberBound)579 public DoubleStream doubles(double randomNumberOrigin, double randomNumberBound) { 580 return proxy.doubles(randomNumberOrigin, randomNumberBound); 581 } 582 } 583