[
https://issues.apache.org/jira/browse/RNG-153?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17377338#comment-17377338
]
Alex Herbert commented on RNG-153:
----------------------------------
The above tests used the ZigguratSampler.NormalisedGaussian instead of the
ZigguratNormalisedGaussianSampler that is being used in the master branch.
RNG-152 shows that the UnitBall and UnitSphere sampler are not as fast on JDK
11.0.11 with the updated Gaussian.
I updated the benchmark in master to use the ZigguratSampler.Exponential in
place of the AhrensDieterExponentialSampler. The test still uses the current
ZigguratNormalisedGaussianSampler:
{noformat}
JDK 11.0.11
Benchmark (size) (type) Mode Cnt
Score Error Units
UnitBallSamplerBenchmark.create3D 100 Baseline avgt 5
694.716 ± 16.913 ns/op
UnitBallSamplerBenchmark.create3D 100 Rejection avgt 5
3235.418 ± 57.741 ns/op
UnitBallSamplerBenchmark.create3D 100 BallPoint avgt 5
2831.942 ± 80.004 ns/op
UnitBallSamplerBenchmark.create3D 100 HypersphereInternal avgt 5
7131.233 ± 50.653 ns/op
UnitBallSamplerBenchmark.create3D 100 HypersphereDiscard avgt 5
3302.054 ± 77.247 ns/op
JDK 1.8.0_241
Benchmark (size) (type) Mode Cnt
Score Error Units
UnitBallSamplerBenchmark.create3D 100 Baseline avgt 5
855.618 ± 158.680 ns/op
UnitBallSamplerBenchmark.create3D 100 Rejection avgt 5
3541.567 ± 426.249 ns/op
UnitBallSamplerBenchmark.create3D 100 BallPoint avgt 5
4178.345 ± 210.024 ns/op
UnitBallSamplerBenchmark.create3D 100 HypersphereInternal avgt 5
9858.016 ± 15.723 ns/op
UnitBallSamplerBenchmark.create3D 100 HypersphereDiscard avgt 5
5204.914 ± 31.457 ns/op
{noformat}
Then added the ZigguratSampler.NormalisedGaussian:
{noformat}
JDK 11.0.11
Benchmark (size) (type) Mode Cnt
Score Error Units
UnitBallSamplerBenchmark.create3D 100 Baseline avgt 5
696.990 ± 13.179 ns/op
UnitBallSamplerBenchmark.create3D 100 Rejection avgt 5
3272.826 ± 50.515 ns/op
UnitBallSamplerBenchmark.create3D 100 BallPoint avgt 5
3596.309 ± 37.557 ns/op
UnitBallSamplerBenchmark.create3D 100 HypersphereInternal avgt 5
7653.404 ± 61.476 ns/op
UnitBallSamplerBenchmark.create3D 100 HypersphereDiscard avgt 5
3761.582 ± 201.457 ns/op
JDK 1.8.0_241
Benchmark (size) (type) Mode Cnt
Score Error Units
UnitBallSamplerBenchmark.create3D 100 Baseline avgt 5
820.663 ± 148.224 ns/op
UnitBallSamplerBenchmark.create3D 100 Rejection avgt 5
3130.499 ± 488.764 ns/op
UnitBallSamplerBenchmark.create3D 100 BallPoint avgt 5
3625.267 ± 57.456 ns/op
UnitBallSamplerBenchmark.create3D 100 HypersphereInternal avgt 5
9861.103 ± 406.527 ns/op
UnitBallSamplerBenchmark.create3D 100 HypersphereDiscard avgt 5
3976.578 ± 37.083 ns/op
{noformat}
The BallPoint method is faster than the currently used HypersphereDiscard
method.
The question is whether to use the Rejection method for 3D sampling. This
method is faster when the new ZigguratSampler.NormalisedGaussian is used. It is
faster on JDK 8 when the old ZigguratNormalisedGaussianSampler is used, but
slower on JDK 11.
The timings for the rejection method have a high error. This is not useful
here. The rejection method in 3D has a rejection rate of approximately 2^3 /
(4pi/3) = 1.91 cube positions per sample. So it is roughly 50/50 and this makes
it impossible for efficient branch prediction by the CPU. Thus timings have a
lot of variation.
The BallPoint method has far more stable timings. So the least destructive
action in the UnitBallSampler is to update it to swap the HypersphereDiscard
method to the BallPoint method for both 3D and ND. This effectively substitutes
2 normalised Gaussian samples with an exponential sample of mean 2. Note that
the Exponential(mean=2) == Chi-squared distribution(degrees freedom=2) which is
equivalent to sampling 2 independent Gaussians.
> Update the UnitBallSampler method to use an exponential deviate
> ---------------------------------------------------------------
>
> Key: RNG-153
> URL: https://issues.apache.org/jira/browse/RNG-153
> Project: Commons RNG
> Issue Type: Improvement
> Components: sampling
> Affects Versions: 1.4
> Reporter: Alex Herbert
> Priority: Trivial
> Fix For: 1.4
>
>
> Currently the UnitBallSampler uses n+2 normalised Gaussian deviates for
> sampling in n dimensions. An alternative algorithm is to use n normalised
> Gaussian deviates and one exponential deviate, see [BallPointPicking
> (wolfram)|https://mathworld.wolfram.com/BallPointPicking.html].
> The new ziggurat exponential sampler is as fast as the ziggurat Gaussian
> sampler. Changing the algorithm should result in faster sampling.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
