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

多线程环境下生成随机数

技术杂谈 勤劳的小蚂蚁 3个月前 (02-03) 81次浏览 已收录 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类里的方法。每个方案都说明了如何使用随机生成器。

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——它向下兼容已有的代码且运营成本更低。


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

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

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

客服QQ


QQ:2248886839


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