[
https://issues.apache.org/jira/browse/RNG-202?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18108242#comment-18108242
]
Alex Herbert commented on RNG-202:
----------------------------------
There are at least two ways to address this issue:
# Bound the scaling factor to limit memory allocation relative to the number
of categories
# Document the potentially large memory allocation
Since memory allocation is bounded by an array size, it is possible to create a
sampler with a large scaling factor only if there is memory available.
Otherwise an OutOfMemoryError will occur. This result should be self
explanatory for a downstream user to check the documentation and adjust the
scaling appropriately.
In general increasing the size of the internal table will increase performance.
This may see diminishing returns as the scaling increases. However the point at
which performance improvements drop-off is dependent on the underlying
probabilities of the enumerated distribution. So there is no way to set a limit
on the scaling that will not compromise performance in all cases.
I suggest adding additional documentation to the samplers to advise users to
limit scaling unless benchmarking the use case shows valuable performance gains
at higher scaling.
> Scaling factors in GuideTableDiscreteSampler and AliasMethodDiscreteSampler
> allow very large memory allocation
> --------------------------------------------------------------------------------------------------------------
>
> Key: RNG-202
> URL: https://issues.apache.org/jira/browse/RNG-202
> Project: Commons RNG
> Issue Type: Improvement
> Components: sampling
> Affects Versions: 1.7
> Reporter: Alex Herbert
> Priority: Trivial
>
> The GuideTableDiscreteSampler and AliasMethodDiscreteSampler sample an
> enumerated distribution of {{n}} categories defined by probabilities.
> The GuideTableDiscreteSampler allocates a guide table of length {{n *
> alpha}}, where {{alpha}} is a scaling factor.
> The AliasMethodDiscreteSampler allocates alias tables using the size {{n}}.
> The input probabilities may be padded using a factor {{alpha}} to increase
> the table size by 2^alpha and then rounded to the next power of 2.
> In both samplers there is no limit on the increase in size made by the
> scaling factor. This allows construction to be bounded by the maximum memory
> allocation of an array.
> Issue identified using a security scan.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
