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));
+        }
+    }
 }