[
https://issues.apache.org/jira/browse/RNG-57?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16631801#comment-16631801
]
Alex D Herbert commented on RNG-57:
-----------------------------------
I tried a large benchmark using 100 runs in JMH.
The results for {{nextBoolean}} will need more work. They indicate that using
bit masking is not as fast as bit shifting for {{IntProvider.}}
Bit masking:
{code:java}
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.nextInt();
// Set the least significant bit
booleanBitMask = 1;
}
// Return if the bit is set
return (booleanSource & booleanBitMask) != 0;
}
{code}
against bit shifting:
{code:java}
public boolean nextBoolean() {
// Check the current shift.
// In multi-thread use the decrement can pass zero
// so use <= and not ==.
// Note: Current RNG are not thread safe though.
if (--discardShift <= 0) {
// Set shift to the size of an int
discardShift = Integer.SIZE;
// Get the next value
booleanSource = rng.nextInt();
// Check the most significant bit
return (booleanSource >>> 31) != 0;
}
// The discard shift is in the range 31 to 1
return ((booleanSource << discardShift) >>> 31) != 0;
}
{code}
The difference is significant at the P<0.001 level using a T-Test.
Using a {{LongProvider}} and the same ideas the bit masking is faster than the
bit shifting. So the different providers demand different methods.
This indicates that the 32 bit shifting is relatively faster than bit masking,
compared to 64 bit. I'm going to test it on some different machines.
For the {{LongProvider}} the {{nextInt}} results are clear: storing a value
from {{nextLong}} is optimal:
- Method 0 = No cache
- Method 1 = Cache the {{long}} from {{nextLong}}
- Method 2 = Cache an {{int}} from half of {{nextLong}}
||cacheMethod||randomSourceName||Method||Average||SD||Median||Rel.Average||Rel.Median||T-Test
P-value||
|nextIntLongProvider|FLIP|0|2214.4|18.23|2203.48|1.000|1.000|-|
|nextIntLongProvider|FLIP|1|2575.88|24.18|2545.56|1.163|1.155|1.36E-16|
|nextIntLongProvider|FLIP|2|2737.5|52.86|2657.27|1.236|1.206|-|
|nextIntLongProvider|MT_64|0|5909.35|65.69|5775.07|1.000|1.000|-|
|nextIntLongProvider|MT_64|1|4431.69|101.07|4257.25|0.750|0.737|0.219|
|nextIntLongProvider|MT_64|2|4389.76|45.33|4318.91|0.743|0.748|-|
|nextIntLongProvider|SPLIT_MIX_64|0|3568.26|64.09|3488.36|1.000|1.000|-|
|nextIntLongProvider|SPLIT_MIX_64|1|3268.32|75.49|3189|0.916|0.914|1.288E-13|
|nextIntLongProvider|SPLIT_MIX_64|2|3464.65|27.02|3451.67|0.971|0.989|-|
|nextIntLongProvider|TWO_CMRES|0|4496.06|73.06|4446.6|1.000|1.000|-|
|nextIntLongProvider|TWO_CMRES|1|3807.1|92.8|3657.3|0.847|0.822|0.905|
|nextIntLongProvider|TWO_CMRES|2|3811.41|79.68|3703.69|0.848|0.833|-|
|nextIntLongProvider|XOR_SHIFT_1024_S|0|4311.68|3.26|4309.63|1.000|1.000|-|
|nextIntLongProvider|XOR_SHIFT_1024_S|1|3559.53|59.25|3479.41|0.826|0.807|1.33E-5|
|nextIntLongProvider|XOR_SHIFT_1024_S|2|3724.05|105.79|3543.18|0.864|0.822|-|
Note:
* The FLIP random source just returns a single value for {{nextLong}} bit
flipping it each time.
* All results are faster than the native implementation.
* For MT_64 method 2 is faster but the T-Test P-value is is not significant
(0.22).
* For TWO_CMRES the P-value is not significant.
* For all other generators method 1 is faster and significant at the P=0.001
level.
> 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)
