[
https://issues.apache.org/jira/browse/RNG-151?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17374878#comment-17374878
]
Alex Herbert commented on RNG-151:
----------------------------------
I have adpated the reference c code provide on Github:
[fast_prng|https://github.com/cd-mcfarland/fast_prng]. The code uses an
embedded SIMD version of the Mersenne Twister. I pulled this out and replaced
it with a SplitMix64 implementation. I have verified the output from the Java
versions I created for the normal and exponential case is the same over 10
million samples when using a SplitMix64 generator with the same seed. This is
enough to hit all major code branches.
I put the samplers into JMH and tested against the current ziggurat versions
with a few VMs:
{noformat}
VM version: JDK 1.8.0_241, Java HotSpot(TM) 64-Bit Server VM, 25.241-b07
Benchmark (randomSourceName)
(samplerType) Mode Cnt Score Error Units
ContinuousSamplersPerformance.baseline N/A
N/A avgt 5 2.338 ± 0.041 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ZigguratNormalizedGaussianSampler avgt 5 12.179 ± 0.093 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ModifiedZigguratNormalizedGaussianSampler avgt 5 7.653 ± 0.059 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ZigguratExponentialSampler avgt 5 7.610 ± 0.026 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ModifiedZigguratExponentialSampler avgt 5 6.394 ± 0.071 ns/op
VM version: JDK 11.0.6, Java HotSpot(TM) 64-Bit Server VM, 11.0.6+8-LTS
Benchmark (randomSourceName)
(samplerType) Mode Cnt Score Error Units
ContinuousSamplersPerformance.baseline N/A
N/A avgt 5 2.425 ± 0.008 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ZigguratNormalizedGaussianSampler avgt 5 11.694 ± 0.048 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ModifiedZigguratNormalizedGaussianSampler avgt 5 7.290 ± 0.081 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ZigguratExponentialSampler avgt 5 7.293 ± 0.016 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ModifiedZigguratExponentialSampler avgt 5 6.578 ± 0.008 ns/op
VM version: JDK 11.0.11, OpenJDK 64-Bit Server VM,
11.0.11+9-Ubuntu-0ubuntu2.18.04
Benchmark (randomSourceName)
(samplerType) Mode Cnt Score Error Units
ContinuousSamplersPerformance.baseline N/A
N/A avgt 5 2.515 ± 0.104 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ZigguratNormalizedGaussianSampler avgt 5 7.419 ± 0.171 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ModifiedZigguratNormalizedGaussianSampler avgt 5 7.449 ± 0.480 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ZigguratExponentialSampler avgt 5 7.118 ± 0.030 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ModifiedZigguratExponentialSampler avgt 5 6.433 ± 0.029 ns/op
VM version: JDK 14, OpenJDK 64-Bit Server VM, 14+36-1461
Benchmark (randomSourceName)
(samplerType) Mode Cnt Score Error Units
ContinuousSamplersPerformance.baseline N/A
N/A avgt 5 2.420 ± 0.036 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ZigguratNormalizedGaussianSampler avgt 5 7.494 ± 0.070 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ModifiedZigguratNormalizedGaussianSampler avgt 5 7.203 ± 0.491 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ZigguratExponentialSampler avgt 5 7.147 ± 0.165 ns/op
ContinuousSamplersPerformance.sample XO_RO_SHI_RO_128_PP
ModifiedZigguratExponentialSampler avgt 5 6.454 ± 0.040 ns/op
{noformat}
The modified ziggurat method is faster for the exponential.
After JDK 11.0.11 the current ZigguratNormalizedGaussianSampler is comparable
in speed. Before that it is slower. The ZigguratNormalizedGaussianSampler uses
the Math.log function about 5.7624515E-4 times per sample (according to notes
in the source code). It is possible that Math.log has had a speed increase.
Otherwise I cannot explain this jump in performance.
I think these methods justify inclusion in the library as they are at the
current limit of sampling performance. One issue is naming conventions. I
created separate classes:
{code:java}
UniformRandomProvider rng = ...;
ModifiedZigguratNormalizedGaussianSampler sampler1 =
ModifiedZigguratNormalizedGaussianSampler.of(rng)
ModifiedZigguratExponentialSampler sampler2 =
ModifiedZigguratExponentialSampler.of(rng);
{code}
This is a very verbose naming. The alternative of nested classes may be better
to group the classes with the same underlying method. It is still verbose:
{code:java}
UniformRandomProvider rng = ...;
ModifiedZigguratSampler.Gaussian sampler1 =
ModifiedZigguratSampler.Gaussian.of(rng)
ModifiedZigguratSampler.Exponential sampler2 =
ModifiedZigguratSampler.Exponential.of(rng);
{code}
> Modified Ziggurat algorithm for normal and exponential sampling
> ---------------------------------------------------------------
>
> Key: RNG-151
> URL: https://issues.apache.org/jira/browse/RNG-151
> Project: Commons RNG
> Issue Type: Improvement
> Components: sampling
> Affects Versions: 1.3
> Reporter: Alex Herbert
> Priority: Major
>
> The following paper describes a modification of the ziggurat method for
> sampling normal and exponential deviates:
> {noformat}
> McFarland, C.D. (2016)
> "A modified ziggurat algorithm for generating exponentially and normally
> distributed pseudorandom numbers".
> Journal of Statistical Computation and Simulation 86, 1281-1294.
> {noformat}
> [McFarland (2016) JSCS 86,
> 1281-294|https://www.tandfonline.com/doi/abs/10.1080/00949655.2015.1060234]
> Note: This method is the one that has been chosen as the default
> implementation for the java.util.random.RandomGenerator nextGaussian and
> nextExponential methods to be added in JDK 17.
> The method should be investigated in comparison to the current ziggurat
> method of Marsaglia used in ZigguratNormalizedGaussianSampler and
> ZigguratExponentialSampler.
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
