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

Alex Herbert commented on RNG-179:
----------------------------------

I have created an implementation of the Fast Loaded Dice Roller (FDLR). For 
review the code is in [PR 112|https://github.com/apache/commons-rng/pull/112].

The adaption is very close to the reference c code. The sample algorithm is the 
same. A copy-paste between c and java for this code requires no changes. The 
algorithm uses a modified version of the boolean bit cache functionality in 
IntProvider to provide the bit source for boolean bits (\{0, 1}). This returns 
an int rather than a boolean. Creation of the sampler from frequencies (long[]) 
is identical to the reference c code. Creation of the sampler from weights 
(double[]) uses some BigInteger arithmetic. This avoids the custom code for 
unlimited precision math used in the original c code. It affects only 
construction and not the sampling routine.
h2. Performance

I added it to the existing JMH benchmark for enumerated distributions. This 
tests samples from:
 * 4-sided loaded die: p = 1/2, 1/3, 1/12, 1/12
 * Binomial(n=67, p=0.7)
 * Geometric(p=0.2)
 * Poisson(mean=3.22)
 * Bimodal distribution of Poisson(mean=10) + Poisson(mean=20)
 * Random probability arrays with different sizes

The benchmark was performed using XO_RO_SHI_RO_128_PLUS generator using:
{noformat}
Java version: 11.0.12, vendor: Eclipse Foundation, runtime: 
/Library/Java/JavaVirtualMachines/temurin-11.jdk/Contents/Home
OS name: "mac os x", version: "11.3", arch: "x86_64", family: "mac"
{noformat}
*Sample*
This tests the time for a sample from an already created sampler.
||Distribution||BinarySearch||FLDR||GuideTable||AliasMethod||MarsagliaTsangWang||
|4 Sided Loaded Die|16.67|18.45|19.55|13.52|5.55|
|Binomial(n=67, p=0.7)|32.57|49.66|12.44|14.51|8.49|
|Geometric(p=0.2)|31.03|28.21|15.72|11.74|7.38|
|Poisson (mean=3.22)|23.47|23.41|14.21|14.21|6.56|
|Poisson (mean1=10, mean2=20)|37.58|25.92|14.45|12.87|9.32|
|Random 6|20.36|31.68|17.73|12.47|6.08|
|Random 96|44.74|38.00|17.66|14.34|11.45|
|Random 3072|89.40|51.50|18.17|15.38|11.00|
| |295.83|266.83|129.92|109.04|65.83|

Here the sampler is better than binary search. But not as fast as other more 
optimised samplers.

The original paper states the sampler is fast on low entropy distributions. 
Entropy is defined as:
{noformat}
H = sum [ p * log2(1 / p) ]{noformat}
where p are the probabilities for each category. The entropy increases with the 
number of categories. It is highest when the distribution is uniform. As the 
distribution becomes more skewed (i.e. weighted to a few categories) the 
entropy decreases. So the sampler should do best on small, skewed 
distributions. This is observed for the 4 sided loaded die.

*Single Sample*
This tests the time to create a sampler then perform a single sample.
||Distribution||BinarySearch||FLDR||GuideTable||AliasMethod||MarsagliaTsangWang||
|4 Sided Loaded Die|40.09|905.11|55.51|72.10|215.23|
|Binomial(n=67, p=0.7)|277.57|49098.62|360.37|818.00|2209.45|
|Geometric(p=0.2)|357.48|44719.90|491.57|1032.77|3146.81|
|Poisson (mean=3.22)|105.14|7506.44|137.38|260.71|893.37|
|Poisson (mean1=10, mean2=20)|226.58|19303.88|297.53|561.43|2354.08|
|Random 3072|11440.83|2184490.83|15225.15|56482.53|355280.61|
|Random 6|51.95|1185.35|64.31|100.88|383.89|
|Random 96|390.91|15681.71|539.40|1155.64|5326.40|
| |12890.56|2322891.84|17171.22|60484.06|369809.84|

Here the sampler is relatively slow to construct. This is due to the 
construction using exact representation of the input probabilities. All 
probability values are converted to rational numbers (p / q) where q is a power 
of 2. These can then be summed exactly to unity when adjusted to use a common 
denominator. This process extracts the mantissa and exponent from each weight. 
It uses BigInteger if the range of magnitude of the probabilities is large, 
otherwise can use long arithmetic. The Discrete Distribution Generating (DDG) 
tree construction also requires a nested for loop over the rational number 
numerators. This may also be slow compared to some of the single loop 
construction routines in other samplers.
h2. Conclusion

The sampler is not as fast as other implementations in the library. It has a 
big construction cost.

The sampler does have the advantage of offering _exact_ samples from the input 
weighted distribution. In a typical inexact implementation the input weights 
are summed and probabilities computed using weight / sum. This can alter the 
relative weights due to rounding. The sampler may also discard small 
probabilities that cannot be represented. For example the Alias sampler 
implementation converts probabilities to integers that sum to 2^53. This will 
discard any probability below 2^-53. Similarly the MarsagliaTsangWang 
represents probabilities as fractions with a denominator of 2^30. As the number 
of categories increases this may significantly round the probabilities. At 
large number of categories (i.e. above 2^30) this will not represent the 
distribution at all.

Based solely on performance this method offers no benefit to the library. The 
question is whether the advantage of being able to exactly represent a 
distribution merits inclusion in the library.

> The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete 
> Probability Distributions
> ------------------------------------------------------------------------------------------------
>
>                 Key: RNG-179
>                 URL: https://issues.apache.org/jira/browse/RNG-179
>             Project: Commons RNG
>          Issue Type: New Feature
>          Components: sampling
>            Reporter: Vladimir Sitnikov
>            Priority: Major
>          Time Spent: 10m
>  Remaining Estimate: 0h
>
> It might make sense to implement Fast Loaded Dice Roller sampler.
> See https://arxiv.org/pdf/2003.03830v2.pdf, 
> https://github.com/probcomp/fast-loaded-dice-roller
> The authors claim that Fast Loaded Dice Roller is faster than the Alias 
> Method.



--
This message was sent by Atlassian Jira
(v8.20.7#820007)

Reply via email to