Unexplicably slow (WRT HotSpot) PRNG methods

[vigna]

While testing for speed some PRNG methods (notably, nextInt(int)) using JMH, results for GraalVM were, as expected, significantly better than HotSpot's, in some cases spectacularly. However, there is a class of methods for which GraalVM is 50% slower than HotSpot.

The JHM benchmarks are available at https://github.com/vigna/dsiutils/tree/master/prngperf

OpenJDK Runtime Environment GraalVM CE 22.3.0-dev (build 17.0.5+3-jvmci-22.3-b04)
Linux Fedora 35
CPU Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz

In the table below I highlighted the 6 tests in which GraalVM (timings on the left) is 50% slower than HotSpot (timings on the right). In all other cases GraalVM is much faster.

The involved methods contain 64-bit arithmetic (in particular, moduli).

https://github.com/vigna/dsiutils/blob/924bbb27bc2494f0c4a032cbc6b5e83ff9868628/src/it/unimi/dsi/util/XoShiRo256PlusPlusRandomGenerator.java#L145

Note that the method above is nextLong(long), but nextInt(int) just delegates to that.

The problematic generators use 4 longs of state. Identical methods for generators with 2 words of state do not have this problem:

https://github.com/vigna/dsiutils/blob/924bbb27bc2494f0c4a032cbc6b5e83ff9868628/src/it/unimi/dsi/util/XoRoShiRo128PlusPlusRandomGenerator.java#L138

Please let me know if there's any additional tests I can do to clarify the matter.

BenchmarkRandom.nextDouble                   avgt   25  17.096 ± 0.060  ns/op	Benchmark                                    Mode  Cnt   Score   Error  Units
BenchmarkRandom.nextInt100000                avgt   25   8.727 ± 0.052  ns/op	BenchmarkRandom.nextDouble                   avgt   25  16.993 ± 0.081  ns/op
BenchmarkRandom.nextInt2301                  avgt   25  19.316 ± 0.095  ns/op	BenchmarkRandom.nextInt100000                avgt   25   8.493 ± 0.032  ns/op
BenchmarkRandom.nextLong                     avgt   25  17.062 ± 0.080  ns/op	BenchmarkRandom.nextInt2301                  avgt   25  19.489 ± 0.109  ns/op
BenchmarkSplitMix64.nextDouble               avgt   25   1.935 ± 0.008  ns/op	BenchmarkRandom.nextLong                     avgt   25  17.002 ± 0.074  ns/op
BenchmarkSplitMix64.nextInt100000            avgt   25   2.329 ± 0.010  ns/op	BenchmarkSplitMix64.nextDouble               avgt   25   1.942 ± 0.009  ns/op
BenchmarkSplitMix64.nextInt2301              avgt   25   2.477 ± 0.010  ns/op	BenchmarkSplitMix64.nextInt100000            avgt   25   2.185 ± 0.007  ns/op
BenchmarkSplitMix64.nextLong                 avgt   25   0.979 ± 0.005  ns/op	BenchmarkSplitMix64.nextInt2301              avgt   25   2.409 ± 0.012  ns/op
BenchmarkSplittableRandom.nextDouble         avgt   25   1.937 ± 0.007  ns/op	BenchmarkSplitMix64.nextLong                 avgt   25   1.348 ± 0.006  ns/op
BenchmarkSplittableRandom.nextInt100000      avgt   25   1.904 ± 0.007  ns/op	BenchmarkSplittableRandom.nextDouble         avgt   25   1.936 ± 0.008  ns/op
BenchmarkSplittableRandom.nextInt2301        avgt   25  11.656 ± 0.052  ns/op	BenchmarkSplittableRandom.nextInt100000      avgt   25   2.138 ± 0.009  ns/op
BenchmarkSplittableRandom.nextLong           avgt   25   0.848 ± 0.005  ns/op	BenchmarkSplittableRandom.nextInt2301        avgt   25  13.321 ± 0.053  ns/op
BenchmarkThreadLocalRandom.nextDouble        avgt   25   2.721 ± 0.016  ns/op	BenchmarkSplittableRandom.nextLong           avgt   25   1.348 ± 0.006  ns/op
BenchmarkThreadLocalRandom.nextInt100000     avgt   25   2.164 ± 0.008  ns/op	BenchmarkThreadLocalRandom.nextDouble        avgt   25   3.073 ± 0.010  ns/op
BenchmarkThreadLocalRandom.nextInt2301       avgt   25  12.909 ± 0.144  ns/op	BenchmarkThreadLocalRandom.nextInt100000     avgt   25   2.612 ± 0.010  ns/op
BenchmarkThreadLocalRandom.nextLong          avgt   25   1.056 ± 0.006  ns/op	BenchmarkThreadLocalRandom.nextInt2301       avgt   25  13.446 ± 0.082  ns/op
BenchmarkXoRoShiRo128Plus.nextDouble         avgt   25   1.939 ± 0.010  ns/op	BenchmarkThreadLocalRandom.nextLong          avgt   25   1.458 ± 0.008  ns/op
BenchmarkXoRoShiRo128Plus.nextInt100000      avgt   25   2.128 ± 0.009  ns/op	BenchmarkXoRoShiRo128Plus.nextDouble         avgt   25   1.940 ± 0.008  ns/op
BenchmarkXoRoShiRo128Plus.nextInt2301        avgt   25   2.290 ± 0.010  ns/op	BenchmarkXoRoShiRo128Plus.nextInt100000      avgt   25   2.290 ± 0.010  ns/op
BenchmarkXoRoShiRo128Plus.nextLong           avgt   25   0.909 ± 0.003  ns/op	BenchmarkXoRoShiRo128Plus.nextInt2301        avgt   25   2.324 ± 0.010  ns/op
BenchmarkXoRoShiRo128PlusPlus.nextDouble     avgt   25   1.941 ± 0.009  ns/op	BenchmarkXoRoShiRo128Plus.nextLong           avgt   25   1.801 ± 0.009  ns/op
BenchmarkXoRoShiRo128PlusPlus.nextInt100000  avgt   25   2.280 ± 0.009  ns/op	BenchmarkXoRoShiRo128PlusPlus.nextDouble     avgt   25   1.962 ± 0.007  ns/op
BenchmarkXoRoShiRo128PlusPlus.nextInt2301    avgt   25   2.372 ± 0.012  ns/op	BenchmarkXoRoShiRo128PlusPlus.nextInt100000  avgt   25   2.357 ± 0.004  ns/op
BenchmarkXoRoShiRo128PlusPlus.nextLong       avgt   25   1.056 ± 0.004  ns/op	BenchmarkXoRoShiRo128PlusPlus.nextInt2301    avgt   25   2.442 ± 0.008  ns/op
BenchmarkXoRoShiRo128StarStar.nextDouble     avgt   25   1.936 ± 0.007  ns/op	BenchmarkXoRoShiRo128PlusPlus.nextLong       avgt   25   1.884 ± 0.007  ns/op
BenchmarkXoRoShiRo128StarStar.nextInt100000  avgt   25   2.563 ± 0.017  ns/op	BenchmarkXoRoShiRo128StarStar.nextDouble     avgt   25   2.063 ± 0.009  ns/op
BenchmarkXoRoShiRo128StarStar.nextInt2301    avgt   25   2.601 ± 0.007  ns/op	BenchmarkXoRoShiRo128StarStar.nextInt100000  avgt   25   2.557 ± 0.009  ns/op
BenchmarkXoRoShiRo128StarStar.nextLong       avgt   25   1.122 ± 0.005  ns/op	BenchmarkXoRoShiRo128StarStar.nextInt2301    avgt   25   2.597 ± 0.014  ns/op
BenchmarkXoShiRo256Plus.nextDouble           avgt   25   1.939 ± 0.009  ns/op	BenchmarkXoRoShiRo128StarStar.nextLong       avgt   25   1.891 ± 0.007  ns/op
BenchmarkXoShiRo256Plus.nextInt100000        avgt   25   3.428 ± 0.014  ns/op	BenchmarkXoShiRo256Plus.nextDouble           avgt   25   1.994 ± 0.009  ns/op*
BenchmarkXoShiRo256Plus.nextInt2301          avgt   25   3.642 ± 0.144  ns/op	BenchmarkXoShiRo256Plus.nextInt100000        avgt   25   2.473 ± 0.006  ns/op*
BenchmarkXoShiRo256Plus.nextLong             avgt   25   1.608 ± 0.009  ns/op	BenchmarkXoShiRo256Plus.nextInt2301          avgt   25   2.597 ± 0.013  ns/op
BenchmarkXoShiRo256PlusPlus.nextDouble       avgt   25   1.943 ± 0.010  ns/op	BenchmarkXoShiRo256Plus.nextLong             avgt   25   1.953 ± 0.008  ns/op
BenchmarkXoShiRo256PlusPlus.nextInt100000    avgt   25   3.503 ± 0.021  ns/op	BenchmarkXoShiRo256PlusPlus.nextDouble       avgt   25   2.079 ± 0.010  ns/op*
BenchmarkXoShiRo256PlusPlus.nextInt2301      avgt   25   3.874 ± 0.026  ns/op	BenchmarkXoShiRo256PlusPlus.nextInt100000    avgt   25   2.580 ± 0.010  ns/op*
BenchmarkXoShiRo256PlusPlus.nextLong         avgt   25   1.619 ± 0.010  ns/op	BenchmarkXoShiRo256PlusPlus.nextInt2301      avgt   25   2.662 ± 0.008  ns/op
BenchmarkXoShiRo256StarStar.nextDouble       avgt   25   1.941 ± 0.013  ns/op	BenchmarkXoShiRo256PlusPlus.nextLong         avgt   25   1.919 ± 0.010  ns/op
BenchmarkXoShiRo256StarStar.nextInt100000    avgt   25   3.642 ± 0.016  ns/op	BenchmarkXoShiRo256StarStar.nextDouble       avgt   25   2.287 ± 0.009  ns/op*
BenchmarkXoShiRo256StarStar.nextInt2301      avgt   25   3.759 ± 0.020  ns/op	BenchmarkXoShiRo256StarStar.nextInt100000    avgt   25   2.675 ± 0.015  ns/op*
BenchmarkXoShiRo256StarStar.nextLong         avgt   25   1.648 ± 0.008  ns/op	BenchmarkXoShiRo256StarStar.nextInt2301      avgt   25   2.641 ± 0.010  ns/op
BenchmarkXorShift1024StarPhi.nextDouble      avgt   25   1.942 ± 0.008  ns/op	BenchmarkXoShiRo256StarStar.nextLong         avgt   25   2.042 ± 0.008  ns/op
BenchmarkXorShift1024StarPhi.nextInt100000   avgt   25   2.466 ± 0.006  ns/op	BenchmarkXorShift1024StarPhi.nextDouble      avgt   25   2.261 ± 0.008  ns/op
BenchmarkXorShift1024StarPhi.nextInt2301     avgt   25   2.610 ± 0.010  ns/op	BenchmarkXorShift1024StarPhi.nextInt100000   avgt   25   3.286 ± 0.019  ns/op
BenchmarkXorShift1024StarPhi.nextLong        avgt   25   1.337 ± 0.007  ns/op	BenchmarkXorShift1024StarPhi.nextInt2301     avgt   25   3.433 ± 0.012  ns/op

[dougxc]

The columns in the table are unaligned. I think this shows the difference more clearly:

                                                         GraalVM         HotSpot
Benchmark                                    Mode  Cnt   Score   Error   Score   Error  Units
BenchmarkRandom.nextDouble                   avgt   25  17.096 ± 0.060  16.993 ± 0.081  ns/op    
BenchmarkRandom.nextInt100000                avgt   25   8.727 ± 0.052   8.493 ± 0.032  ns/op    
BenchmarkRandom.nextInt2301                  avgt   25  19.316 ± 0.095  19.489 ± 0.109  ns/op    
BenchmarkRandom.nextLong                     avgt   25  17.062 ± 0.080  17.002 ± 0.074  ns/op    
BenchmarkSplitMix64.nextDouble               avgt   25   1.935 ± 0.008   1.942 ± 0.009  ns/op    
BenchmarkSplitMix64.nextInt100000            avgt   25   2.329 ± 0.010   2.185 ± 0.007  ns/op    
BenchmarkSplitMix64.nextInt2301              avgt   25   2.477 ± 0.010   2.409 ± 0.012  ns/op    
BenchmarkSplitMix64.nextLong                 avgt   25   0.979 ± 0.005   1.348 ± 0.006  ns/op    
BenchmarkSplittableRandom.nextDouble         avgt   25   1.937 ± 0.007   1.936 ± 0.008  ns/op    
BenchmarkSplittableRandom.nextInt100000      avgt   25   1.904 ± 0.007   2.138 ± 0.009  ns/op    
BenchmarkSplittableRandom.nextInt2301        avgt   25  11.656 ± 0.052  13.321 ± 0.053  ns/op    
BenchmarkSplittableRandom.nextLong           avgt   25   0.848 ± 0.005   1.348 ± 0.006  ns/op    
BenchmarkThreadLocalRandom.nextDouble        avgt   25   2.721 ± 0.016   3.073 ± 0.010  ns/op    
BenchmarkThreadLocalRandom.nextInt100000     avgt   25   2.164 ± 0.008   2.612 ± 0.010  ns/op    
BenchmarkThreadLocalRandom.nextInt2301       avgt   25  12.909 ± 0.144  13.446 ± 0.082  ns/op    
BenchmarkThreadLocalRandom.nextLong          avgt   25   1.056 ± 0.006   1.458 ± 0.008  ns/op    
BenchmarkXoRoShiRo128Plus.nextDouble         avgt   25   1.939 ± 0.010   1.940 ± 0.008  ns/op    
BenchmarkXoRoShiRo128Plus.nextInt100000      avgt   25   2.128 ± 0.009   2.290 ± 0.010  ns/op    
BenchmarkXoRoShiRo128Plus.nextInt2301        avgt   25   2.290 ± 0.010   2.324 ± 0.010  ns/op    
BenchmarkXoRoShiRo128Plus.nextLong           avgt   25   0.909 ± 0.003   1.801 ± 0.009  ns/op    
BenchmarkXoRoShiRo128PlusPlus.nextDouble     avgt   25   1.941 ± 0.009   1.962 ± 0.007  ns/op    
BenchmarkXoRoShiRo128PlusPlus.nextInt100000  avgt   25   2.280 ± 0.009   2.357 ± 0.004  ns/op    
BenchmarkXoRoShiRo128PlusPlus.nextInt2301    avgt   25   2.372 ± 0.012   2.442 ± 0.008  ns/op    
BenchmarkXoRoShiRo128PlusPlus.nextLong       avgt   25   1.056 ± 0.004   1.884 ± 0.007  ns/op    
BenchmarkXoRoShiRo128StarStar.nextDouble     avgt   25   1.936 ± 0.007   2.063 ± 0.009  ns/op    
BenchmarkXoRoShiRo128StarStar.nextInt100000  avgt   25   2.563 ± 0.017   2.557 ± 0.009  ns/op    
BenchmarkXoRoShiRo128StarStar.nextInt2301    avgt   25   2.601 ± 0.007   2.597 ± 0.014  ns/op    
BenchmarkXoRoShiRo128StarStar.nextLong       avgt   25   1.122 ± 0.005   1.891 ± 0.007  ns/op    
BenchmarkXoShiRo256Plus.nextDouble           avgt   25   1.939 ± 0.009   1.994 ± 0.009  ns/op   
BenchmarkXoShiRo256Plus.nextInt100000        avgt   25   3.428 ± 0.014   2.473 ± 0.006  ns/op <--- GraalVM slower
BenchmarkXoShiRo256Plus.nextInt2301          avgt   25   3.642 ± 0.144   2.597 ± 0.013  ns/op <--- GraalVM slower
BenchmarkXoShiRo256Plus.nextLong             avgt   25   1.608 ± 0.009   1.953 ± 0.008  ns/op    
BenchmarkXoShiRo256PlusPlus.nextDouble       avgt   25   1.943 ± 0.010   2.079 ± 0.010  ns/op
BenchmarkXoShiRo256PlusPlus.nextInt100000    avgt   25   3.503 ± 0.021   2.580 ± 0.010  ns/op <--- GraalVM slower
BenchmarkXoShiRo256PlusPlus.nextInt2301      avgt   25   3.874 ± 0.026   2.662 ± 0.008  ns/op <--- GraalVM slower
BenchmarkXoShiRo256PlusPlus.nextLong         avgt   25   1.619 ± 0.010   1.919 ± 0.010  ns/op    
BenchmarkXoShiRo256StarStar.nextDouble       avgt   25   1.941 ± 0.013   2.287 ± 0.009  ns/op  
BenchmarkXoShiRo256StarStar.nextInt100000    avgt   25   3.642 ± 0.016   2.675 ± 0.015  ns/op <--- GraalVM slower
BenchmarkXoShiRo256StarStar.nextInt2301      avgt   25   3.759 ± 0.020   2.641 ± 0.010  ns/op <--- GraalVM slower
BenchmarkXoShiRo256StarStar.nextLong         avgt   25   1.648 ± 0.008   2.042 ± 0.008  ns/op    
BenchmarkXorShift1024StarPhi.nextDouble      avgt   25   1.942 ± 0.008   2.261 ± 0.008  ns/op    
BenchmarkXorShift1024StarPhi.nextInt100000   avgt   25   2.466 ± 0.006   3.286 ± 0.019  ns/op    
BenchmarkXorShift1024StarPhi.nextInt2301     avgt   25   2.610 ± 0.010   3.433 ± 0.012  ns/op    

[dougxc]

@mur47x111 can you please look into this. I am suspecting missing intrinsics.

[vigna]

The columns in the table are unaligned. I think this shows the difference more clearly:

You're totally right. It was an embarrassing mistake.

[vigna]

There's another really weird thing happening here: essentially all nextDouble() methods have the same timing. This is nonsensical, as the base nextLong() method timings vary significantly.

[mur47x111]

Sorry for not replying you earlier. These benchmarks boil down to duplicated memory stores at nextLong() implementations, e.g. XoShiRo256StarStarRandom.java#L102-L109. We are working on a more general read/write elimination optimization. Meanwhile if you want to bypass this regression, you can make the first two s2 s3 computations assigning to local variables.

[vigna]

Thanks, I'll do that. Any idea why all the nextDouble() methods have the same timing, in spite of major differences between PRNGs?

[mur47x111]

In some of the random implementations (I have not verified all), nextDouble are implemented by nextLong

[vigna]

Yes, that's my point. The timings of nextLong() are very different from PRNG to PRNG, but as soon I benchmark nextDouble() (which just calls nextLong(), shifts and multiply by 2^-53) all timings are the same. It does not make any sense...

[mur47x111]

ah ok. I misinterpret your previous comment. Then it is either our existing read/write elimination can handle that, or HotSpot C2's read/write elimination cannot handle that. Try use -XX:CompileCommand=dontinline,package/to/XoShiRo256StarStarRandom.nextLong when evaluating nextDouble and see if HotSpot C2 returns significant different scores.

[vigna]

But the timings are the same even with radically different PRNGs, with which there is no problem of read/write elimination, such as SplitMix64 (whose state is just one long). Almost all nextDouble() timings are 1.9ns.

So I should run the benchmark with the standard JVM and that option, right?