[
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)