多线程环境下生成随机数

￡神魔★判官ぃ 2021-06-24 14:34 382阅读 0赞

## 生成伪随机数据 ##

Java里有伪随机型和安全型两种随机数生成器。伪随机生成器根据特定公式将seed转换成新的伪随机数据的一部分。安全随机生成器在底层依赖到操作系统提供的随机事件来生成数据。

安全随机生成器

*  需要生成加密性强的随机数据的时候才用它；
 *  生成速度慢；
 *  如果需要生成（Linux /dev/random 就是个这样的安全随机生成器）大量随机数据，可能会产生堵塞需要等待外部中断事件。

而伪随机生成器，只依赖于”seed”的初始值。如果你给生成算法提供相同的seed，可以得到一样的伪随机序列。一般情况下，由于它是计算密集型的（不依赖于任何IO设备），因此生成速度更快。接下来，我们将回顾伪随机生成器的进化史。

### java.util.Random ###

java.util.Random 从Java 1.0开始就存在了。它是一个线程安全类，理论上可以通过它同时在多个线程中获得互不相同的随机数。这样的线程安全是通过AtomicLong实现的。

Random 使用 AtomicLong CAS （compare-and-set）操作来更新它的seed，尽管很多非阻塞式算法中使用了非阻塞式原语，CAS在资源高度竞争时的表现依然糟糕。在后面的测试结果中你可以看到它的糟糕表现。

### java.util.concurrent.ThreadLocalRandom ###

Java 7增加了java.util.concurrent.ThreadLocalRandom 并企图将它与 java.util.Random 结合以克服所有的性能问题。ThreadLocalRandom类继承自java.util.Random。

ThreadLocalRandom 的主要实现细节：

*  它使用一个普通的 long 而不是使用 Random 中的 AtomicLong 作为seed。
 *  你不能自己创建ThreadLocalRandom实例，因为它的构造函数没有设置为public。可以使用它的静态工厂ThreadLocalRandom.current()，这个工厂方法调用了内置的ThreadLocal< ThreadLocalRandom>。
 *  它是CPU缓存感知式的，使用8个 long 虚拟域来填充64位L1高速缓存行。

所有这些改变都是很重要的，在接下来的测试中你将会感受到。

## 测试 ##

我们将进行下面5种测试：

1.  一个单独的java.util.Random被N个线程共享
2.  ThreadLocal< Random>
3.  java.util.concurrent.ThreadLocalRandom
4.  java.util.Random\[\]，其中每个线程N使用一个数组下标为N的Random。
5.  java.util.Random\[\]，其中每个线程N使用一个数组下标为N \* 2的Random。

所有的测试都使用了封装在RandomTask类里的方法。每个方案都说明了如何使用随机生成器。

import java.security.SecureRandom;
    import java.util.Random;
    import java.util.concurrent.CountDownLatch;
    import java.util.concurrent.ThreadLocalRandom;
    
    
    public class RandomTask {
    
    	private static final long COUNT = 10000000;
    	private static final int THREADS = 2;
    	  
    	public static void main(String[] args) {
    	   System.out.println( "Shared Random" );
    	    testRandom(THREADS, COUNT);
    	  /*System.out.println("ThreadLocal<Random>");
    	  testTL_Random(THREADS, COUNT);*/
    	  /*System.out.println("ThreadLocalRandom");
    	  testTLRandom(THREADS, COUNT);*/
    	//  System.out.println("Shared Random[] with no padding");
    	//  testRandomArray(THREADS, COUNT, 1);
    	//  System.out.println("Shared Random[] with padding");
    	//  testRandomArray(THREADS, COUNT, 2);
    	}
    	  
    	//runner for all tests
    	private static class RandomTest implements Runnable {
    	    private final Random rnd;
    	    protected final int id;
    	    private final long cnt;
    	    private final CountDownLatch latch;
    	  
    	    private RandomTest(Random rnd, int id, long cnt, CountDownLatch latch) {
    	        this.rnd = rnd;
    	        this.id = id;
    	        this.cnt = cnt;
    	        this.latch = latch;
    	    }
    	  
    	    protected Random getRandom() {
    	        return rnd;
    	    }
    	  
    	    @Override
    	    public void run() {
    	        try {
    	            final Random r = getRandom();
    	            latch.countDown();
    	            latch.await();
    	            final long start = System.currentTimeMillis();
    	            int sum = 0;
    	            for ( long j = 0; j < cnt; ++j )
    	            {
    	                sum += r.nextInt();
    	            }
    	            final long time = System.currentTimeMillis() - start;
    	            System.out.println( "Thread #" + id + " Time = " + time / 1000.0 + " sec, sum = " + sum );
    	        } catch (InterruptedException e) {
    	        }
    	    }
    	}
    	  
    	private static void testRandom( final int threads, final long cnt ){
    	    final CountDownLatch latch = new CountDownLatch( threads );
    	    final Random r = new Random( 100 );
    	    for ( int i = 0; i < threads; ++i ) {
    	        final Thread thread = new Thread( new RandomTest( r, i, cnt, latch ) );
    	        thread.start();
    	    }
    	}
    	  
    	private static void testRandomArray( final int threads, final long cnt, final int padding ){
    	    final CountDownLatch latch = new CountDownLatch( threads );
    	    final Random[] rnd = new Random[threads * padding];
    	    for ( int i = 0; i < threads * padding; ++i ) //allocate together
    	        rnd[ i ] = new Random( 100 );
    	    for ( int i = 0; i < threads; ++i )
    	    {
    	        final Thread thread = new Thread( new RandomTest( rnd[ i * padding ], i, cnt, latch ) );
    	        thread.start();
    	    }
    	}
    	  
    	private static void testTLRandom( final int threads, final long cnt ) {
    	    final CountDownLatch latch = new CountDownLatch( threads );
    	    for ( int i = 0; i < threads; ++i ) {
    	        final Thread thread = new Thread( new RandomTest( null, i, cnt, latch ) {
    	            @Override
    	            protected Random getRandom() {
    	                return ThreadLocalRandom.current();
    	            }
    	        } );
    	        thread.start();
    	    }
    	}
    	  
    	private static void testTL_Random( final int threads, final long cnt ){
    	    final CountDownLatch latch = new CountDownLatch( threads );
    	    final ThreadLocal<Random> rnd = new ThreadLocal<Random>() {
    	        @Override
    	        protected Random initialValue() {
    	            return new Random( 100 );
    	        }
    	    };
    	    for ( int i = 0; i < threads; ++i ) {
    	        final Thread thread = new Thread( new RandomTest( null, i, cnt, latch ) {
    	            @Override
    	            protected Random getRandom() {
    	                return rnd.get();
    	            }
    	        } );
    	        thread.start();
    	    }
    	}
    }

## 测试结果 ##

所有测试都是在我的工作站上（Xeon E5-2650八核16线程2Ghz、128Gb内存、操作系统是Linux 3.5.0）完成。

### Shared java.util.Random ###

第一个测试使用的是共享的java.util.Random实例。高争夺的CAS操作严重影响了它的性能。仅仅开两个线程都会受争夺的影响，然后现实中很少会发生这种争夺的情况。下面是所有线程的最小和最大运行时间。

1 thread - 1.69 sec
    2 threads - 13.2, 13.3 sec
    4 threads - 34 - 47 sec
    8 threads - 89 - 135 sec

### “Shared” java.util.concurrent.ThreadLocalRandom ###

接下来的测试使用第二个类——java.util.concurrent.ThreadLocalRandom。 如你所见，在程序运行的线程数低于CPU的线程数时性能没有下降，当程序运行的线程数超过CPU的线程数时性能才线性的降低。另一个要注意的重点是，单一线程执行的效率是第一个案例的3倍——无竞争的CAS操作仍然表现糟糕。

1 thread - 0.57 sec
    2 threads - 0.55 sec
    4 threads - 0.51 sec
    8 threads - 0.50 sec
    16 threads - 0.53 - 0.56 sec
    32 threads - 0.91 - 1.07 sec
    64 threads - 0.89 - 2.07 sec
    128 threads - 1.1 - 4.03 sec

### “Shared” ThreadLocal<java.util.Random> ###

把java.util.Random实例装入ThreadLocal后执行的效率有些不一样，当线程数超过CPU核心数时性能就下降了——听起来像是CAS操作不能执行那么多单元。不过接下来的性能下降是线性的，和第二个案例很相似。

1 thread - 1.69 sec
    2 threads - 1.66 sec
    4 threads - 1.71 sec
    8 threads - 1.76 sec
    16 threads - 2.12 - 2.17 sec
    32 threads - 3.7 - 4.3 sec
    64 threads - 7.2 - 9.3 sec
    128 threads - 14.6 - 17.4 sec

### Array of java.util.Random ###

最后我想要检查CPU缓存行对ThreadLocalRandom 的改善作用和模拟java.util.Random在缺乏这种功能下的情况。你需要做的就是创建可以被很多线程使用的java.util.Random实例，我用java.util.Random\[\]来实现此目的并用array\[N\]表示第N个线程。

8线程测试的结果是4 sec和13.9 sec，看来缓存很重要！

我决定找出合适的填充数组大小以避免缓存失效，我给testRandomArray方法添加了一个padding参数然后测试。当padding=2时缓存问题解决了：8线程测试的时间是1.765 – 1.77 sec(和之前用ThreadLocal< java.util.Random>进行8线程测试花的时间差不多)。

## 使用Linux perf工具来分析结果 ##

我很想知道为什么会得到这样的结果，在看了[reviewed Systems Performance: Enterprise and the Cloud][reviewed Systems Performance_ Enterprise and the Cloud]这本书(6.6.12章节)之后，我用`perf stat -d`命令运行8线程的各方案测试，它会打印详细的统计数据(你可以加\-e参数打印更多信息; 用 perf list 命令查看可用选项)。

不幸的是，这些数据中包括了JVM的启动时间，因此对于运行时间短的程序要格外小心。

### Random and ThreadLocalRandom ###

让我们来比较一下差异比较大的两个测试结果——shared java.util.Random 和java.util.concurrent.ThreadLocalRandom。第一个图是Random的测试结果，第二个图是ThreadLocalRandom的测试结果

2,553,076,870,919 cycles                    #    2.398 GHz
    2,501,593,471,621 stalled-cycles-frontend   #   97.98% frontend cycles idle
    2,454,797,083,551 stalled-cycles-backend    #   96.15% backend  cycles idle
       42,807,128,658 instructions              #    0.02  insns per cycle
                                                #   58.44  stalled cycles per insn
     4,999,510,690 branches                     #    4.697 M/sec
       862,334,730 branch-misses                #   17.25% of all branches
    12,231,515,289 L1-dcache-loads              #   11.490 M/sec
     5,471,297,449 L1-dcache-load-misses        #   44.73% of all L1-dcache hits

9,321,932,029 cycles                       #    2.206 GHz
     6,767,646,797 stalled-cycles-frontend      #   72.60% frontend cycles idle
     2,049,190,051 stalled-cycles-backend       #   21.98% backend  cycles idle
    10,094,934,215 instructions                 #    1.08  insns per cycle
                                                #    0.67  stalled cycles per insn
       816,688,169 branches                     #  193.249 M/sec
         1,506,379 branch-misses                #    0.18% of all branches
     1,683,890,500 L1-dcache-loads              #  398.451 M/sec
         4,508,729 L1-dcache-load-misses        #    0.27% of all L1-dcache hits

如上表所示，Random的结果很糟糕——它完成同样任务所需的机器周期是ThreadLocalRandom的284倍！几乎每个周期都停滞在CPU管道上了。用25500亿 (10^12) 的机器周期只执行了428亿(10^9)指令，这揭露了它糟糕的性能——一个机器周期只执行了0.02个指令（好的非基于IO类软件每个机器周期至少执行1个指令）。下一个指标是分支数——被执行大约50亿个分支，但是有17.25%的分支预测出错了（这个预测率很糟糕还会导致CPU管道重置）。最后，程序要通过一级缓存加载数据122亿次，但是44.73%失败了，随后我们再解释这些值的意义。

ThreadLocalRandom只需要93亿个机器周期来完成同样的事情。停滞指令的份额比较小——只有22%的后台指令（数据预提取）失效，我认为多数的失效是在JVM启动的时候发生的。这次我们只需执行100亿指令（比上一个例子少4倍——通过这个差异你可以期望到单线程方案下的差异；实际相差大约是3.4倍）和8.16亿次分支（比上一个少6倍）而且几乎全部都预测对了（这正是你预期的结果）。我们从一级缓存加载数据17亿次几乎每次都成功了（失败率是0.27%）.

接下来我们解释上面那些值的意义。首先，我们有8个线程，每个线程执行循环1亿次，所以我们应该先找8亿的倍数。

Branches是最明显的， 我们有8个线程，每个线程都执行for loop 1亿次，这意味着测试程序执行8亿个分支。ThreadLocalRandom执行8.16亿分支，因此我们有1600万分支留给JVM启动时检验用。我们可以断定没有分支需要ThreadLocalRandom，不然我们可以在输出中看到至少16亿分支（每个循环有额外的一个分支）。没有分支的代码一般运行得更快。

然而Random需要大概50亿的分支。从上面我们可以发现，JVM仅仅负责处理很小一部分分支，因此seed上的每个CAS操作需要大约6.25个分支。8.62亿的分支失效次数说明了这次CPU期望循环继续（即便CAS操作赋值失败）并且把成功的处理也当做了失效。

L1 cache loads. 我们企图从L1缓存中加载122亿个Random和17亿ThreadLocalRandom。看下面的代码，每次迭代需要至少访问内存中的随机 seed 2次（一次是获取，一次是用来比较），但实际上可能不止两次。

protectedint next(intbits) {
    longoldseed, nextseed;
    AtomicLong seed = this.seed;
    do{
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    }while(!seed.compareAndSet(oldseed, nextseed));
    return(int)(nextseed >>> (48- bits));
    }

ThreadLocalRandom.next(int)同样需要访问内存2次

protectedint next(intbits) {
        rnd = (rnd * multiplier + addend) & mask;
        return(int) (rnd >>> (48-bits));
    }

在ThreadLocalRandom这个方案中每次迭代要进行2次内存访问，需要一级缓存加载16亿次。

不幸的是，在没有生成汇编代码前不容易发现Randon.next(int)每次迭代真正需要进行多少次内存访问。

### ThreadLocal ###

33,255,538,502cycles                    #    2.338GHz
    26,334,159,876stalled-cycles-frontend   #   79.19% frontend cycles idle
    13,886,446,385stalled-cycles-backend    #   41.76% backend  cycles idle
    19,278,411,972instructions              #    0.58 insns per cycle
                                             #   1.37 stalled cycles per insn
     2,431,012,359branches                  #  170.882M/sec
         1,462,720branch-misses             #    0.06% of all branches
     5,700,951,571L1-dcache-loads           #  400.734M/sec
         6,710,655L1-dcache-load-misses     #    0.12% of all L1-dcache hits

在这个例子中我们没有执行的是无竞争的Random, 这样可能得到的计数器值是最小的。

我们有24亿个分支，这意味着1次迭代需要3个分支。第一个分支在for loop测试中，其它的分支出现在Random.next(int)中。

do{
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    }while(!seed.compareAndSet(oldseed, nextseed));

while对应第二个分支， AtomicLong.compareAndSet对应第三个分支。

### Random\[\] with no padding ###

最后我们来看2个不同的Random实例进行CPU缓存争夺的例子。在下表中，分支数和一级缓存加载数和之前无争夺的例子非常相似。但是缓存加载失败的次数暴涨到了17亿，这暗示了每次迭代会有两次缓存加载失效。上面的一小段代码显示每次迭代都会访问seed两次（第二行和第四行各访问一次）。这意味着每次迭代都会访问两次RAM，使得程序慢了6倍。

209,445,037,827 cycles                    #    2.416 GHz
    189,365,989,000 stalled-cycles-frontend   #   90.41% frontend cycles idle
    169,936,986,823 stalled-cycles-backend    #   81.14% backend  cycles idle
     19,659,497,312 instructions              #    0.09  insns per cycle
                                              #    9.63  stalled cycles per insn
      2,475,303,839 branches                  #   28.552 M/sec
          2,315,797 branch-misses             #    0.09% of all branches
      5,719,174,890 L1-dcache-loads           #   65.968 M/sec
      1,703,679,647 L1-dcache-load-misses     #   29.79% of all L1-dcache hits

## 总结 ##

*  任何情况下都不要在多个线程间共享一个java.util.Random实例，而该把它放入ThreadLocal之中。
 *  Java7在所有情形下都更推荐使用java.util.concurrent.ThreadLocalRandom——它向下兼容已有的代码且运营成本更低。

[reviewed Systems Performance_ Enterprise and the Cloud]: http://www.amazon.com/gp/product/0133390098/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0133390098&linkCode=as2&tag=javaperfor07e-20