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 }