[jira] [Commented] (RNG-129) Performance improvement for UnitSphereSampler

["Alex Herbert (Jira)" <ji...@apache.org>]

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

Alex Herbert commented on RNG-129:
----------------------------------

I created a JMH benchmark comparing the array based version to a non-array based version. For 1D a few methods were tested to sample a unit vector of 1 dimension:
||Method||Description||
|signedDouble|Subtract either 0 or 2 from 1. A single bit can create the value 0 or 2:
 
 return new double[] \{1.0 - (rng.nextInt() & 0x2)};|
|boolean|Check a boolean and return -1 or 1:
 
 return new double[] \{rng.nextBoolean() ? -1.0 : 1.0};|

The baseline reference is creation of a new array of the correct dimension with position zero set to 1.0.

Results:

The baseline is just creation of an array. This time has been subtracted from the other times for the same dimension to produce an adjusted time. The adjusted time is expressed relative to the current array based method.
||Method||type||size||Score||Adjusted||Relative||
|create1D|Baseline|100|684.127|0| |
|create1D|Array|100|3300.444|2616.317|1.0000|
|create1D|boolean|100|1283.47|599.343|0.2291|
|create1D|signedDouble|100|767.069|82.942|0.0317|
|create2D|Baseline|100|744.885|0| |
|create2D|Array|100|4473.787|3728.902|1.0000|
|create2D|NonArray|100|3169.104|2424.219|0.6501|
|create3D|Baseline|100|818.766|0| |
|create3D|Array|100|6692.303|5873.537|1.0000|
|create3D|NonArray|100|4313.607|3494.841|0.5950|
|create4D|Baseline|100|879.7|0| |
|create4D|Array|100|8623.089|7743.389|1.0000|
|create4D|NonArray|100|5465.992|4586.292|0.5923|

For 2D, 3D and 4D removal of the array iteration produces an approximate 1.6 - 1.7x speed increase.

For 1D the current sampler is very slow compared to methods that exploit the fact the result is either 1 or -1. The signedDouble method is over 30x faster than the current sampler.

I propose to add a factory method to the UnitSphereSampler and specialisations for 1D, 2D and 3D.

The 1D method will create different samples than the current UnitSphereSampler. However that has a public constructor and the change would not break functional compatibility of code using the sampler via the constructor. The new sampler would only be created by the new factory method. This must be preserved by any use of the SharedStateSampler interface to create a new 1D sampler with a new RNG from an existing UnitSphereSampler.

The 2D and 3D methods are for the common case of creating vectors in 2D and 3D for geometry applications. These samplers would return the same samples as the existing UnitSphereSampler (due to the use of the same method).

 

> Performance improvement for UnitSphereSampler
> ---------------------------------------------
>
>                 Key: RNG-129
>                 URL: https://issues.apache.org/jira/browse/RNG-129
>             Project: Commons RNG
>          Issue Type: Improvement
>          Components: sampling
>    Affects Versions: 1.3
>            Reporter: Alex Herbert
>            Priority: Minor
>
> The UnitSphereSampler accepts a dimension argument and creates the sample using iteration over an array of the given dimension creating n Gaussian samples. This can be optimised for low order dimensions to remove the use of array iteration, e.g.
> {code:java}
> final double[] v = new double[dimension];
> double sum = 0;
> for (int i = 0; i < dimension; i++) {
>     final double x = sampler.sample();
>     v[i] = x;
>     sum += x * x;
> }
> {code}
> becomes for 3D:
> {code:java}
> final double x = sampler.sample();
> final double y = sampler.sample();
> final double z = sampler.sample();
> final double sum = x * x + y * y + z * z;
> {code}
> The special case of 1D sampling can be handled by returning either 1 or -1 in a vector based on a single bit of the random source.
> Optimised versions can be created by adding a factory method to the class:
> {code:java}
> public static UnitSphereSampler of(int dimension, UniformRandomProvider rng) {
>     // ...
> }
> {code}



--
This message was sent by Atlassian Jira
(v8.3.4#803005)