changeset 2352: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");
     }
 }