| /* |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| /* |
| * This file is available under and governed by the GNU General Public |
| * License version 2 only, as published by the Free Software Foundation. |
| * However, the following notice accompanied the original version of this |
| * file: |
| * |
| * Written by Doug Lea with assistance from members of JCP JSR-166 |
| * Expert Group and released to the public domain, as explained at |
| * http://creativecommons.org/publicdomain/zero/1.0/ |
| */ |
| |
| package java.util.concurrent; |
| |
| import java.io.ObjectStreamField; |
| import java.util.Random; |
| import java.util.concurrent.atomic.AtomicInteger; |
| import java.util.concurrent.atomic.AtomicLong; |
| import java.util.stream.DoubleStream; |
| import java.util.stream.IntStream; |
| import java.util.stream.LongStream; |
| |
| /** |
| * A random number generator isolated to the current thread. Like the |
| * global {@link java.util.Random} generator used by the {@link |
| * java.lang.Math} class, a {@code ThreadLocalRandom} is initialized |
| * with an internally generated seed that may not otherwise be |
| * modified. When applicable, use of {@code ThreadLocalRandom} rather |
| * than shared {@code Random} objects in concurrent programs will |
| * typically encounter much less overhead and contention. Use of |
| * {@code ThreadLocalRandom} is particularly appropriate when multiple |
| * tasks (for example, each a {@link ForkJoinTask}) use random numbers |
| * in parallel in thread pools. |
| * |
| * <p>Usages of this class should typically be of the form: |
| * {@code ThreadLocalRandom.current().nextX(...)} (where |
| * {@code X} is {@code Int}, {@code Long}, etc). |
| * When all usages are of this form, it is never possible to |
| * accidently share a {@code ThreadLocalRandom} across multiple threads. |
| * |
| * <p>This class also provides additional commonly used bounded random |
| * generation methods. |
| * |
| * @since 1.7 |
| * @author Doug Lea |
| */ |
| public class ThreadLocalRandom extends Random { |
| /* |
| * This class implements the java.util.Random API (and subclasses |
| * Random) using a single static instance that accesses random |
| * number state held in class Thread (primarily, field |
| * threadLocalRandomSeed). In doing so, it also provides a home |
| * for managing package-private utilities that rely on exactly the |
| * same state as needed to maintain the ThreadLocalRandom |
| * instances. We leverage the need for an initialization flag |
| * field to also use it as a "probe" -- a self-adjusting thread |
| * hash used for contention avoidance, as well as a secondary |
| * simpler (xorShift) random seed that is conservatively used to |
| * avoid otherwise surprising users by hijacking the |
| * ThreadLocalRandom sequence. The dual use is a marriage of |
| * convenience, but is a simple and efficient way of reducing |
| * application-level overhead and footprint of most concurrent |
| * programs. |
| * |
| * Because this class is in a different package than class Thread, |
| * field access methods use Unsafe to bypass access control rules. |
| * The base functionality of Random methods is conveniently |
| * isolated in method next(bits), that just reads and writes the |
| * Thread field rather than its own field. However, to conform to |
| * the requirements of the Random superclass constructor, the |
| * common static ThreadLocalRandom maintains an "initialized" |
| * field for the sake of rejecting user calls to setSeed while |
| * still allowing a call from constructor. Note that |
| * serialization is completely unnecessary because there is only a |
| * static singleton. But we generate a serial form containing |
| * "rnd" and "initialized" fields to ensure compatibility across |
| * versions. |
| * |
| * Per-thread initialization is similar to that in the no-arg |
| * Random constructor, but we avoid correlation among not only |
| * initial seeds of those created in different threads, but also |
| * those created using class Random itself; while at the same time |
| * not changing any statistical properties. So we use the same |
| * underlying multiplicative sequence, but start the sequence far |
| * away from the base version, and then merge (xor) current time |
| * and per-thread probe bits to generate initial values. |
| * |
| * The nextLocalGaussian ThreadLocal supports the very rarely used |
| * nextGaussian method by providing a holder for the second of a |
| * pair of them. As is true for the base class version of this |
| * method, this time/space tradeoff is probably never worthwhile, |
| * but we provide identical statistical properties. |
| */ |
| |
| // same constants as Random, but must be redeclared because private |
| private static final long multiplier = 0x5DEECE66DL; |
| private static final long addend = 0xBL; |
| private static final long mask = (1L << 48) - 1; |
| private static final int PROBE_INCREMENT = 0x61c88647; |
| |
| /** Generates the basis for per-thread initial seed values */ |
| private static final AtomicLong seedGenerator = |
| new AtomicLong(1269533684904616924L); |
| |
| /** Generates per-thread initialization/probe field */ |
| private static final AtomicInteger probeGenerator = |
| new AtomicInteger(0xe80f8647); |
| |
| /** Rarely-used holder for the second of a pair of Gaussians */ |
| private static final ThreadLocal<Double> nextLocalGaussian = |
| new ThreadLocal<Double>(); |
| |
| /** |
| * Field used only during singleton initialization. |
| * True when constructor completes. |
| */ |
| boolean initialized; |
| |
| /** Constructor used only for static singleton */ |
| private ThreadLocalRandom() { |
| initialized = true; // false during super() call |
| } |
| |
| /** The common ThreadLocalRandom */ |
| static final ThreadLocalRandom instance = new ThreadLocalRandom(); |
| |
| /** |
| * Initialize Thread fields for the current thread. Called only |
| * when Thread.threadLocalRandomProbe is zero, indicating that a |
| * thread local seed value needs to be generated. Note that even |
| * though the initialization is purely thread-local, we need to |
| * rely on (static) atomic generators to initialize the values. |
| */ |
| static final void localInit() { |
| int p = probeGenerator.getAndAdd(PROBE_INCREMENT); |
| int probe = (p == 0) ? 1 : p; // skip 0 |
| long current, next; |
| do { // same sequence as j.u.Random but different initial value |
| current = seedGenerator.get(); |
| next = current * 181783497276652981L; |
| } while (!seedGenerator.compareAndSet(current, next)); |
| long r = next ^ ((long)probe << 32) ^ System.nanoTime(); |
| Thread t = Thread.currentThread(); |
| UNSAFE.putLong(t, SEED, r); |
| UNSAFE.putInt(t, PROBE, probe); |
| } |
| |
| /** |
| * Returns the current thread's {@code ThreadLocalRandom}. |
| * |
| * @return the current thread's {@code ThreadLocalRandom} |
| */ |
| public static ThreadLocalRandom current() { |
| if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0) |
| localInit(); |
| return instance; |
| } |
| |
| /** |
| * Throws {@code UnsupportedOperationException}. Setting seeds in |
| * this generator is not supported. |
| * |
| * @throws UnsupportedOperationException always |
| */ |
| public void setSeed(long seed) { |
| // only allow call from super() constructor |
| if (initialized) |
| throw new UnsupportedOperationException(); |
| } |
| |
| protected int next(int bits) { |
| Thread t; long r; // read and update per-thread seed |
| UNSAFE.putLong |
| (t = Thread.currentThread(), SEED, |
| r = (UNSAFE.getLong(t, SEED) * multiplier + addend) & mask); |
| return (int) (r >>> (48-bits)); |
| } |
| |
| /** |
| * Returns a pseudorandom, uniformly distributed value between the |
| * given least value (inclusive) and bound (exclusive). |
| * |
| * @param least the least value returned |
| * @param bound the upper bound (exclusive) |
| * @throws IllegalArgumentException if least greater than or equal |
| * to bound |
| * @return the next value |
| */ |
| public int nextInt(int least, int bound) { |
| if (least >= bound) |
| throw new IllegalArgumentException(); |
| return nextInt(bound - least) + least; |
| } |
| |
| /** |
| * Returns a pseudorandom, uniformly distributed value |
| * between 0 (inclusive) and the specified value (exclusive). |
| * |
| * @param n the bound on the random number to be returned. Must be |
| * positive. |
| * @return the next value |
| * @throws IllegalArgumentException if n is not positive |
| */ |
| public long nextLong(long n) { |
| if (n <= 0) |
| throw new IllegalArgumentException("n must be positive"); |
| // Divide n by two until small enough for nextInt. On each |
| // iteration (at most 31 of them but usually much less), |
| // randomly choose both whether to include high bit in result |
| // (offset) and whether to continue with the lower vs upper |
| // half (which makes a difference only if odd). |
| long offset = 0; |
| while (n >= Integer.MAX_VALUE) { |
| int bits = next(2); |
| long half = n >>> 1; |
| long nextn = ((bits & 2) == 0) ? half : n - half; |
| if ((bits & 1) == 0) |
| offset += n - nextn; |
| n = nextn; |
| } |
| return offset + nextInt((int) n); |
| } |
| |
| @Override |
| public IntStream ints() { |
| return IntStream.generate(() -> current().nextInt()); |
| } |
| |
| @Override |
| public LongStream longs() { |
| return LongStream.generate(() -> current().nextLong()); |
| } |
| |
| @Override |
| public DoubleStream doubles() { |
| return DoubleStream.generate(() -> current().nextDouble()); |
| } |
| |
| @Override |
| public DoubleStream gaussians() { |
| return DoubleStream.generate(() -> current().nextGaussian()); |
| } |
| |
| /** |
| * Returns a pseudorandom, uniformly distributed value between the |
| * given least value (inclusive) and bound (exclusive). |
| * |
| * @param least the least value returned |
| * @param bound the upper bound (exclusive) |
| * @return the next value |
| * @throws IllegalArgumentException if least greater than or equal |
| * to bound |
| */ |
| public long nextLong(long least, long bound) { |
| if (least >= bound) |
| throw new IllegalArgumentException(); |
| return nextLong(bound - least) + least; |
| } |
| |
| /** |
| * Returns a pseudorandom, uniformly distributed {@code double} value |
| * between 0 (inclusive) and the specified value (exclusive). |
| * |
| * @param n the bound on the random number to be returned. Must be |
| * positive. |
| * @return the next value |
| * @throws IllegalArgumentException if n is not positive |
| */ |
| public double nextDouble(double n) { |
| if (n <= 0) |
| throw new IllegalArgumentException("n must be positive"); |
| return nextDouble() * n; |
| } |
| |
| /** |
| * Returns a pseudorandom, uniformly distributed value between the |
| * given least value (inclusive) and bound (exclusive). |
| * |
| * @param least the least value returned |
| * @param bound the upper bound (exclusive) |
| * @return the next value |
| * @throws IllegalArgumentException if least greater than or equal |
| * to bound |
| */ |
| public double nextDouble(double least, double bound) { |
| if (least >= bound) |
| throw new IllegalArgumentException(); |
| return nextDouble() * (bound - least) + least; |
| } |
| |
| public double nextGaussian() { |
| // Use nextLocalGaussian instead of nextGaussian field |
| Double d = nextLocalGaussian.get(); |
| if (d != null) { |
| nextLocalGaussian.set(null); |
| return d.doubleValue(); |
| } |
| double v1, v2, s; |
| do { |
| v1 = 2 * nextDouble() - 1; // between -1 and 1 |
| v2 = 2 * nextDouble() - 1; // between -1 and 1 |
| s = v1 * v1 + v2 * v2; |
| } while (s >= 1 || s == 0); |
| double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s); |
| nextLocalGaussian.set(new Double(v2 * multiplier)); |
| return v1 * multiplier; |
| } |
| |
| // Within-package utilities |
| |
| /* |
| * Descriptions of the usages of the methods below can be found in |
| * the classes that use them. Briefly, a thread's "probe" value is |
| * a non-zero hash code that (probably) does not collide with |
| * other existing threads with respect to any power of two |
| * collision space. When it does collide, it is pseudo-randomly |
| * adjusted (using a Marsaglia XorShift). The nextSecondarySeed |
| * method is used in the same contexts as ThreadLocalRandom, but |
| * only for transient usages such as random adaptive spin/block |
| * sequences for which a cheap RNG suffices and for which it could |
| * in principle disrupt user-visible statistical properties of the |
| * main ThreadLocalRandom if we were to use it. |
| * |
| * Note: Because of package-protection issues, versions of some |
| * these methods also appear in some subpackage classes. |
| */ |
| |
| /** |
| * Returns the probe value for the current thread without forcing |
| * initialization. Note that invoking ThreadLocalRandom.current() |
| * can be used to force initialization on zero return. |
| */ |
| static final int getProbe() { |
| return UNSAFE.getInt(Thread.currentThread(), PROBE); |
| } |
| |
| /** |
| * Pseudo-randomly advances and records the given probe value for the |
| * given thread. |
| */ |
| static final int advanceProbe(int probe) { |
| probe ^= probe << 13; // xorshift |
| probe ^= probe >>> 17; |
| probe ^= probe << 5; |
| UNSAFE.putInt(Thread.currentThread(), PROBE, probe); |
| return probe; |
| } |
| |
| /** |
| * Returns the pseudo-randomly initialized or updated secondary seed. |
| */ |
| static final int nextSecondarySeed() { |
| int r; |
| Thread t = Thread.currentThread(); |
| if ((r = UNSAFE.getInt(t, SECONDARY)) != 0) { |
| r ^= r << 13; // xorshift |
| r ^= r >>> 17; |
| r ^= r << 5; |
| } |
| else { |
| localInit(); |
| if ((r = (int)UNSAFE.getLong(t, SEED)) == 0) |
| r = 1; // avoid zero |
| } |
| UNSAFE.putInt(t, SECONDARY, r); |
| return r; |
| } |
| |
| // Serialization support |
| |
| private static final long serialVersionUID = -5851777807851030925L; |
| |
| /** |
| * @serialField rnd long |
| * seed for random computations |
| * @serialField initialized boolean |
| * always true |
| */ |
| private static final ObjectStreamField[] serialPersistentFields = { |
| new ObjectStreamField("rnd", long.class), |
| new ObjectStreamField("initialized", boolean.class) |
| }; |
| |
| /** |
| * Saves the {@code ThreadLocalRandom} to a stream (that is, serializes it). |
| */ |
| private void writeObject(java.io.ObjectOutputStream out) |
| throws java.io.IOException { |
| |
| java.io.ObjectOutputStream.PutField fields = out.putFields(); |
| fields.put("rnd", UNSAFE.getLong(Thread.currentThread(), SEED)); |
| fields.put("initialized", true); |
| out.writeFields(); |
| } |
| |
| /** |
| * Returns the {@link #current() current} thread's {@code ThreadLocalRandom}. |
| */ |
| private Object readResolve() { |
| return current(); |
| } |
| |
| // Unsafe mechanics |
| private static final sun.misc.Unsafe UNSAFE; |
| private static final long SEED; |
| private static final long PROBE; |
| private static final long SECONDARY; |
| static { |
| try { |
| UNSAFE = sun.misc.Unsafe.getUnsafe(); |
| Class<?> tk = Thread.class; |
| SEED = UNSAFE.objectFieldOffset |
| (tk.getDeclaredField("threadLocalRandomSeed")); |
| PROBE = UNSAFE.objectFieldOffset |
| (tk.getDeclaredField("threadLocalRandomProbe")); |
| SECONDARY = UNSAFE.objectFieldOffset |
| (tk.getDeclaredField("threadLocalRandomSecondarySeed")); |
| } catch (Exception e) { |
| throw new Error(e); |
| } |
| } |
| } |