Mercurial > hg > openjdk > icedtea > jdk7 > jdk
changeset 2491:df4d3e3e465a
6937857: Concurrent calls to new Random() not random enough
Summary: seed uniquifier should use an independent PRNG
Reviewed-by: dl
author | martin |
---|---|
date | Sun, 09 May 2010 16:03:13 -0700 |
parents | 0144f2fc69a3 |
children | ab0673a2e681 |
files | src/share/classes/java/util/Random.java test/java/util/Random/DistinctSeeds.java |
diffstat | 2 files changed, 61 insertions(+), 8 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/java/util/Random.java Sun May 09 00:59:49 2010 -0700 +++ b/src/share/classes/java/util/Random.java Sun May 09 16:03:13 2010 -0700 @@ -86,8 +86,23 @@ * the seed of the random number generator to a value very likely * to be distinct from any other invocation of this constructor. */ - public Random() { this(++seedUniquifier + System.nanoTime()); } - private static volatile long seedUniquifier = 8682522807148012L; + public Random() { + this(seedUniquifier() ^ System.nanoTime()); + } + + private static long seedUniquifier() { + // L'Ecuyer, "Tables of Linear Congruential Generators of + // Different Sizes and Good Lattice Structure", 1999 + for (;;) { + long current = seedUniquifier.get(); + long next = current * 181783497276652981L; + if (seedUniquifier.compareAndSet(current, next)) + return next; + } + } + + private static final AtomicLong seedUniquifier + = new AtomicLong(8682522807148012L); /** * Creates a new random number generator using a single {@code long} seed. @@ -103,8 +118,11 @@ * @see #setSeed(long) */ public Random(long seed) { - this.seed = new AtomicLong(0L); - setSeed(seed); + this.seed = new AtomicLong(initialScramble(seed)); + } + + private static long initialScramble(long seed) { + return (seed ^ multiplier) & mask; } /** @@ -127,8 +145,7 @@ * @param seed the initial seed */ synchronized public void setSeed(long seed) { - seed = (seed ^ multiplier) & mask; - this.seed.set(seed); + this.seed.set(initialScramble(seed)); haveNextNextGaussian = false; }
--- a/test/java/util/Random/DistinctSeeds.java Sun May 09 00:59:49 2010 -0700 +++ b/test/java/util/Random/DistinctSeeds.java Sun May 09 16:03:13 2010 -0700 @@ -33,18 +33,54 @@ /* * @test - * @bug 4949279 + * @bug 4949279 6937857 * @summary Independent instantiations of Random() have distinct seeds. */ +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; import java.util.Random; public class DistinctSeeds { public static void main(String[] args) throws Exception { // Strictly speaking, it is possible for these to randomly fail, - // but the probability should be *extremely* small (< 2**-63). + // but the probability should be small (approximately 2**-48). if (new Random().nextLong() == new Random().nextLong() || new Random().nextLong() == new Random().nextLong()) throw new RuntimeException("Random() seeds not unique."); + + // Now try generating seeds concurrently + class RandomCollector implements Runnable { + long[] randoms = new long[1<<17]; + public void run() { + for (int i = 0; i < randoms.length; i++) + randoms[i] = new Random().nextLong(); + } + } + final int threadCount = 2; + List<RandomCollector> collectors = new ArrayList<RandomCollector>(); + List<Thread> threads = new ArrayList<Thread>(); + for (int i = 0; i < threadCount; i++) { + RandomCollector r = new RandomCollector(); + collectors.add(r); + threads.add(new Thread(r)); + } + for (Thread thread : threads) + thread.start(); + for (Thread thread : threads) + thread.join(); + int collisions = 0; + HashSet<Long> s = new HashSet<Long>(); + for (RandomCollector r : collectors) { + for (long x : r.randoms) { + if (s.contains(x)) + collisions++; + s.add(x); + } + } + System.out.printf("collisions=%d%n", collisions); + if (collisions > 10) + throw new Error("too many collisions"); } }