In depth analysis of the defects of Random class under high concurrency and its optimization by JUC

Random can be said that every developer knows and uses a very 6 class. If you say that you have never used Random and don't know what Random is, then you won't come to this technical type community and can't see my blog. However, not everyone knows the principle of Random, and fewer people should know the defects of Random under high concurrency. In this article, I will analyze the defects of Random class under concurrency and the optimization of JUC.

Principle and Defects of Random

 public static void main(String[] args) {
  Random random = new Random();
  System.out.println(random.nextInt(100));
 }

When I was learning programming, I was puzzled by JDK developers: Why is the name of the method that produces random numbers: "nextXXX"? Although my English only stays at the level of "nodding yes, shaking no, coming come, going go", I know that next means "the next one". If I name it, it will be named "create" and "generate". Isn't this more "appropriate"? Why did JDK developers name it "nextXXX"? Is it because they are suddenly "poor in words" and can't think of any words, so they just have one? Later, I learned that the random number originally generated by Random is not really random. It has the concept of a seed, and the "next one" value is calculated according to the seed value. If the seed value is the same, the random number generated by it must be equal, that is, "a certain input produces a certain output".

If you don't believe me, we can do an experiment:

 public static void main(String[] args) {
  for (int i = 0; i < 10; i++) {
   Random random = new Random(15);
   System.out.println(random.nextInt(100));
  }
 }

The Random class not only provides a parametric construction method, but also provides a parametric construction method. We can pass in the parameter of int type, which is called "seed", so that the "seed" is fixed and the generated random numbers are all 1:

Let's simply look at the source code of nextInt. The source code involves algorithms. Of course, algorithms are not the focus of this blog discussion. We can simplify the source code as follows:

 public int nextInt(int bound) {
  if (bound <= 0)
   throw new IllegalArgumentException(BadBound);
  //1. Generate new seeds from old seeds 
  int r = next(31);
  //2. Calculate random numbers from new seeds 
  ...
  return r;
 }

The core code of nextXXX can be simplified by first generating new seeds from old seeds and then calculating random numbers from new seeds.
Now let's think about a question. If there are N threads in the case of high concurrency, and we execute to step 1 at the same time: generate new seeds from old seeds, won't we get one kind of seeds? Since the second step is to calculate random numbers according to the new seeds, and this algorithm is fixed, what will happen? Isn't the random number finally obtained by N threads all 1? Obviously, this is not what we want, so the JDK developers thought of this. Let's look at what is done in the next method:

protected int next(int bits) {
  long oldseed, nextseed;// Define the old seed, under 1 Seeds 
  AtomicLong seed = this.seed;
  do {
   oldseed = seed.get();// Get the old seed value and assign it to oldseed 
   nextseed = (oldseed * multiplier + addend) & mask;//1 A mysterious algorithm 
  } while (!seed.compareAndSet(oldseed, nextseed));//CAS , if seed Or is the value of oldseed , just use nextseed Replace and return true , exit while Loop, if it is no longer oldseed If you have, you will return false , continue the cycle 
  return (int)(nextseed >>> (48 - bits));//1 A mysterious algorithm 
 }

1. The old seed oldseed and the next seed (new seed) nextseed are defined.

2. Get the value of the old seed and assign it to oldseed.
3.1 Mysterious algorithm to calculate the next seed (new seed) assigned to nextseed.
4. Use the CAS operation. If the value of seed is still oldseed, replace it with nextseed and return true,! true is false, exit while cycle; If the value of seed is no longer oldseed, it means that the value of seed has been replaced, and false is returned! false is true, continue the next while cycle.
5.1 Mysterious algorithm, according to nextseed to calculate the random number, and return.

We can see that the core is in step 4. I will describe it in more detail. First, we need to know the type of seed:
private final AtomicLong seed;

The type of seed is AtomicLong, which is an atomic operation class, which can guarantee atomicity. seed. get is to obtain the specific value of seed, and seed is what we call seed, that is, the seed value is stored in atomic variables.

When two threads enter the next method at the same time, the following things happen:

1. Thread A and thread B get the value of seed at the same time and assign it to oldseed variable.

2. According to a mysterious algorithm, nextseed is calculated as XXX. Note that since this algorithm is fixed, the resulting nextseed must also be fixed.

3. Enter the while loop:

3.1 Thread A, using CAS algorithm, found that the value of seed is still oldseed, indicating that the value of seed has not been replaced, then replace the value of seed with nextseed generated in step 2, and return true after successful replacement. true is false, exit the while loop.
3.2 Thread B, using CAS algorithm, found that the value of seed is no longer oldseed, because thread A has replaced the value of seed with nextseed, so CAS failed and can only be circulated again. When the loop is repeated, seed. get () gets the latest seed value, and then obtains nextSeed according to a mysterious algorithm. CAS succeeds and exits the loop.

It seems that 1 cut is beautiful, but it is not. If the concurrency is high, what will happen? A large number of threads are looping through while, which is quite consuming CPU, so JUC introduced ThreadLocalRandom to solve this problem.

ThreadLocalRandom

First, let's look at how to use ThreadLocalRandom:

public static void main(String[] args) {
  for (int i = 0; i < 10; i++) {
   ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();
   System.out.println(threadLocalRandom.nextInt(100));
  }
 }

As you can see a slight change in usage, let's take a look at the implementation logic of the ThreadLocalRandom core code:

current

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

One thing to note is that since current is a static method, calling this method multiple times returns the same ThreadLocalRandom object.

If the PROBE of the current thread is 0, indicating that it is the first time to call the current method, then the localInit method needs to be called, otherwise, the generated instance will be returned directly.

localInit
  static final void localInit() {
    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);
  }

Initialize probe and seed first, and then call the methods of the UNSAFE class to set probe and seed to the current thread so that other threads can't get them.

nextInt
  public int nextInt(int bound) {
    if (bound <= 0)
      throw new IllegalArgumentException(BadBound);
    int r = mix32(nextSeed());
    int m = bound - 1;
    if ((bound & m) == 0) // power of two
      r &= m;
    else { // reject over-represented candidates
      for (int u = r >>> 1;
         u + m - (r = u % bound) < 0;
         u = mix32(nextSeed()) >>> 1)
        ;
    }
    return r;
  }

Like the principle 1 of nextXXX method under Random class, it also generates new seeds according to old seeds, and then generates random numbers according to new seeds. Let's look at what nextSeed method does:

nextSeed
  final long nextSeed() {
    Thread t; long r; // read and update per-thread seed
    UNSAFE.putLong(t = Thread.currentThread(), SEED,
            r = UNSAFE.getLong(t, SEED) + GAMMA);
    return r;
  }

First use UNSAFE.getLong(t, SEED) To get the SEED of the current thread, then + GAMMA as the new seed value, and then put the new seed value into the current thread.

Summarize

In this paper, the implementation principle of Random is simply analyzed, and the defect of nextXXX method under high concurrency is introduced: it needs to compete for seed atomic variables. Then it introduces the usage and principle of ThreadLocalRandom. From the naming of class, we can see that the implementation principle is similar to ThreadLocal. seed seeds are stored in each thread, and new seeds are calculated according to seed in each thread, thus avoiding the problem of competition.