[
https://issues.apache.org/jira/browse/RNG-196?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alex Herbert updated RNG-196:
-----------------------------
Description:
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 (k) used to allocate the DDG
tree. The DDG tree is sized using bit length k multiplied by the number of
categories + 1: k * (n+1).
The default sampler s1 will require look-up tables of length 1076*(4+1).
Sampler s2 will require look-up tables of length 2*(3+1). 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.
was:
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.
> 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
> Priority: Trivial
>
> 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 (k) used to allocate
> the DDG tree. The DDG tree is sized using bit length k multiplied by the
> number of categories + 1: k * (n+1).
> The default sampler s1 will require look-up tables of length 1076*(4+1).
> Sampler s2 will require look-up tables of length 2*(3+1). 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)
