57369
|
1 |
/*
|
|
2 |
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
|
|
3 |
*
|
|
4 |
*
|
|
5 |
*
|
|
6 |
*
|
|
7 |
*
|
|
8 |
*
|
|
9 |
*
|
|
10 |
*
|
|
11 |
*
|
|
12 |
*
|
|
13 |
*
|
|
14 |
*
|
|
15 |
*
|
|
16 |
*
|
|
17 |
*
|
|
18 |
*
|
|
19 |
*
|
|
20 |
*
|
|
21 |
*
|
|
22 |
*
|
|
23 |
*/
|
|
24 |
|
|
25 |
/*
|
|
26 |
*
|
|
27 |
*
|
|
28 |
*
|
|
29 |
*
|
|
30 |
*
|
|
31 |
* Written by Doug Lea with assistance from members of JCP JSR-166
|
|
32 |
* Expert Group and released to the public domain, as explained at
|
|
33 |
* http://creativecommons.org/publicdomain/zero/1.0/
|
|
34 |
*/
|
|
35 |
|
|
36 |
// package java.util.concurrent;
|
|
37 |
|
|
38 |
import java.io.ObjectStreamField;
|
|
39 |
import java.math.BigInteger;
|
|
40 |
// import java.util.Random;
|
|
41 |
import java.util.Spliterator;
|
|
42 |
import java.util.concurrent.atomic.AtomicInteger;
|
|
43 |
import java.util.concurrent.atomic.AtomicLong;
|
|
44 |
|
|
45 |
/**
|
|
46 |
* A random number generator isolated to the current thread. Like the
|
|
47 |
* global {@link java.util.Random} generator used by the {@link
|
|
48 |
* java.lang.Math} class, a {@code ThreadLocalRandom} is initialized
|
|
49 |
* with an internally generated seed that may not otherwise be
|
|
50 |
* modified. When applicable, use of {@code ThreadLocalRandom} rather
|
|
51 |
* than shared {@code Random} objects in concurrent programs will
|
|
52 |
* typically encounter much less overhead and contention. Use of
|
|
53 |
* {@code ThreadLocalRandom} is particularly appropriate when multiple
|
|
54 |
* tasks (for example, each a {@link ForkJoinTask}) use random numbers
|
|
55 |
* in parallel in thread pools.
|
|
56 |
*
|
|
57 |
* <p>Usages of this class should typically be of the form:
|
|
58 |
* {@code ThreadLocalRandom.current().nextX(...)} (where
|
|
59 |
* {@code X} is {@code Int}, {@code Long}, etc).
|
|
60 |
* When all usages are of this form, it is never possible to
|
|
61 |
* accidently share a {@code ThreadLocalRandom} across multiple threads.
|
|
62 |
*
|
|
63 |
* <p>This class also provides additional commonly used bounded random
|
|
64 |
* generation methods.
|
|
65 |
*
|
|
66 |
* <p>Instances of {@code ThreadLocalRandom} are not cryptographically
|
|
67 |
* secure. Consider instead using {@link java.security.SecureRandom}
|
|
68 |
* in security-sensitive applications. Additionally,
|
|
69 |
* default-constructed instances do not use a cryptographically random
|
|
70 |
* seed unless the {@linkplain System#getProperty system property}
|
|
71 |
* {@code java.util.secureRandomSeed} is set to {@code true}.
|
|
72 |
*
|
|
73 |
* @since 1.7
|
|
74 |
* @author Doug Lea
|
|
75 |
*/
|
|
76 |
public class ThreadLocalRandom extends Random {
|
|
77 |
/*
|
|
78 |
* This class implements the java.util.Random API (and subclasses
|
|
79 |
* Random) using a single static instance that accesses random
|
|
80 |
* number state held in class Thread (primarily, field
|
|
81 |
* threadLocalRandomSeed). In doing so, it also provides a home
|
|
82 |
* for managing package-private utilities that rely on exactly the
|
|
83 |
* same state as needed to maintain the ThreadLocalRandom
|
|
84 |
* instances. We leverage the need for an initialization flag
|
|
85 |
* field to also use it as a "probe" -- a self-adjusting thread
|
|
86 |
* hash used for contention avoidance, as well as a secondary
|
|
87 |
* simpler (xorShift) random seed that is conservatively used to
|
|
88 |
* avoid otherwise surprising users by hijacking the
|
|
89 |
* ThreadLocalRandom sequence. The dual use is a marriage of
|
|
90 |
* convenience, but is a simple and efficient way of reducing
|
|
91 |
* application-level overhead and footprint of most concurrent
|
|
92 |
* programs.
|
|
93 |
*
|
|
94 |
* Even though this class subclasses java.util.Random, it uses the
|
|
95 |
* same basic algorithm as java.util.SplittableRandom. (See its
|
|
96 |
* internal documentation for explanations, which are not repeated
|
|
97 |
* here.) Because ThreadLocalRandoms are not splittable
|
|
98 |
* though, we use only a single 64bit gamma.
|
|
99 |
*
|
|
100 |
* Because this class is in a different package than class Thread,
|
|
101 |
* field access methods use Unsafe to bypass access control rules.
|
|
102 |
* To conform to the requirements of the Random superclass
|
|
103 |
* constructor, the common static ThreadLocalRandom maintains an
|
|
104 |
* "initialized" field for the sake of rejecting user calls to
|
|
105 |
* setSeed while still allowing a call from constructor. Note
|
|
106 |
* that serialization is completely unnecessary because there is
|
|
107 |
* only a static singleton. But we generate a serial form
|
|
108 |
* containing "rnd" and "initialized" fields to ensure
|
|
109 |
* compatibility across versions.
|
|
110 |
*
|
|
111 |
* Implementations of non-core methods are mostly the same as in
|
|
112 |
* SplittableRandom, that were in part derived from a previous
|
|
113 |
* version of this class.
|
|
114 |
*
|
|
115 |
* The nextLocalGaussian ThreadLocal supports the very rarely used
|
|
116 |
* nextGaussian method by providing a holder for the second of a
|
|
117 |
* pair of them. As is true for the base class version of this
|
|
118 |
* method, this time/space tradeoff is probably never worthwhile,
|
|
119 |
* but we provide identical statistical properties.
|
|
120 |
*/
|
|
121 |
|
|
122 |
/** Generates per-thread initialization/probe field */
|
|
123 |
private static final AtomicInteger probeGenerator =
|
|
124 |
new AtomicInteger();
|
|
125 |
|
|
126 |
/**
|
|
127 |
* The next seed for default constructors.
|
|
128 |
*/
|
|
129 |
private static final AtomicLong seeder = new AtomicLong(RngSupport.initialSeed());
|
|
130 |
|
|
131 |
/**
|
|
132 |
* The seed increment
|
|
133 |
*/
|
|
134 |
private static final long GAMMA = 0x9e3779b97f4a7c15L;
|
|
135 |
|
|
136 |
/**
|
|
137 |
* The increment for generating probe values
|
|
138 |
*/
|
|
139 |
private static final int PROBE_INCREMENT = 0x9e3779b9;
|
|
140 |
|
|
141 |
/**
|
|
142 |
* The increment of seeder per new instance
|
|
143 |
*/
|
|
144 |
private static final long SEEDER_INCREMENT = 0xbb67ae8584caa73bL;
|
|
145 |
|
|
146 |
// Constants from SplittableRandom
|
|
147 |
private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53)
|
|
148 |
private static final float FLOAT_UNIT = 0x1.0p-24f; // 1.0f / (1 << 24)
|
|
149 |
|
|
150 |
/** Rarely-used holder for the second of a pair of Gaussians */
|
|
151 |
private static final ThreadLocal<Double> nextLocalGaussian =
|
|
152 |
new ThreadLocal<Double>();
|
|
153 |
|
|
154 |
private static long mix64(long z) {
|
|
155 |
z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
|
|
156 |
z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;
|
|
157 |
return z ^ (z >>> 33);
|
|
158 |
}
|
|
159 |
|
|
160 |
private static int mix32(long z) {
|
|
161 |
z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
|
|
162 |
return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32);
|
|
163 |
}
|
|
164 |
|
|
165 |
/**
|
|
166 |
* Field used only during singleton initialization.
|
|
167 |
* True when constructor completes.
|
|
168 |
*/
|
|
169 |
boolean initialized;
|
|
170 |
|
|
171 |
/** Constructor used only for static singleton */
|
|
172 |
private ThreadLocalRandom() {
|
|
173 |
initialized = true; // false during super() call
|
|
174 |
}
|
|
175 |
|
|
176 |
/** The common ThreadLocalRandom */
|
|
177 |
static final ThreadLocalRandom instance = new ThreadLocalRandom();
|
|
178 |
|
|
179 |
/**
|
|
180 |
* Initialize Thread fields for the current thread. Called only
|
|
181 |
* when Thread.threadLocalRandomProbe is zero, indicating that a
|
|
182 |
* thread local seed value needs to be generated. Note that even
|
|
183 |
* though the initialization is purely thread-local, we need to
|
|
184 |
* rely on (static) atomic generators to initialize the values.
|
|
185 |
*/
|
|
186 |
static final void localInit() {
|
|
187 |
int p = probeGenerator.addAndGet(PROBE_INCREMENT);
|
|
188 |
int probe = (p == 0) ? 1 : p; // skip 0
|
|
189 |
long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));
|
|
190 |
Thread t = Thread.currentThread();
|
|
191 |
UNSAFE.putLong(t, SEED, seed);
|
|
192 |
UNSAFE.putInt(t, PROBE, probe);
|
|
193 |
}
|
|
194 |
|
|
195 |
/**
|
|
196 |
* Returns the current thread's {@code ThreadLocalRandom}.
|
|
197 |
*
|
|
198 |
* @return the current thread's {@code ThreadLocalRandom}
|
|
199 |
*/
|
|
200 |
public static ThreadLocalRandom current() {
|
|
201 |
if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
|
|
202 |
localInit();
|
|
203 |
return instance;
|
|
204 |
}
|
|
205 |
|
|
206 |
/**
|
|
207 |
* Throws {@code UnsupportedOperationException}. Setting seeds in
|
|
208 |
* this generator is not supported.
|
|
209 |
*
|
|
210 |
* @throws UnsupportedOperationException always
|
|
211 |
*/
|
|
212 |
public void setSeed(long seed) {
|
|
213 |
// only allow call from super() constructor
|
|
214 |
if (initialized)
|
|
215 |
throw new UnsupportedOperationException();
|
|
216 |
}
|
|
217 |
|
|
218 |
final long nextSeed() {
|
|
219 |
Thread t; long r; // read and update per-thread seed
|
|
220 |
UNSAFE.putLong(t = Thread.currentThread(), SEED,
|
|
221 |
r = UNSAFE.getLong(t, SEED) + GAMMA);
|
|
222 |
return r;
|
|
223 |
}
|
|
224 |
|
|
225 |
// We must define this (to override the definition inherited from
|
|
226 |
// class Random), but we don't use it from within other methods.
|
|
227 |
protected int next(int bits) {
|
|
228 |
return (int)(mix64(nextSeed()) >>> (64 - bits));
|
|
229 |
}
|
|
230 |
|
|
231 |
/**
|
|
232 |
* Returns a pseudorandom {@code int} value.
|
|
233 |
*
|
|
234 |
* @return a pseudorandom {@code int} value
|
|
235 |
*/
|
|
236 |
public int nextInt() {
|
|
237 |
return mix32(nextSeed());
|
|
238 |
}
|
|
239 |
|
|
240 |
/**
|
|
241 |
* Returns a pseudorandom {@code long} value.
|
|
242 |
*
|
|
243 |
* @return a pseudorandom {@code long} value
|
|
244 |
*/
|
|
245 |
public long nextLong() {
|
|
246 |
return mix64(nextSeed());
|
|
247 |
}
|
|
248 |
|
|
249 |
public double nextGaussian() {
|
|
250 |
// Use nextLocalGaussian instead of nextGaussian field
|
|
251 |
Double d = nextLocalGaussian.get();
|
|
252 |
if (d != null) {
|
|
253 |
nextLocalGaussian.set(null);
|
|
254 |
return d.doubleValue();
|
|
255 |
}
|
|
256 |
double v1, v2, s;
|
|
257 |
do {
|
|
258 |
v1 = 2 * nextDouble() - 1; // between -1 and 1
|
|
259 |
v2 = 2 * nextDouble() - 1; // between -1 and 1
|
|
260 |
s = v1 * v1 + v2 * v2;
|
|
261 |
} while (s >= 1 || s == 0);
|
|
262 |
double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
|
|
263 |
nextLocalGaussian.set(new Double(v2 * multiplier));
|
|
264 |
return v1 * multiplier;
|
|
265 |
}
|
|
266 |
|
|
267 |
static final BigInteger thePeriod = BigInteger.valueOf(1).shiftLeft(64); // Period is 2**64
|
|
268 |
public BigInteger period() { return thePeriod; }
|
|
269 |
|
|
270 |
// Within-package utilities
|
|
271 |
|
|
272 |
/*
|
|
273 |
* Descriptions of the usages of the methods below can be found in
|
|
274 |
* the classes that use them. Briefly, a thread's "probe" value is
|
|
275 |
* a non-zero hash code that (probably) does not collide with
|
|
276 |
* other existing threads with respect to any power of two
|
|
277 |
* collision space. When it does collide, it is pseudo-randomly
|
|
278 |
* adjusted (using a Marsaglia XorShift). The nextSecondarySeed
|
|
279 |
* method is used in the same contexts as ThreadLocalRandom, but
|
|
280 |
* only for transient usages such as random adaptive spin/block
|
|
281 |
* sequences for which a cheap Rng suffices and for which it could
|
|
282 |
* in principle disrupt user-visible statistical properties of the
|
|
283 |
* main ThreadLocalRandom if we were to use it.
|
|
284 |
*
|
|
285 |
* Note: Because of package-protection issues, versions of some
|
|
286 |
* these methods also appear in some subpackage classes.
|
|
287 |
*/
|
|
288 |
|
|
289 |
/**
|
|
290 |
* Returns the probe value for the current thread without forcing
|
|
291 |
* initialization. Note that invoking ThreadLocalRandom.current()
|
|
292 |
* can be used to force initialization on zero return.
|
|
293 |
*/
|
|
294 |
static final int getProbe() {
|
|
295 |
return UNSAFE.getInt(Thread.currentThread(), PROBE);
|
|
296 |
}
|
|
297 |
|
|
298 |
/**
|
|
299 |
* Pseudo-randomly advances and records the given probe value for the
|
|
300 |
* given thread.
|
|
301 |
*/
|
|
302 |
static final int advanceProbe(int probe) {
|
|
303 |
probe ^= probe << 13; // xorshift
|
|
304 |
probe ^= probe >>> 17;
|
|
305 |
probe ^= probe << 5;
|
|
306 |
UNSAFE.putInt(Thread.currentThread(), PROBE, probe);
|
|
307 |
return probe;
|
|
308 |
}
|
|
309 |
|
|
310 |
/**
|
|
311 |
* Returns the pseudo-randomly initialized or updated secondary seed.
|
|
312 |
*/
|
|
313 |
static final int nextSecondarySeed() {
|
|
314 |
int r;
|
|
315 |
Thread t = Thread.currentThread();
|
|
316 |
if ((r = UNSAFE.getInt(t, SECONDARY)) != 0) {
|
|
317 |
r ^= r << 13; // xorshift
|
|
318 |
r ^= r >>> 17;
|
|
319 |
r ^= r << 5;
|
|
320 |
}
|
|
321 |
else {
|
|
322 |
localInit();
|
|
323 |
if ((r = (int)UNSAFE.getLong(t, SEED)) == 0)
|
|
324 |
r = 1; // avoid zero
|
|
325 |
}
|
|
326 |
UNSAFE.putInt(t, SECONDARY, r);
|
|
327 |
return r;
|
|
328 |
}
|
|
329 |
|
|
330 |
// Serialization support
|
|
331 |
|
|
332 |
private static final long serialVersionUID = -5851777807851030925L;
|
|
333 |
|
|
334 |
/**
|
|
335 |
* @serialField rnd long
|
|
336 |
* seed for random computations
|
|
337 |
* @serialField initialized boolean
|
|
338 |
* always true
|
|
339 |
*/
|
|
340 |
private static final ObjectStreamField[] serialPersistentFields = {
|
|
341 |
new ObjectStreamField("rnd", long.class),
|
|
342 |
new ObjectStreamField("initialized", boolean.class),
|
|
343 |
};
|
|
344 |
|
|
345 |
/**
|
|
346 |
* Saves the {@code ThreadLocalRandom} to a stream (that is, serializes it).
|
|
347 |
* @param s the stream
|
|
348 |
* @throws java.io.IOException if an I/O error occurs
|
|
349 |
*/
|
|
350 |
private void writeObject(java.io.ObjectOutputStream s)
|
|
351 |
throws java.io.IOException {
|
|
352 |
|
|
353 |
java.io.ObjectOutputStream.PutField fields = s.putFields();
|
|
354 |
fields.put("rnd", UNSAFE.getLong(Thread.currentThread(), SEED));
|
|
355 |
fields.put("initialized", true);
|
|
356 |
s.writeFields();
|
|
357 |
}
|
|
358 |
|
|
359 |
/**
|
|
360 |
* Returns the {@link #current() current} thread's {@code ThreadLocalRandom}.
|
|
361 |
* @return the {@link #current() current} thread's {@code ThreadLocalRandom}
|
|
362 |
*/
|
|
363 |
private Object readResolve() {
|
|
364 |
return current();
|
|
365 |
}
|
|
366 |
|
|
367 |
// Unsafe mechanics
|
|
368 |
private static final sun.misc.Unsafe UNSAFE;
|
|
369 |
private static final long SEED;
|
|
370 |
private static final long PROBE;
|
|
371 |
private static final long SECONDARY;
|
|
372 |
static {
|
|
373 |
try {
|
|
374 |
UNSAFE = sun.misc.Unsafe.getUnsafe();
|
|
375 |
Class<?> tk = Thread.class;
|
|
376 |
SEED = UNSAFE.objectFieldOffset
|
|
377 |
(tk.getDeclaredField("threadLocalRandomSeed"));
|
|
378 |
PROBE = UNSAFE.objectFieldOffset
|
|
379 |
(tk.getDeclaredField("threadLocalRandomProbe"));
|
|
380 |
SECONDARY = UNSAFE.objectFieldOffset
|
|
381 |
(tk.getDeclaredField("threadLocalRandomSecondarySeed"));
|
|
382 |
} catch (Exception e) {
|
|
383 |
throw new Error(e);
|
|
384 |
}
|
|
385 |
}
|
|
386 |
}
|