--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2013/08/23 20:12:21 1.115 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2013/09/11 14:53:38 1.116 @@ -276,6 +276,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,27 +382,26 @@ 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 - * 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 - * cases where old nodes can be reused because their next fields - * won't change. On average, only about one-sixth of them need - * cloning when a table doubles. The nodes they replace will be - * garbage collectable as soon as they are no longer referenced by - * any reader thread that may be in the midst of concurrently - * traversing table. Upon transfer, the old table bin contains - * only a special forwarding node (with hash field "MOVED") that - * contains the next table as its key. On encountering a - * forwarding node, access and update operations restart, using - * the new table. + * from the table to the next table. However, threads claim small + * blocks of indices to transfer (via field transferIndex) before + * doing so, reducing contention. 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 cases where old + * nodes can be reused because their next fields won't change. On + * average, only about one-sixth of them need cloning when a table + * doubles. The nodes they replace will be garbage collectable as + * soon as they are no longer referenced by any reader thread that + * may be in the midst of concurrently traversing table. Upon + * transfer, the old table bin contains only a special forwarding + * node (with hash field "MOVED") that contains the next table as + * its key. On encountering a forwarding node, access and update + * operations restart, using the new table. * * Each bin transfer requires its bin lock, which can stall * waiting for locks while resizing. However, because other @@ -409,13 +409,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) @@ -784,11 +790,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; @@ -2252,7 +2253,7 @@ public class ConcurrentHashMapV8 ex while (s >= (long)(sc = sizeCtl) && (tab = table) != null && tab.length < MAXIMUM_CAPACITY) { if (sc < 0) { - if (sc == -1 || transferIndex <= transferOrigin || + if (sc == -1 || transferIndex <= 0 || (nt = nextTable) == null) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) @@ -2272,10 +2273,13 @@ public class ConcurrentHashMapV8 ex Node[] nextTab; int sc; if ((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); + while (transferIndex > 0 && nextTab == nextTable && + (sc = sizeCtl) < -1) { + if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) { + transfer(tab, nextTab); + break; + } + } return nextTab; } return table; @@ -2326,35 +2330,26 @@ public class ConcurrentHashMapV8 ex if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked") - Node[] nt = (Node[])new Node[n << 1]; + 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 +2363,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)) { + if (sc != -1) + 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 { @@ -3128,6 +3116,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 +3151,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 +3173,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 +3191,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 +6200,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 +6214,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