[RNG-171] Reduce memory footprint of cached int and boolean source

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Implemented
• Affects Version/s: 1.4
• Fix Version/s: 1.5
• Component/s: core
• Assignee: Unassigned
• Reporter: Alex Herbert
• Created: 18/Mar/22 09:22
• Updated: 10/Oct/22 11:54
• Resolved: 05/Apr/22 15:14

Description

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.

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).

@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;
}

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.

@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;
}

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:

@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;
}

This is arguably simpler but would be a functionally breaking change.

Memory footprint would change:

IntProvider
8 bytes (int,int)                 -> 4 bytes (int)

LongProvider
25 bytes (long,long,long,boolean) -> 16 bytes (long,long)

Issue Links

• is related to: RNG-57 CachedUniformRandomProvider for nextBoolean() and nextInt()