57369
|
1 |
/*
|
|
2 |
* Copyright (c) 2013, 2019, Oracle and/or its affiliates. All rights reserved.
|
|
3 |
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
|
|
4 |
*
|
|
5 |
*
|
|
6 |
*
|
|
7 |
*
|
|
8 |
*
|
|
9 |
*
|
|
10 |
*
|
|
11 |
*
|
|
12 |
*
|
|
13 |
*
|
|
14 |
*
|
|
15 |
*
|
|
16 |
*
|
|
17 |
*
|
|
18 |
*
|
|
19 |
*
|
|
20 |
*
|
|
21 |
*
|
|
22 |
*
|
|
23 |
*
|
|
24 |
*/
|
|
25 |
|
|
26 |
// package java.util;
|
|
27 |
|
|
28 |
import java.math.BigInteger;
|
|
29 |
import java.util.concurrent.atomic.AtomicLong;
|
|
30 |
|
|
31 |
/**
|
|
32 |
* A generator of uniform pseudorandom values applicable for use in
|
|
33 |
* (among other contexts) isolated parallel computations that may
|
|
34 |
* generate subtasks. Class {@code SplittableRandom} supports methods for
|
|
35 |
* producing pseudorandom numbers of type {@code int}, {@code long},
|
|
36 |
* and {@code double} with similar usages as for class
|
|
37 |
* {@link java.util.Random} but differs in the following ways:
|
|
38 |
*
|
|
39 |
* <ul>
|
|
40 |
*
|
|
41 |
* <li>Series of generated values pass the DieHarder suite testing
|
|
42 |
* independence and uniformity properties of random number generators.
|
|
43 |
* (Most recently validated with <a
|
|
44 |
* href="http://www.phy.duke.edu/~rgb/General/dieharder.php"> version
|
|
45 |
* 3.31.1</a>.) These tests validate only the methods for certain
|
|
46 |
* types and ranges, but similar properties are expected to hold, at
|
|
47 |
* least approximately, for others as well. The <em>period</em>
|
|
48 |
* (length of any series of generated values before it repeats) is at
|
|
49 |
* least 2<sup>64</sup>. </li>
|
|
50 |
*
|
|
51 |
* <li> Method {@link #split} constructs and returns a new
|
|
52 |
* SplittableRandom instance that shares no mutable state with the
|
|
53 |
* current instance. However, with very high probability, the
|
|
54 |
* values collectively generated by the two objects have the same
|
|
55 |
* statistical properties as if the same quantity of values were
|
|
56 |
* generated by a single thread using a single {@code
|
|
57 |
* SplittableRandom} object. </li>
|
|
58 |
*
|
|
59 |
* <li>Instances of SplittableRandom are <em>not</em> thread-safe.
|
|
60 |
* They are designed to be split, not shared, across threads. For
|
|
61 |
* example, a {@link java.util.concurrent.ForkJoinTask
|
|
62 |
* fork/join-style} computation using random numbers might include a
|
|
63 |
* construction of the form {@code new
|
|
64 |
* Subtask(aSplittableRandom.split()).fork()}.
|
|
65 |
*
|
|
66 |
* <li>This class provides additional methods for generating random
|
|
67 |
* streams, that employ the above techniques when used in {@code
|
|
68 |
* stream.parallel()} mode.</li>
|
|
69 |
*
|
|
70 |
* </ul>
|
|
71 |
*
|
|
72 |
* <p>Instances of {@code SplittableRandom} are not cryptographically
|
|
73 |
* secure. Consider instead using {@link java.security.SecureRandom}
|
|
74 |
* in security-sensitive applications. Additionally,
|
|
75 |
* default-constructed instances do not use a cryptographically random
|
|
76 |
* seed unless the {@linkplain System#getProperty system property}
|
|
77 |
* {@code java.util.secureRandomSeed} is set to {@code true}.
|
|
78 |
*
|
|
79 |
* @author Guy Steele
|
|
80 |
* @author Doug Lea
|
|
81 |
* @since 1.8
|
|
82 |
*/
|
|
83 |
public final class SplittableRandom extends AbstractSplittableRng {
|
|
84 |
|
|
85 |
/*
|
|
86 |
* Implementation Overview.
|
|
87 |
*
|
|
88 |
* This algorithm was inspired by the "DotMix" algorithm by
|
|
89 |
* Leiserson, Schardl, and Sukha "Deterministic Parallel
|
|
90 |
* Random-Number Generation for Dynamic-Multithreading Platforms",
|
|
91 |
* PPoPP 2012, as well as those in "Parallel random numbers: as
|
|
92 |
* easy as 1, 2, 3" by Salmon, Morae, Dror, and Shaw, SC 2011. It
|
|
93 |
* differs mainly in simplifying and cheapening operations.
|
|
94 |
*
|
|
95 |
* The primary update step (method nextSeed()) is to add a
|
|
96 |
* constant ("gamma") to the current (64 bit) seed, forming a
|
|
97 |
* simple sequence. The seed and the gamma values for any two
|
|
98 |
* SplittableRandom instances are highly likely to be different.
|
|
99 |
*
|
|
100 |
* Methods nextLong, nextInt, and derivatives do not return the
|
|
101 |
* sequence (seed) values, but instead a hash-like bit-mix of
|
|
102 |
* their bits, producing more independently distributed sequences.
|
|
103 |
* For nextLong, the mix64 function is based on David Stafford's
|
|
104 |
* (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)
|
|
105 |
* "Mix13" variant of the "64-bit finalizer" function in Austin
|
|
106 |
* Appleby's MurmurHash3 algorithm (see
|
|
107 |
* http://code.google.com/p/smhasher/wiki/MurmurHash3). The mix32
|
|
108 |
* function is based on Stafford's Mix04 mix function, but returns
|
|
109 |
* the upper 32 bits cast as int.
|
|
110 |
*
|
|
111 |
* The split operation uses the current generator to form the seed
|
|
112 |
* and gamma for another SplittableRandom. To conservatively
|
|
113 |
* avoid potential correlations between seed and value generation,
|
|
114 |
* gamma selection (method mixGamma) uses different
|
|
115 |
* (Murmurhash3's) mix constants. To avoid potential weaknesses
|
|
116 |
* in bit-mixing transformations, we restrict gammas to odd values
|
|
117 |
* with at least 24 0-1 or 1-0 bit transitions. Rather than
|
|
118 |
* rejecting candidates with too few or too many bits set, method
|
|
119 |
* mixGamma flips some bits (which has the effect of mapping at
|
|
120 |
* most 4 to any given gamma value). This reduces the effective
|
|
121 |
* set of 64bit odd gamma values by about 2%, and serves as an
|
|
122 |
* automated screening for sequence constant selection that is
|
|
123 |
* left as an empirical decision in some other hashing and crypto
|
|
124 |
* algorithms.
|
|
125 |
*
|
|
126 |
* The resulting generator thus transforms a sequence in which
|
|
127 |
* (typically) many bits change on each step, with an inexpensive
|
|
128 |
* mixer with good (but less than cryptographically secure)
|
|
129 |
* avalanching.
|
|
130 |
*
|
|
131 |
* The default (no-argument) constructor, in essence, invokes
|
|
132 |
* split() for a common "defaultGen" SplittableRandom. Unlike
|
|
133 |
* other cases, this split must be performed in a thread-safe
|
|
134 |
* manner, so we use an AtomicLong to represent the seed rather
|
|
135 |
* than use an explicit SplittableRandom. To bootstrap the
|
|
136 |
* defaultGen, we start off using a seed based on current time
|
|
137 |
* unless the java.util.secureRandomSeed property is set. This
|
|
138 |
* serves as a slimmed-down (and insecure) variant of SecureRandom
|
|
139 |
* that also avoids stalls that may occur when using /dev/random.
|
|
140 |
*
|
|
141 |
* It is a relatively simple matter to apply the basic design here
|
|
142 |
* to use 128 bit seeds. However, emulating 128bit arithmetic and
|
|
143 |
* carrying around twice the state add more overhead than appears
|
|
144 |
* warranted for current usages.
|
|
145 |
*
|
|
146 |
* File organization: First the non-public methods that constitute
|
|
147 |
* the main algorithm, then the main public methods, followed by
|
|
148 |
* some custom spliterator classes needed for stream methods.
|
|
149 |
*/
|
|
150 |
|
|
151 |
/**
|
|
152 |
* The golden ratio scaled to 64bits, used as the initial gamma
|
|
153 |
* value for (unsplit) SplittableRandoms.
|
|
154 |
*/
|
|
155 |
private static final long GOLDEN_GAMMA = 0x9e3779b97f4a7c15L;
|
|
156 |
|
|
157 |
/**
|
|
158 |
* The seed. Updated only via method nextSeed.
|
|
159 |
*/
|
|
160 |
private long seed;
|
|
161 |
|
|
162 |
/**
|
|
163 |
* The step value.
|
|
164 |
*/
|
|
165 |
private final long gamma;
|
|
166 |
|
|
167 |
/**
|
|
168 |
* Internal constructor used by all others except default constructor.
|
|
169 |
*/
|
|
170 |
private SplittableRandom(long seed, long gamma) {
|
|
171 |
this.seed = seed;
|
|
172 |
this.gamma = gamma;
|
|
173 |
}
|
|
174 |
|
|
175 |
/* The implementation of AbstractSplittableRng requires this. */
|
|
176 |
// SplittableRandom getThis() { return this; }
|
|
177 |
|
|
178 |
/**
|
|
179 |
* Computes Stafford variant 13 of 64bit mix function.
|
|
180 |
* http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
|
|
181 |
*/
|
|
182 |
private static long mix64(long z) {
|
|
183 |
z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L;
|
|
184 |
z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL;
|
|
185 |
return z ^ (z >>> 31);
|
|
186 |
}
|
|
187 |
|
|
188 |
/**
|
|
189 |
* Returns the 32 high bits of Stafford variant 4 mix64 function as int.
|
|
190 |
* http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
|
|
191 |
*/
|
|
192 |
private static int mix32(long z) {
|
|
193 |
z = (z ^ (z >>> 33)) * 0x62a9d9ed799705f5L;
|
|
194 |
return (int)(((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
|
|
195 |
}
|
|
196 |
|
|
197 |
/**
|
|
198 |
* Returns the gamma value to use for a new split instance.
|
|
199 |
* Uses the 64bit mix function from MurmurHash3.
|
|
200 |
* https://github.com/aappleby/smhasher/wiki/MurmurHash3
|
|
201 |
*/
|
|
202 |
private static long mixGamma(long z) {
|
|
203 |
z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; // MurmurHash3 mix constants
|
|
204 |
z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;
|
|
205 |
z = (z ^ (z >>> 33)) | 1L; // force to be odd
|
|
206 |
int n = Long.bitCount(z ^ (z >>> 1)); // ensure enough transitions
|
|
207 |
return (n < 24) ? z ^ 0xaaaaaaaaaaaaaaaaL : z;
|
|
208 |
}
|
|
209 |
|
|
210 |
/**
|
|
211 |
* Adds gamma to seed.
|
|
212 |
*/
|
|
213 |
private long nextSeed() {
|
|
214 |
return seed += gamma;
|
|
215 |
}
|
|
216 |
|
|
217 |
/**
|
|
218 |
* The seed generator for default constructors.
|
|
219 |
*/
|
|
220 |
private static final AtomicLong defaultGen = new AtomicLong(RngSupport.initialSeed());
|
|
221 |
|
|
222 |
/* ---------------- public methods ---------------- */
|
|
223 |
|
|
224 |
/**
|
|
225 |
* Creates a new SplittableRandom instance using the specified
|
|
226 |
* initial seed. SplittableRandom instances created with the same
|
|
227 |
* seed in the same program generate identical sequences of values.
|
|
228 |
*
|
|
229 |
* @param seed the initial seed
|
|
230 |
*/
|
|
231 |
public SplittableRandom(long seed) {
|
|
232 |
this(seed, GOLDEN_GAMMA);
|
|
233 |
}
|
|
234 |
|
|
235 |
/**
|
|
236 |
* Creates a new SplittableRandom instance that is likely to
|
|
237 |
* generate sequences of values that are statistically independent
|
|
238 |
* of those of any other instances in the current program; and
|
|
239 |
* may, and typically does, vary across program invocations.
|
|
240 |
*/
|
|
241 |
public SplittableRandom() { // emulate defaultGen.split()
|
|
242 |
long s = defaultGen.getAndAdd(2 * GOLDEN_GAMMA);
|
|
243 |
this.seed = mix64(s);
|
|
244 |
this.gamma = mixGamma(s + GOLDEN_GAMMA);
|
|
245 |
}
|
|
246 |
|
|
247 |
// public SplittableRandom copy() { return new SplittableRandom(seed, gamma); }
|
|
248 |
|
|
249 |
/**
|
|
250 |
* Constructs and returns a new SplittableRandom instance that
|
|
251 |
* shares no mutable state with this instance. However, with very
|
|
252 |
* high probability, the set of values collectively generated by
|
|
253 |
* the two objects has the same statistical properties as if the
|
|
254 |
* same quantity of values were generated by a single thread using
|
|
255 |
* a single SplittableRandom object. Either or both of the two
|
|
256 |
* objects may be further split using the {@code split()} method,
|
|
257 |
* and the same expected statistical properties apply to the
|
|
258 |
* entire set of generators constructed by such recursive
|
|
259 |
* splitting.
|
|
260 |
*
|
|
261 |
* @return the new SplittableRandom instance
|
|
262 |
*/
|
|
263 |
public SplittableRandom split() {
|
|
264 |
return new SplittableRandom(nextLong(), mixGamma(nextSeed()));
|
|
265 |
}
|
|
266 |
|
|
267 |
public SplittableRandom split(SplittableRng source) {
|
|
268 |
return new SplittableRandom(source.nextLong(), mixGamma(source.nextLong()));
|
|
269 |
}
|
|
270 |
|
|
271 |
/**
|
|
272 |
* Returns a pseudorandom {@code int} value.
|
|
273 |
*
|
|
274 |
* @return a pseudorandom {@code int} value
|
|
275 |
*/
|
|
276 |
public int nextInt() {
|
|
277 |
return mix32(nextSeed());
|
|
278 |
}
|
|
279 |
|
|
280 |
/**
|
|
281 |
* Returns a pseudorandom {@code long} value.
|
|
282 |
*
|
|
283 |
* @return a pseudorandom {@code long} value
|
|
284 |
*/
|
|
285 |
public long nextLong() {
|
|
286 |
return mix64(nextSeed());
|
|
287 |
}
|
|
288 |
|
|
289 |
static final BigInteger thePeriod = BigInteger.ONE.shiftLeft(64); // Period is 2**64
|
|
290 |
public BigInteger period() { return thePeriod; }
|
|
291 |
|
|
292 |
}
|