多线程环境下生成随机数

生成伪随机数据

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种测试：

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

所有的测试都使用了封装在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 RandomTask implements Runnable
{
private final Random rnd;
protected final int id;
private final long cnt;
private final CountDownLatch latch;

private RandomTask(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 RandomTask( 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 RandomTask( 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 RandomTask( 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 RandomTask( 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这本书(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次（一次是获取，一次是用来比较），但实际上可能不止两次。

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));
return (int)(nextseed >>> (48 - bits));
}

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

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

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

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

ThreadLocal

33,255,538,502 cycles # 2.338 GHz
26,334,159,876 stalled-cycles-frontend # 79.19% frontend cycles idle
13,886,446,385 stalled-cycles-backend # 41.76% backend cycles idle
19,278,411,972 instructions # 0.58 insns per cycle
# 1.37 stalled cycles per insn
2,431,012,359 branches # 170.882 M/sec
1,462,720 branch-misses # 0.06% of all branches
5,700,951,571 L1-dcache-loads # 400.734 M/sec
6,710,655 L1-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——它向下兼容已有的代码且运营成本更低。

更多相关文章

随机推荐