Shulou(Shulou.com)06/03 Report--

This article introduces the knowledge of "how to generate random numbers with Random". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Preface

Generating random numbers in code is a very common feature, and JDK has provided a ready-made Random class to implement it, and the Random class is thread-safe.

Here is the implementation of Random.next () to generate a random integer:

Protected int next (int bits) {long oldseed, nextseed; AtomicLong seed = this.seed; do {oldseed = seed.get (); nextseed = (oldseed * multiplier + addend) & mask; / / CAS competition is inefficient} while (! seed.compareAndSet (oldseed, nextseed); return (int) (nextseed > (48-bits));}

It is not difficult to see that in the above method, the CAS operation is used to update the seed. In the scenario of a large number of thread competition, the CAS operation is likely to fail, and if it fails, it will retry, and this retry will consume the CPU operation, which will greatly degrade the performance.

Therefore, although Random is thread-safe, it is not "highly concurrency".

In order to improve this problem and enhance the performance of random number generator in high concurrency environment, ThreadLocalRandom-- has a strong performance high concurrency random number generator.

ThreadLocalRandom inherits from Random, according to the Richter substitution principle, which shows that ThreadLocalRandom provides the same random number generation function as Random, but the implementation algorithm is slightly different.

Variables in Thread

To cope with thread competition, there is a ThreadLocal class in Java that allocates a separate, unrelated storage space for each thread.

The implementation of ThreadLocal depends on the ThreadLocal.ThreadLocalMap threadLocals member field in the Thread object.

Similarly, in order to allow the random number generator to access only local thread data, thereby avoiding competition, three more members have been added to Thread:

/ * * The current seed for a ThreadLocalRandom * / @ sun.misc.Contended ("tlr") long threadLocalRandomSeed; / * * Probe hash value; nonzero if threadLocalRandomSeed initialized * / @ sun.misc.Contended ("tlr") int threadLocalRandomProbe; / * * Secondary seed isolated from public ThreadLocalRandom sequence * / @ sun.misc.Contended ("tlr") int threadLocalRandomSecondarySeed

As members of the Thread class, these three fields are naturally tied to each Thread object, so they become veritable ThreadLocal variables, and the random number generator that relies on these variables becomes ThreadLocalRandom.

Eliminate pseudo-sharing

I wonder if you have noticed that on top of these variables, there is an annotation @ sun.misc.Contended. What is this annotation for? To understand this, you need to know an important problem in concurrent programming-pseudo-sharing:

As we know, CPU does not access memory directly, data is loaded into registers from cache, and cache has L1, L2, L3 and other levels. Here, let's simplify these responsible hierarchies, assuming that there is only one level of cache and one main memory.

When CPU reads and updates the cache, it is done in behavior units, also known as a cache line, with a line of 64 bytes, or the length of 8 long.

So the problem is that a cache line can put multiple variables, and what happens if multiple threads access different variables at the same time, and these different variables happen to be on the same cache line?

As shown in the figure above, XQuery Y is two adjacent variables located in the same cache line, and both CPU core1 core2 loads them, core1 updates X, and core2 updates Y, because data reads and updates are in cache behavior units, which means that when these two things happen at the same time, there is competition, resulting in core1 and core2 may need to refresh their own data (cache rows are updated by each other) This leads to a great discount on the performance of the system, which is the problem of pseudo-sharing.

Then how to improve it? As shown below:

In the figure above, we occupy a separate cache line for X and a cache line for Y, so that updating and reading separately will not have any impact.

The @ sun.misc.Contended ("tlr") in the above code will help us generate some padding before and after the variable at the virtual machine level, so that the marked variable is on the same cache line and does not conflict with other variables.

In the Thread object, the member variable threadLocalRandomSeed,threadLocalRandomProbe,threadLocalRandomSecondarySeed is marked as the same group tlr, so that the three variables are placed on a separate cache line without conflicts with other variables, thus improving the access speed in the concurrent environment.

An efficient alternative to reflection

The generation of random numbers requires access to members such as threadLocalRandomSeed of Thread, but given the encapsulation of the class, these members are visible in the package.

Unfortunately, ThreadLocalRandom is located in the java.util.concurrent package, while Thread is in the java.lang package, so ThreadLocalRandom has no way to access variables such as Thread's threadLocalRandomSeed.

At this time, Java old birds may jump out and say: what is this, look at my reflection Dafa, no matter what can be scratched out to visit.

It is true that reflection is a way to bypass encapsulation and directly access the internal data of an object, but the performance of reflection is not very good and is not suitable as a high-performance solution.

Is there any way for ThreadLocalRandom to access internal members of Thread while having methods that are far beyond reflection and infinitely close to direct variable access? The answer is yes, this is to use the Unsafe class.

Here, let's briefly introduce the two Unsafe methods used:

Public native long getLong (Object o, long offset); public native void putLong (Object o, long offset, long x)

The getLong () method reads a long data of the offset byte offset of the object o, while putLong () writes x to the offset byte offset of the object o.

This kind of C-like operation brings a great performance improvement, and more importantly, because it avoids the field name and uses the offset directly, you can easily bypass the visibility limit of the member.

The performance problem is solved, so the next question is, how do I know the offset position of the threadLocalRandomSeed member in the Thread? this requires the objectFieldOffset () method of unsafe. See the following code:

The above static code gets the position of the Thread member variable threadLocalRandomSeed,threadLocalRandomProbe,threadLocalRandomSecondarySeed in the object offset when the ThreadLocalRandom class is initialized.

Therefore, whenever ThreadLocalRandom needs to use these variables, it can be accessed through unsafe's getLong () and putLong () (or getInt () and putInt ()).

For example, when generating a random number:

Protected int next (int bits) {return (int) (mix64 (nextSeed ()) > > (64-bits));} final long nextSeed () {Thread t; long r; / / read and update per-thread seed / / in ThreadLocalRandom, accessed Thread's threadLocalRandomSeed variable UNSAFE.putLong (t = Thread.currentThread (), SEED, r = UNSAFE.getLong (t, SEED) + GAMMA); return r;}

Let's take a look at how fast this Unsafe method can fall to the ground:

Here, we write a ThreadTest class and use reflection and unsafe methods to read and write threadLocalRandomSeed member variables and compare their performance differences. The code is as follows:

In the above code, the reflection method byReflection () and Unsafe method byUnsafe () are used to read and write the threadLocalRandomSeed variable 100 million times, and the test results are as follows:

ByUnsafe spend: 171ms byReflection spend: 645ms

It is not difficult to see that the method of using Unsafe is much better than the method of reflection, which is one of the reasons why Unsafe is widely used to replace reflection within JDK.

Random number seed

We know that pseudorandom number generation requires a seed, and threadLocalRandomSeed and threadLocalRandomSecondarySeed are the seeds here. Where threadLocalRandomSeed is long and threadLocalRandomSecondarySeed is int.

ThreadLocalRandomSeed is the most widely used large number of random numbers that are actually based on threadLocalRandomSeed. While threadLocalRandomSecondarySeed is only used in some specific JDK internal implementations, it is not widely used.

The initial seed defaults to system time:

In the above code, the seed is initialized, and the initialized seed is stored through the UNSAFE at the location of the SEED (that is, threadLocalRandomSeed).

You can then use the nextInt () method to get random integers:

Public int nextInt () {return mix32 (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;}

Each call to nextInt () updates the threadLocalRandomSeed with nextSeed (). Because this is a thread-specific variable, there will be no competition at all, no CAS retry, and performance will be greatly improved.

The function of probe Probe

In addition to the seed, there is also a threadLocalRandomProbe probe variable, what is this variable used for?

We can think of threadLocalRandomProbe as a hash value (not 0) for each Thread, which can be used as an eigenvalue of a thread, based on which you can find a specific position in the array for the thread.

Static final int getProbe () {return UNSAFE.getInt (Thread.currentThread (), PROBE);}

Let's look at a code snippet:

CounterCell [] as; long b, s; if ((as = counterCells)! = null | |! U.compareAndSwapLong (this, BASECOUNT, b = baseCount, s = b + x)) {CounterCell a; long v; int m; boolean uncontended = true; if (as = = null | | (m = as.length-1)

< 0 || // 使用probe，为每个线程找到一个在数组as中的位置 // 由于每个线程的probe值不一样，因此大概率 每个线程对应的数组中的元素也是不一样的 // 每个线程对应了不同的元素，就可以没有冲突的进行完全的并发操作 // 因此探针probe在这里 就起到了防止冲突的作用 (a = as[ThreadLocalRandom.getProbe() & m]) == null || !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { 在具体的实现中，如果上述代码发生了冲突，那么，还可以使用ThreadLocalRandom.advanceProbe()方法来修改一个线程的探针值，这样可以进一步避免未来可能得冲突，从而减少竞争，提高并发性能。 static final int advanceProbe(int probe) { //根据当前探针值，计算一个更新的探针值 probe ^= probe >

> 17; probe ^ = probe

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.