[
https://issues.apache.org/jira/browse/RNG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17509346#comment-17509346
]
Alex Herbert commented on RNG-171:
----------------------------------
A closer inspection of the current code shows that it is using the bits for the
boolean cache in *little-endian* order. The faster code in this ticket uses the
bits in *big-endian* order. This has the advantage of being able to check for a
boolean using a sign test. So changing the implementation would break
functional compatibility.
However the int cache in the LongProvider uses big endian order. This is
inconsistent but is the standard we currently have.
There are a few options here:
Boolean
* Break functional compatibility for nextBoolean and use the faster method
benchmarked here (big endian)
* Update nextBoolean benchmarks to use the smaller memory footprint but use
little endian order
Int
* Break functional compatibility for nextInt and use the most consistently fast
method here (little endian)
* Update the nextInt code to use a smaller memory footprint but maintain
functional compatibility (big endian)
I will prepare a new benchmark for little-endian nextBoolean to see if the
changes are noticeable. The speed-up may not come from the sign test but from
using one 64-bit long rather than two that have to be loaded and saved per
cycle.
> Reduce memory footprint of cached int and boolean source
> --------------------------------------------------------
>
> Key: RNG-171
> URL: https://issues.apache.org/jira/browse/RNG-171
> Project: Commons RNG
> Issue Type: Improvement
> Components: core
> Affects Versions: 1.4
> Reporter: Alex Herbert
> Priority: Major
> Fix For: 1.5
>
>
> The base implementation for the IntProvider and LongProvider caches values
> from the generation method to be used as the source for boolean bits, and in
> the case of the LongProvider, for int bits. The nextBoolean and nextInt
> methods thus use all the bits output by the generator. The memory footprint
> of this cache can be reduced.
> h3. Boolean
> IntProvider
> Currently a 32-bit value and a 32-bit mask is stored.
> However when the cache is refilled a single bit is used for the boolean
> return value. The cache need only store the unused 31-bits. This leaves room
> to use a bit to indicate when to reset the cache. A similar change can be
> made for the LongProvider by only storing 63-bit unused bits.
> In this example for a 64-bit cache the booleanSource is initialised as
> MIN_VALUE (a single bit in the most significant position).
> {code:java}
> @Override
> public boolean nextBoolean() {
> long l = booleanSource;
> if (l == Long.MIN_VALUE) {
> // Refill
> l = next();
> // Store unused 63 bits and a refill flag, return highest bit
> booleanSource = (l << 1) | 1;
> return l < 0;
> }
> // Shift up eventually resetting, return current high bit
> booleanSource = l << 1;
> return l < 0;
> }
> {code}
> h3. Int
> LongProvider only
> Stores a 64-bit value and a boolean flag. However only 32-bits of the stored
> value are used. Thus the remaining 32-bits can be used as a flag. In this
> example the sign bit is used as it can be easily checked with a < operator.
> {code:java}
> @Override
> public int nextInt() {
> long l = intSource;
> if (l < 0) {
> // Refill
> l =next();
> // Store low 32 bits, return high 32 bits
> intSource = l & 0xffff_ffffL;
> // OR
> // Store low 63 bits, return high 32 bits
> //intSource = (l << 1) >>> 1;
> return (int) (l >>> 32);
> }
> // Reset and return previous low bits
> intSource = -1;
> return (int) l;
> }{code}
> The example above maintains compatibility to return the upper then lower
> parts of the long for the 2 int values. An alternative with fewer operations
> is:
> {code:java}
> @Override
> public int nextInt() {
> long l = intSource;
> if (l < 0) {
> // Refill
> l = next();
> // FUNCTIONALLY BREAKING CHANGE
> // Store high 32 bits, return low 32 bits
> intSource = (l >>> 32);
> return (int) l;
> }
> // Reset and return previous low bits
> intSource = -1;
> return (int) l;
> }
> {code}
> This is arguably simpler but would be a functionally breaking change.
> Memory footprint would change:
> {noformat}
> IntProvider
> 8 bytes (int,int) -> 4 bytes (int)
> LongProvider
> 25 bytes (long,long,long,boolean) -> 16 bytes (long,long)
> {noformat}
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
