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

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

I updated the code to remove the use of BigInteger to store the relative 
weights. The integers are now stored as a 53-bit long integer (created from the 
mantissa of the input double weight) and an exponent offset. The weight is thus:
{code:java}
weight = value * 2^exponent

BigInteger.valueOf(value).shiftLeft(exponent) {code}
Each bit of the integer can now be tested by determining if the bit is within 
the integer using:
{code:java}
// Old (the BigInteger value was cached)
BigInteger.valueOf(value).shiftLeft(offset).testBit(n)

// New
private static boolean testBit(long value, int offset, int n) {
    if (n < offset) {
        // All logical trailing bits are zero
        return false;
    }
    final int bit = n - offset;
    return bit <= 53 && (value & (1L << bit)) != 0;
}{code}
The new code is marginally faster at testing the bits. Looking at the source 
for BigInteger there are some branch statements that are avoided and the number 
of instructions is lower (since BigInteger does some extra logic to handle zero 
and negatives).

The construction performance can be improved further by ignoring very small 
weights. I added an alpha parameter that will ignore any weights that are at 
least 2^alpha smaller in magnitude than the largest weight. The comparison uses 
only the exponent offsets. Any filtered weights are set to zero and ignored 
from further processing. This does not reduce the in-memory size of the 
discrete distribution generating tree.

The following table shows the previous BigInteger performance against the new 
version. A version with alpha=53 is shown. This only affects the Binomial 
distribution which reduces from 68 weights down to 55 with a noticeable 
improvement in construction speed. The speed is still much slower than just 
approximately mapping to long[].
||Distribution||double[] BigInteger||double[]||double[] alpha=53||long[]||
|4SidedLoadedDie|842.9|703.2|738.1|666.6|
|Binomial_N67_P0.7|55466.3|34948.1|23003.8|6833.3|
|Geometric_P0.2|48722.1|37459.9|36418.5|10702.3|
|Poisson_Mean10_Mean20|19013.6|15893.4|13786.8|5862.4|
|Poisson_Mean3.22|7434.5|6600.3|6395.6|2417.2|
|Random 3072|2184490.83|1551266.0|1560548.4|1009663.4|

The slowest to construct is the Random 3072 data. This has 3072 weights. In 
this case alpha=53 makes no difference as the weights are sampled from the 2^53 
dyadic rationals and no weights can be excluded. The speed of the new version 
is approximately 0.71x the old version.

For the Binomial distribution the affect of alpha on sampling is negligible 
(data not shown). This is due to the fact that the weights that were excluded 
will be sampled at most every 2^53 times. Thus the bulk of the distribution 
targeted by the sampler is essentially unchanged.
h2. Conclusion

The sampler construction is slow. To maintain the property of exact sampling 
from the input distribution requires exact math to be performed on the weights. 
This can be changed to ignore very small relative weights, or the weights 
mapped to long. Both improve construction performance but result is the 
sampling no longer being exact. The performance of sampling is not affected (if 
only very small weights are ignored).

 

> 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: 20m
>  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