You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Alex Herbert (Jira)" <ji...@apache.org> on 2026/03/02 13:18:00 UTC

[jira] [Commented] (RNG-191) Use java.lang.invoke to dynamically call Math multiply high methods

    [ https://issues.apache.org/jira/browse/RNG-191?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18062145#comment-18062145 ] 

Alex Herbert commented on RNG-191:
----------------------------------

h2. LXM generators are not slowed by unsigned multiply

Further to the benchmark results above, I added a dedicated benchmark for the LXM generators using either the current unsigned multiply high or the use of Math.unsignedMultiplyHigh/multiplyHigh. I tested this on an M2 Pro across various JVMs. I will not show the results as they are similar to those above. The use of the Math multiply methods are either the same speed or slower.

The conclusion is that the unsigned multiply is not the performance critical part of the LXM generators. To test this I removed the call completely and used a standard 64-bit multiply. This will create a broken generator with the wrong output. These generators were either the same speed or slower than the original implementation.
h2. Use within a sampler

It is possible that the nextLong benchmark is optimising the generator so that the unsigned multiply can be computed in parallel on the processor pipeline. I tested using the generator in more complex code to generate Gaussian samples:
||Sampler||RNG use||
|BoxMullerNormalizedGaussianSampler|Creates two samples with a call to nextDouble and nextLong. Most of the time is used to map samples to a Gaussian using Math calls to sin, cos, sqrt and log. There is no rejection rate.|
|MarsagliaNormalizedGaussianSampler|Creates 2 double samples from a unit box and maps to a unit circle. Rejection rate is 1 - pi/4 = 21.4%. When inside the circle a call to Math sqrt and log is used to map to a Gaussian.|
|ZigguratNormalizedGaussianSampler|Uses a look-up table approximately 98.5% of the time with nextLong. The other branch fixes the sample output using branches with either nextLong or nextDouble.|
|ZigguratSampler.NormalizedGaussian|Uses a look-up table approximately 98.8% of the time with nextLong. The other branch fixes the sample output using branches with nextLong.|

Results on an M2 Max using OpenJDK 1.8.0_472 or 21.0.9. Results in ns/operation. 
||RNG||JDK||Version||BoxMullerNormalizedGaussianSampler||MarsagliaNormalizedGaussianSampler||ZigguratNormalizedGaussianSampler||ZigguratSampler.NormalizedGaussian||
|L128_X1024_MIX|8|Original|167.04|113.28|16.80|7.29|
|L128_X1024_MIX|8|UM|170.36|118.70|16.55|6.79|
|L128_X1024_MIX|21|Original|15.09|13.26|5.14|4.61|
|L128_X1024_MIX|21|UM|14.59|12.12|4.98|4.13|
|L128_X128_MIX|8|Original|165.87|113.71|16.51|5.93|
|L128_X128_MIX|8|UM|167.37|112.62|15.12|6.07|
|L128_X128_MIX|21|Original|17.55|13.13|4.74|4.21|
|L128_X128_MIX|21|UM|15.73|11.01|4.29|3.97|
|L128_X256_MIX|8|Original|167.73|114.23|15.52|6.06|
|L128_X256_MIX|8|UM|170.72|113.64|14.91|6.06|
|L128_X256_MIX|21|Original|17.26|13.03|5.02|4.39|
|L128_X256_MIX|21|UM|15.75|11.12|4.22|4.66|
|PHILOX_4X64|8|Original|182.16|129.03|25.57|19.21|
|PHILOX_4X64|8|UM|183.91|131.07|25.71|19.67|
|PHILOX_4X64|21|Original|25.45|25.65|12.02|11.63|
|PHILOX_4X64|21|UM|20.13|20.62|4.88|5.40|

The BoxMuller and Marsaglia samplers are slow. The speed of the generator is not critical. Use of unsigned multiply can speed up the Philox results by 20%. A smaller speed-up is observed for the LXM generators. This is in contrast to the benchmark of the generator on its own. This is the first consistent result showing use of unsigned multiply can speed up LXM output.

The lookup table samplers are fast enough that the generator speed is significant. Here use of unsigned multiply doubles the speed of the Philox sampler. The LXM generators can get faster but the difference is relatively small. One result is slower for the ZigguratSampler.NormalizedGaussian using L128_X256_MIX but this is within noise of the test results. The time for the original result on JDK 21 is 4.38 +/- 0.51 showing large variation in this result.
h2. Conclusion

When used within a sampler the LXM family of generator show a small increase in speed. This is not consistent across all generators. The L128_X256_MIX generator shows slowdown more often than the other generators tested.

The Philox generator consistently increases performance with Math multiply high methods.

I would recommend using the Math multiply high methods within the Philox generator only. Use across the LXM family shows inconsistent results and further testing is required.

 

 

> Use java.lang.invoke to dynamically call Math multiply high methods
> -------------------------------------------------------------------
>
>                 Key: RNG-191
>                 URL: https://issues.apache.org/jira/browse/RNG-191
>             Project: Commons RNG
>          Issue Type: Improvement
>          Components: core
>            Reporter: Alex Herbert
>            Priority: Minor
>
> The following generators rely on a 128-bit multiplication result from two 64-bit longs:
>  * L128_X128_MIX
>  * L128_X256_MIX
>  * L128_X1024_MIX
>  * PHILOX_4X64
> Java added support to java.lang.Math to compute the upper 64-bit result with potential intrinsic calls to native functions:
> ||Method||JDK||Notes||
> |[multiplyHigh (Javadoc JDK 21)|https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Math.html#multiplyHigh(long,long)]|9|Convert to unsigned using:
> Math.multiplyHigh(a, b) + ((a >> 63) & b) + ((b >> 63) & a)|
> |[unsignedMultiplyHigh (Javadoc JDK 21)|https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Math.html#unsignedMultiplyHigh(long,long)]|18| |
> Since Commons RNG targets Java 8 these methods cannot be used. The current RNGs use a software implementation to compose the upper bits of the 128-bit result. However the methods can be used with a [MethodHandle|https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/invoke/MethodHandle.html] introduced in Java 7:
> {code:java}
> // find the method
> MethodHandle h = MethodHandles.publicLookup()
>     .findStatic(Math.class,
>                 "unsignedMultiplyHigh",
>                 MethodType.methodType(long.class, long.class, long.class));
> // invoke (snippet)
> long a, b;
> try {
>     long r = (long) h2.invokeExact(a, b);
> } catch (Throwable e) {
>     throw new RuntimeException(e);
> }
> {code}
> Investigate the use of MethodHandle within the named RNGs.



--
This message was sent by Atlassian Jira
(v8.20.10#820010)