ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166e/Striped64.java

Comparing jsr166/src/jsr166e/Striped64.java (file contents):
Revision 1.1 by dl, Tue Aug 2 18:04:12 2011 UTC vs.
Revision 1.10 by jsr166, Sun Jan 18 20:17:33 2015 UTC

#	Line 5 | Line 5
5		*/
6
7		package jsr166e;
8	+
9		import java.util.Random;
9	–	import java.util.concurrent.atomic.AtomicInteger;
10	–	import java.util.concurrent.atomic.AtomicLong;
10
11		/**
12		* A package-local class holding common representation and mechanics
13		* for classes supporting dynamic striping on 64bit values. The class
14	<	* extends Number so that concrete subclasses can publicly do so.
14	>	* extends Number so that concrete subclasses must publicly do so.
15		*/
16		abstract class Striped64 extends Number {
17		/*
#	Line 42 | Line 41 | abstract class Striped64 extends Number
41		*
42		* A single spinlock ("busy") is used for initializing and
43		* resizing the table, as well as populating slots with new Cells.
44	<	* There is no need for a blocking lock: When the lock is not
44	>	* There is no need for a blocking lock; when the lock is not
45		* available, threads try other slots (or the base).  During these
46		* retries, there is increased contention and reduced locality,
47		* which is still better than alternatives.
#	Line 79 | Line 78 | abstract class Striped64 extends Number
78		*/
79
80		/**
81	<	* Padded variant of AtomicLong supporting only raw accesses plus
82	<	* CAS The value field is placed between pads, hoping that the JVM
83	<	* doesn't reorder them.
81	>	* Padded variant of AtomicLong supporting only raw accesses plus CAS.
82	>	* The value field is placed between pads, hoping that the JVM doesn't
83	>	* reorder them.
84		*
85		* JVM intrinsics note: It would be possible to use a release-only
86		* form of CAS here, if it were provided.
#	Line 109 | Line 108 | abstract class Striped64 extends Number
108		throw new Error(e);
109		}
110		}
112	–
113	–	}
111
115	–	/**
116	–	* Holder for the thread-local hash code. The code is initially
117	–	* random, but may be set to a different value upon collisions.
118	–	*/
119	–	static final class HashCode {
120	–	static final Random rng = new Random();
121	–	int code;
122	–	HashCode() {
123	–	int h = rng.nextInt(); // Avoid zero to allow xorShift rehash
124	–	code = (h == 0) ? 1 : h;
125	–	}
112		}
113	<
113	>
114		/**
115	<	* The corresponding ThreadLocal class
115	>	* ThreadLocal holding a single-slot int array holding hash code.
116	>	* Unlike the JDK8 version of this class, we use a suboptimal
117	>	* int[] representation to avoid introducing a new type that can
118	>	* impede class-unloading when ThreadLocals are not removed.
119		*/
120	<	static final class ThreadHashCode extends ThreadLocal<HashCode> {
132	<	public HashCode initialValue() { return new HashCode(); }
133	<	}
120	>	static final ThreadLocal<int[]> threadHashCode = new ThreadLocal<int[]>();
121
122		/**
123	<	* Static per-thread hash codes. Shared across all instances to
137	<	* reduce ThreadLocal pollution and because adjustments due to
138	<	* collisions in one table are likely to be appropriate for
139	<	* others.
123	>	* Generator of new random hash codes
124		*/
125	<	static final ThreadHashCode threadHashCode = new ThreadHashCode();
125	>	static final Random rng = new Random();
126
127	<	/** Nomber of CPUS, to place bound on table size */
127	>	/** Number of CPUS, to place bound on table size */
128		static final int NCPU = Runtime.getRuntime().availableProcessors();
129
130		/**
#	Line 150 | Line 134 | abstract class Striped64 extends Number
134
135		/**
136		* Base value, used mainly when there is no contention, but also as
137	<	* a fallback during table initializion races. Updated via CAS.
137	>	* a fallback during table initialization races. Updated via CAS.
138		*/
139		transient volatile long base;
140
#	Line 166 | Line 150 | abstract class Striped64 extends Number
150		}
151
152		/**
153	<	* CAS the base field
153	>	* CASes the base field.
154		*/
155		final boolean casBase(long cmp, long val) {
156		return UNSAFE.compareAndSwapLong(this, baseOffset, cmp, val);
157		}
158
159		/**
160	<	* CAS the busy field from 0 to 1 to acquire lock.
160	>	* CASes the busy field from 0 to 1 to acquire lock.
161		*/
162		final boolean casBusy() {
163		return UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1);
#	Line 201 | Line 185 | abstract class Striped64 extends Number
185		* @param hc the hash code holder
186		* @param wasUncontended false if CAS failed before call
187		*/
188	<	final void retryUpdate(long x, HashCode hc, boolean wasUncontended) {
189	<	int h = hc.code;
188	>	final void retryUpdate(long x, int[] hc, boolean wasUncontended) {
189	>	int h;
190	>	if (hc == null) {
191	>	threadHashCode.set(hc = new int[1]); // Initialize randomly
192	>	int r = rng.nextInt(); // Avoid zero to allow xorShift rehash
193	>	h = hc[0] = (r == 0) ? 1 : r;
194	>	}
195	>	else
196	>	h = hc[0];
197		boolean collide = false;                // True if last slot nonempty
198		for (;;) {
199		Cell[] as; Cell a; int n; long v;
#	Line 238 | Line 229 | abstract class Striped64 extends Number
229		collide = false;            // At max size or stale
230		else if (!collide)
231		collide = true;
232	<	else if (busy == 0 && casBusy()) {
232	>	else if (busy == 0 && casBusy()) {
233		try {
234		if (cells == as) {      // Expand table unless stale
235		Cell[] rs = new Cell[n << 1];
#	Line 255 | Line 246 | abstract class Striped64 extends Number
246		h ^= h << 13;                   // Rehash
247		h ^= h >>> 17;
248		h ^= h << 5;
249	+	hc[0] = h;                      // Record index for next time
250		}
251		else if (busy == 0 && cells == as && casBusy()) {
252		boolean init = false;
#	Line 274 | Line 266 | abstract class Striped64 extends Number
266		else if (casBase(v = base, fn(v, x)))
267		break;                          // Fall back on using base
268		}
277	–	hc.code = h;                            // Record index for next time
269		}
270
271
272		/**
273	<	* Set base and all cells to the given value
273	>	* Sets base and all cells to the given value.
274		*/
275		final void internalReset(long initialValue) {
276		Cell[] as = cells;
#	Line 293 | Line 284 | abstract class Striped64 extends Number
284		}
285		}
286		}
287	<
287	>
288		// Unsafe mechanics
289		private static final sun.misc.Unsafe UNSAFE;
290		private static final long baseOffset;
#	Line 321 | Line 312 | abstract class Striped64 extends Number
312		private static sun.misc.Unsafe getUnsafe() {
313		try {
314		return sun.misc.Unsafe.getUnsafe();
315	<	} catch (SecurityException se) {
316	<	try {
317	<	return java.security.AccessController.doPrivileged
318	<	(new java.security
319	<	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
320	<	public sun.misc.Unsafe run() throws Exception {
321	<	java.lang.reflect.Field f = sun.misc
322	<	.Unsafe.class.getDeclaredField("theUnsafe");
323	<	f.setAccessible(true);
324	<	return (sun.misc.Unsafe) f.get(null);
325	<	}});
326	<	} catch (java.security.PrivilegedActionException e) {
327	<	throw new RuntimeException("Could not initialize intrinsics",
328	<	e.getCause());
329	<	}
315	>	} catch (SecurityException tryReflectionInstead) {}
316	>	try {
317	>	return java.security.AccessController.doPrivileged
318	>	(new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
319	>	public sun.misc.Unsafe run() throws Exception {
320	>	Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
321	>	for (java.lang.reflect.Field f : k.getDeclaredFields()) {
322	>	f.setAccessible(true);
323	>	Object x = f.get(null);
324	>	if (k.isInstance(x))
325	>	return k.cast(x);
326	>	}
327	>	throw new NoSuchFieldError("the Unsafe");
328	>	}});
329	>	} catch (java.security.PrivilegedActionException e) {
330	>	throw new RuntimeException("Could not initialize intrinsics",
331	>	e.getCause());
332		}
333		}
334	<
342	<	}
334	>	}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines