• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

Java随机数探秘

技术杂谈 勤劳的小蚂蚁 2个月前 (02-10) 71次浏览 已收录 0个评论 扫描二维码

1 前言

一提到 Java 中的随机数,很多人就会想到 Random,当出现生成随机数这样需求时,大多数人都会选择使用 Random 来生成随机数。Random 类是线程安全的,但其内部使用 CAS 来保证线程安全性,在多线程并发的时候它的表现是存在优化空间的。在 JDK1.7 之后,Java 提供了更好的解决方案 ThreadLocalRandom,接下来,我们一起探讨下这几个随机数生成器的实现到底有何不同。

2 Random

Random 这个类是 JDK 提供的用来生成随机数的一个类,这个类并不是真正的随机,而是伪随机,伪随机的意思是生成的随机数其实是有一定规律的,而这个规律出现的周期随着伪随机算法的优劣而不同,一般来说周期比较长,但是可以预测。通过下面的代码我们可以对 Random 进行简单的使用: 
public class RandomDemo {
    public static void main(String[] args) {
        Random rand = new Random();
        System.out.println(rand.nextInt());
        System.out.println(rand.nextInt(10));
    }
}

Random原理

Random 中的方法比较多,这里就针对比较常见的 nextInt() 和 nextInt(int bound) 方法进行分析,前者会计算出 int 范围内的随机数,后者如果我们传入 10,那么他会返回 [0,10) 之间的 int 类型的随机数,左闭右开。我们首先看一下 Random() 的构造方法: 
public Random() {
    // 默认构造方法传入的seed值, 
    // 这个值由种子算法得到的一个唯一值与纳秒值通过位运算得到
    // 尽可能做到了和另一个构造方法的seed值的不同
    this(seedUniquifier() ^ System.nanoTime());
}

public Random(long seed) {
    if (getClass() == Random.class)
        this.seed = new AtomicLong(initialScramble(seed));
    else {
        // subclass might have overriden setSeed
        this.seed = new AtomicLong();
        setSeed(seed);
    }
}

private static long seedUniquifier() {
    // L’Ecuyer, “Tables of Linear Congruential Generators of
    // Different Sizes and Good Lattice Structure”, 1999
    for (;;) {
        long current = seedUniquifier.get();
        long next = current * 181783497276652981L;
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}

private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);

可以发现在构造方法当中,根据当前时间(纳秒)的种子生成了一个 AtomicLong 类型的 seed,这也是我们后续的关键所在。

nextInt()

nextInt() 的代码如下所示:
public int nextInt() {
    return next(32);
}

这个里面直接调用的是 next() 方法,传入的 32,代指的是 Int 类型的位数。

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        // 根据一定的规则生成nextseed
        nextseed = (oldseed * multiplier + addend) & mask;
        // 更新oldseed的值,通过cas保证线程安全
    } while (!seed.compareAndSet(oldseed, nextseed));
    // 返回前还需要位运算
    return (int)(nextseed >>> (48 – bits));
}

这里会根据 seed 当前的值,通过一定的规则((oldseed * multiplier + addend) & mask; 即伪随机算法)算出下一个 seed,然后进行 CAS,如果 CAS 失败则继续循环上面的操作。最后根据我们需要的 bit 位数来进行返回。核心便是 CAS 算法

nextInt(int bound)

nextInt(int bound) 的代码如下所示:
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;
}

这个流程比 nextInt() 多了几步,具体步骤如下:
  1. 首先获取 31 位的随机数,注意这里是 31 位,和上面 32 位不同,因为在 nextInt() 方法中可以获取到随机数可能是负数,而 nextInt(int bound) 规定只能获取到 [0,bound) 之前的随机数,也就意味着必须是正数,预留一位符号位,所以只获取了31位。(不要想着使用取绝对值这样操作,会导致性能下降)
  2. 然后进行取 bound 操作。
  3. 如果 bound 是2的幂次方,可以直接将第一步获取的值乘以 bound 然后右移31位,解释一下:如果 bound 是4,那么乘以4其实就是左移2位,其实就是变成了33位,再右移31位的话,就又会变成2位,最后,2位 int 的范围其实就是 [0,4) 了。
  4. 如果不是 2 的幂,通过模运算进行处理。

并发瓶颈

一般而言,CAS 相比加锁有一定的优势,但并不一定意味着高效,并发很大的情况下回造成CPU飙高。一个立刻被想到的解决方案是每次使用 Random 时都去 new 一个新的线程私有化的 Random 对象,或者使用 ThreadLocal 来维护线程私有化对象,但除此之外还存在更高效的方案,下面便来介绍本文的主角 ThreadLocalRandom。

3 ThreadLocalRandom

在 JDK1.7 之后提供了新的类 ThreadLocalRandom 用来在并发场景下代替 Random。使用方法比较简单:
public class RandomTest {
    public static void main(String[] args) {
        System.out.println(ThreadLocalRandom.current().nextInt());
        System.out.println(ThreadLocalRandom.current().nextInt());
        System.out.println(ThreadLocalRandom.current().nextInt(10));
    }
}
在 current 方法中有:
public static ThreadLocalRandom current() {
    if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
        // 判断当前线程是否初始化, 如果没有则初始化
        localInit();
    return instance;
}

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);
}

可以看见如果没有初始化会对其进行初始化,而这里我们的 seed 不再是一个全局变量,而是每个线程私有的,在我们的Thread中有三个变量: 
  • threadLocalRandomSeed:ThreadLocalRandom 使用它来控制随机数种子。
  • threadLocalRandomProbe:ThreadLocalRandom 使用它来控制初始化。
  • threadLocalRandomSecondarySeed:二级种子。
可以看见所有的变量都加了 @sun.misc.Contended 这个注解,用来处理伪共享问题。
在 nextInt() 方法当中代码如下:
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;
}

我们的关键代码如下:
  1. UNSAFE.putLong(t =Thread.currentThread(), SEED,r=UNSAFE.getLong(t, SEED)+ GAMMA);
可以看见由于我们每个线程各自都维护了种子,这个时候并不需要 CAS,直接进行 put,在这里利用线程之间隔离,减少了并发冲突;相比较 ThreadLocal<Random>,ThreadLocalRandom 不仅仅减少了对象维护的成本,其内部实现也更轻量级。所以 ThreadLocalRandom 性能很高。

4 性能测试

除了文章中详细介绍的 Random,ThreadLocalRandom,我还将 netty4 实现的 ThreadLocalRandom,以及 ThreadLocal<Random> 作为参考对象,一起参与 JMH 测评。
  1. @BenchmarkMode({Mode.AverageTime})
  2. @OutputTimeUnit(TimeUnit.NANOSECONDS)
  3. @Warmup(iterations =3, time =5)
  4. @Measurement(iterations =3, time =5)
  5. @Threads(50)
  6. @Fork(1)
  7. @State(Scope.Benchmark)
  8. publicclassRandomBenchmark{
  9.    Random random =newRandom();
  10.    ThreadLocal<Random> threadLocalRandomHolder =ThreadLocal.withInitial(Random::new);
  11.    @Benchmark
  12.    publicint random(){
  13.        return random.nextInt();
  14.    }
  15.    @Benchmark
  16.    publicint threadLocalRandom(){
  17.        returnThreadLocalRandom.current().nextInt();
  18.    }
  19.    @Benchmark
  20.    publicint threadLocalRandomHolder(){
  21.        return threadLocalRandomHolder.get().nextInt();
  22.    }
  23.    @Benchmark
  24.    publicint nettyThreadLocalRandom(){
  25.        return io.netty.util.internal.ThreadLocalRandom.current().nextInt();
  26.    }
  27.    publicstaticvoid main(String[] args)throwsRunnerException{
  28.        Options opt =newOptionsBuilder()
  29.                .include(RandomBenchmark.class.getSimpleName())
  30.                .build();
  31.        newRunner(opt).run();
  32.    }
  33. }
测评结果如下:
  1. Benchmark                                Mode  Cnt     Score     Error  Units
  2. RandomBenchmark.nettyThreadLocalRandom   avgt    3   192.202±295.897  ns/op
  3. RandomBenchmark.random                   avgt    3  3197.620±380.981  ns/op
  4. RandomBenchmark.threadLocalRandom        avgt    3    90.731±  39.098  ns/op
  5. RandomBenchmark.threadLocalRandomHolder  avgt    3   229.502±267.144  ns/op
从上图可以发现,JDK1.7 的 ThreadLocalRandom 取得了最好的成绩,仅仅需要 90 ns 就可以生成一次随机数,netty 实现的 ThreadLocalRandom 以及使用 ThreadLocal 维护 Random 的方式差距不是很大,位列 2、3 位,共享的 Random 变量则效果最差。
可见,在并发场景下,ThreadLocalRandom 可以明显的提升性能。

5 注意点

注意,ThreadLocalRandom 切记不要调用 current 方法之后,作为共享变量使用
  1. publicclassWrongCase{
  2.    ThreadLocalRandom threadLocalRandom =ThreadLocalRandom.current();
  3.    publicint concurrentNextInt(){
  4.        return threadLocalRandom.nextInt();
  5.    }
  6. }
这是因为 ThreadLocalRandom.current() 会使用初始化它的线程来填充随机种子,这会带来导致多个线程使用相同的 seed。
public class BadCase {
    public static void main(String[] args) {
        ThreadLocalRandom rand = ThreadLocalRandom.current();
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                System.out.println(rand.nextInt());
            }).start();
        }
    }
}
输出相同的随机数:
  1. -1667209487
  2. -1667209487
  3. -1667209487
  4. -1667209487
  5. -1667209487
  6. -1667209487
  7. -1667209487
  8. -1667209487
  9. -1667209487
  10. -1667209487
确保不同线程获取不同的 seed,最简单的方式便是每次调用都是使用 current():
public class GoodCase {
    public static void main(String[] args) {
        for (int i = 0; i < 3; i++) {
            new Thread(() -> {
                System.out.println(ThreadLocalRandom.current().nextInt());
                System.out.println(ThreadLocalRandom.current().nextInt());
                System.out.println(ThreadLocalRandom.current().nextInt());
            }).start();
        }
    }
}

彩蛋1

梁飞博客中一句话常常在我脑海中萦绕:魔鬼在细节中。优秀的代码都是一个个小细节堆砌出来,今天介绍的 ThreadLocalRandom 也不例外。
在 incubator-dubbo-2.7.0 中,随机负载均衡器的一个小改动便是将 Random 替换为了 ThreadLocalRandom,用于优化并发性能。

彩蛋2

ThreadLocalRandom 的 nextInt(int bound) 方法中,当 bound 不为 2 的幂次方时,进入 else 分支,使用了一个循环来修改 r 的值,我认为这可能不必要,你觉得呢?
  1. publicint nextInt(int bound){
  2.    if(bound <=0)
  3.        thrownewIllegalArgumentException(BadBound);
  4.    int r = mix32(nextSeed());
  5.    int m = bound -1;
  6.    if((bound & m)==0)// power of two
  7.        r &= m;
  8.    else{// reject over-represented candidates
  9.        for(int u = r >>>1;
  10.             u + m -(r = u % bound)<0;
  11.             u = mix32(nextSeed())>>>1)
  12.            ;
  13.    }
  14.    return r;
  15. }

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:Java随机数探秘
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00