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