在本文中,探讨将Java随机数算法优化为高吞吐量和低延迟的各种技巧。技巧包括更有效的对象分配,更有效的内存访问,消除不必要的间接访问以及机械同情。(对于分布式环境的抢拍很重要)
Java 7引入了, ThreadLocalRandom 以在竞争激烈的环境中提高随机数生成的吞吐量。
背后的原理ThreadLocalRandom很简单:Random每个线程都维护自己的版本,而不是共享一个全局实例Random。反过来,这减少了争用,从而提高了吞吐量。
由于这是一个简单的想法,因此我们应该能够袖手旁观,并ThreadLocalRandom以类似的性能实现类似的功能,对吗?
让我们来看看。
第一次尝试
在我们的第一次尝试中,我们将使用简单的方法ThreadLocal<Random>:
<font><i>// A few annotations</i></font><font> <b>public</b> <b>class</b> RandomBenchmark { <b>private</b> <b>final</b> Random random = <b>new</b> Random(); <b>private</b> <b>final</b> ThreadLocal<Random> simpleThreadLocal = ThreadLocal.withInitial(Random::<b>new</b>); @Benchmark @BenchmarkMode(Throughput) <b>public</b> <b>int</b> regularRandom() { <b>return</b> random.nextInt(); } @Benchmark @BenchmarkMode(Throughput) <b>public</b> <b>int</b> simpleThreadLocal() { <b>return</b> simpleThreadLocal.get().nextInt(); } @Benchmark @BenchmarkMode(Throughput) <b>public</b> <b>int</b> builtinThreadLocal() { <b>return</b> ThreadLocalRandom.current().nextInt(); } </font><font><i>// omitted</i></font><font> } </font>
在此基准测试中,我们正在比较Random,我们自己简单的ThreadLocal<Random>和内置的ThreadLocalRandom:
Benchmark Mode Cnt Score Error Units RandomBenchmark.builtinThreadLocal thrpt 40 1023676193.004 ± 26617584.814 ops/s RandomBenchmark.regularRandom thrpt 40 7487301.035 ± 244268.309 ops/s RandomBenchmark.simpleThreadLocal thrpt 40 382674281.696 ± 13197821.344 ops/s
ThreadLocalRandom生成每秒约1十亿随机数。
线性同余法
迄今为止,当今使用最广泛的随机数生成器是DH Lehmer在1949年推出的线性同余伪随机数生成器。
(具体算法见原文),Java实现:
<b>protected</b> <b>int</b> next(<b>int</b> bits) { <b>long</b> oldseed, nextseed; AtomicLong seed = <b>this</b>.seed; <b>do</b> { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend) & mask; } <b>while</b> (!seed.compareAndSet(oldseed, nextseed)); <b>return</b> (<b>int</b>)(nextseed >>> (48 - bits)); }
由于多个线程可以潜在地同时更新值seed,因此我们需要某种同步来协调并发访问。在这里,Java 在原子的帮助下使用了无锁方法。
基本上,每个线程都会尝试通过原子地将种子值更改为一个新值compareAndSet。如果线程无法执行此操作,它将重试相同的过程,直到可以成功提交更新。
当争用较高时,CAS失败的次数会增加。这是Random并发环境中性能低下的主要原因。
没有更多的CAS
在基于ThreadLocal的实现中,seed值限于每个线程。因此,由于没有共享的可变状态,因此我们不需要原子或任何其他形式的同步:
<b>public</b> <b>class</b> MyThreadLocalRandom <b>extends</b> Random { <font><i>// omitted</i></font><font> <b>private</b> <b>static</b> <b>final</b> ThreadLocal<MyThreadLocalRandom> threadLocal = ThreadLocal.withInitial(MyThreadLocalRandom::<b>new</b>); <b>private</b> MyThreadLocalRandom() {} <b>public</b> <b>static</b> MyThreadLocalRandom current() { <b>return</b> threadLocal.get(); } @Override <b>protected</b> <b>int</b> next(<b>int</b> bits) { seed = (seed * multiplier + addend) & mask; <b>return</b> (<b>int</b>) (seed >>> (48 - bits)); } } </font>
如果我们再次运行相同的基准测试:
Benchmark Mode Cnt Score Error Units RandomBenchmark.builtinThreadLocal thrpt 40 1023676193.004 ± 26617584.814 ops/s RandomBenchmark.lockFreeThreadLocal thrpt 40 695217843.076 ± 17455041.160 ops/s RandomBenchmark.regularRandom thrpt 40 7487301.035 ± 244268.309 ops/s RandomBenchmark.simpleThreadLocal thrpt 40 382674281.696 ± 13197821.344 ops/s
MyThreadLocalRandom的吞吐量几乎是简单ThreadLocal<Random>的两倍。
在compareAndSet提供了原子和内存排序保证,我们只是在一个线程上下文限制也不需要。由于这些保证是昂贵且不必要的,因此删除保证会大大提高吞吐量。
但是,我们仍然落后于内置功能ThreadLocalRandom!
删除间接
事实证明,每个线程都不需要自己的单独且完整的副本Random。它只需要最新seed值即可。
从 Java 8开始 ,这些值已添加到Thread类本身:
<font><i>/** The current seed for a ThreadLocalRandom */</i></font><font> @jdk.internal.vm.annotation.Contended(</font><font>"tlr"</font><font>) <b>long</b> threadLocalRandomSeed; </font><font><i>/** Probe hash value; nonzero if threadLocalRandomSeed initialized */</i></font><font> @jdk.internal.vm.annotation.Contended(</font><font>"tlr"</font><font>) <b>int</b> threadLocalRandomProbe; </font><font><i>/** Secondary seed isolated from public ThreadLocalRandom sequence */</i></font><font> @jdk.internal.vm.annotation.Contended(</font><font>"tlr"</font><font>) <b>int</b> threadLocalRandomSecondarySeed; </font>
MyThreadLocalRandom每个线程实例都在threadLocalRandomSeed变量中维护其当前值seed。结果,ThreadLocalRandom类成为 单例 :
<font><i>/** The common ThreadLocalRandom */</i></font><font> <b>static</b> <b>final</b> ThreadLocalRandom instance = <b>new</b> ThreadLocalRandom(); </font>
每次我们调用ThreadLocalRandom.current()的时候,它 懒初始化 threadLocalRandomSeed,然后返回singelton:
<b>public</b> <b>static</b> ThreadLocalRandom current() { <b>if</b> (U.getInt(Thread.currentThread(), PROBE) == 0) localInit(); <b>return</b> instance; }
使用MyThreadLocalRandom,每次对current()factory方法的调用都会转换为ThreadLocal实例的哈希值计算和在基础哈希表中的查找。
相反,使用这种新的Java 8+方法,我们要做的就是直接读取threadLocalRandomSeed值,然后再对其进行更新。
高效的内存访问
为了更新种子值,java.util.concurrent.ThreadLocalRandom需要更改类中的threadLocalRandomSeed状态java.lang.Thread。如果我们设置为state public,那么每个人都可能更新threadLocalRandomSeed,这不是很好。
我们可以使用反射来更新非公开状态,但是仅仅因为我们可以,并不意味着我们应该!
事实证明,ThreadLocalRandom可以使用本机方法Unsafe.putLong有效地更新threadLocalRandomSeed状态:
<font><i>/** * The seed increment. */</i></font><font> <b>private</b> <b>static</b> <b>final</b> <b>long</b> GAMMA = 0x9e3779b97f4a7c15L; <b>private</b> <b>static</b> <b>final</b> Unsafe U = Unsafe.getUnsafe(); <b>private</b> <b>static</b> <b>final</b> <b>long</b> SEED = U.objectFieldOffset(Thread.<b>class</b>, </font><font>"threadLocalRandomSeed"</font><font>); <b>final</b> <b>long</b> nextSeed() { Thread t; <b>long</b> r; </font><font><i>// read and update per-thread seed</i></font><font> U.putLong(t = Thread.currentThread(), SEED, r = U.getLong(t, SEED) + GAMMA); <b>return</b> r; } </font>
putLong方法将r值写入相对于当前线程的某个内存地址。内存偏移量已经通过调用另一个本机方法计算得出Unsafe.objectFieldOffset。
与反射相反,所有这些方法都具有本机实现,并且非常有效。
虚假共享 False Sharing
CPU高速缓存根据高速缓存行进行工作。即,高速缓存行是CPU高速缓存和主存储器之间的传输单位。
基本上,处理器倾向于将一些其他值与请求的值一起缓存。这种空间局部性优化通常可以提高吞吐量和内存访问延迟。
但是,当两个或多个线程竞争同一条缓存行时,多线程可能会产生适得其反的效果。
为了更好地理解这一点,让我们假设以下变量位于同一缓存行中:
<b>public</b> <b>class</b> Thread implements Runnable { <b>private</b> <b>final</b> <b>long</b> tid; <b>long</b> threadLocalRandomSeed; <b>int</b> threadLocalRandomProbe; <b>int</b> threadLocalRandomSecondarySeed; <font><i>// omitted</i></font><font> } </font>
一些线程tid出于某些未知目的而使用or线程ID。现在,如果我们更新threadLocalRandomSeed线程中的值以生成随机数,那么应该不会发生什么不好的事情,对吗?听起来好像没什么大不了的,因为有些线程正在读取tid,而另一个线程则将整个线程写入另一个内存位置。
尽管我们可能会想,但由于所有这些值都在同一缓存行中,因此读取线程将遇到缓存未命中。编写器需要刷新其存储缓冲区。这种现象称为错误共享False Sharing,会给我们的多线程应用程序带来性能下降。
为了避免错误的共享问题,我们可以在有争议的值周围添加一些填充。这样,每个竞争激烈的值将驻留在自己的缓存行中:
<b>public</b> <b>class</b> Thread implements Runnable { <b>private</b> <b>final</b> <b>long</b> tid; <b>private</b> <b>long</b> p11, p12, p13, p14, p15, p16, p17 = 0; <font><i>// one 64 bit long + 7 more => 64 Bytes</i></font><font> <b>long</b> threadLocalRandomSeed; <b>private</b> <b>long</b> p21, p22, p23, p24, p25, p26, p27 = 0; <b>int</b> threadLocalRandomProbe; <b>private</b> <b>long</b> p31, p32, p33, p34, p35, p36, p37 = 0; <b>int</b> threadLocalRandomSecondarySeed; <b>private</b> <b>long</b> p41, p42, p43, p44, p45, p46, p47 = 0; </font><font><i>// omitted</i></font><font> } </font>
在大多数现代处理器中,缓存行大小通常为64或128字节。在我的机器上,它是64个字节,因此long在tid声明之后,我又添加了7个哑数值。
通常,这些threadLocal*变量将在同一线程中更新。因此,最好隔离一下tid:
<b>public</b> <b>class</b> Thread implements Runnable { <b>private</b> <b>final</b> <b>long</b> tid; <b>private</b> <b>long</b> p11, p12, p13, p14, p15, p16, p17 = 0; <b>long</b> threadLocalRandomSeed; <b>int</b> threadLocalRandomProbe; <b>int</b> threadLocalRandomSecondarySeed; <font><i>// omitted</i></font><font> } </font>
读取器线程不会遇到高速缓存未命中的情况,而写入器则不需要立即清除其存储缓冲区,因为这些局部变量不是volatile。
竞争注释
jdk.internal.vm.annotation.Contended注解(如果你是在Java8则是sun.misc.Contended)是JVM隔离注释字段,以避免错误共享的提示。因此,以下内容应该更有意义:
<font><i>/** The current seed for a ThreadLocalRandom */</i></font><font> @jdk.internal.vm.annotation.Contended(</font><font>"tlr"</font><font>) <b>long</b> threadLocalRandomSeed; </font><font><i>/** Probe hash value; nonzero if threadLocalRandomSeed initialized */</i></font><font> @jdk.internal.vm.annotation.Contended(</font><font>"tlr"</font><font>) <b>int</b> threadLocalRandomProbe; </font><font><i>/** Secondary seed isolated from public ThreadLocalRandom sequence */</i></font><font> @jdk.internal.vm.annotation.Contended(</font><font>"tlr"</font><font>) <b>int</b> threadLocalRandomSecondarySeed; </font>
借助ContendedPaddingWidth调整标记,我们可以控制 填充宽度 。
threadLocalRandomSecondarySeed是ForkJoinPool或ConcurrentSkipListMap的内部使用的seed。另外,threadLocalRandomProbe表示当前线程是否已初始化其seed。
在本文中,我们探讨了将RNG优化为高吞吐量和低延迟的各种技巧。技巧包括更有效的对象分配,更有效的内存访问,消除不必要的间接访问以及机械同情。