[
https://issues.apache.org/jira/browse/RNG-57?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16630299#comment-16630299
]
Alex D Herbert commented on RNG-57:
-----------------------------------
{quote}So I'm going to test a version that uses int bit masking for the
nextBoolean, having generated an int using a cached long.
{quote}
I've done this. It is not faster. The boolean is found using bit shift
operations. On a modern machine 64 bit operations are natively supported in the
register and as fast as 32 bit operations (AFAIK). So the source should always
use the native primitive type of the underlying RNG.
As for {{nextBoolean()}} I have tried a few methods and all fast bit shifting
variants seem quite similar. Some other methods are definitely worse. I do not
want to micro-benchmark this so am fine with this implementation:
{code:java}
/**
* Wrap a LongProvider instance to enable fast provision of
* {@link UniformRandomProvider#nextBoolean()}.
*/
static final class CachedLongProvider
extends LongProvider
implements CachedUniformRandomProvider {
/** The underlying source of randomness. */
private final UniformRandomProvider rng;
/**
* Provides a bit source for booleans.
*
* <p>A cached value from a call to random
* {@link UniformRandomProvider#nextLong()}.
*/
private long booleanSource; // Initialised as 0
/**
* The bit mask of the boolean source to obtain the boolean bit.
*
* <p>The bit mask contains a single bit set.
* This begins at the least significant bit and is gradually shifted
* upwards until overflow to zero.
*
* <p>When zero a new boolean source should be created and the mask
* set to the least significant bit (i.e. 1).
*/
private long booleanBitMask; // Initialised as 0
/**
* Provides a source for ints.
*
* <p>A cached value from a call to random
* {@link UniformRandomProvider#nextLong()}.
*/
private long intSource;
/** Flag to indicate an int source has been cached. */
private boolean cachedIntSource; // Initialised as false
/**
* Create a new instance.
*
* @param rng the source of randomness
*/
CachedLongProvider(LongProvider rng) {
this.rng = rng;
}
@Override
public long next() {
// Delegate this
return rng.nextLong();
}
@Override
public boolean nextBoolean() {
// Shift up. This will eventually overflow and become zero.
booleanBitMask <<= 1;
// The mask will either contain a single bit or none.
if (booleanBitMask == 0) {
// Get the next value
booleanSource = rng.nextLong();
// Set the least significant bit
booleanBitMask = 1;
}
// Return if the bit is set
return (booleanSource & booleanBitMask) != 0;
}
@Override
public int nextInt() {
// Directly store and use the long value as a source for ints
if (cachedIntSource) {
// Consume the cache value
cachedIntSource = false;
// Return the lower 32 bits
return (int) intSource;
}
// Fill the cache
cachedIntSource = true;
intSource = rng.nextLong();
// Return the upper 32 bits
return (int) (intSource >>> Integer.SIZE);
}
}
{code}
The same applies for {{IntProvider}} but just using an {{int}} as the boolean
source.
I'll run a new benchmark later on a free machine. For this test where the speed
differences can be small it helps to have a lot of repeats. I'm also finding
that the standard deviation can be quite high. I noticed because some
benchmarks use the same method and the standard deviation varies. This could be
due to the use of a underlying randomly seeded UniformRandomProvider which may
have different run time depending on the sequence. So I am also testing with
this which should run in linear time:
{code:java}
/**
* Simple test class to flip the bits in a long and return it.
*
* <p>Flipping the bits ensures that repeat sampling booleans should be 50:50
* true:false.
*/
private static final class LongFlip extends LongProvider {
/** The value. This is flipped on each call to next(). */
private long value;
LongFlip(long seed) {
value = seed;
}
@Override
public long next() {
// Flip the bits.
value = ~value;
return value;
}
}
{code}
It serves as an optimistic lower limit on the speed of the default
implementation of {{nextBoolean()}}.
> CachedUniformRandomProvider for nextBoolean() and nextInt()
> -----------------------------------------------------------
>
> Key: RNG-57
> URL: https://issues.apache.org/jira/browse/RNG-57
> Project: Commons RNG
> Issue Type: Improvement
> Components: sampling
> Affects Versions: 1.2
> Reporter: Alex D Herbert
> Priority: Minor
> Labels: performance
>
> Implement a wrapper around a {{UniformRandomProvider}} that can cache the
> underlying source of random bytes for use in the methods {{nextBoolean()}}
> and {{nextInt()}} (in the case of {{LongProvider}}). E.g.
> {code:java}
> LongProvider provider = RandomSource.create(RandomSource.SPLIT_MIX_64);
> CachedLongProvider rng = new CachedLongProvider(provider);
> // Uses cached nextLong() 64 times
> rng.nextBoolean();
> // Uses cached nextLong() twice
> rng.nextInt();
> IntProvider provider = RandomSource.create(RandomSource.KISS);
> CachedIntProvider rng2 = new CachedIntProvider(provider);
> // Uses cached nextInt() 32 times
> rng2.nextBoolean();
> // This could be wrapped by a factory method:
> UniformRandomProvider rng = CachedUniformRandomProviderFactory.wrap(
> // Any supported source: IntProvider or LongProvider
> RandomSource.create(RandomSource...));
> {code}
> The implementation should be speed tested to determine the benefit for
> {{nextBoolean()}} and if {{nextInt()}} can be improved for {{LongProviders}}.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
