[RNG-50] PoissonSampler single use speed improvements

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Implemented
• Affects Version/s: 1.0
• Fix Version/s: 1.1
• Component/s: sampling
• Assignee: Unassigned
• Reporter: Alex Herbert
• Created: 26/Jul/18 15:54
• Updated: 14/Aug/18 13:48
• Resolved: 08/Aug/18 12:27

Description

The Sampler architecture of org.apache.commons.rng.sampling.distribution is nicely written for fast sampling of small dataset sizes. The constructors for the samplers do not check the input parameters are valid for the respective distributions (in contrast to the old org.apache.commons.math3.random.distribution classes). I assume this is a design choice for speed. Thus most of the samplers can be used within a loop to sample just one value with very little overhead.

The PoissonSampler precomputes log factorial numbers upon construction if the mean is above 40. This is done using the InternalUtils.FactorialLog class. As of version 1.0 this internal class is currently only used in the PoissonSampler.

The cache size is limited to 2*PIVOT (where PIVOT=40). But it creates and precomputes the cache every time a PoissonSampler is constructed if the mean is above the PIVOT value.

Why not create this once in a static block for the PoissonSampler?

/** {@code log(n!)}. */
private static final FactorialLog factorialLog;
     
static 
{
    factorialLog = FactorialLog.create().withCache((int) (2 * PoissonSampler.PIVOT));
}

This will make the construction cost of a new PoissonSampler negligible. If the table is computed dynamically as a static construction method then the overhead will be in the first use. Thus the following call will be much faster:

UniformRandomProvider rng = ...;
int value = new PoissonSampler(rng, 50).sample();

I have tested this modification (see attached file) and the results are:

Mean 40  Single construction ( 7330792) vs Loop construction                          (24334724)   (3.319522.2x faster)
Mean 40  Single construction ( 7330792) vs Loop construction with static FactorialLog ( 7990656)   (1.090013.2x faster)
Mean 50  Single construction ( 6390303) vs Loop construction                          (19389026)   (3.034132.2x faster)
Mean 50  Single construction ( 6390303) vs Loop construction with static FactorialLog ( 6146556)   (0.961857.2x faster)
Mean 60  Single construction ( 6041165) vs Loop construction                          (21337678)   (3.532047.2x faster)
Mean 60  Single construction ( 6041165) vs Loop construction with static FactorialLog ( 5329129)   (0.882136.2x faster)
Mean 70  Single construction ( 6064003) vs Loop construction                          (23963516)   (3.951765.2x faster)
Mean 70  Single construction ( 6064003) vs Loop construction with static FactorialLog ( 5306081)   (0.875013.2x faster)
Mean 80  Single construction ( 6064772) vs Loop construction                          (26381365)   (4.349935.2x faster)
Mean 80  Single construction ( 6064772) vs Loop construction with static FactorialLog ( 6341274)   (1.045591.2x faster)

Thus the speed improvements would be approximately 3-4 fold for single use Poisson sampling.

Issue Links

• relates to: RNG-51 PoissonSampler single use speed improvements using a cache
• links to: GitHub Pull Request #9