This is an automated email from the ASF dual-hosted git repository. aherbert pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-rng.git
commit d16d614cf0340c99d339a3c652e125b048904594 Author: Alex Herbert <[email protected]> AuthorDate: Sun Mar 20 20:51:36 2022 +0000 RNG-171: Reduce the memory footprint in cached boolean and int source This change has a performance improvement on some JDKs. Add a benchmark to compare the performance with and without the cache. --- .../commons/rng/core/source32/IntProvider.java | 53 ++--- .../commons/rng/core/source64/LongProvider.java | 93 ++++----- .../rng/core/JumpableProvidersParametricTest.java | 36 ++-- .../rng/core/source64/LongProviderTest.java | 7 +- .../jmh/core/CachedNextGenerationPerformance.java | 221 +++++++++++++++++++++ src/changes/changes.xml | 8 + 6 files changed, 314 insertions(+), 104 deletions(-) diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/IntProvider.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/IntProvider.java index 57d91e0..ed4964a 100644 --- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/IntProvider.java +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source32/IntProvider.java @@ -28,23 +28,20 @@ public abstract class IntProvider extends BaseProvider implements RandomIntSource { + /** Empty boolean source. This is the location of the sign-bit after 31 right shifts on + * the boolean source. */ + private static final int EMPTY_BOOL_SOURCE = 1; + /** * Provides a bit source for booleans. * * <p>A cached value from a call to {@link #nextInt()}. - */ - private int 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). + * <p>Only stores 31-bits when full as 1 bit has already been consumed. + * The sign bit is a flag that shifts down so the source eventually equals 1 + * when all bits are consumed and will trigger a refill. */ - private int booleanBitMask; // Initialised as 0 + private int booleanSource = EMPTY_BOOL_SOURCE; /** * Creates a new instance. @@ -65,7 +62,6 @@ public abstract class IntProvider */ protected IntProvider(IntProvider source) { booleanSource = source.booleanSource; - booleanBitMask = source.booleanBitMask; } /** @@ -78,26 +74,21 @@ public abstract class IntProvider * @since 1.3 */ protected void resetCachedState() { - booleanSource = 0; - booleanBitMask = 0; + booleanSource = EMPTY_BOOL_SOURCE; } /** {@inheritDoc} */ @Override protected byte[] getStateInternal() { - final int[] state = {booleanSource, - booleanBitMask}; - return composeStateInternal(NumberFactory.makeByteArray(state), + return composeStateInternal(NumberFactory.makeByteArray(booleanSource), super.getStateInternal()); } /** {@inheritDoc} */ @Override protected void setStateInternal(byte[] s) { - final byte[][] c = splitStateInternal(s, 8); - final int[] state = NumberFactory.makeIntArray(c[0]); - booleanSource = state[0]; - booleanBitMask = state[1]; + final byte[][] c = splitStateInternal(s, Integer.BYTES); + booleanSource = NumberFactory.makeInt(c[0]); super.setStateInternal(c[1]); } @@ -110,17 +101,17 @@ public abstract class IntProvider /** {@inheritDoc} */ @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) { - // Set the least significant bit - booleanBitMask = 1; - // Get the next value - booleanSource = nextInt(); + int bits = booleanSource; + if (bits == 1) { + // Refill + bits = next(); + // Store a refill flag in the sign bit and the unused 31 bits, return lowest bit + booleanSource = Integer.MIN_VALUE | (bits >>> 1); + return (bits & 0x1) == 1; } - // Return if the bit is set - return (booleanSource & booleanBitMask) != 0; + // Shift down eventually triggering refill, return current lowest bit + booleanSource = bits >>> 1; + return (bits & 0x1) == 1; } /** {@inheritDoc} */ diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LongProvider.java b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LongProvider.java index 7660d32..63bbd7f 100644 --- a/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LongProvider.java +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/core/source64/LongProvider.java @@ -28,33 +28,32 @@ public abstract class LongProvider extends BaseProvider implements RandomLongSource { + /** Empty boolean source. This is the location of the sign-bit after 63 right shifts on + * the boolean source. */ + private static final long EMPTY_BOOL_SOURCE = 1; + /** Empty int source. This requires a negative value as the sign-bit is used to + * trigger a refill. */ + private static final long EMPTY_INT_SOURCE = -1; + /** * Provides a bit source for booleans. * * <p>A cached value from a call to {@link #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). + * <p>Only stores 63-bits when full as 1 bit has already been consumed. + * The sign bit is a flag that shifts down so the source eventually equals 1 + * when all bits are consumed and will trigger a refill. */ - private long booleanBitMask; // Initialised as 0 + private long booleanSource = EMPTY_BOOL_SOURCE; /** * Provides a source for ints. * - * <p>A cached value from a call to {@link #nextLong()}. + * <p>A cached half-value value from a call to {@link #nextLong()}. + * The int is stored in the lower 32 bits with zeros in the upper bits. + * When empty this is set to negative to trigger a refill. */ - private long intSource; - - /** Flag to indicate an int source has been cached. */ - private boolean cachedIntSource; // Initialised as false + private long intSource = EMPTY_INT_SOURCE; /** * Creates a new instance. @@ -75,9 +74,7 @@ public abstract class LongProvider */ protected LongProvider(LongProvider source) { booleanSource = source.booleanSource; - booleanBitMask = source.booleanBitMask; intSource = source.intSource; - cachedIntSource = source.cachedIntSource; } /** @@ -91,20 +88,14 @@ public abstract class LongProvider * @since 1.3 */ protected void resetCachedState() { - booleanSource = 0L; - booleanBitMask = 0L; - intSource = 0L; - cachedIntSource = false; + booleanSource = EMPTY_BOOL_SOURCE; + intSource = EMPTY_INT_SOURCE; } /** {@inheritDoc} */ @Override protected byte[] getStateInternal() { - // Pack the boolean inefficiently as a long - final long[] state = {booleanSource, - booleanBitMask, - intSource, - cachedIntSource ? 1 : 0 }; + final long[] state = {booleanSource, intSource}; return composeStateInternal(NumberFactory.makeByteArray(state), super.getStateInternal()); } @@ -112,13 +103,10 @@ public abstract class LongProvider /** {@inheritDoc} */ @Override protected void setStateInternal(byte[] s) { - final byte[][] c = splitStateInternal(s, 32); + final byte[][] c = splitStateInternal(s, 2 * Long.BYTES); final long[] state = NumberFactory.makeLongArray(c[0]); booleanSource = state[0]; - booleanBitMask = state[1]; - intSource = state[2]; - // Non-zero is true - cachedIntSource = state[3] != 0; + intSource = state[1]; super.setStateInternal(c[1]); } @@ -131,18 +119,17 @@ public abstract class LongProvider /** {@inheritDoc} */ @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 NumberFactory.extractLo(intSource); + long bits = intSource; + if (bits < 0) { + // Refill + bits = next(); + // Store high 32 bits, return low 32 bits + intSource = bits >>> 32; + return (int) bits; } - // Fill the cache - cachedIntSource = true; - intSource = nextLong(); - // Return the upper 32 bits - return NumberFactory.extractHi(intSource); + // Reset and return previous low bits + intSource = -1; + return (int) bits; } /** {@inheritDoc} */ @@ -154,17 +141,17 @@ public abstract class LongProvider /** {@inheritDoc} */ @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) { - // Set the least significant bit - booleanBitMask = 1; - // Get the next value - booleanSource = nextLong(); + long bits = booleanSource; + if (bits == 1) { + // Refill + bits = next(); + // Store a refill flag in the sign bit and the unused 63 bits, return lowest bit + booleanSource = Long.MIN_VALUE | (bits >>> 1); + return (bits & 0x1) == 1; } - // Return if the bit is set - return (booleanSource & booleanBitMask) != 0; + // Shift down eventually triggering refill, return current lowest bit + booleanSource = bits >>> 1; + return (bits & 0x1) == 1; } /** {@inheritDoc} */ diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/JumpableProvidersParametricTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/JumpableProvidersParametricTest.java index 8071fd4..f96f63a 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/JumpableProvidersParametricTest.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/JumpableProvidersParametricTest.java @@ -35,14 +35,14 @@ import org.apache.commons.rng.core.source64.LongProvider; * Tests which all {@link JumpableUniformRandomProvider} generators must pass. */ class JumpableProvidersParametricTest { - /** The size of the state for the IntProvider. */ - private static final int INT_PROVIDER_STATE_SIZE; - /** The size of the state for the LongProvider. */ - private static final int LONG_PROVIDER_STATE_SIZE; + /** The default state for the IntProvider. */ + private static final byte[] INT_PROVIDER_STATE; + /** The default state for the LongProvider. */ + private static final byte[] LONG_PROVIDER_STATE; static { - INT_PROVIDER_STATE_SIZE = new State32Generator().getStateSize(); - LONG_PROVIDER_STATE_SIZE = new State64Generator().getStateSize(); + INT_PROVIDER_STATE = new State32Generator().getState(); + LONG_PROVIDER_STATE = new State64Generator().getState(); } /** @@ -194,15 +194,15 @@ class JumpableProvidersParametricTest { */ private static void assertJumpResetsDefaultState(TestJumpFunction jumpFunction, JumpableUniformRandomProvider generator) { - int stateSize; + byte[] expected; if (generator instanceof IntProvider) { - stateSize = INT_PROVIDER_STATE_SIZE; + expected = INT_PROVIDER_STATE; } else if (generator instanceof LongProvider) { - stateSize = LONG_PROVIDER_STATE_SIZE; + expected = LONG_PROVIDER_STATE; } else { throw new AssertionError("Unsupported RNG"); } - final byte[] expected = new byte[stateSize]; + final int stateSize = expected.length; for (int repeats = 0; repeats < 2; repeats++) { // Exercise the generator. // This calls nextInt() once so the default implementation of LongProvider @@ -238,12 +238,13 @@ class JumpableProvidersParametricTest { } /** - * Gets the state size. This captures the state size of the IntProvider. + * Gets the default state. This captures the initial state of the IntProvider + * including the values of the cache variables. * - * @return the state size + * @return the state */ - int getStateSize() { - return getStateInternal().length; + byte[] getState() { + return getStateInternal(); } } @@ -258,12 +259,13 @@ class JumpableProvidersParametricTest { } /** - * Gets the state size. This captures the state size of the LongProvider. + * Gets the default state. This captures the initial state of the LongProvider + * including the values of the cache variables. * * @return the state size */ - int getStateSize() { - return getStateInternal().length; + byte[] getState() { + return getStateInternal(); } } diff --git a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/LongProviderTest.java b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/LongProviderTest.java index f799999..ec62c32 100644 --- a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/LongProviderTest.java +++ b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source64/LongProviderTest.java @@ -16,6 +16,7 @@ */ package org.apache.commons.rng.core.source64; +import org.apache.commons.rng.core.util.NumberFactory; import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; import org.junit.jupiter.params.ParameterizedTest; @@ -74,15 +75,15 @@ class LongProviderTest { /** * This test ensures that the call to {@link LongProvider#nextInt()} returns the - * upper and then lower 32-bits from {@link LongProvider#nextLong()}. + * lower and then upper 32-bits from {@link LongProvider#nextLong()}. */ @Test void testNextInt() { final int max = 5; for (int i = 0; i < max; i++) { for (int j = 0; j < max; j++) { - // Pack into upper then lower bits - final long value = (((long) i) << 32) | (j & 0xffffffffL); + // Pack into lower then upper bits + final long value = NumberFactory.makeLong(j, i); final LongProvider provider = new FixedLongProvider(value); Assertions.assertEquals(i, provider.nextInt(), "1st call not the upper 32-bits"); Assertions.assertEquals(j, provider.nextInt(), "2nd call not the lower 32-bits"); diff --git a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/core/CachedNextGenerationPerformance.java b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/core/CachedNextGenerationPerformance.java new file mode 100644 index 0000000..5698b98 --- /dev/null +++ b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/core/CachedNextGenerationPerformance.java @@ -0,0 +1,221 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.rng.examples.jmh.core; + +import java.util.function.IntSupplier; +import org.apache.commons.rng.UniformRandomProvider; +import org.apache.commons.rng.core.source64.LongProvider; +import org.apache.commons.rng.examples.jmh.RandomSources; +import org.apache.commons.rng.simple.RandomSource; +import org.openjdk.jmh.annotations.Benchmark; +import org.openjdk.jmh.annotations.Param; +import org.openjdk.jmh.annotations.Scope; +import org.openjdk.jmh.annotations.Setup; +import org.openjdk.jmh.annotations.State; + +/** + * Executes a benchmark to compare the speed of generation of random numbers from the + * various source providers using the bit cache verses simple generation. + */ +public class CachedNextGenerationPerformance extends AbstractBenchmark { + /** The value. Must NOT be final to prevent JVM optimisation! */ + private boolean booleanValue; + /** The value. Must NOT be final to prevent JVM optimisation! */ + private int intValue; + + /** + * Provides a function to obtain a boolean value from the various "RandomSource"s. + * It exercise the default nextBoolean() method (which may use + * a cache of bits) against a sign test on the native output. + */ + @State(Scope.Benchmark) + public static class BooleanSources extends RandomSources { + /** Functional interface for a boolean generator. */ + interface BooleanSupplier { + /** + * @return the boolean + */ + boolean getAsBoolean(); + } + + /** + * The method to create the boolean value. + */ + @Param({"nextBoolean", "signTest"}) + private String method; + + /** The generator. */ + private BooleanSupplier generator; + + /** + * @return the next boolean + */ + boolean next() { + return generator.getAsBoolean(); + } + + /** {@inheritDoc} */ + @Override + @Setup + public void setup() { + // Create the generator. + super.setup(); + final UniformRandomProvider rng = getGenerator(); + + // Create the method to generate the boolean + if ("signTest".equals(method)) { + if (rng instanceof LongProvider) { + generator = () -> rng.nextLong() < 0; + } else { + // Assumed IntProvider + generator = () -> rng.nextInt() < 0; + } + } else if ("nextBoolean".equals(method)) { + // Do not use a method handle 'rng::nextBoolean' for the nextBoolean + // to attempt to maintain a comparable lambda function. The JVM may + // optimise this away. + generator = () -> rng.nextBoolean(); + } else { + throw new IllegalStateException("Unknown boolean method: " + method); + } + } + } + /** + * Provides a function to obtain an int value from the various "RandomSource"s + * that produce 64-bit output. + * It exercise the default nextInt() method (which may use + * a cache of bits) against a shift on the native output. + */ + @State(Scope.Benchmark) + public static class IntSources { + /** + * RNG providers. This list is maintained in the order of the {@link RandomSource} enum. + * + * <p>Include only those that are a {@link LongProvider}.</p> + */ + @Param({"SPLIT_MIX_64", + "XOR_SHIFT_1024_S", + "TWO_CMRES", + "MT_64", + "XOR_SHIFT_1024_S_PHI", + "XO_RO_SHI_RO_128_PLUS", + "XO_RO_SHI_RO_128_SS", + "XO_SHI_RO_256_PLUS", + "XO_SHI_RO_256_SS", + "XO_SHI_RO_512_PLUS", + "XO_SHI_RO_512_SS", + "PCG_RXS_M_XS_64", + "SFC_64", + "JSF_64", + "XO_RO_SHI_RO_128_PP", + "XO_SHI_RO_256_PP", + "XO_SHI_RO_512_PP", + "XO_RO_SHI_RO_1024_PP", + "XO_RO_SHI_RO_1024_S", + "XO_RO_SHI_RO_1024_SS", + "PCG_RXS_M_XS_64_OS"}) + private String randomSourceName; + + /** + * The method to create the int value. + */ + @Param({"nextInt", "shiftLong"}) + private String method; + + /** The generator. */ + private IntSupplier gen; + + /** + * @return the next int + */ + int next() { + return gen.getAsInt(); + } + + /** Create the int source. */ + @Setup + public void setup() { + final UniformRandomProvider rng = RandomSource.valueOf(randomSourceName).create(); + if (!(rng instanceof LongProvider)) { + throw new IllegalStateException("Not a LongProvider: " + rng.getClass().getName()); + } + + // Create the method to generate the int + if ("shiftLong".equals(method)) { + gen = () -> (int) (rng.nextLong() >>> 32); + } else if ("nextInt".equals(method)) { + // Do not use a method handle 'rng::nextInt' for the nextInt + // to attempt to maintain a comparable lambda function. The JVM may + // optimise this away. + gen = () -> rng.nextInt(); + } else { + throw new IllegalStateException("Unknown int method: " + method); + } + } + } + + /** + * Baseline for a JMH method call with no return value. + */ + @Benchmark + public void baselineVoid() { + // Do nothing, this is a baseline + } + + /** + * Baseline for a JMH method call returning a {@code boolean}. + * + * @return the value + */ + @Benchmark + public boolean baselineBoolean() { + return booleanValue; + } + + /** + * Baseline for a JMH method call returning an {@code int}. + * + * @return the value + */ + @Benchmark + public int baselineInt() { + return intValue; + } + + /** + * Exercise the boolean generation method. + * + * @param sources Source of randomness. + * @return the boolean + */ + @Benchmark + public boolean nextBoolean(BooleanSources sources) { + return sources.next(); + } + + /** + * Exercise the int generation method. + * + * @param sources Source of randomness. + * @return the int + */ + @Benchmark + public int nextInt(IntSources sources) { + return sources.next(); + } +} diff --git a/src/changes/changes.xml b/src/changes/changes.xml index 598e1fe..0926c7f 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -81,6 +81,14 @@ re-run tests that fail, and pass the build if they succeed within the allotted number of reruns (the test will be marked as 'flaky' in the report). "> + <action dev="aherbert" type="update" issue="171"> + Recuce the memory footprint of the cached boolean and int source for the IntProvider + and LongProvider. This change has a performance improvement on some JDKs. + Note: This introduces a functional compatibility change to the output from the + nextInt method of any LongProvider; the output is now little-endian as + each long is returned as the low 32-bits then the high 32-bits. + The bit output from nextBoolean is unchanged (little-endian order). + </action> <action dev="aherbert" type="update" issue="172"> "UniformLongSampler": Precompute rejection threshold for a non-power of 2 range. </action>
