1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation. Oracle designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Oracle in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
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.util.Random;
40 import java.util.concurrent.atomic.AtomicInteger;
41 import java.util.concurrent.atomic.AtomicLong;
42 import java.util.stream.DoubleStream;
43 import java.util.stream.IntStream;
44 import java.util.stream.LongStream;
45
46 /**
47 * A random number generator isolated to the current thread. Like the
48 * global {@link java.util.Random} generator used by the {@link
49 * java.lang.Math} class, a {@code ThreadLocalRandom} is initialized
50 * with an internally generated seed that may not otherwise be
51 * modified. When applicable, use of {@code ThreadLocalRandom} rather
52 * than shared {@code Random} objects in concurrent programs will
53 * typically encounter much less overhead and contention. Use of
54 * {@code ThreadLocalRandom} is particularly appropriate when multiple
55 * tasks (for example, each a {@link ForkJoinTask}) use random numbers
56 * in parallel in thread pools.
57 *
58 * <p>Usages of this class should typically be of the form:
59 * {@code ThreadLocalRandom.current().nextX(...)} (where
60 * {@code X} is {@code Int}, {@code Long}, etc).
61 * When all usages are of this form, it is never possible to
62 * accidently share a {@code ThreadLocalRandom} across multiple threads.
63 *
64 * <p>This class also provides additional commonly used bounded random
65 * generation methods.
66 *
67 * @since 1.7
68 * @author Doug Lea
69 */
70 public class ThreadLocalRandom extends Random {
71 /*
72 * This class implements the java.util.Random API (and subclasses
73 * Random) using a single static instance that accesses random
74 * number state held in class Thread (primarily, field
75 * threadLocalRandomSeed). In doing so, it also provides a home
76 * for managing package-private utilities that rely on exactly the
77 * same state as needed to maintain the ThreadLocalRandom
78 * instances. We leverage the need for an initialization flag
79 * field to also use it as a "probe" -- a self-adjusting thread
80 * hash used for contention avoidance, as well as a secondary
81 * simpler (xorShift) random seed that is conservatively used to
82 * avoid otherwise surprising users by hijacking the
83 * ThreadLocalRandom sequence. The dual use is a marriage of
84 * convenience, but is a simple and efficient way of reducing
85 * application-level overhead and footprint of most concurrent
86 * programs.
87 *
88 * Because this class is in a different package than class Thread,
89 * field access methods use Unsafe to bypass access control rules.
90 * The base functionality of Random methods is conveniently
91 * isolated in method next(bits), that just reads and writes the
92 * Thread field rather than its own field. However, to conform to
93 * the requirements of the Random superclass constructor, the
94 * common static ThreadLocalRandom maintains an "initialized"
95 * field for the sake of rejecting user calls to setSeed while
96 * still allowing a call from constructor. Note that
97 * serialization is completely unnecessary because there is only a
98 * static singleton. But we generate a serial form containing
99 * "rnd" and "initialized" fields to ensure compatibility across
100 * versions.
101 *
102 * Per-thread initialization is similar to that in the no-arg
103 * Random constructor, but we avoid correlation among not only
104 * initial seeds of those created in different threads, but also
105 * those created using class Random itself; while at the same time
106 * not changing any statistical properties. So we use the same
107 * underlying multiplicative sequence, but start the sequence far
108 * away from the base version, and then merge (xor) current time
109 * and per-thread probe bits to generate initial values.
110 *
111 * The nextLocalGaussian ThreadLocal supports the very rarely used
112 * nextGaussian method by providing a holder for the second of a
113 * pair of them. As is true for the base class version of this
114 * method, this time/space tradeoff is probably never worthwhile,
115 * but we provide identical statistical properties.
116 */
117
118 // same constants as Random, but must be redeclared because private
119 private static final long multiplier = 0x5DEECE66DL;
120 private static final long addend = 0xBL;
121 private static final long mask = (1L << 48) - 1;
122 private static final int PROBE_INCREMENT = 0x61c88647;
123
124 /** Generates the basis for per-thread initial seed values */
125 private static final AtomicLong seedGenerator =
126 new AtomicLong(1269533684904616924L);
127
128 /** Generates per-thread initialization/probe field */
129 private static final AtomicInteger probeGenerator =
130 new AtomicInteger(0xe80f8647);
131
132 /** Rarely-used holder for the second of a pair of Gaussians */
133 private static final ThreadLocal<Double> nextLocalGaussian =
134 new ThreadLocal<Double>();
135
136 /**
137 * Field used only during singleton initialization.
138 * True when constructor completes.
139 */
140 boolean initialized;
141
142 /** Constructor used only for static singleton */
143 private ThreadLocalRandom() {
144 initialized = true; // false during super() call
145 }
146
147 /** The common ThreadLocalRandom */
148 static final ThreadLocalRandom instance = new ThreadLocalRandom();
149
150 /**
151 * Initialize Thread fields for the current thread. Called only
152 * when Thread.threadLocalRandomProbe is zero, indicating that a
153 * thread local seed value needs to be generated. Note that even
154 * though the initialization is purely thread-local, we need to
155 * rely on (static) atomic generators to initialize the values.
156 */
157 static final void localInit() {
158 int p = probeGenerator.getAndAdd(PROBE_INCREMENT);
159 int probe = (p == 0) ? 1 : p; // skip 0
160 long current, next;
161 do { // same sequence as j.u.Random but different initial value
162 current = seedGenerator.get();
163 next = current * 181783497276652981L;
164 } while (!seedGenerator.compareAndSet(current, next));
165 long r = next ^ ((long)probe << 32) ^ System.nanoTime();
166 Thread t = Thread.currentThread();
167 UNSAFE.putLong(t, SEED, r);
168 UNSAFE.putInt(t, PROBE, probe);
169 }
170
171 /**
172 * Returns the current thread's {@code ThreadLocalRandom}.
173 *
174 * @return the current thread's {@code ThreadLocalRandom}
175 */
176 public static ThreadLocalRandom current() {
177 if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
178 localInit();
179 return instance;
180 }
181
182 /**
183 * Throws {@code UnsupportedOperationException}. Setting seeds in
184 * this generator is not supported.
185 *
186 * @throws UnsupportedOperationException always
187 */
188 public void setSeed(long seed) {
189 // only allow call from super() constructor
190 if (initialized)
191 throw new UnsupportedOperationException();
192 }
193
194 protected int next(int bits) {
195 Thread t; long r; // read and update per-thread seed
196 UNSAFE.putLong
197 (t = Thread.currentThread(), SEED,
198 r = (UNSAFE.getLong(t, SEED) * multiplier + addend) & mask);
199 return (int) (r >>> (48-bits));
200 }
201
202 /**
203 * Returns a pseudorandom, uniformly distributed value between the
204 * given least value (inclusive) and bound (exclusive).
205 *
206 * @param least the least value returned
207 * @param bound the upper bound (exclusive)
208 * @throws IllegalArgumentException if least greater than or equal
209 * to bound
210 * @return the next value
211 */
212 public int nextInt(int least, int bound) {
213 if (least >= bound)
214 throw new IllegalArgumentException();
215 return nextInt(bound - least) + least;
216 }
217
218 /**
219 * Returns a pseudorandom, uniformly distributed value
220 * between 0 (inclusive) and the specified value (exclusive).
221 *
222 * @param n the bound on the random number to be returned. Must be
223 * positive.
224 * @return the next value
225 * @throws IllegalArgumentException if n is not positive
226 */
227 public long nextLong(long n) {
228 if (n <= 0)
229 throw new IllegalArgumentException("n must be positive");
230 // Divide n by two until small enough for nextInt. On each
231 // iteration (at most 31 of them but usually much less),
232 // randomly choose both whether to include high bit in result
233 // (offset) and whether to continue with the lower vs upper
234 // half (which makes a difference only if odd).
235 long offset = 0;
236 while (n >= Integer.MAX_VALUE) {
237 int bits = next(2);
238 long half = n >>> 1;
239 long nextn = ((bits & 2) == 0) ? half : n - half;
240 if ((bits & 1) == 0)
241 offset += n - nextn;
242 n = nextn;
243 }
244 return offset + nextInt((int) n);
245 }
246
247 @Override
248 public IntStream ints() {
249 return IntStream.generate(() -> current().nextInt());
250 }
251
252 @Override
253 public LongStream longs() {
254 return LongStream.generate(() -> current().nextLong());
255 }
256
257 @Override
258 public DoubleStream doubles() {
259 return DoubleStream.generate(() -> current().nextDouble());
260 }
261
262 @Override
263 public DoubleStream gaussians() {
264 return DoubleStream.generate(() -> current().nextGaussian());
265 }
266
267 /**
268 * Returns a pseudorandom, uniformly distributed value between the
269 * given least value (inclusive) and bound (exclusive).
270 *
271 * @param least the least value returned
272 * @param bound the upper bound (exclusive)
273 * @return the next value
274 * @throws IllegalArgumentException if least greater than or equal
275 * to bound
276 */
277 public long nextLong(long least, long bound) {
278 if (least >= bound)
279 throw new IllegalArgumentException();
280 return nextLong(bound - least) + least;
281 }
282
283 /**
284 * Returns a pseudorandom, uniformly distributed {@code double} value
285 * between 0 (inclusive) and the specified value (exclusive).
286 *
287 * @param n the bound on the random number to be returned. Must be
288 * positive.
289 * @return the next value
290 * @throws IllegalArgumentException if n is not positive
291 */
292 public double nextDouble(double n) {
293 if (n <= 0)
294 throw new IllegalArgumentException("n must be positive");
295 return nextDouble() * n;
296 }
297
298 /**
299 * Returns a pseudorandom, uniformly distributed value between the
300 * given least value (inclusive) and bound (exclusive).
301 *
302 * @param least the least value returned
303 * @param bound the upper bound (exclusive)
304 * @return the next value
305 * @throws IllegalArgumentException if least greater than or equal
306 * to bound
307 */
308 public double nextDouble(double least, double bound) {
309 if (least >= bound)
310 throw new IllegalArgumentException();
311 return nextDouble() * (bound - least) + least;
312 }
313
314 public double nextGaussian() {
315 // Use nextLocalGaussian instead of nextGaussian field
316 Double d = nextLocalGaussian.get();
317 if (d != null) {
318 nextLocalGaussian.set(null);
319 return d.doubleValue();
320 }
321 double v1, v2, s;
322 do {
323 v1 = 2 * nextDouble() - 1; // between -1 and 1
324 v2 = 2 * nextDouble() - 1; // between -1 and 1
325 s = v1 * v1 + v2 * v2;
326 } while (s >= 1 || s == 0);
327 double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
328 nextLocalGaussian.set(new Double(v2 * multiplier));
329 return v1 * multiplier;
330 }
331
332 // Within-package utilities
333
334 /*
335 * Descriptions of the usages of the methods below can be found in
336 * the classes that use them. Briefly, a thread's "probe" value is
337 * a non-zero hash code that (probably) does not collide with
338 * other existing threads with respect to any power of two
339 * collision space. When it does collide, it is pseudo-randomly
340 * adjusted (using a Marsaglia XorShift). The nextSecondarySeed
341 * method is used in the same contexts as ThreadLocalRandom, but
342 * only for transient usages such as random adaptive spin/block
343 * sequences for which a cheap RNG suffices and for which it could
344 * in principle disrupt user-visible statistical properties of the
345 * main ThreadLocalRandom if we were to use it.
346 *
347 * Note: Because of package-protection issues, versions of some
348 * these methods also appear in some subpackage classes.
349 */
350
351 /**
352 * Returns the probe value for the current thread without forcing
353 * initialization. Note that invoking ThreadLocalRandom.current()
354 * can be used to force initialization on zero return.
355 */
356 static final int getProbe() {
357 return UNSAFE.getInt(Thread.currentThread(), PROBE);
358 }
359
360 /**
361 * Pseudo-randomly advances and records the given probe value for the
362 * given thread.
363 */
364 static final int advanceProbe(int probe) {
365 probe ^= probe << 13; // xorshift
366 probe ^= probe >>> 17;
367 probe ^= probe << 5;
368 UNSAFE.putInt(Thread.currentThread(), PROBE, probe);
369 return probe;
370 }
371
372 /**
373 * Returns the pseudo-randomly initialized or updated secondary seed.
374 */
375 static final int nextSecondarySeed() {
376 int r;
377 Thread t = Thread.currentThread();
378 if ((r = UNSAFE.getInt(t, SECONDARY)) != 0) {
379 r ^= r << 13; // xorshift
380 r ^= r >>> 17;
381 r ^= r << 5;
382 }
383 else {
384 localInit();
385 if ((r = (int)UNSAFE.getLong(t, SEED)) == 0)
386 r = 1; // avoid zero
387 }
388 UNSAFE.putInt(t, SECONDARY, r);
389 return r;
390 }
391
392 // Serialization support
393
394 private static final long serialVersionUID = -5851777807851030925L;
395
396 /**
397 * @serialField rnd long
398 * seed for random computations
399 * @serialField initialized boolean
400 * always true
401 */
402 private static final ObjectStreamField[] serialPersistentFields = {
403 new ObjectStreamField("rnd", long.class),
404 new ObjectStreamField("initialized", boolean.class)
405 };
406
407 /**
408 * Saves the {@code ThreadLocalRandom} to a stream (that is, serializes it).
409 */
410 private void writeObject(java.io.ObjectOutputStream out)
411 throws java.io.IOException {
412
413 java.io.ObjectOutputStream.PutField fields = out.putFields();
414 fields.put("rnd", UNSAFE.getLong(Thread.currentThread(), SEED));
415 fields.put("initialized", true);
416 out.writeFields();
417 }
418
419 /**
420 * Returns the {@link #current() current} thread's {@code ThreadLocalRandom}.
421 */
422 private Object readResolve() {
423 return current();
424 }
425
426 // Unsafe mechanics
427 private static final sun.misc.Unsafe UNSAFE;
428 private static final long SEED;
429 private static final long PROBE;
430 private static final long SECONDARY;
431 static {
432 try {
433 UNSAFE = sun.misc.Unsafe.getUnsafe();
434 Class<?> tk = Thread.class;
435 SEED = UNSAFE.objectFieldOffset
436 (tk.getDeclaredField("threadLocalRandomSeed"));
437 PROBE = UNSAFE.objectFieldOffset
438 (tk.getDeclaredField("threadLocalRandomProbe"));
439 SECONDARY = UNSAFE.objectFieldOffset
440 (tk.getDeclaredField("threadLocalRandomSecondarySeed"));
441 } catch (Exception e) {
442 throw new Error(e);
443 }
444 }
445 }