Alex Herbert created RNG-171:
--------------------------------
Summary: 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
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)
