--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2011/08/28 19:08:07 1.1 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2011/08/30 18:31:25 1.11 @@ -54,7 +54,7 @@ import java.io.Serializable; *

Resizing this or any other kind of hash table is a relatively * slow operation, so, when possible, it is a good idea to provide * estimates of expected table sizes in constructors. Also, for - * compatability with previous versions of this class, constructors + * compatibility with previous versions of this class, constructors * may optionally specify an expected {@code concurrencyLevel} as an * additional hint for internal sizing. * @@ -83,8 +83,8 @@ public class ConcurrentHashMapV8 /** * A function computing a mapping from the given key to a value, - * or null if there is no mapping. This is a - * place-holder for an upcoming JDK8 interface. + * or {@code null} if there is no mapping. This is a place-holder + * for an upcoming JDK8 interface. */ public static interface MappingFunction { /** @@ -125,8 +125,8 @@ public class ConcurrentHashMapV8 * within bins are always accurately traversable under volatile * reads, so long as lookups check hash code and non-nullness of * key and value before checking key equality. (All valid hash - * codes are nonnegative. Negative values are served for special - * nodes.) + * codes are nonnegative. Negative values are reserved for special + * forwarding nodes; see below.) * * A bin may be locked during update (insert, delete, and replace) * operations. We do not want to waste the space required to @@ -139,18 +139,22 @@ public class ConcurrentHashMapV8 * that it is still the first node, and retry if not. (Because new * nodes are always appended to lists, once a node is first in a * bin, it remains first until deleted or the bin becomes - * invalidated.) However, update operations can and usually do + * invalidated.) However, update operations can and sometimes do * still traverse the bin until the point of update, which helps * reduce cache misses on retries. This is a converse of sorts to * the lazy locking technique described by Herlihy & Shavit. If * there is no existing node during a put operation, then one can * be CAS'ed in (without need for lock except in computeIfAbsent); * the CAS serves as validation. This is on average the most - * common case for put operations. The expected number of locks - * covering different elements (i.e., bins with 2 or more nodes) - * is approximately 10% at steady state under default settings. - * Lock contention probability for two threads accessing arbitrary - * distinct elements is thus less than 1% even for small tables. + * common case for put operations -- under random hash codes, the + * distribution of nodes in bins follows a Poisson distribution + * (see http://en.wikipedia.org/wiki/Poisson_distribution) with a + * parameter of 0.5 on average under the default loadFactor of + * 0.75. The expected number of locks covering different elements + * (i.e., bins with 2 or more nodes) is approximately 10% at + * steady state under default settings. Lock contention + * probability for two threads accessing arbitrary distinct + * elements is, roughly, 1 / (8 * #elements). * * The table is resized when occupancy exceeds a threshold. Only * a single thread performs the resize (using field "resizing", to @@ -172,27 +176,28 @@ public class ConcurrentHashMapV8 * complexity of access and iteration schemes that could admit * out-of-order or concurrent bin transfers. * - * (While not yet implemented, a similar traversal scheme can - * apply to partial traversals during partitioned aggregate - * operations. Also, read-only operations give up if ever - * forwarded to a null table, which provides support for - * shutdown-style clearing, which is also not currently - * implemented.) + * A similar traversal scheme (not yet implemented) can apply to + * partial traversals during partitioned aggregate operations. + * Also, read-only operations give up if ever forwarded to a null + * table, which provides support for shutdown-style clearing, + * which is also not currently implemented. * * The element count is maintained using a LongAdder, which avoids * contention on updates but can encounter cache thrashing if read * too frequently during concurrent updates. To avoid reading so - * often, resizing is attempted only upon adding to a bin already - * holding two or more nodes. Under the default threshold (0.75), - * and uniform hash distributions, the probability of this + * often, resizing is normally attempted only upon adding to a bin + * already holding two or more nodes. Under the default threshold + * (0.75), and uniform hash distributions, the probability of this * occurring at threshold is around 13%, meaning that only about 1 * in 8 puts check threshold (and after resizing, many fewer do - * so). To increase the probablity that a resize occurs soon - * enough, we offset the threshold (see THRESHOLD_OFFSET) by the - * expected number of puts between checks. This is currently set - * to 8, in accord with the default load factor. In practice, this - * is rarely overridden, and in any case is close enough to other - * plausible values not to waste dynamic probablity computation + * so). But this approximation has high variance for small table + * sizes, so we check on any collision for sizes <= 64. Further, + * to increase the probability that a resize occurs soon enough, we + * offset the threshold (see THRESHOLD_OFFSET) by the expected + * number of puts between checks. This is currently set to 8, in + * accord with the default load factor. In practice, this is + * rarely overridden, and in any case is close enough to other + * plausible values not to waste dynamic probability computation * for more precision. */ @@ -212,7 +217,7 @@ public class ConcurrentHashMapV8 /** * The default initial table capacity. Must be a power of 2, at - * least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY + * least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY. */ static final int DEFAULT_CAPACITY = 16; @@ -229,7 +234,7 @@ public class ConcurrentHashMapV8 static final int DEFAULT_CONCURRENCY_LEVEL = 16; /** - * The count value to offset thesholds to compensate for checking + * The count value to offset thresholds to compensate for checking * for resizing only when inserting into bins with two or more * elements. See above for explanation. */ @@ -266,7 +271,7 @@ public class ConcurrentHashMapV8 transient Set> entrySet; transient Collection values; - /** For serialization compatability. Null unless serialized; see below */ + /** For serialization compatibility. Null unless serialized; see below */ Segment[] segments; /** @@ -304,14 +309,15 @@ public class ConcurrentHashMapV8 } /* - * Volatile access nethods are used for table elements as well as + * Volatile access methods are used for table elements as well as * elements of in-progress next table while resizing. Uses in * access and update methods are null checked by callers, and * implicitly bounds-checked, relying on the invariants that tab * arrays have non-zero size, and all indices are masked with * (tab.length - 1) which is never negative and always less than - * length. The only other usage is in HashIterator.advance, which - * performs explicit checks. + * length. The "relaxed" non-volatile forms are used only during + * table initialization. The only other usage is in + * HashIterator.advance, which performs explicit checks. */ static final Node tabAt(Node[] tab, int i) { // used in HashIterator @@ -326,9 +332,17 @@ public class ConcurrentHashMapV8 UNSAFE.putObjectVolatile(tab, ((long)i< if (ev != null && ek != null && (k == ek || k.equals(ek))) return ev; } - if (eh < 0) { // bin was moved during resize + else if (eh < 0) { // bin was moved during resize tab = (Node[])e.key; continue retry; } @@ -352,20 +366,18 @@ public class ConcurrentHashMapV8 return null; } - /** Implements put and putIfAbsent **/ + + /** Implementation for put and putIfAbsent */ private final Object internalPut(Object k, Object v, boolean replace) { int h = spread(k.hashCode()); Object oldVal = null; // the previous value or null if none - Node node = null; // the node created if absent Node[] tab = table; for (;;) { Node e; int i; if (tab == null) tab = grow(0); else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) { - if (node == null) - node = new Node(h, k, v, null); - if (casTabAt(tab, i, null, node)) + if (casTabAt(tab, i, null, new Node(h, k, v, null))) break; } else if (e.hash < 0) @@ -373,33 +385,27 @@ public class ConcurrentHashMapV8 else { boolean validated = false; boolean checkSize = false; - synchronized(e) { - Node first = e; - for (;;) { - Object ek, ev; - if ((ev = e.val) == null) - break; - if (e.hash == h && (ek = e.key) != null && - (k == ek || k.equals(ek))) { - if (tabAt(tab, i) == first) { - validated = true; + synchronized (e) { + if (tabAt(tab, i) == e) { + validated = true; + for (Node first = e;;) { + Object ek, ev; + if (e.hash == h && + (ek = e.key) != null && + (ev = e.val) != null && + (k == ek || k.equals(ek))) { oldVal = ev; if (replace) e.val = v; + break; } - break; - } - Node last = e; - if ((e = e.next) == null) { - if (tabAt(tab, i) == first) { - validated = true; - if (node == null) - node = new Node(h, k, v, null); - last.next = node; - if (last != first) + Node last = e; + if ((e = e.next) == null) { + last.next = new Node(h, k, v, null); + if (last != first || tab.length <= 64) checkSize = true; + break; } - break; } } } @@ -417,9 +423,9 @@ public class ConcurrentHashMapV8 } /** - * Covers the four public remove/replace methods: Replaces node - * value with v, conditional upon match of cv if non-null. If - * resulting value is null, delete. + * Implementation for the four public remove/replace methods: + * Replaces node value with v, conditional upon match of cv if + * non-null. If resulting value is null, delete. */ private final Object internalReplace(Object k, Object v, Object cv) { int h = spread(k.hashCode()); @@ -433,17 +439,16 @@ public class ConcurrentHashMapV8 else { boolean validated = false; boolean deleted = false; - synchronized(e) { - Node pred = null; - Node first = e; - for (;;) { - Object ek, ev; - if ((ev = e.val) == null) - break; - if (e.hash == h && (ek = e.key) != null && - (k == ek || k.equals(ek))) { - if (tabAt(tab, i) == first) { - validated = true; + synchronized (e) { + if (tabAt(tab, i) == e) { + validated = true; + Node pred = null; + do { + Object ek, ev; + if (e.hash == h && + (ek = e.key) != null && + (ev = e.val) != null && + (k == ek || k.equals(ek))) { if (cv == null || cv == ev || cv.equals(ev)) { oldVal = ev; if ((e.val = v) == null) { @@ -455,15 +460,10 @@ public class ConcurrentHashMapV8 setTabAt(tab, i, en); } } + break; } - break; - } - pred = e; - if ((e = e.next) == null) { - if (tabAt(tab, i) == first) - validated = true; - break; - } + pred = e; + } while ((e = e.next) != null); } } if (validated) { @@ -476,23 +476,23 @@ public class ConcurrentHashMapV8 return oldVal; } - /** Implements computeIfAbsent */ + /** Implementation for computeIfAbsent and compute */ @SuppressWarnings("unchecked") - private final V computeVal(K k, MappingFunction f) { + private final V internalCompute(K k, + MappingFunction f, + boolean replace) { int h = spread(k.hashCode()); V val = null; - Node node = null; boolean added = false; - boolean validated = false; Node[] tab = table; - do { + for(;;) { Node e; int i; if (tab == null) tab = grow(0); else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) { - if (node == null) - node = new Node(h, k, null, null); - synchronized(node) { + Node node = new Node(h, k, null, null); + boolean validated = false; + synchronized (node) { if (casTabAt(tab, i, null, node)) { validated = true; try { @@ -507,49 +507,51 @@ public class ConcurrentHashMapV8 } } } + if (validated) + break; } else if (e.hash < 0) tab = (Node[])e.key; + else if (Thread.holdsLock(e)) + throw new IllegalStateException("Recursive map computation"); else { + boolean validated = false; boolean checkSize = false; - synchronized(e) { - Node first = e; - for (;;) { - Object ek, ev; - if ((ev = e.val) == null) - break; - if (e.hash == h && (ek = e.key) != null && - (k == ek || k.equals(ek))) { - if (tabAt(tab, i) == first) { - validated = true; + synchronized (e) { + if (tabAt(tab, i) == e) { + validated = true; + for (Node first = e;;) { + Object ek, ev, fv; + if (e.hash == h && + (ek = e.key) != null && + (ev = e.val) != null && + (k == ek || k.equals(ek))) { + if (replace && (fv = f.map(k)) != null) + ev = e.val = fv; val = (V)ev; + break; } - break; - } - Node last = e; - if ((e = e.next) == null) { - if (tabAt(tab, i) == first) { - validated = true; + Node last = e; + if ((e = e.next) == null) { if ((val = f.map(k)) != null) { - if (node == null) - node = new Node(h, k, val, null); - else - node.val = val; - last.next = node; - if (last != first) - checkSize = true; + last.next = new Node(h, k, val, null); added = true; + if (last != first || tab.length <= 64) + checkSize = true; } + break; } - break; } } } - if (checkSize && tab.length < MAXIMUM_CAPACITY && - resizing == 0 && counter.sum() >= threshold) - grow(0); + if (validated) { + if (checkSize && tab.length < MAXIMUM_CAPACITY && + resizing == 0 && counter.sum() >= threshold) + grow(0); + break; + } } - } while (!validated); + } if (added) counter.increment(); return val; @@ -582,26 +584,26 @@ public class ConcurrentHashMapV8 break; } else { + int idx = e.hash & mask; boolean validated = false; - synchronized(e) { - int idx = e.hash & mask; - Node lastRun = e; - for (Node p = e.next; p != null; p = p.next) { - int j = p.hash & mask; - if (j != idx) { - idx = j; - lastRun = p; - } - } + synchronized (e) { if (tabAt(tab, i) == e) { validated = true; - setTabAt(nextTab, idx, lastRun); + Node lastRun = e; + for (Node p = e.next; p != null; p = p.next) { + int j = p.hash & mask; + if (j != idx) { + idx = j; + lastRun = p; + } + } + relaxedSetTabAt(nextTab, idx, lastRun); for (Node p = e; p != lastRun; p = p.next) { int h = p.hash; int j = h & mask; - Object pk = p.key, pv = p.val; - Node r = tabAt(nextTab, j); - setTabAt(nextTab, j, new Node(h, pk, pv, r)); + Node r = relaxedTabAt(nextTab, j); + relaxedSetTabAt(nextTab, j, + new Node(h, p.key, p.val, r)); } setTabAt(tab, i, fwd); } @@ -623,13 +625,13 @@ public class ConcurrentHashMapV8 * @return current table */ private final Node[] grow(int sizeHint) { - Node[] tab; if (resizing == 0 && UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) { try { for (;;) { int cap, n; - if ((tab = table) == null) { + Node[] tab = table; + if (tab == null) { int c = initCap; if (c < sizeHint) c = sizeHint; @@ -653,28 +655,28 @@ public class ConcurrentHashMapV8 if (tab != null) transfer(tab, nextTab); table = nextTab; - if (tab == null || counter.sum() < threshold) { - tab = nextTab; + if (tab == null || cap >= MAXIMUM_CAPACITY || + ((sizeHint > 0) ? cap >= sizeHint : + counter.sum() < threshold)) break; - } } } finally { resizing = 0; } } - else if ((tab = table) == null) + else if (table == null) Thread.yield(); // lost initialization race; just spin - return tab; + return table; } /** - * Implements putAll and constructor with Map argument. Tries to - * first override initial capacity or grow (once) based on map - * size to pre-allocate table space. + * Implementation for putAll and constructor with Map + * argument. Tries to first override initial capacity or grow + * based on map size to pre-allocate table space. */ private final void internalPutAll(Map m) { int s = m.size(); - grow((s >= (MAXIMUM_CAPACITY >>> 1))? s : s + (s >>> 1)); + grow((s >= (MAXIMUM_CAPACITY >>> 1)) ? s : s + (s >>> 1)); for (Map.Entry e : m.entrySet()) { Object k = e.getKey(); Object v = e.getValue(); @@ -685,10 +687,10 @@ public class ConcurrentHashMapV8 } /** - * Implements clear. Steps through each bin, removing all nodes. + * Implementation for clear. Steps through each bin, removing all nodes. */ private final void internalClear() { - long delta = 0L; // negative of number of deletions + long deletions = 0L; int i = 0; Node[] tab = table; while (tab != null && i < tab.length) { @@ -699,23 +701,29 @@ public class ConcurrentHashMapV8 tab = (Node[])e.key; else { boolean validated = false; - synchronized(e) { + synchronized (e) { if (tabAt(tab, i) == e) { validated = true; do { if (e.val != null) { e.val = null; - --delta; + ++deletions; } } while ((e = e.next) != null); setTabAt(tab, i, null); } } - if (validated) + if (validated) { ++i; + if (deletions > THRESHOLD_OFFSET) { // bound lag in counts + counter.add(-deletions); + deletions = 0L; + } + } } } - counter.add(delta); + if (deletions != 0L) + counter.add(-deletions); } /** @@ -894,7 +902,7 @@ public class ConcurrentHashMapV8 * nonpositive. */ public ConcurrentHashMapV8(int initialCapacity, - float loadFactor, int concurrencyLevel) { + float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); this.initCap = initialCapacity; @@ -962,7 +970,7 @@ public class ConcurrentHashMapV8 * @return {@code true} if this map contains no key-value mappings */ public boolean isEmpty() { - return counter.sum() == 0L; + return counter.sum() <= 0L; // ignore transient negative values } /** @@ -974,7 +982,7 @@ public class ConcurrentHashMapV8 */ public int size() { long n = counter.sum(); - return n >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)n; + return ((n >>> 31) == 0) ? (int)n : (n < 0L) ? 0 : Integer.MAX_VALUE; } /** @@ -1103,18 +1111,21 @@ public class ConcurrentHashMapV8 * return map.get(key); * value = mappingFunction.map(key); * if (value != null) - * return map.put(key, value); - * else - * return null; + * map.put(key, value); + * return value; * * * except that the action is performed atomically. Some attempted - * operations on this map by other threads may be blocked while - * computation is in progress. Because this function is invoked - * within atomicity control, the computation should be short and - * simple, and must not attempt to update any other mappings of - * this Map. The most common usage is to construct a new object - * serving as an initial mapped value, or memoized result. + * update operations on this map by other threads may be blocked + * while computation is in progress, so the computation should be + * short and simple, and must not attempt to update any other + * mappings of this Map. The most appropriate usage is to + * construct a new object serving as an initial mapped value, or + * memoized result, as in: + * 

{@code
+     * map.computeIfAbsent(key, new MappingFunction() {
+     *   public V map(K k) { return new Value(f(k)); }};
+     * }
* * @param key key with which the specified value is to be associated * @param mappingFunction the function to compute a value @@ -1123,13 +1134,55 @@ public class ConcurrentHashMapV8 * returned {@code null}. * @throws NullPointerException if the specified key or mappingFunction * is null, + * @throws IllegalStateException if the computation detectably + * attempts a recursive update to this map that would + * otherwise never complete. * @throws RuntimeException or Error if the mappingFunction does so, * in which case the mapping is left unestablished. */ public V computeIfAbsent(K key, MappingFunction mappingFunction) { if (key == null || mappingFunction == null) throw new NullPointerException(); - return computeVal(key, mappingFunction); + return internalCompute(key, mappingFunction, false); + } + + /** + * Computes the value associated with the given key using the given + * mappingFunction, and if non-null, enters it into the map. This + * is equivalent to + * + * 
+     *   value = mappingFunction.map(key);
+     *   if (value != null)
+     *      map.put(key, value);
+     *   else
+     *      value = map.get(key);
+     *   return value;
+     *
+ * + * except that the action is performed atomically. Some attempted + * update operations on this map by other threads may be blocked + * while computation is in progress, so the computation should be + * short and simple, and must not attempt to update any other + * mappings of this Map. + * + * @param key key with which the specified value is to be associated + * @param mappingFunction the function to compute a value + * @return the current value associated with + * the specified key, or {@code null} if the computation + * returned {@code null} and the value was not otherwise present. + * @throws NullPointerException if the specified key or mappingFunction + * is null, + * @throws IllegalStateException if the computation detectably + * attempts a recursive update to this map that would + * otherwise never complete. + * @throws RuntimeException or Error if the mappingFunction does so, + * in which case the mapping is unchanged. + */ + public V compute(K key, MappingFunction mappingFunction) { + if (key == null || mappingFunction == null) + throw new NullPointerException(); + return internalCompute(key, mappingFunction, true); } /** @@ -1145,7 +1198,7 @@ public class ConcurrentHashMapV8 public V remove(Object key) { if (key == null) throw new NullPointerException(); - return (V)internalReplace(key, null, null); + return (V)internalReplace(key, null, null); } /** @@ -1169,7 +1222,7 @@ public class ConcurrentHashMapV8 public boolean replace(K key, V oldValue, V newValue) { if (key == null || oldValue == null || newValue == null) throw new NullPointerException(); - return internalReplace(key, newValue, oldValue) != null; + return internalReplace(key, newValue, oldValue) != null; } /** @@ -1183,7 +1236,7 @@ public class ConcurrentHashMapV8 public V replace(K key, V value) { if (key == null || value == null) throw new NullPointerException(); - return (V)internalReplace(key, value, null); + return (V)internalReplace(key, value, null); } /** @@ -1277,21 +1330,40 @@ public class ConcurrentHashMapV8 } /** - * {@inheritDoc} + * Returns the hash code value for this {@link Map}, i.e., + * the sum of, for each key-value pair in the map, + * {@code key.hashCode() ^ value.hashCode()}. + * + * @return the hash code value for this map */ public int hashCode() { return new HashIterator().mapHashCode(); } /** - * {@inheritDoc} + * Returns a string representation of this map. The string + * representation consists of a list of key-value mappings (in no + * particular order) enclosed in braces ("{@code {}}"). Adjacent + * mappings are separated by the characters {@code ", "} (comma + * and space). Each key-value mapping is rendered as the key + * followed by an equals sign ("{@code =}") followed by the + * associated value. + * + * @return a string representation of this map */ public String toString() { return new HashIterator().mapToString(); } /** - * {@inheritDoc} + * Compares the specified object with this map for equality. + * Returns {@code true} if the given object is a map with the same + * mappings as this map. This operation may return misleading + * results if either map is concurrently modified during execution + * of this method. + * + * @param o object to be compared for equality with this map + * @return {@code true} if the specified object is equal to this map */ public boolean equals(Object o) { if (o == this) @@ -1471,8 +1543,7 @@ public class ConcurrentHashMapV8 } /** - * Reconstitutes the instance from a - * stream (i.e., deserializes it). + * Reconstitutes the instance from a stream (that is, deserializes it). * @param s the stream */ @SuppressWarnings("unchecked")