gistfile1.diff

diff --git a/src/org/jruby/util/Random.java b/src/org/jruby/util/Random.java
index d14719d..bc0bb85 100644
--- a/src/org/jruby/util/Random.java
+++ b/src/org/jruby/util/Random.java
@@ -27,6 +27,7 @@ package org.jruby.util;
 
 import java.math.BigInteger;
 import java.util.Arrays;
+import java.util.concurrent.atomic.AtomicStampedReference;
 
 public class Random {
     public static int N = 624;
@@ -43,28 +44,28 @@ public class Random {
         return (MIXBITS(u, v) >>> 1) ^ (((v & 1) != 0) ? MATRIX_A : 0);
     }
 
-    private final int[] state = new int[N];
-    private int left = 1;
+    private final AtomicStampedReference<int[]> holder = new AtomicStampedReference<int[]>(new int[N], 1);
 
     public Random(int s) {
         initGenrand(s);
     }
 
     public Random(int[] initKey) {
-        initByArray(initKey);
+        holder.set(initByArray(initKey), 1);
     }
 
     public Random(Random orig) {
-        System.arraycopy(orig.state, 0, this.state, 0, this.state.length);
-        this.left = orig.left;
+        int[] rhsStamp = new int[1], rhsState = orig.holder.get(rhsStamp);
+        holder.set(Arrays.copyOf(rhsState, N), rhsStamp[0]);
     }
 
     public Random(int[] state, int left) {
-        if (state.length != this.state.length) {
+        if (state.length != this.holder.getReference().length) {
             throw new IllegalStateException("wrong state length: " + state.length);
         }
-        System.arraycopy(state, 0, this.state, 0, this.state.length);
-        this.left = left;
+        // use existing initial state[]
+        System.arraycopy(state, 0, this.holder.getReference(), 0, N);
+        this.holder.set(this.holder.getReference(), left);
     }
 
     @Override
@@ -75,29 +76,33 @@ public class Random {
             return false;
         }
         Random rhs = (Random) obj;
-        return (left == rhs.left) && Arrays.equals(state, rhs.state);
+        int[] rhsStamp = new int[1], rhsState = rhs.holder.get(rhsStamp);
+        int[] lhsStamp = new int[1], lhsState = this.holder.get(lhsStamp);
+        return (lhsStamp[0] == rhsStamp[0]) && Arrays.equals(lhsState, rhsState);
     }
 
     @Override
     public int hashCode() {
         // Using 17 as the initializer, 37 as the multiplier.
-        return (629 + left) * 37 + state.hashCode();
+        return (629 + holder.getStamp()) * 37 + holder.hashCode();
     }
     
-    private void initGenrand(int s) {
+    private static int[] initGenrand(int s) {
+        int[] state = new int[N];
         state[0] = s;
         for (int j = 1; j < N; j++) {
             state[j] = (1812433253 * (state[j - 1] ^ (state[j - 1] >>> 30)) + j);
         }
-        left = 1;
+        return state;
     }
 
-    private void initByArray(int[] initKey) {
-        initGenrand(19650218);
+    private static int[] initByArray(int[] initKey) {
+        int[] newState = initGenrand(19650218);
         int len = initKey.length;
         int i = 1;
         int j = 0;
         int k = N > len ? N : len;
+        int[] state = Arrays.copyOf(newState, N);
         for (; k > 0; k--) {
             state[i] = (state[i] ^ ((state[i - 1] ^ (state[i - 1] >>> 30)) * 1664525)) + initKey[j]
                     + j;
@@ -120,13 +125,13 @@ public class Random {
             }
         }
         state[0] = 0x80000000;
+
+        return state;
     }
 
-    private void nextState() {
+    private static void nextState(int[] state) {
         int p = 0;
 
-        left = N;
-
         for (int j = N - M + 1; --j > 0; p++) {
             state[p] = state[p + M] ^ TWIST(state[p + 0], state[p + 1]);
         }
@@ -140,14 +145,39 @@ public class Random {
 
     public int genrandInt32() {
         int y;
-
-        synchronized (this) {
-            if (--left <= 0)
-                nextState();
-
-            y = state[N - left];
+        int[] state;
+        int[] stateCopy = null;
+        int left;
+        AtomicStampedReference<int[]> holder = this.holder;
+
+        while (true) {
+            state = holder.getReference();
+            left = holder.getStamp();
+            if (left > 1) {
+                if (holder.compareAndSet(state, state, left, left - 1)) {
+                    // success! update left to the actual value, and break out
+                    left--;
+                    break;
+                } else {
+                    // someone beaten us to it, respin
+                }
+            } else {
+                // try to update
+                // $left should be exactly one at this point
+                assert left == 1;
+
+                // nextState() should be idempotent
+                if (stateCopy == null) stateCopy = Arrays.copyOf(state, N); // only create new array once
+                else System.arraycopy(state, 0, stateCopy, 0, N);
+                nextState(stateCopy);
+
+                // allow only one CAS, don't care about the result, respin
+                holder.compareAndSet(state, stateCopy, 1, N);
+            }
         }
 
+        y = state[N - left];
+
         /* Tempering */
         y ^= (y >>> 11);
         y ^= (y << 7) & 0x9d2c5680L;
@@ -182,10 +212,10 @@ public class Random {
     }
 
     public int[] getState() {
-        return state;
+        return holder.getReference();
     }
 
     public int getLeft() {
-        return left;
+        return holder.getStamp();
     }
 }