You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2019/06/29 10:25:41 UTC
[commons-rng] 01/03: RNG-108: Update the SeedFactory to improve
performance
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 f9185e91c77cc717c53aab6ff5e05ed853401d87
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Fri Jun 28 00:32:43 2019 +0100
RNG-108: Update the SeedFactory to improve performance
- Use XorShift1024SPhi
- Use a ReentrantLock for synchronization
- Output arrays using blocks of numbers per synchronisation event
---
.../commons/rng/simple/internal/SeedFactory.java | 283 +++++++++------------
.../rng/simple/internal/SeedFactoryTest.java | 111 +++++++-
2 files changed, 227 insertions(+), 167 deletions(-)
diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedFactory.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedFactory.java
index 5ebf42f..8802622 100644
--- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedFactory.java
+++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedFactory.java
@@ -17,11 +17,13 @@
package org.apache.commons.rng.simple.internal;
import java.security.SecureRandom;
+import java.util.concurrent.locks.ReentrantLock;
+
import org.apache.commons.rng.core.util.NumberFactory;
-import org.apache.commons.rng.core.source32.RandomIntSource;
-import org.apache.commons.rng.core.source32.Well44497b;
+import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.source64.RandomLongSource;
import org.apache.commons.rng.core.source64.SplitMix64;
+import org.apache.commons.rng.core.source64.XorShift1024StarPhi;
/**
* Utilities related to seeding.
@@ -43,19 +45,41 @@ import org.apache.commons.rng.core.source64.SplitMix64;
* @since 1.0
*/
public final class SeedFactory {
+ /** Size of the state array of "XorShift1024StarPhi". */
+ private static final int XOR_SHIFT_1024_STATE_SIZE = 16;
+ /** Size of block to fill in an {@code int[]} seed per synchronized operation. */
+ private static final int INT_ARRAY_BLOCK_SIZE = 8;
+ /** Size of block to fill in a {@code long[]} seed per synchronized operation. */
+ private static final int LONG_ARRAY_BLOCK_SIZE = 4;
+
+ /**
+ * The lock to own when using the seed generator. This lock is unfair and there is no
+ * particular access order for waiting threads.
+ *
+ * <p>This is used as an alternative to {@code synchronized} statements to guard access
+ * to the seed generator.</p>
+ */
+ private static final ReentrantLock LOCK = new ReentrantLock(false);
+
/** Generator with a long period. */
- private static final RandomIntSource SEED_GENERATOR;
- /** Size of the state array of "Well44497b". */
- private static final int WELL_44497_BLOCK_COUNT = 1391;
+ private static final UniformRandomProvider SEED_GENERATOR;
static {
// Use a secure RNG so that different instances (e.g. in multiple JVM
// instances started in rapid succession) will have different seeds.
final SecureRandom seedGen = new SecureRandom();
- final long initSeed = NumberFactory.makeLong(seedGen.generateSeed(8));
- final SplitMix64 rng = new SplitMix64(initSeed);
+ final long[] seed = NumberFactory.makeLongArray(
+ seedGen.generateSeed(8 * XOR_SHIFT_1024_STATE_SIZE));
+ // The XorShift1024StarPhi generator cannot recover from an all zero seed and
+ // will produce low quality initial output if initialised with some zeros.
+ // Ensure it is non zero at all array positions using a SplitMix64
+ // generator (this is insensitive to a zero seed so can use the first seed value).
+ final SplitMix64 rng = new SplitMix64(seed[0]);
+ for (int i = 0; i < seed.length; i++) {
+ seed[i] = ensureNonZero(rng, seed[i]);
+ }
- SEED_GENERATOR = new Well44497b(createIntArray(WELL_44497_BLOCK_COUNT, rng));
+ SEED_GENERATOR = new XorShift1024StarPhi(seed);
}
/**
@@ -64,207 +88,116 @@ public final class SeedFactory {
private SeedFactory() {}
/**
- * Creates a number for use as a seed.
+ * Creates an {@code int} number for use as a seed.
*
* @return a random number.
*/
public static int createInt() {
- return createInt(SEED_GENERATOR, System.identityHashCode(new Object()));
+ LOCK.lock();
+ try {
+ return SEED_GENERATOR.nextInt();
+ } finally {
+ LOCK.unlock();
+ }
}
/**
- * Creates a number for use as a seed.
+ * Creates a {@code long} number for use as a seed.
*
* @return a random number.
*/
public static long createLong() {
- return createLong(SEED_GENERATOR, System.identityHashCode(new Object()));
+ LOCK.lock();
+ try {
+ return SEED_GENERATOR.nextLong();
+ } finally {
+ LOCK.unlock();
+ }
}
/**
- * Creates an array of numbers for use as a seed.
+ * Creates an array of {@code int} numbers for use as a seed.
*
* @param n Size of the array to create.
* @return an array of {@code n} random numbers.
*/
public static int[] createIntArray(int n) {
- final int[] seed = createIntArray(n, SEED_GENERATOR, new Object());
+ final int[] seed = new int[n];
+ // Compute the size that can be filled with complete blocks
+ final int blockSize = INT_ARRAY_BLOCK_SIZE * (n / INT_ARRAY_BLOCK_SIZE);
+ int i = 0;
+ while (i < blockSize) {
+ final int end = i + INT_ARRAY_BLOCK_SIZE;
+ fillIntArray(seed, i, end);
+ i = end;
+ }
+ // Final fill only if required
+ if (i != n) {
+ fillIntArray(seed, i, n);
+ }
ensureNonZero(seed);
return seed;
}
/**
- * Creates an array of numbers for use as a seed.
+ * Creates an array of {@code long} numbers for use as a seed.
*
* @param n Size of the array to create.
* @return an array of {@code n} random numbers.
*/
public static long[] createLongArray(int n) {
- final long[] seed = createLongArray(n, SEED_GENERATOR, new Object());
+ final long[] seed = new long[n];
+ // Compute the size that can be filled with complete blocks
+ final int blockSize = LONG_ARRAY_BLOCK_SIZE * (n / LONG_ARRAY_BLOCK_SIZE);
+ int i = 0;
+ while (i < blockSize) {
+ final int end = i + LONG_ARRAY_BLOCK_SIZE;
+ fillLongArray(seed, i, end);
+ i = end;
+ }
+ // Final fill only if required
+ if (i != n) {
+ fillLongArray(seed, i, n);
+ }
ensureNonZero(seed);
return seed;
}
/**
- * Creates an array of numbers for use as a seed.
- *
- * @param n Size of the array to create.
- * @param source Source of randomness.
- * @return an array of {@code n} random numbers drawn from the
- * {@code source}.
- */
- static long[] createLongArray(int n,
- RandomIntSource source) {
- return createLongArray(n, source, null);
- }
-
- /**
- * Creates an array of numbers for use as a seed.
- *
- * @param n Size of the array to create.
- * @param source Source of randomness.
- * @return an array of {@code n} random numbers drawn from the
- * {@code source}.
- */
- static int[] createIntArray(int n,
- RandomLongSource source) {
- return createIntArray(n, source, null);
- }
-
- /**
- * Creates an array of numbers for use as a seed.
- *
- * @param n Size of the array to create.
- * @param source Source of randomness.
- * @return an array of {@code n} random numbers drawn from the
- * {@code source}.
- */
- static int[] createIntArray(int n,
- RandomIntSource source) {
- return createIntArray(n, source, null);
- }
-
- /**
- * Creates an array of numbers for use as a seed.
- *
- * @param n Size of the array to create.
- * @param source Source of randomness.
- * @param h Arbitrary object whose {@link System#identityHashCode(Object)
- * hash code} will be combined with the next number drawn from
- * the {@code source}.
- * @return an array of {@code n} random numbers.
- */
- private static long[] createLongArray(int n,
- RandomIntSource source,
- Object h) {
- final long[] array = new long[n];
-
- final int hash = System.identityHashCode(h);
- for (int i = 0; i < n; i++) {
- array[i] = createLong(source, hash);
- }
-
- return array;
- }
-
- /**
- * Creates an array of numbers for use as a seed.
+ * Fill the array between {@code start} inclusive and {@code end} exclusive from the
+ * seed generator. The lock is used to guard access to the generator.
*
- * @param n Size of the array to create.
- * @param source Source of randomness.
- * @param h Arbitrary object whose {@link System#identityHashCode(Object)
- * hash code} will be combined with the next number drawn from
- * the {@code source}.
- * @return an array of {@code n} random numbers.
+ * @param array Array data.
+ * @param start Start (inclusive).
+ * @param end End (exclusive).
*/
- private static int[] createIntArray(int n,
- RandomLongSource source,
- Object h) {
- final int[] array = new int[n];
-
- final int hash = System.identityHashCode(h);
- for (int i = 0; i < n; i += 2) {
- final long v = createLong(source, hash);
-
- array[i] = NumberFactory.extractHi(v);
-
- if (i + 1 < n) {
- array[i + 1] = NumberFactory.extractLo(v);
+ private static void fillIntArray(int[] array, int start, int end) {
+ LOCK.lock();
+ try {
+ for (int i = start; i < end; i++) {
+ array[i] = SEED_GENERATOR.nextInt();
}
+ } finally {
+ LOCK.unlock();
}
-
- return array;
}
/**
- * Creates an array of numbers for use as a seed.
+ * Fill the array between {@code start} inclusive and {@code end} exclusive from the
+ * seed generator. The lock is used to guard access to the generator.
*
- * @param n Size of the array to create.
- * @param source Source of randomness.
- * @param h Arbitrary object whose {@link System#identityHashCode(Object)
- * hash code} will be combined with the next number drawn from
- * the {@code source}.
- * @return an array of {@code n} random numbers.
+ * @param array Array data.
+ * @param start Start (inclusive).
+ * @param end End (exclusive).
*/
- private static int[] createIntArray(int n,
- RandomIntSource source,
- Object h) {
- final int[] array = new int[n];
-
- final int hash = System.identityHashCode(h);
- for (int i = 0; i < n; i++) {
- array[i] = createInt(source, hash);
- }
-
- return array;
- }
-
- /**
- * Creates a random number by performing an "xor" between the
- * next value in the sequence of the {@code source} and the
- * given {@code number}.
- *
- * @param source Source of randomness.
- * @param number Arbitrary number.
- * @return a random number.
- */
- private static long createLong(RandomLongSource source,
- int number) {
- synchronized (source) {
- return source.next() ^ NumberFactory.makeLong(number, number);
- }
- }
-
- /**
- * Creates a random number by performing an "xor" between the
- * the next value in the sequence of the {@code source} and the
- * given {@code number}.
- *
- * @param source Source of randomness.
- * @param number Arbitrary number.
- * @return a random number.
- */
- private static long createLong(RandomIntSource source,
- int number) {
- synchronized (source) {
- return NumberFactory.makeLong(source.next() ^ number,
- source.next() ^ number);
- }
- }
-
- /**
- * Creates a random number by performing an "xor" between the
- * next value in the sequence of the {@code source} and the
- * given {@code number}.
- *
- * @param source Source of randomness.
- * @param number Arbitrary number.
- * @return a random number.
- */
- private static int createInt(RandomIntSource source,
- int number) {
- synchronized (source) {
- return source.next() ^ number;
+ private static void fillLongArray(long[] array, int start, int end) {
+ LOCK.lock();
+ try {
+ for (int i = start; i < end; i++) {
+ array[i] = SEED_GENERATOR.nextLong();
+ }
+ } finally {
+ LOCK.unlock();
}
}
@@ -307,4 +240,22 @@ public final class SeedFactory {
} while (seed[0] == 0);
}
}
+
+ /**
+ * Ensure the value is non-zero.
+ *
+ * <p>This method will replace a zero with a non-zero random number from the random source.</p>
+ *
+ * @param source Source of randomness.
+ * @param value Value.
+ * @return {@code value} if non-zero; else a new random number
+ */
+ static long ensureNonZero(RandomLongSource source,
+ long value) {
+ long result = value;
+ while (result == 0) {
+ result = source.next();
+ }
+ return result;
+ }
}
diff --git a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedFactoryTest.java b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedFactoryTest.java
index d4298f4..296e00a 100644
--- a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedFactoryTest.java
+++ b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedFactoryTest.java
@@ -20,7 +20,7 @@ import java.util.Map;
import java.util.HashMap;
import org.junit.Assert;
import org.junit.Test;
-
+import org.apache.commons.rng.core.source64.RandomLongSource;
import org.apache.commons.rng.core.util.NumberFactory;
/**
@@ -112,6 +112,98 @@ public class SeedFactoryTest {
}
@Test
+ public void testCreateIntArrayWithCompleteBlockSize() {
+ // Block size is 8 for int
+ assertCreateIntArray(8);
+ }
+
+ @Test
+ public void testCreateIntArrayWithIncompleteBlockSize() {
+ // Block size is 8 for int
+ assertCreateIntArray(8 + 1);
+ }
+
+ /**
+ * Checks that the int array values can be placed into 2 bins with
+ * approximately equal number of counts.
+ * The test uses the expectation from a fixed-step "random walk".
+ *
+ * @param n The size of the array.
+ */
+ private static void assertCreateIntArray(int n) {
+ final int[] array = SeedFactory.createIntArray(n);
+ Assert.assertEquals("Incorrect array length", n, array.length);
+ // The bit count should be 50%.
+ int bitCount = 0;
+ for (final int i : array) {
+ bitCount += Integer.bitCount(i);
+ }
+ final int numberOfBits = n * Integer.SIZE;
+ assertMonobit(bitCount, numberOfBits);
+ }
+
+ @Test
+ public void testCreateLongArrayWithCompleteBlockSize() {
+ // Block size is 4 for long
+ assertCreateLongArray(4);
+ }
+
+ @Test
+ public void testCreateLongArrayWithIncompleteBlockSize() {
+ // Block size is 4 for long
+ assertCreateLongArray(4 + 1);
+ }
+
+ /**
+ * Checks that the long array values can be placed into 2 bins with
+ * approximately equal number of counts.
+ * The test uses the expectation from a fixed-step "random walk".
+ *
+ * @param n The size of the array.
+ */
+ private static void assertCreateLongArray(int n) {
+ final long[] array = SeedFactory.createLongArray(n);
+ Assert.assertEquals("Incorrect array length", n, array.length);
+ // The bit count should be 50%.
+ int bitCount = 0;
+ for (final long i : array) {
+ bitCount += Long.bitCount(i);
+ }
+ final int numberOfBits = n * Long.SIZE;
+ assertMonobit(bitCount, numberOfBits);
+ }
+
+ /**
+ * Assert that the number of 1 bits is approximately 50%. This is based upon a
+ * fixed-step "random walk" of +1/-1 from zero.
+ *
+ * <p>The test is equivalent to the NIST Monobit test with a fixed p-value of 0.01.
+ * The number of bits is recommended to be above 100.</p>
+ *
+ * @see <A
+ * href="https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final">Bassham, et
+ * al (2010) NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom
+ * Number Generators for Cryptographic Applications. Section 2.1.</a>
+ *
+ * @param bitCount The bit count.
+ * @param numberOfBits Number of bits.
+ */
+ private static void assertMonobit(int bitCount, int numberOfBits) {
+ // Convert the bit count into a number of +1/-1 steps.
+ final double sum = 2.0 * bitCount - numberOfBits;
+ // The reference distribution is Normal with a standard deviation of sqrt(n).
+ // Check the absolute position is not too far from the mean of 0 with a fixed
+ // p-value of 0.01 taken from a 2-tailed Normal distribution. Computation of
+ // true p-value requires the complimentary error function.
+ final double absSum = Math.abs(sum);
+ final double max = Math.sqrt(numberOfBits) * 2.576;
+ Assert.assertTrue("Walked too far astray: " + absSum +
+ " > " + max +
+ " (test will fail randomly about 1 in 100 times)",
+ absSum <= max);
+ }
+
+ @Test
public void testEnsureNonZeroIntArrayIgnoresEmptySeed() {
final int[] seed = new int[0];
SeedFactory.ensureNonZero(seed);
@@ -170,4 +262,21 @@ public class SeedFactoryTest {
Assert.assertEquals("Position above 0 should be unmodified", before[i], seed[i]);
}
}
+
+ @Test
+ public void testEnsureNonZeroValue() {
+ final long expected = 345;
+ RandomLongSource source = new RandomLongSource() {
+ @Override
+ public long next() {
+ return expected;
+ }
+ };
+ Assert.assertEquals("Zero should be replaced using the random source",
+ expected, SeedFactory.ensureNonZero(source, 0));
+ for (final long nonZero : new long[] {Long.MIN_VALUE, -1, 1, 9876654321L, Long.MAX_VALUE}) {
+ Assert.assertEquals("Non-zero should be unmodified",
+ nonZero, SeedFactory.ensureNonZero(source, nonZero));
+ }
+ }
}