Introduction to the

In JDK7, java.util.Concurrent includes a fairly handy class for generating random numbers, ThreadLocalRandom, when an application expects to use random numbers in multiple threads or ForkJoinTasks. For concurrent access, using TheadLocalRandom instead of Math.random() reduces contention and results in better performance. Use in just call ThreadLocalRandom. Current (), and then call it’s one way to get a random number. Here’s an example:

int randomNum = ThreadLocalRandom.current().nextInt(max);
Copy the code

Source code analysis

Linear congruence method

Linear congruent method is also called “linear congruent random number generator”. One of the methods of generating [0,1] uniformly distributed random numbers. Including mixed congruence method and multiplication congruence method. It was put forward by American Lemmer in 1951. Random in Java is used to generate Random numbers.

X[n + 1] = (a * X[n] + c) mod m

Among them,

• M > 0, module data
• 0 <= a <= m, multiplier
• 0 <= c <= m, increment
• 0 <= X0 < m, X0 start value

Random source code analysis

The following is the core source code for Random

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

The constructor initializes this.seed
public Random(long seed) {
    if (getClass() == Random.class)
        this.seed = new AtomicLong(initialScramble(seed));
    else {
        // subclass might have overriden setSeed
        this.seed = newAtomicLong(); setSeed(seed); }}protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    // CAS ensures thread safety, but there may be performance problems in multi-threading
    } while(! seed.compareAndSet(oldseed, nextseed));return (int)(nextseed >>> (48 - bits));
}


// Get a random number
public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);

    int r = next(31);
    int m = bound - 1;
    if ((bound & m) == 0)  // i.e., bound is a power of 2
        r = (int)((bound * (long)r) >> 31);
    else {
        for (int u = r;
             u - (r = u % bound) + m < 0;
             u = next(31)); }return r;
}
Copy the code

From the source code we can see that the core calculation is

nextseed = (oldseed * multiplier + addend) & mask;

Then substitute the fixed values to get the following formula

nextseed = (oldseed * 25214903917L + 11L) & 281474976710655L;

Seed can also be a random seed. Copy the formula again for easy reading

X[n + 1] = (a * X[n] + c) mod m

Where Multiplier and addend represent a and C in the formula respectively, but what does mask represent? X & [(1L << 48) — 1] is equivalent to x (mod 2^48). To explain: x mod 2 to the NTH power. Since the divisor is 2 to the NTH power, e.g. 0001,0010,0100,1000 is equivalent to moving the binary form of x to the right by N, and the remainder to the right of the decimal is the remainder, e.g. : 13 = 1101 8 = 1000 13/8 = 1.101, so 101 to the right of the decimal point is the remainder, which in decimal form is 5

Note: **AtomicLong seed**** indicates that Random is a thread-safe Random number utility class **

ThreadLocalRandom source code analysis

We can use ThreadLocalRandom. Current (), for instance.

public static ThreadLocalRandom current(a) {
        if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
            localInit();
        return instance;
}
Copy the code

LocalInit () is called if there is no initialization:

static final void localInit(a) {
    int p = probeGenerator.addAndGet(PROBE_INCREMENT);
    int probe = (p == 0)?1 : p; // skip 0
    long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));
    Thread t = Thread.currentThread();
    UNSAFE.putLong(t, SEED, seed);
    UNSAFE.putInt(t, PROBE, probe);
}
Copy the code

We can see from the code that thread.currentthread () is used to get the currentThread. Note The process of generating random numbers does not depend on the CAS to obtain shared objects. Let’s finally look at the nextInt method:

public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);
    // Generate a random number
    int r = mix32(nextSeed());
    int m = bound - 1;
    // Random number judgment
    if ((bound & m) == 0) // power of two
        / / modulo
        r &= m;
    else { // reject over-represented candidates
        // Retry until interval requirements are met
        for (int u = r >>> 1;
             u + m - (r = u % bound) < 0;
             u = mix32(nextSeed()) >>> 1); }return r;
}
Copy the code

NextInt (int bound) is the same as nextInt(int bound). First call mix32(nextSeed()) to generate a random number (int range), then check the parameter n, if n is exactly a power of 2, So you just shift it and you get what you want; If it is not a power of 2, mod n is used to get the result in the range [0,n]. In addition, the purpose of the for loop statement is to prevent the result from being negative.

Here we can see mainly through mix32(nextSeed())

// Generate Random number according to the new seed. The algorithm for Random number is the same as Random
private static int mix32(long z) {
    z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
    return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) > > >32);
}


/ / generated new seeds, preserved in the Thread. ThreadLocalRandomSeed. GAMMA=0x9e3779b97f4a7c15L
final long nextSeed(a) {
    Thread t; long r; // read and update per-thread seed
    UNSAFE.putLong(t = Thread.currentThread(), SEED,
                   r = UNSAFE.getLong(t, SEED) + GAMMA);
    return r;
}
Copy the code

Use case

Random

Here is how the Random class generates Random numbers

public class RandomTest {
    static Random RANDOM = new Random();

    public static void main(String[] args) {
        final int max = 1000000;
        for (int i = 0; i < 1000; i++) {
            new Thread(() -> {
                int randomNum = RANDOM.nextInt(max);
                System.out.println("randomNum: "+ randomNum); }).start(); }}}Copy the code

ThreadLocalRandom

Here is a simple ThreadLocalRandom as follows:

public class ThreadLocalRandomTest {

    public static void main(String[] args) {
        final int max = 1000000;
        for (int i = 0; i < 1000; i++) {
            new Thread(()-> {
                int randomNum = ThreadLocalRandom.current().nextInt(max);
                System.out.println("randomNum: "+ randomNum); }).start(); }}}// Output the result
randomNum: 648582
randomNum: 76984
randomNum: 561085
randomNum: 120131
randomNum: 210919
randomNum: 546645
randomNum: 194225
randomNum: 930034
randomNum: 203882
Copy the code

Used to summarize

** Prevents Random instances from being used by multiple threads, and while sharing the instance is thread-safe, performance degrades due to competing for the same seed. Random instances include instances of java.util.random or math.random (). Example: After JDK7, API ThreadLocalRandom can be used directly, whereas prior to JDK7, coding is required to ensure that each line holds a separate instance of Random.

The resources

• The Art of Computer Programming, TACOP
• Java Development Manual alibaba
• www.cnblogs.com/shamo89/p/8…
• Ifeve.com/tag/threadl…
• www.cnblogs.com/softidea/p/…
• Baike.baidu.com/item/%E7%BA…
• www.cnblogs.com/binarylei/p…