Alex Herbert created RNG-196:
--------------------------------
Summary: FastLoadedDiceRoller defaults can result in performance
degradation for categories unlikely to be sampled
Key: RNG-196
URL: https://issues.apache.org/jira/browse/RNG-196
Project: Commons RNG
Issue Type: Improvement
Components: sampling
Affects Versions: 1.3
Reporter: Alex Herbert
The FastLoadedDiceRollerSampler (FLDR) uses an alpha parameter to exclude
weights that are smaller than the largest weight. The alpha parameter controls
the threshold for ignoring weights relative to the largest weight using a log2
scale.
The default behaviour when the alpha parameter is not provided is to use
alpha=0 and include all weights. This can result in large memory allocation
relative to the number of categories when constructing the internal discrete
distribution generating (DDG) tree, and a change to using BigInteger arithmetic
for an increased construction time. The probability of observing the smallest
weight in the resulting DDG tree is impractically small and thus performance is
impacted for accuracy over efficiency.
Example:
{code:java}
double[] weights = {1, 1, 2, Double.MIN_VALUE};
var s1 = FastLoadedDiceRollerDiscreteSampler.of(rng, weights); // alpha=0
var s2 = FastLoadedDiceRollerDiscreteSampler.of(rng, weights, 60); {code}
During construction the weights are scaled to remove common trailing zero bits,
summed exactly and the full bit length of the sum used to allocate the DDG tree.
The default sampler s1 will require look-up tables of length 1076. Sampler s2
will require look-up tables of length 2. The probability of observing the
smallest weight is w / sum(w) or approximately Double.MIN_VALUE / 4 = 1.2e-324.
An improvement is to introduce a default non-zero value for alpha. A default of
53 would ignore any weight 2^53 smaller than the largest weight. This would
have a sampling probability of 2^-53 (1e-16) relative to the largest weight. In
practice it would require 2^53 samples from the FLDR to observe this category
once. Note that use of this threshold will enable the faster non-BigInteger
construction pathway when the number of categories is less than 2^10, and may
use this pathway for larger numbers of categories depending on the number of
significant bits in the weights.
Issue identified using a security scan.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
