--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2013/08/09 18:43:44 1.114 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2015/02/26 06:53:34 1.122 @@ -15,7 +15,6 @@ import java.lang.reflect.Type; import java.util.AbstractMap; import java.util.Arrays; import java.util.Collection; -import java.util.Comparator; import java.util.ConcurrentModificationException; import java.util.Enumeration; import java.util.HashMap; @@ -276,6 +275,7 @@ public class ConcurrentHashMapV8 ex /** Interface describing a function mapping two ints to an int */ public interface IntByIntToInt { int apply(int a, int b); } + /* * Overview: * @@ -381,14 +381,15 @@ public class ConcurrentHashMapV8 ex * The table is resized when occupancy exceeds a percentage * threshold (nominally, 0.75, but see below). Any thread * noticing an overfull bin may assist in resizing after the - * initiating thread allocates and sets up the replacement - * array. However, rather than stalling, these other threads may - * proceed with insertions etc. The use of TreeBins shields us - * from the worst case effects of overfilling while resizes are in + * initiating thread allocates and sets up the replacement array. + * However, rather than stalling, these other threads may proceed + * with insertions etc. The use of TreeBins shields us from the + * worst case effects of overfilling while resizes are in * progress. Resizing proceeds by transferring bins, one by one, - * from the table to the next table. To enable concurrency, the - * next table must be (incrementally) prefilled with place-holders - * serving as reverse forwarders to the old table. Because we are + * from the table to the next table. However, threads claim small + * blocks of indices to transfer (via field transferIndex) before + * doing so, reducing contention. A generation stamp in field + * sizeCtl ensures that resizings do not overlap. Because we are * using power-of-two expansion, the elements from each bin must * either stay at same index, or move with a power of two * offset. We eliminate unnecessary node creation by catching @@ -409,13 +410,19 @@ public class ConcurrentHashMapV8 ex * locks, average aggregate waits become shorter as resizing * progresses. The transfer operation must also ensure that all * accessible bins in both the old and new table are usable by any - * traversal. This is arranged by proceeding from the last bin - * (table.length - 1) up towards the first. Upon seeing a - * forwarding node, traversals (see class Traverser) arrange to - * move to the new table without revisiting nodes. However, to - * ensure that no intervening nodes are skipped, bin splitting can - * only begin after the associated reverse-forwarders are in - * place. + * traversal. This is arranged in part by proceeding from the + * last bin (table.length - 1) up towards the first. Upon seeing + * a forwarding node, traversals (see class Traverser) arrange to + * move to the new table without revisiting nodes. To ensure that + * no intervening nodes are skipped even when moved out of order, + * a stack (see class TableStack) is created on first encounter of + * a forwarding node during a traversal, to maintain its place if + * later processing the current table. The need for these + * save/restore mechanics is relatively rare, but when one + * forwarding node is encountered, typically many more will be. + * So Traversers use a simple caching scheme to avoid creating so + * many new TableStack nodes. (Thanks to Peter Levart for + * suggesting use of a stack here.) * * The traversal scheme also applies to partial traversals of * ranges of bins (via an alternate Traverser constructor) @@ -572,6 +579,23 @@ public class ConcurrentHashMapV8 ex */ private static final int MIN_TRANSFER_STRIDE = 16; + /** + * The number of bits used for generation stamp in sizeCtl. + * Must be at least 6 for 32bit arrays. + */ + private static int RESIZE_STAMP_BITS = 16; + + /** + * The maximum number of threads that can help resize. + * Must fit in 32 - RESIZE_STAMP_BITS bits. + */ + private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; + + /** + * The bit shift for recording size stamp in sizeCtl. + */ + private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; + /* * Encodings for Node hash fields. See above for explanation. */ @@ -729,7 +753,7 @@ public class ConcurrentHashMapV8 ex * errors by users, these checks must operate on local variables, * which accounts for some odd-looking inline assignments below. * Note that calls to setTabAt always occur within locked regions, - * and so in principle require only release ordering, not need + * and so in principle require only release ordering, not * full volatile semantics, but are currently coded as volatile * writes to be conservative. */ @@ -784,11 +808,6 @@ public class ConcurrentHashMapV8 ex private transient volatile int transferIndex; /** - * The least available table index to split while resizing. - */ - private transient volatile int transferOrigin; - - /** * Spinlock (locked via CAS) used when resizing and/or creating CounterCells. */ private transient volatile int cellsBusy; @@ -1446,8 +1465,8 @@ public class ConcurrentHashMapV8 ex int sz = (int)size; n = tableSizeFor(sz + (sz >>> 1) + 1); } - @SuppressWarnings({"rawtypes","unchecked"}) - Node[] tab = (Node[])new Node[n]; + @SuppressWarnings("unchecked") + Node[] tab = (Node[])new Node[n]; int mask = n - 1; long added = 0L; while (p != null) { @@ -2194,6 +2213,14 @@ public class ConcurrentHashMapV8 ex /* ---------------- Table Initialization and Resizing -------------- */ /** + * Returns the stamp bits for resizing a table of size n. + * Must be negative when shifted left by RESIZE_STAMP_SHIFT. + */ + static final int resizeStamp(int n) { + return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); + } + + /** * Initializes table, using the size recorded in sizeCtl. */ private final Node[] initTable() { @@ -2205,8 +2232,8 @@ public class ConcurrentHashMapV8 ex try { if ((tab = table) == null || tab.length == 0) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; - @SuppressWarnings({"rawtypes","unchecked"}) - Node[] nt = (Node[])new Node[n]; + @SuppressWarnings("unchecked") + Node[] nt = (Node[])new Node[n]; table = tab = nt; sc = n - (n >>> 2); } @@ -2248,17 +2275,20 @@ public class ConcurrentHashMapV8 ex s = sumCount(); } if (check >= 0) { - Node[] tab, nt; int sc; + Node[] tab, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) != null && - tab.length < MAXIMUM_CAPACITY) { + (n = tab.length) < MAXIMUM_CAPACITY) { + int rs = resizeStamp(n); if (sc < 0) { - if (sc == -1 || transferIndex <= transferOrigin || - (nt = nextTable) == null) + if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || + sc == rs + MAX_RESIZERS || (nt = nextTable) == null || + transferIndex <= 0) break; - if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) + if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } - else if (U.compareAndSwapInt(this, SIZECTL, sc, -2)) + else if (U.compareAndSwapInt(this, SIZECTL, sc, + (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); } @@ -2270,12 +2300,19 @@ public class ConcurrentHashMapV8 ex */ final Node[] helpTransfer(Node[] tab, Node f) { Node[] nextTab; int sc; - if ((f instanceof ForwardingNode) && + if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode)f).nextTable) != null) { - if (nextTab == nextTable && tab == table && - transferIndex > transferOrigin && (sc = sizeCtl) < -1 && - U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) - transfer(tab, nextTab); + int rs = resizeStamp(tab.length); + while (nextTab == nextTable && table == tab && + (sc = sizeCtl) < 0) { + if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || + sc == rs + MAX_RESIZERS || transferIndex <= 0) + break; + if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { + transfer(tab, nextTab); + break; + } + } return nextTab; } return table; @@ -2297,8 +2334,8 @@ public class ConcurrentHashMapV8 ex if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if (table == tab) { - @SuppressWarnings({"rawtypes","unchecked"}) - Node[] nt = (Node[])new Node[n]; + @SuppressWarnings("unchecked") + Node[] nt = (Node[])new Node[n]; table = nt; sc = n - (n >>> 2); } @@ -2309,9 +2346,21 @@ public class ConcurrentHashMapV8 ex } else if (c <= sc || n >= MAXIMUM_CAPACITY) break; - else if (tab == table && - U.compareAndSwapInt(this, SIZECTL, sc, -2)) - transfer(tab, null); + else if (tab == table) { + int rs = resizeStamp(n); + if (sc < 0) { + Node[] nt; + if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || + sc == rs + MAX_RESIZERS || (nt = nextTable) == null || + transferIndex <= 0) + break; + if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) + transfer(tab, nt); + } + else if (U.compareAndSwapInt(this, SIZECTL, sc, + (rs << RESIZE_STAMP_SHIFT) + 2)) + transfer(tab, null); + } } } @@ -2325,36 +2374,27 @@ public class ConcurrentHashMapV8 ex stride = MIN_TRANSFER_STRIDE; // subdivide range if (nextTab == null) { // initiating try { - @SuppressWarnings({"rawtypes","unchecked"}) - Node[] nt = (Node[])new Node[n << 1]; + @SuppressWarnings("unchecked") + Node[] nt = (Node[])new Node[n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; - transferOrigin = n; transferIndex = n; - ForwardingNode rev = new ForwardingNode(tab); - for (int k = n; k > 0;) { // progressively reveal ready slots - int nextk = (k > stride) ? k - stride : 0; - for (int m = nextk; m < k; ++m) - nextTab[m] = rev; - for (int m = n + nextk; m < n + k; ++m) - nextTab[m] = rev; - U.putOrderedInt(this, TRANSFERORIGIN, k = nextk); - } } int nextn = nextTab.length; ForwardingNode fwd = new ForwardingNode(nextTab); boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { - int nextIndex, nextBound, fh; Node f; + Node f; int fh; while (advance) { + int nextIndex, nextBound; if (--i >= bound || finishing) advance = false; - else if ((nextIndex = transferIndex) <= transferOrigin) { + else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } @@ -2368,29 +2408,22 @@ public class ConcurrentHashMapV8 ex } } if (i < 0 || i >= n || i + n >= nextn) { + int sc; if (finishing) { nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); return; } - for (int sc;;) { - if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) { - if (sc != -1) - return; - finishing = advance = true; - i = n; // recheck before commit - break; - } - } - } - else if ((f = tabAt(tab, i)) == null) { - if (casTabAt(tab, i, null, fwd)) { - setTabAt(nextTab, i, null); - setTabAt(nextTab, i + n, null); - advance = true; + if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { + if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) + return; + finishing = advance = true; + i = n; // recheck before commit } } + else if ((f = tabAt(tab, i)) == null) + advance = casTabAt(tab, i, null, fwd); else if ((fh = f.hash) == MOVED) advance = true; // already processed else { @@ -2477,11 +2510,8 @@ public class ConcurrentHashMapV8 ex private final void treeifyBin(Node[] tab, int index) { Node b; int n, sc; if (tab != null) { - if ((n = tab.length) < MIN_TREEIFY_CAPACITY) { - if (tab == table && (sc = sizeCtl) >= 0 && - U.compareAndSwapInt(this, SIZECTL, sc, -2)) - transfer(tab, null); - } + if ((n = tab.length) < MIN_TREEIFY_CAPACITY) + tryPresize(n << 1); else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { synchronized (b) { if (tabAt(tab, index) == b) { @@ -2548,7 +2578,7 @@ public class ConcurrentHashMapV8 ex final TreeNode findTreeNode(int h, Object k, Class kc) { if (k != null) { TreeNode p = this; - do { + do { int ph, dir; K pk; TreeNode q; TreeNode pl = p.left, pr = p.right; if ((ph = p.hash) > h) @@ -2679,7 +2709,7 @@ public class ConcurrentHashMapV8 ex private final void contendedLock() { boolean waiting = false; for (int s;;) { - if (((s = lockState) & WRITER) == 0) { + if (((s = lockState) & ~WAITER) == 0) { if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) { if (waiting) waiter = null; @@ -2702,14 +2732,15 @@ public class ConcurrentHashMapV8 ex * using tree comparisons from root, but continues linear * search when lock not available. */ -final Node find(int h, Object k) { + final Node find(int h, Object k) { if (k != null) { - for (Node e = first; e != null; e = e.next) { + for (Node e = first; e != null; ) { int s; K ek; if (((s = lockState) & (WAITER|WRITER)) != 0) { if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; + e = e.next; } else if (U.compareAndSwapInt(this, LOCKSTATE, s, s + READER)) { @@ -2996,7 +3027,7 @@ final Node find(int h, Object k) { static TreeNode balanceDeletion(TreeNode root, TreeNode x) { - for (TreeNode xp, xpl, xpr;;) { + for (TreeNode xp, xpl, xpr;;) { if (x == null || x == root) return root; else if ((xp = x.parent) == null) { @@ -3128,6 +3159,18 @@ final Node find(int h, Object k) { /* ----------------Table Traversal -------------- */ /** + * Records the table, its length, and current traversal index for a + * traverser that must process a region of a forwarded table before + * proceeding with current table. + */ + static final class TableStack { + int length; + int index; + Node[] tab; + TableStack next; + } + + /** * Encapsulates traversal for methods such as containsValue; also * serves as a base class for other iterators and spliterators. * @@ -3151,6 +3194,7 @@ final Node find(int h, Object k) { static class Traverser { Node[] tab; // current table; updated if resized Node next; // the next entry to use + TableStack stack, spare; // to save/restore on ForwardingNodes int index; // index of bin to use next int baseIndex; // current index of initial table int baseLimit; // index bound for initial table @@ -3172,16 +3216,17 @@ final Node find(int h, Object k) { if ((e = next) != null) e = e.next; for (;;) { - Node[] t; int i, n; K ek; // must use locals in checks + Node[] t; int i, n; // must use locals in checks if (e != null) return next = e; if (baseIndex >= baseLimit || (t = tab) == null || (n = t.length) <= (i = index) || i < 0) return next = null; - if ((e = tabAt(t, index)) != null && e.hash < 0) { + if ((e = tabAt(t, i)) != null && e.hash < 0) { if (e instanceof ForwardingNode) { tab = ((ForwardingNode)e).nextTable; e = null; + pushState(t, i, n); continue; } else if (e instanceof TreeBin) @@ -3189,9 +3234,48 @@ final Node find(int h, Object k) { else e = null; } - if ((index += baseSize) >= n) - index = ++baseIndex; // visit upper slots if present + if (stack != null) + recoverState(n); + else if ((index = i + baseSize) >= n) + index = ++baseIndex; // visit upper slots if present + } + } + + /** + * Saves traversal state upon encountering a forwarding node. + */ + private void pushState(Node[] t, int i, int n) { + TableStack s = spare; // reuse if possible + if (s != null) + spare = s.next; + else + s = new TableStack(); + s.tab = t; + s.length = n; + s.index = i; + s.next = stack; + stack = s; + } + + /** + * Possibly pops traversal state. + * + * @param n length of current table + */ + private void recoverState(int n) { + TableStack s; int len; + while ((s = stack) != null && (index += (len = s.length)) >= n) { + n = len; + index = s.index; + tab = s.tab; + s.tab = null; + TableStack next = s.next; + s.next = spare; // save for reuse + stack = next; + spare = s; } + if (s == null && (index += baseSize) >= n) + index = ++baseIndex; } } @@ -6159,7 +6243,6 @@ final Node find(int h, Object k) { private static final sun.misc.Unsafe U; private static final long SIZECTL; private static final long TRANSFERINDEX; - private static final long TRANSFERORIGIN; private static final long BASECOUNT; private static final long CELLSBUSY; private static final long CELLVALUE; @@ -6174,8 +6257,6 @@ final Node find(int h, Object k) { (k.getDeclaredField("sizeCtl")); TRANSFERINDEX = U.objectFieldOffset (k.getDeclaredField("transferIndex")); - TRANSFERORIGIN = U.objectFieldOffset - (k.getDeclaredField("transferOrigin")); BASECOUNT = U.objectFieldOffset (k.getDeclaredField("baseCount")); CELLSBUSY = U.objectFieldOffset