ThreadLocalRandom原理解析
# ThreadLocalRandom原理解析
# 了解Random类
# 作用
用来获取随机数,提供nextInt(),nextLong()...api获取随机数
# 方法解析
先看一段代码
Random random = new Random();
for (int i = 0; i < 10; i++) {
// 输出0~5的数
System.out.println("random = " + random.nextInt(5));
}
2
3
4
5
上面的意思就是循环10次,每次都是调用random
对象的nextInt(5)
来获取[0,5)之间的数。
再来看下nextInt()
方法
public int nextInt(int bound) {
if (bound <= 0) // 1
throw new IllegalArgumentException(BadBound);
int r = next(31); // 2
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)) // 3
;
}
return r;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
处的代码先简单校验下传入的上限值是否小于0,如果小于0则抛出异常
2
处代码,咱们先简单理解下next(31) 就是一个算法,无论谁执行最终计算出来的值是固定的,下面 (bound & m) == 0
,判断bound值是不是2的幂,如果是bound*r再右移31位
如果不是,则不断循环r = u % bound
直到u - (r = u % bound) + m < 0
为true退出循环,返回r。
注意
(bound & m) == 0 这里为什么加一个判断? 没有判断照样也能通过不断循环得到随机数,看代码肯定是为了提高性能,因为右移的性能比循环好
那为什么要判断bound值是不是2的幂?再来看下(int)((bound * (long)r) >> 31)
bound如果是2的幂,bound*r
相当于r向左移,移几位就要看下,bound是2的多少次幂,右边补0
r其实就是int类型,这里转成long我也不知道为什么,int是4个字节一共32位(一个符号位+31),r >> 31
就是右移31位。举一个实际例子:
- 比如 r = 3 它的是二进制 00000000 00000000 00000011
- 传入的 bound = 4 它的二进制 00000000 00000000 00000100
- r * bound = 12 相当于 r左移2位(4是2的2次幂) r * bound的二进制 00000000 00000000 00001100
- 然后 r * bound 再右移31位 二进制 00000000 00000000 00000000
注意r的最前面的两位已经移到最后两位,也就是说最后的结果 最大也是2的2次幂,实际中r肯定不会这样小(初始r实际大小为10068633),结果既不会超过bound,只要r够随机,就可以获取小于bound的随机数,所以这就是为什么作者发现bound是2次幂时,可以利用先左移,再右移获取随机数,这样也减少了cpu计算的消耗。 其实hashMap的求hash表索引也是利用了这样的原理,键的hash值&hashMap的容量-1 这样也是获得一个[0,map.length)的数。
现在再来看下next(31) 这行代码
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed)); // 4
return (int)(nextseed >>> (48 - bits));
}
public final boolean compareAndSet(long expect, long update) {
return unsafe.compareAndSwapLong(this, valueOffset, expect, update);
}
2
3
4
5
6
7
8
9
10
11
12
13
流程:random
类自己有一个内置seed, 每次获取随机数都需要这个seed
去经过一系列的计算获取新的seed
,新的seed
再去替换掉旧的seed
,新的seed
再无符号右移11位(48-11)得到我们上面说的r值。
重要的点来了,因为有新seed
替换旧seed
的操作,如果涉及到多线程,this.seed
又是被多个线程共享的,可能会造成多个线程拿到的随机数是一样的,所以作者在这里加了个compareAndSet
方法,里面就是调用了unsafe的compareAndSwapLong
方法,我们理解为这就是一个CAS操作,同一时间只能被一个线程修改,如果有其他线程竞争,其他线程必须自旋。这样就解决了多线程下,使用random
获取随机数,随机数出现一样的情况。
警告
可是还是有问题,如果使用random获取随机数,线程过多,会造成很多线程自旋,自旋是很浪费cpu性能的,所以作者又发明了ThreadLocalRandom
就是为了解决这个问题!
# 了解ThreadLocalRandom类
# 作用
在多线程环境下,解决获取随机数,多个线程自旋问题。功能和Random类似
# 方法解析
ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();
for (int i = 0; i < 10; i++) {
// 输出0~5的数
System.out.println("random = " + threadLocalRandom.nextInt(5));
}
public int nextInt(int bound) {
if (bound <= 0)
throw new IllegalArgumentException(BadBound);
int r = mix32(nextSeed()); // 1
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;
}
private static int mix32(long z) {
z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32);
}
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;
}
2
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
32
33
34
还是拿nextInt()方法举例子,nextInt()方法里面内容和Random类中的差不多,具体说下1
处的代码
- 首先方法
mix32()
就是一系列的运算获取一个随机数, 方法nextSeed()
,里面也很简单,就是调用了unsafe.putLong
方法 - 这个方法需要三个参数分别是对象内存地址,偏移量,新值,作用就是修改(对象内存地址+偏移量)这个位置的值,而且是原子操作,再来看下实际传的参数,
Thread.currentThread()
为当前线程的引用也就是当前线程的内存地址,SEED
是当前线程内置变量threadLocalRandomSeed
在当前线程的偏移量,UNSAFE.getLong(t, SEED) + GAMMA
先是获取当前线程变量threadLocalRandomSeed
的值,再加上常量GAMMA
(0x9e3779b97f4a7c15L) - 所以这样看下来
nextSeed()
方法就是替换当前线程threadLocalRandomSeed
变量的值
这个原理其实很像random类里面内置变量seed的替换,区别就是seed变量是在random类里面的,而threadLocalRandomSeed
变量是存在Thread类里面的而不是存在ThreadLocalRandom
类里,ThreadLocalRandom
只是提供了api的实现具体值则是存在Thread
对象中,这样做的目的就是每个线程都有自己的seed
,不会出现多个线程竞争共享seed
问题,这样就解决了多线程下,自旋导致cpu消耗问题了
参考资料
- java中左移、右移、无符号右移的区别 (opens new window)
- java并发编程之美 第三章Java并发包中ThreadLocal Random类原理剖析