多线程环境下生成随机数

生成伪随机数据

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 sec13.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.Randomjava.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——它向下兼容已有的代码且运营成本更低。
原文链接: java-performance 翻译: ImportNew.com - 李 广
译文链接: http://www.importnew.com/12460.html
[ 转载请保留原文出处、译者和译文链接。]

关于作者: 李 广

(新浪微博:@genslow

查看李 广的更多文章 >>



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部