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.util.Random;
39
40 /**
41 * A random number generator isolated to the current thread. Like the
42 * global {@link java.util.Random} generator used by the {@link
43 * java.lang.Math} class, a {@code ThreadLocalRandom} is initialized
44 * with an internally generated seed that may not otherwise be
45 * modified. When applicable, use of {@code ThreadLocalRandom} rather
46 * than shared {@code Random} objects in concurrent programs will
47 * typically encounter much less overhead and contention. Use of
48 * {@code ThreadLocalRandom} is particularly appropriate when multiple
49 * tasks (for example, each a {@link ForkJoinTask}) use random numbers
50 * in parallel in thread pools.
51 *
52 * <p>Usages of this class should typically be of the form:
53 * {@code ThreadLocalRandom.current().nextX(...)} (where
54 * {@code X} is {@code Int}, {@code Long}, etc).
55 * When all usages are of this form, it is never possible to
56 * accidently share a {@code ThreadLocalRandom} across multiple threads.
57 *
58 * <p>This class also provides additional commonly used bounded random
59 * generation methods.
60 *
61 * @since 1.7
62 * @author Doug Lea
63 */
64 public class ThreadLocalRandom extends Random {
65 // same constants as Random, but must be redeclared because private
66 private static final long multiplier = 0x5DEECE66DL;
67 private static final long addend = 0xBL;
68 private static final long mask = (1L << 48) - 1;
69
70 /**
71 * The random seed. We can't use super.seed.
72 */
73 private long rnd;
74
75 /**
76 * Initialization flag to permit calls to setSeed to succeed only
77 * while executing the Random constructor. We can't allow others
78 * since it would cause setting seed in one part of a program to
79 * unintentionally impact other usages by the thread.
80 */
81 boolean initialized;
82
83 // Padding to help avoid memory contention among seed updates in
84 // different TLRs in the common case that they are located near
85 // each other.
86 private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
87
88 /**
89 * The actual ThreadLocal
90 */
91 private static final ThreadLocal<ThreadLocalRandom> localRandom =
92 new ThreadLocal<ThreadLocalRandom>() {
93 protected ThreadLocalRandom initialValue() {
94 return new ThreadLocalRandom();
95 }
96 };
97
98
99 /**
100 * Constructor called only by localRandom.initialValue.
101 */
102 ThreadLocalRandom() {
103 super();
104 initialized = true;
105 }
106
107 /**
108 * Returns the current thread's {@code ThreadLocalRandom}.
109 *
110 * @return the current thread's {@code ThreadLocalRandom}
111 */
112 public static ThreadLocalRandom current() {
113 return localRandom.get();
114 }
115
116 /**
117 * Throws {@code UnsupportedOperationException}. Setting seeds in
118 * this generator is not supported.
119 *
120 * @throws UnsupportedOperationException always
121 */
122 public void setSeed(long seed) {
123 if (initialized)
124 throw new UnsupportedOperationException();
125 rnd = (seed ^ multiplier) & mask;
126 }
127
128 protected int next(int bits) {
129 rnd = (rnd * multiplier + addend) & mask;
130 return (int) (rnd >>> (48-bits));
131 }
132
133 /**
134 * Returns a pseudorandom, uniformly distributed value between the
135 * given least value (inclusive) and bound (exclusive).
136 *
137 * @param least the least value returned
138 * @param bound the upper bound (exclusive)
139 * @throws IllegalArgumentException if least greater than or equal
140 * to bound
141 * @return the next value
142 */
143 public int nextInt(int least, int bound) {
144 if (least >= bound)
145 throw new IllegalArgumentException();
146 return nextInt(bound - least) + least;
147 }
148
149 /**
150 * Returns a pseudorandom, uniformly distributed value
205 throw new IllegalArgumentException("n must be positive");
206 return nextDouble() * n;
207 }
208
209 /**
210 * Returns a pseudorandom, uniformly distributed value between the
211 * given least value (inclusive) and bound (exclusive).
212 *
213 * @param least the least value returned
214 * @param bound the upper bound (exclusive)
215 * @return the next value
216 * @throws IllegalArgumentException if least greater than or equal
217 * to bound
218 */
219 public double nextDouble(double least, double bound) {
220 if (least >= bound)
221 throw new IllegalArgumentException();
222 return nextDouble() * (bound - least) + least;
223 }
224
225 private static final long serialVersionUID = -5851777807851030925L;
226 }
|
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 must use Unsafe to bypass access control
87 * rules. The base functionality of Random methods is
88 * conveniently isolated in method next(bits), that just reads and
89 * writes the Thread field rather than its own field. However, to
90 * conform to the requirements of the Random constructor, during
91 * construction, the common static ThreadLocalRandom must maintain
92 * initialization and value fields, mainly for the sake of
93 * disabling user calls to setSeed while still allowing a call
94 * from constructor. For serialization compatibility, these
95 * fields are left with the same declarations as used in the
96 * previous ThreadLocal-based version of this class, that used
97 * them differently. Note that serialization is completely
98 * unnecessary because there is only a static singleton. But these
99 * mechanics still ensure compatibility across versions.
100 *
101 * Per-instance initialization is similar to that in the no-arg
102 * Random constructor, but we avoid correlation among not only
103 * initial seeds of those created in different threads, but also
104 * those created using class Random itself; while at the same time
105 * not changing any statistical properties. So we use the same
106 * underlying multiplicative sequence, but start the sequence far
107 * away from the base version, and then merge (xor) current time
108 * and per-thread probe bits to generate initial values.
109 *
110 * The nextLocalGaussian ThreadLocal supports the very rarely used
111 * nextGaussian method by providing a holder for the second of a
112 * pair of them. As is true for the base class version of this
113 * method, this time/space tradeoff is probably never worthwhile,
114 * but we provide identical statistical properties.
115 */
116
117 // same constants as Random, but must be redeclared because private
118 private static final long multiplier = 0x5DEECE66DL;
119 private static final long addend = 0xBL;
120 private static final long mask = (1L << 48) - 1;
121 private static final int PROBE_INCREMENT = 0x61c88647;
122
123 /** Generates the basis for per-thread initial seed values */
124 private static final AtomicLong seedGenerator =
125 new AtomicLong(1269533684904616924L);
126
127 /** Generates per-thread initialization/probe field */
128 private static final AtomicInteger probeGenerator =
129 new AtomicInteger(0xe80f8647);
130
131 /** Rarely-used holder for the second of a pair of Gaussians */
132 private static final ThreadLocal<Double> nextLocalGaussian =
133 new ThreadLocal<Double>();
134
135 /*
136 * Field used only during singleton initialization
137 */
138 boolean initialized; // true when constructor completes
139
140 /** Constructor used only for static singleton */
141 private ThreadLocalRandom() {
142 initialized = true; // false during super() call
143 }
144
145 /** The common ThreadLocalRandom */
146 static final ThreadLocalRandom instance = new ThreadLocalRandom();
147
148 /**
149 * Initialize Thread fields for the current thread. Called only
150 * when Thread.threadLocalRandomProbe is zero, indicating that a
151 * thread local seed value needs to be generated. Note that even
152 * though the initialization is purely thread-local, we need to
153 * rely on (static) atomic generators to initialize the values.
154 */
155 static final void localInit() {
156 int p = probeGenerator.getAndAdd(PROBE_INCREMENT);
157 int probe = (p == 0) ? 1 : p; // skip 0
158 long current, next;
159 do { // same sequence as j.u.Random but different initial value
160 current = seedGenerator.get();
161 next = current * 181783497276652981L;
162 } while (!seedGenerator.compareAndSet(current, next));
163 long r = next ^ ((long)probe << 32) ^ System.nanoTime();
164 Thread t = Thread.currentThread();
165 UNSAFE.putLong(t, SEED, r);
166 UNSAFE.putInt(t, PROBE, probe);
167 }
168
169 /**
170 * Returns the current thread's {@code ThreadLocalRandom}.
171 *
172 * @return the current thread's {@code ThreadLocalRandom}
173 */
174 public static ThreadLocalRandom current() {
175 if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
176 localInit();
177 return instance;
178 }
179
180 /**
181 * Throws {@code UnsupportedOperationException}. Setting seeds in
182 * this generator is not supported.
183 *
184 * @throws UnsupportedOperationException always
185 */
186 public void setSeed(long seed) {
187 if (initialized) // allow call from super() constructor
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
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 if ((r = (int)UNSAFE.getLong(t, SEED)) == 0)
361 r = 1; // avoid zero
362 UNSAFE.putInt(t, SECONDARY, r);
363 return r;
364 }
365
366 // Serialization support, maintains original persistent form.
367
368 private static final long serialVersionUID = -5851777807851030925L;
369
370 /**
371 * @serialField rnd long
372 * @serialField initialized boolean
373 * @serialField pad0 long
374 * @serialField pad1 long
375 * @serialField pad2 long
376 * @serialField pad3 long
377 * @serialField pad4 long
378 * @serialField pad5 long
379 * @serialField pad6 long
380 * @serialField pad7 long
381 */
382 private static final ObjectStreamField[] serialPersistentFields = {
383 new ObjectStreamField("rnd", long.class),
384 new ObjectStreamField("initialized", boolean.class),
385 new ObjectStreamField("pad0", long.class),
386 new ObjectStreamField("pad1", long.class),
387 new ObjectStreamField("pad2", long.class),
388 new ObjectStreamField("pad3", long.class),
389 new ObjectStreamField("pad4", long.class),
390 new ObjectStreamField("pad5", long.class),
391 new ObjectStreamField("pad6", long.class),
392 new ObjectStreamField("pad7", long.class) };
393
394 /**
395 * Saves the {@code ThreadLocalRandom} to a stream (that is, serializes it).
396 */
397 private void writeObject(java.io.ObjectOutputStream out)
398 throws java.io.IOException {
399
400 java.io.ObjectOutputStream.PutField fields = out.putFields();
401 fields.put("rnd", 0L);
402 fields.put("initialized", true);
403 fields.put("pad0", 0L);
404 fields.put("pad1", 0L);
405 fields.put("pad2", 0L);
406 fields.put("pad3", 0L);
407 fields.put("pad4", 0L);
408 fields.put("pad5", 0L);
409 fields.put("pad6", 0L);
410 fields.put("pad7", 0L);
411 out.writeFields();
412 }
413
414 /**
415 * Returns the {@link #current() current} thread's {@code ThreadLocalRandom}.
416 */
417 private Object readResolve() {
418 return current();
419 }
420
421 // Unsafe mechanics
422 private static final sun.misc.Unsafe UNSAFE;
423 private static final long SEED;
424 private static final long PROBE;
425 private static final long SECONDARY;
426 static {
427 try {
428 UNSAFE = sun.misc.Unsafe.getUnsafe();
429 Class<?> tk = Thread.class;
430 SEED = UNSAFE.objectFieldOffset
431 (tk.getDeclaredField("threadLocalRandomSeed"));
432 PROBE = UNSAFE.objectFieldOffset
433 (tk.getDeclaredField("threadLocalRandomProbe"));
434 SECONDARY = UNSAFE.objectFieldOffset
435 (tk.getDeclaredField("threadLocalRandomSecondarySeed"));
436 } catch (Exception e) {
437 throw new Error(e);
438 }
439 }
440 }
|