RFR: 8248862: Implement Enhanced Pseudo-Random Number Generators

[Jim Laskey]

On Tue, 16 Mar 2021 20:37:57 GMT, Tommy Ettinger <github.com+160684+tommyettinger at openjdk.org> wrote:

>> This is now looking very nicely structured.
>> 
>> The only thing i am unsure are the details around `RandomGenerator` being a service provider interface. The documentation mentions this at various points (mostly as implementation notes), but it's not really called out on `RandomGenerator`. 
>> 
>> Trying out the patch, I can implement `RandomGenerator` and register it as a service:
>> 
>> public class AlwaysZero implements RandomGenerator {
>>     @Override
>>     public long nextLong() {
>>         return 0;
>>     }
>> }
>> ...
>>         RandomGenerator alwaysZero = RandomGenerator.of("AlwaysZero");
>>  
>> 
>> Is that intended? (esp. since the annotation `RandomGeneratorProperties` is not public). If i rename the above to `L32X64MixRandom` an `ExceptionInInitializerError` is produced due to duplicate keys.
>> 
>> I suspect you want to filter out the service providers to those that only declare `RandomGeneratorProperties`, thereby restricting to providers only supplied by the platform.
>
> Has anyone here benchmarked this? I've run BumbleBench benchmarks (one of the AdoptOpenJDK team's tools, [available here](https://github.com/adoptium/bumblebench)) and I'm skeptical of the original claims in [JEP 356](https://openjdk.java.net/jeps/356), namely:
> 
>> ...a new class of splittable PRNG algorithms (LXM) has also been discovered that are almost as fast [as SplittableRandom]...
> 
> On my machine, L64X128MixRandom's algorithm is 53% slower than SplittableRandom, a halving in performance that I think would be inaccurate to describe as "almost as fast." I've benchmarked on Java 8 HotSpot (Windows 10, x64) and Java 15 OpenJ9 (same machine). On HotSpot, which I think is the main concern, I go from 1021770880 (over 1 billion) random longs per second with SplittableRandom to 479769280 (over 479 million) with my (I believe faithful) implementation of L64X128MixRandom. That is where I observed the 53% reduction. While SplittableRandom specifically seems to perform relatively badly on OpenJ9, with 893283072 longs per second (893 million), other similar random number generators do extremely well on OpenJ9; [LaserRandom](https://github.com/tommyettinger/jdkgdxds/blob/master/src/main/java/com/github/tommyettinger/ds/support/LaserRandom.java) generates 4232752128 random longs per second (4.2 billion) where L64X128MixRandom gets 840015872 (840 million). My benchmark repo is
  a mess, but if anyone wants to see and verify, [here it is](https://github.com/tommyettinger/assorted-benchmarks/tree/master/src/main/java/net/adoptopenjdk/bumblebench/examples). JMH benchmarks might provide different or just additional useful information; I've only run BumbleBench.
> 
> One could make the argument that getting a random long from a PRNG takes so little time in the first place that it is unlikely to be a bottleneck, and by that logic, LXM is "almost as fast." However, if random generation is not being called often enough for its speed to matter, you are exceedingly unlikely to need so many (over 9 quintillion) parallel streams or such a long period per stream ((2 to the 192) minus (2 to the 64)). LXM is also 1-dimensionally equidistributed, while the foundation it is built on should allow 4-dimensional equidistribution (with the caveat of any LFSR that an all-zero state is impossible), with the same memory use per generator (4 longs), a longer period, and comparable quality using `xoshiro256**`, or possibly `xoshiro256++`, giving up streams but permitting twice as many leaps as LXM has streams if you maintain the same period as L64X128MixRandom.
> 
> If I were implementing a PRNG to operate in a future official version of the JVM, I would definitely look into ways to use AES-NI, and I think the interfaces provided here should be valuable for any similar addition, even if I disagree with the provided implementations of those interfaces. Thank you for your time.

> This is now looking very nicely structured.
> 
> The only thing i am unsure are the details around `RandomGenerator` being a service provider interface. The documentation mentions this at various points (mostly as implementation notes), but it's not really called out on `RandomGenerator`.
> 
> Trying out the patch, I can implement `RandomGenerator` and register it as a service:
> 
> ```java
> public class AlwaysZero implements RandomGenerator {
>     @Override
>     public long nextLong() {
>         return 0;
>     }
> }
> ...
>         RandomGenerator alwaysZero = RandomGenerator.of("AlwaysZero");
> ```
> 
> Is that intended? (esp. since the annotation `RandomGeneratorProperties` is not public). If i rename the above to `L32X64MixRandom` an `ExceptionInInitializerError` is produced due to duplicate keys.
> 
> I suspect you want to filter out the service providers to those that only declare `RandomGeneratorProperties`, thereby restricting to providers only supplied by the platform.

Added the filter.

> Has anyone here benchmarked this? I've run BumbleBench benchmarks (one of the AdoptOpenJDK team's tools, [available here](https://github.com/adoptium/bumblebench)) and I'm skeptical of the original claims in [JEP 356](https://openjdk.java.net/jeps/356), namely:
> 
> > ...a new class of splittable PRNG algorithms (LXM) has also been discovered that are almost as fast [as SplittableRandom]...
> 
> On my machine, L64X128MixRandom's algorithm is 53% slower than SplittableRandom, a halving in performance that I think would be inaccurate to describe as "almost as fast." I've benchmarked on Java 8 HotSpot (Windows 10, x64) and Java 15 OpenJ9 (same machine). On HotSpot, which I think is the main concern, I go from 1021770880 (over 1 billion) random longs per second with SplittableRandom to 479769280 (over 479 million) with my (I believe faithful) implementation of L64X128MixRandom. That is where I observed the 53% reduction. While SplittableRandom specifically seems to perform relatively badly on OpenJ9, with 893283072 longs per second (893 million), other similar random number generators do extremely well on OpenJ9; [LaserRandom](https://github.com/tommyettinger/jdkgdxds/blob/master/src/main/java/com/github/tommyettinger/ds/support/LaserRandom.java) generates 4232752128 random longs per second (4.2 billion) where L64X128MixRandom gets 840015872 (840 million). My benchmark repo is
  a mess, but if anyone wants to see and verify, [here it is](https://github.com/tommyettinger/assorted-benchmarks/tree/master/src/main/java/net/adoptopenjdk/bumblebench/examples). JMH benchmarks might provide different or just additional useful information; I've only run BumbleBench.
> 
> One could make the argument that getting a random long from a PRNG takes so little time in the first place that it is unlikely to be a bottleneck, and by that logic, LXM is "almost as fast." However, if random generation is not being called often enough for its speed to matter, you are exceedingly unlikely to need so many (over 9 quintillion) parallel streams or such a long period per stream ((2 to the 192) minus (2 to the 64)). LXM is also 1-dimensionally equidistributed, while the foundation it is built on should allow 4-dimensional equidistribution (with the caveat of any LFSR that an all-zero state is impossible), with the same memory use per generator (4 longs), a longer period, and comparable quality using `xoshiro256**`, or possibly `xoshiro256++`, giving up streams but permitting twice as many leaps as LXM has streams if you maintain the same period as L64X128MixRandom.
> 
> If I were implementing a PRNG to operate in a future official version of the JVM, I would definitely look into ways to use AES-NI, and I think the interfaces provided here should be valuable for any similar addition, even if I disagree with the provided implementations of those interfaces. Thank you for your time.

Thanks for this feedback.  -- Guy

-------------

PR: https://git.openjdk.java.net/jdk/pull/1292