多线程环境下生成随机数 ￡神魔★判官ぃ 2021-06-24 14:34 319阅读 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
还没有评论，来说两句吧...