--- jsr166/src/main/java/util/SplittableRandom.java 2013/08/05 13:58:02 1.14 +++ jsr166/src/main/java/util/SplittableRandom.java 2013/08/09 12:12:10 1.15 @@ -25,7 +25,7 @@ package java.util; -import java.security.SecureRandom; +import java.net.InetAddress; import java.util.concurrent.atomic.AtomicLong; import java.util.Spliterator; import java.util.function.IntConsumer; @@ -84,105 +84,80 @@ import java.util.stream.DoubleStream; public class SplittableRandom { /* - * File organization: First the non-public methods that constitute - * the main algorithm, then the main public methods, followed by - * some custom spliterator classes needed for stream methods. - * - * Credits: Primary algorithm and code by Guy Steele. Stream - * support methods by Doug Lea. Documentation jointly produced - * with additional help from Brian Goetz. - */ - - /* * Implementation Overview. * * This algorithm was inspired by the "DotMix" algorithm by * Leiserson, Schardl, and Sukha "Deterministic Parallel * Random-Number Generation for Dynamic-Multithreading Platforms", - * PPoPP 2012, but improves and extends it in several ways. - * - * The primary update step (see method nextSeed()) is simply to - * add a constant ("gamma") to the current seed, modulo a prime - * ("George"). However, the nextLong and nextInt methods do not - * return this value, but instead the results of bit-mixing - * transformations that produce more uniformly distributed - * sequences. - * - * "George" is the otherwise nameless (because it cannot be - * represented) prime number 2^64+13. Using a prime number larger - * than can fit in a long ensures that all possible long values - * can occur, plus 13 others that just get skipped over when they - * are encountered; see method addGammaModGeorge. For this to - * work, initial gamma values must be at least 13. - * - * The mix64 bit-mixing function called by nextLong and other - * methods computes the same value as the "64-bit finalizer" - * function in Austin Appleby's MurmurHash3 algorithm. See + * PPoPP 2012, as well as those in "Parallel random numbers: as + * easy as 1, 2, 3" by Salmon, Morae, Dror, and Shaw, SC 2011. It + * differs mainly in simplifying and cheapening operations. + * + * The primary update step (method nextSeed()) is to add a + * constant ("gamma") to the current (64 bit) seed, forming a + * simple sequence. The seed and the gamma values for any two + * SplittableRandom instances are highly likely to be different. + * + * Methods nextLong, nextInt, and derivatives do not return the + * sequence (seed) values, but instead a hash-like bit-mix of + * their bits, producing more independently distributed sequences. + * For nextLong, the mix64 bit-mixing function computes the same + * value as the "64-bit finalizer" function in Austin Appleby's + * MurmurHash3 algorithm. See * http://code.google.com/p/smhasher/wiki/MurmurHash3 , which * comments: "The constants for the finalizers were generated by a * simple simulated-annealing algorithm, and both avalanche all - * bits of 'h' to within 0.25% bias." - * - * The value of gamma differs for each instance across a series of - * splits, and is generated using an independent variant of the - * same algorithm, but operating across calls to split(), not - * calls to nextSeed(): Each instance carries the state of this - * generator as nextSplit. Gammas are treated as 57bit values, - * advancing by adding GAMMA_GAMMA mod GAMMA_PRIME, and bit-mixed - * with a 57-bit version of mix, using the "Mix13" multiplicative - * constants for MurmurHash3 described by David Stafford - * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html). - * The value of GAMMA_GAMMA is arbitrary (except must be at least - * 13 and less than GAMMA_PRIME), but because it serves as the - * base of split sequences, should be subject to validation of - * consequent random number quality metrics. - * - * The mix32 function used for nextInt just consists of two of the - * five lines of mix64; avalanche testing shows that the 64-bit - * result has its top 32 bits avalanched well, though not the - * bottom 32 bits. DieHarder tests show that it is adequate for - * generating one random int from the 64-bit result of nextSeed. + * bits of 'h' to within 0.25% bias." The mix32 function is + * equivalent to (int)(mix64(seed) >>> 32), but faster because it + * omits a step that doesn't contribute to result. + * + * The split operation uses the current generator to form the seed + * and gamma for another SplittableRandom. To conservatively + * avoid potential correlations between seed and value generation, + * gamma selection (method nextGamma) uses the "Mix13" constants + * for MurmurHash3 described by David Stafford + * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html) + * To avoid potential weaknesses in bit-mixing transformations, we + * restrict gammas to odd values with at least 12 and no more than + * 52 bits set. Rather than rejecting candidates with too few or + * too many bits set, method nextGamma flips some bits (which has + * the effect of mapping at most 4 to any given gamma value). + * This reduces the effective set of 64bit odd gamma values by + * about 214, a very tiny percentage, and serves as an + * automated screening for sequence constant selection that is + * left as an empirical decision in some other hashing and crypto + * algorithms. + * + * The resulting generator thus transforms a sequence in which + * (typically) many bits change on each step, with an inexpensive + * mixer with good (but less than cryptographically secure) + * avalanching. + * + * The default (no-argument) constructor, in essence, invokes + * split() for a common "seeder" SplittableRandom. Unlike other + * cases, this split must be performed in a thread-safe manner, so + * we use an AtomicLong to represent the seed rather than use an + * explicit SplittableRandom. To bootstrap the seeder, we start + * off using a seed based on current time and host. This serves as + * a slimmed-down (and insecure) variant of SecureRandom that also + * avoids stalls that may occur when using /dev/random. + * + * It is a relatively simple matter to apply the basic design here + * to use 128 bit seeds. However, emulating 128bit arithmetic and + * carrying around twice the state add more overhead than appears + * warranted for current usages. * - * Support for the default (no-argument) constructor relies on an - * AtomicLong (defaultSeedGenerator) to help perform the - * equivalent of a split of a statically constructed - * SplittableRandom. Unlike other cases, this split must be - * performed in a thread-safe manner. We use - * AtomicLong.compareAndSet as the (typically) most efficient - * mechanism. To bootstrap, we start off using a SecureRandom - * initial default seed, and update using a fixed - * DEFAULT_SEED_GAMMA. The default constructor uses GAMMA_GAMMA, - * not 0, for its splitSeed argument (addGammaModGeorge(0, - * GAMMA_GAMMA) == GAMMA_GAMMA) to reflect that each is split from - * this root generator, even though the root is not explicitly - * represented as a SplittableRandom. - */ - - /** - * The prime modulus for gamma values. - */ - private static final long GAMMA_PRIME = (1L << 57) - 13L; - - /** - * The value for producing new gamma values. Must be greater or - * equal to 13 and less than GAMMA_PRIME. Otherwise, the value is - * arbitrary subject to validation of the resulting statistical - * quality of splits. - */ - private static final long GAMMA_GAMMA = 0x00aae38294f712aabL; - - /** - * The seed update value for default constructors. Must be - * greater or equal to 13. Otherwise, the value is arbitrary - * subject to quality checks. + * File organization: First the non-public methods that constitute + * the main algorithm, then the main public methods, followed by + * some custom spliterator classes needed for stream methods. */ - private static final long DEFAULT_SEED_GAMMA = 0x9e3779b97f4a7c15L; /** - * The value 13 with 64bit sign bit set. Used in the signed - * comparison in addGammaModGeorge. + * The initial gamma value for (unsplit) SplittableRandoms. Must + * be odd with at least 12 and no more than 52 bits set. Currently + * set to the golden ratio scaled to 64bits. */ - private static final long BOTTOM13 = 0x800000000000000DL; + private static final long INITIAL_GAMMA = 0x9e3779b97f4a7c15L; /** * The least non-zero value returned by nextDouble(). This value @@ -191,136 +166,82 @@ public class SplittableRandom { private static final double DOUBLE_UNIT = 1.0 / (1L << 53); /** - * The next seed for default constructors. - */ - private static final AtomicLong defaultSeedGenerator = - new AtomicLong(getInitialDefaultSeed()); - - /** - * The seed, updated only via method nextSeed. + * The seed. Updated only via method nextSeed. */ private long seed; /** - * The constant value added to seed (mod George) on each update. + * The step value. */ private final long gamma; /** - * The next seed to use for splits. Propagated using - * addGammaModGeorge across instances. + * Internal constructor used by all others except default constructor. */ - private final long nextSplit; - - /** - * Adds the given gamma value, g, to the given seed value s, mod - * George (2^64+13). We regard s and g as unsigned values - * (ranging from 0 to 2^64-1). We add g to s either once or twice - * (mod George) as necessary to produce an (unsigned) result less - * than 2^64. We require that g must be at least 13. This - * guarantees that if (s+g) mod George >= 2^64 then (s+g+g) mod - * George < 2^64; thus we need only a conditional, not a loop, - * to be sure of getting a representable value. - * - * Because Java comparison operators are signed, we implement this - * by conceptually offsetting seed values downwards by 2^63, so - * 0..13 is represented as Long.MIN_VALUE..BOTTOM13. - * - * @param s a seed value, viewed as a signed long - * @param g a gamma value, 13 <= g (as unsigned) - */ - private static long addGammaModGeorge(long s, long g) { - long p = s + g; - return (p >= s) ? p : ((p >= BOTTOM13) ? p : p + g) - 13L; + private SplittableRandom(long seed, long gamma) { + this.seed = seed; + this.gamma = gamma; } /** - * Returns a bit-mixed transformation of its argument. - * See above for explanation. + * Computes MurmurHash3 64bit mix function. */ private static long mix64(long z) { - z ^= (z >>> 33); - z *= 0xff51afd7ed558ccdL; - z ^= (z >>> 33); - z *= 0xc4ceb9fe1a85ec53L; - z ^= (z >>> 33); - return z; + z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; + z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L; + return z ^ (z >>> 33); } /** - * Returns a bit-mixed int transformation of its argument. - * See above for explanation. + * Returns the 32 high bits of mix64(z) as int. */ private static int mix32(long z) { - z ^= (z >>> 33); - z *= 0xc4ceb9fe1a85ec53L; - return (int)(z >>> 32); + z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; + return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32); } /** - * Returns a 57-bit mixed transformation of its argument. See - * above for explanation. + * Returns the gamma value to use for a new split instance. */ - private static long mix57(long z) { - z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L; - z &= 0x01FFFFFFFFFFFFFFL; + private static long nextGamma(long z) { + z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L; // Stafford "Mix13" z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL; - z &= 0x01FFFFFFFFFFFFFFL; - z ^= (z >>> 31); - return z; + z = (z ^ (z >>> 31)) | 1L; // force to be odd + int n = Long.bitCount(z); // ensure enough 0 and 1 bits + return (n < 12 || n > 52) ? z ^ 0xaaaaaaaaaaaaaaaaL : z; } /** - * Internal constructor used by all other constructors and by - * method split. Establishes the initial seed for this instance, - * and uses the given splitSeed to establish gamma, as well as the - * nextSplit to use by this instance. The loop to skip ineligible - * gammas very rarely iterates, and does so at most 13 times. - */ - private SplittableRandom(long seed, long splitSeed) { - this.seed = seed; - long s = splitSeed, g; - do { // ensure gamma >= 13, considered as an unsigned integer - s += GAMMA_GAMMA; - if (s >= GAMMA_PRIME) - s -= GAMMA_PRIME; - g = mix57(s); - } while (g < 13L); - this.gamma = g; - this.nextSplit = s; - } - - /** - * Updates in-place and returns seed. - * See above for explanation. + * Adds gamma to seed. */ private long nextSeed() { - return seed = addGammaModGeorge(seed, gamma); + return seed += gamma; } /** - * Atomically updates and returns next seed for default constructor. + * The seed generator for default constructors. */ - private static long nextDefaultSeed() { - long oldSeed, newSeed; - do { - oldSeed = defaultSeedGenerator.get(); - newSeed = addGammaModGeorge(oldSeed, DEFAULT_SEED_GAMMA); - } while (!defaultSeedGenerator.compareAndSet(oldSeed, newSeed)); - return mix64(newSeed); - } + private static final AtomicLong seeder = + new AtomicLong(mix64((((long)hashedHostAddress()) << 32) ^ + System.currentTimeMillis()) ^ + mix64(System.nanoTime())); /** - * Returns an initial default seed. + * Returns hash of local host IP address, if available; else 0. */ - private static long getInitialDefaultSeed() { - byte[] seedBytes = java.security.SecureRandom.getSeed(8); - long s = (long)(seedBytes[0]) & 0xffL; - for (int i = 1; i < 8; ++i) - s = (s << 8) | ((long)(seedBytes[i]) & 0xffL); - return s; + private static int hashedHostAddress() { + try { + return InetAddress.getLocalHost().hashCode(); + } catch (Exception ex) { + return 0; + } } + // IllegalArgumentException messages + static final String BadBound = "bound must be positive"; + static final String BadRange = "bound must be greater than origin"; + static final String BadSize = "size must be non-negative"; + /* * Internal versions of nextX methods used by streams, as well as * the public nextX(origin, bound) methods. These exist mainly to @@ -440,7 +361,7 @@ public class SplittableRandom { * @param seed the initial seed */ public SplittableRandom(long seed) { - this(seed, 0L); + this(seed, INITIAL_GAMMA); } /** @@ -449,8 +370,8 @@ public class SplittableRandom { * of those of any other instances in the current program; and * may, and typically does, vary across program invocations. */ - public SplittableRandom() { - this(nextDefaultSeed(), GAMMA_GAMMA); + public SplittableRandom() { // emulate seeder.split() + this.gamma = nextGamma(this.seed = seeder.addAndGet(INITIAL_GAMMA)); } /** @@ -468,7 +389,8 @@ public class SplittableRandom { * @return the new SplittableRandom instance */ public SplittableRandom split() { - return new SplittableRandom(nextSeed(), nextSplit); + long s = nextSeed(); + return new SplittableRandom(s, nextGamma(s)); } /** @@ -492,7 +414,7 @@ public class SplittableRandom { */ public int nextInt(int bound) { if (bound <= 0) - throw new IllegalArgumentException("bound must be positive"); + throw new IllegalArgumentException(BadBound); // Specialize internalNextInt for origin 0 int r = mix32(nextSeed()); int m = bound - 1; @@ -520,7 +442,7 @@ public class SplittableRandom { */ public int nextInt(int origin, int bound) { if (origin >= bound) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return internalNextInt(origin, bound); } @@ -545,7 +467,7 @@ public class SplittableRandom { */ public long nextLong(long bound) { if (bound <= 0) - throw new IllegalArgumentException("bound must be positive"); + throw new IllegalArgumentException(BadBound); // Specialize internalNextLong for origin 0 long r = mix64(nextSeed()); long m = bound - 1; @@ -573,7 +495,7 @@ public class SplittableRandom { */ public long nextLong(long origin, long bound) { if (origin >= bound) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return internalNextLong(origin, bound); } @@ -600,7 +522,7 @@ public class SplittableRandom { */ public double nextDouble(double bound) { if (!(bound > 0.0)) - throw new IllegalArgumentException("bound must be positive"); + throw new IllegalArgumentException(BadBound); double result = (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT * bound; return (result < bound) ? result : // correct for rounding Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1); @@ -619,7 +541,7 @@ public class SplittableRandom { */ public double nextDouble(double origin, double bound) { if (!(origin < bound)) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return internalNextDouble(origin, bound); } @@ -646,7 +568,7 @@ public class SplittableRandom { */ public IntStream ints(long streamSize) { if (streamSize < 0L) - throw new IllegalArgumentException("negative Stream size"); + throw new IllegalArgumentException(BadSize); return StreamSupport.intStream (new RandomIntsSpliterator (this, 0L, streamSize, Integer.MAX_VALUE, 0), @@ -686,9 +608,9 @@ public class SplittableRandom { public IntStream ints(long streamSize, int randomNumberOrigin, int randomNumberBound) { if (streamSize < 0L) - throw new IllegalArgumentException("negative Stream size"); + throw new IllegalArgumentException(BadSize); if (randomNumberOrigin >= randomNumberBound) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return StreamSupport.intStream (new RandomIntsSpliterator (this, 0L, streamSize, randomNumberOrigin, randomNumberBound), @@ -711,7 +633,7 @@ public class SplittableRandom { */ public IntStream ints(int randomNumberOrigin, int randomNumberBound) { if (randomNumberOrigin >= randomNumberBound) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return StreamSupport.intStream (new RandomIntsSpliterator (this, 0L, Long.MAX_VALUE, randomNumberOrigin, randomNumberBound), @@ -729,7 +651,7 @@ public class SplittableRandom { */ public LongStream longs(long streamSize) { if (streamSize < 0L) - throw new IllegalArgumentException("negative Stream size"); + throw new IllegalArgumentException(BadSize); return StreamSupport.longStream (new RandomLongsSpliterator (this, 0L, streamSize, Long.MAX_VALUE, 0L), @@ -769,9 +691,9 @@ public class SplittableRandom { public LongStream longs(long streamSize, long randomNumberOrigin, long randomNumberBound) { if (streamSize < 0L) - throw new IllegalArgumentException("negative Stream size"); + throw new IllegalArgumentException(BadSize); if (randomNumberOrigin >= randomNumberBound) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return StreamSupport.longStream (new RandomLongsSpliterator (this, 0L, streamSize, randomNumberOrigin, randomNumberBound), @@ -794,7 +716,7 @@ public class SplittableRandom { */ public LongStream longs(long randomNumberOrigin, long randomNumberBound) { if (randomNumberOrigin >= randomNumberBound) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return StreamSupport.longStream (new RandomLongsSpliterator (this, 0L, Long.MAX_VALUE, randomNumberOrigin, randomNumberBound), @@ -813,7 +735,7 @@ public class SplittableRandom { */ public DoubleStream doubles(long streamSize) { if (streamSize < 0L) - throw new IllegalArgumentException("negative Stream size"); + throw new IllegalArgumentException(BadSize); return StreamSupport.doubleStream (new RandomDoublesSpliterator (this, 0L, streamSize, Double.MAX_VALUE, 0.0), @@ -855,9 +777,9 @@ public class SplittableRandom { public DoubleStream doubles(long streamSize, double randomNumberOrigin, double randomNumberBound) { if (streamSize < 0L) - throw new IllegalArgumentException("negative Stream size"); + throw new IllegalArgumentException(BadSize); if (!(randomNumberOrigin < randomNumberBound)) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return StreamSupport.doubleStream (new RandomDoublesSpliterator (this, 0L, streamSize, randomNumberOrigin, randomNumberBound), @@ -880,7 +802,7 @@ public class SplittableRandom { */ public DoubleStream doubles(double randomNumberOrigin, double randomNumberBound) { if (!(randomNumberOrigin < randomNumberBound)) - throw new IllegalArgumentException("bound must be greater than origin"); + throw new IllegalArgumentException(BadRange); return StreamSupport.doubleStream (new RandomDoublesSpliterator (this, 0L, Long.MAX_VALUE, randomNumberOrigin, randomNumberBound), @@ -938,9 +860,10 @@ public class SplittableRandom { long i = index, f = fence; if (i < f) { index = f; + SplittableRandom r = rng; int o = origin, b = bound; do { - consumer.accept(rng.internalNextInt(o, b)); + consumer.accept(r.internalNextInt(o, b)); } while (++i < f); } } @@ -992,9 +915,10 @@ public class SplittableRandom { long i = index, f = fence; if (i < f) { index = f; + SplittableRandom r = rng; long o = origin, b = bound; do { - consumer.accept(rng.internalNextLong(o, b)); + consumer.accept(r.internalNextLong(o, b)); } while (++i < f); } } @@ -1047,9 +971,10 @@ public class SplittableRandom { long i = index, f = fence; if (i < f) { index = f; + SplittableRandom r = rng; double o = origin, b = bound; do { - consumer.accept(rng.internalNextDouble(o, b)); + consumer.accept(r.internalNextDouble(o, b)); } while (++i < f); } }