ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166e/ConcurrentHashMapV8.java
(Generate patch)

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.115 by jsr166, Fri Aug 23 20:12:21 2013 UTC vs.
Revision 1.119 by jsr166, Sun Dec 1 16:56:07 2013 UTC

# Line 276 | Line 276 | public class ConcurrentHashMapV8<K,V> ex
276      /** Interface describing a function mapping two ints to an int */
277      public interface IntByIntToInt { int apply(int a, int b); }
278  
279 +
280      /*
281       * Overview:
282       *
# Line 381 | Line 382 | public class ConcurrentHashMapV8<K,V> ex
382       * The table is resized when occupancy exceeds a percentage
383       * threshold (nominally, 0.75, but see below).  Any thread
384       * noticing an overfull bin may assist in resizing after the
385 <     * initiating thread allocates and sets up the replacement
386 <     * array. However, rather than stalling, these other threads may
387 <     * proceed with insertions etc.  The use of TreeBins shields us
388 <     * from the worst case effects of overfilling while resizes are in
385 >     * initiating thread allocates and sets up the replacement array.
386 >     * However, rather than stalling, these other threads may proceed
387 >     * with insertions etc.  The use of TreeBins shields us from the
388 >     * worst case effects of overfilling while resizes are in
389       * progress.  Resizing proceeds by transferring bins, one by one,
390 <     * from the table to the next table. To enable concurrency, the
391 <     * next table must be (incrementally) prefilled with place-holders
392 <     * serving as reverse forwarders to the old table.  Because we are
390 >     * from the table to the next table. However, threads claim small
391 >     * blocks of indices to transfer (via field transferIndex) before
392 >     * doing so, reducing contention.  A generation stamp in field
393 >     * sizeCtl ensures that resizings do not overlap. Because we are
394       * using power-of-two expansion, the elements from each bin must
395       * either stay at same index, or move with a power of two
396       * offset. We eliminate unnecessary node creation by catching
# Line 409 | Line 411 | public class ConcurrentHashMapV8<K,V> ex
411       * locks, average aggregate waits become shorter as resizing
412       * progresses.  The transfer operation must also ensure that all
413       * accessible bins in both the old and new table are usable by any
414 <     * traversal.  This is arranged by proceeding from the last bin
415 <     * (table.length - 1) up towards the first.  Upon seeing a
416 <     * forwarding node, traversals (see class Traverser) arrange to
417 <     * move to the new table without revisiting nodes.  However, to
418 <     * ensure that no intervening nodes are skipped, bin splitting can
419 <     * only begin after the associated reverse-forwarders are in
420 <     * place.
414 >     * traversal.  This is arranged in part by proceeding from the
415 >     * last bin (table.length - 1) up towards the first.  Upon seeing
416 >     * a forwarding node, traversals (see class Traverser) arrange to
417 >     * move to the new table without revisiting nodes.  To ensure that
418 >     * no intervening nodes are skipped even when moved out of order,
419 >     * a stack (see class TableStack) is created on first encounter of
420 >     * a forwarding node during a traversal, to maintain its place if
421 >     * later processing the current table. The need for these
422 >     * save/restore mechanics is relatively rare, but when one
423 >     * forwarding node is encountered, typically many more will be.
424 >     * So Traversers use a simple caching scheme to avoid creating so
425 >     * many new TableStack nodes. (Thanks to Peter Levart for
426 >     * suggesting use of a stack here.)
427       *
428       * The traversal scheme also applies to partial traversals of
429       * ranges of bins (via an alternate Traverser constructor)
# Line 572 | Line 580 | public class ConcurrentHashMapV8<K,V> ex
580       */
581      private static final int MIN_TRANSFER_STRIDE = 16;
582  
583 +    /**
584 +     * The number of bits used for generation stamp in sizeCtl.
585 +     * Must be at least 6 for 32bit arrays.
586 +     */
587 +    private static int RESIZE_STAMP_BITS = 16;
588 +
589 +    /**
590 +     * The maximum number of threads that can help resize.
591 +     * Must fit in 32 - RESIZE_STAMP_BITS bits.
592 +     */
593 +    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
594 +
595 +    /**
596 +     * The bit shift for recording size stamp in sizeCtl.
597 +     */
598 +    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
599 +
600      /*
601       * Encodings for Node hash fields. See above for explanation.
602       */
# Line 729 | Line 754 | public class ConcurrentHashMapV8<K,V> ex
754       * errors by users, these checks must operate on local variables,
755       * which accounts for some odd-looking inline assignments below.
756       * Note that calls to setTabAt always occur within locked regions,
757 <     * and so in principle require only release ordering, not need
757 >     * and so in principle require only release ordering, not
758       * full volatile semantics, but are currently coded as volatile
759       * writes to be conservative.
760       */
# Line 784 | Line 809 | public class ConcurrentHashMapV8<K,V> ex
809      private transient volatile int transferIndex;
810  
811      /**
787     * The least available table index to split while resizing.
788     */
789    private transient volatile int transferOrigin;
790
791    /**
812       * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
813       */
814      private transient volatile int cellsBusy;
# Line 2194 | Line 2214 | public class ConcurrentHashMapV8<K,V> ex
2214      /* ---------------- Table Initialization and Resizing -------------- */
2215  
2216      /**
2217 +     * Returns the stamp bits for resizing a table of size n.
2218 +     * Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2219 +     */
2220 +    static final int resizeStamp(int n) {
2221 +        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2222 +    }
2223 +
2224 +    /**
2225       * Initializes table, using the size recorded in sizeCtl.
2226       */
2227      private final Node<K,V>[] initTable() {
# Line 2206 | Line 2234 | public class ConcurrentHashMapV8<K,V> ex
2234                      if ((tab = table) == null || tab.length == 0) {
2235                          int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2236                          @SuppressWarnings("unchecked")
2237 <                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2237 >                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2238                          table = tab = nt;
2239                          sc = n - (n >>> 2);
2240                      }
# Line 2248 | Line 2276 | public class ConcurrentHashMapV8<K,V> ex
2276              s = sumCount();
2277          }
2278          if (check >= 0) {
2279 <            Node<K,V>[] tab, nt; int sc;
2279 >            Node<K,V>[] tab, nt; int n, sc;
2280              while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2281 <                   tab.length < MAXIMUM_CAPACITY) {
2281 >                   (n = tab.length) < MAXIMUM_CAPACITY) {
2282 >                int rs = resizeStamp(n);
2283                  if (sc < 0) {
2284 <                    if (sc == -1 || transferIndex <= transferOrigin ||
2285 <                        (nt = nextTable) == null)
2284 >                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2285 >                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2286 >                        transferIndex <= 0)
2287                          break;
2288 <                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2288 >                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2289                          transfer(tab, nt);
2290                  }
2291 <                else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2291 >                else if (U.compareAndSwapInt(this, SIZECTL, sc,
2292 >                                             (rs << RESIZE_STAMP_SHIFT) + 2))
2293                      transfer(tab, null);
2294                  s = sumCount();
2295              }
# Line 2270 | Line 2301 | public class ConcurrentHashMapV8<K,V> ex
2301       */
2302      final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2303          Node<K,V>[] nextTab; int sc;
2304 <        if ((f instanceof ForwardingNode) &&
2304 >        if (tab != null && (f instanceof ForwardingNode) &&
2305              (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2306 <            if (nextTab == nextTable && tab == table &&
2307 <                transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2308 <                U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2309 <                transfer(tab, nextTab);
2306 >            int rs = resizeStamp(tab.length);
2307 >            while (nextTab == nextTable && table == tab &&
2308 >                   (sc = sizeCtl) < 0) {
2309 >                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2310 >                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
2311 >                    break;
2312 >                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2313 >                    transfer(tab, nextTab);
2314 >                    break;
2315 >                }
2316 >            }
2317              return nextTab;
2318          }
2319          return table;
# Line 2298 | Line 2336 | public class ConcurrentHashMapV8<K,V> ex
2336                      try {
2337                          if (table == tab) {
2338                              @SuppressWarnings("unchecked")
2339 <                                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2339 >                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2340                              table = nt;
2341                              sc = n - (n >>> 2);
2342                          }
# Line 2309 | Line 2347 | public class ConcurrentHashMapV8<K,V> ex
2347              }
2348              else if (c <= sc || n >= MAXIMUM_CAPACITY)
2349                  break;
2350 <            else if (tab == table &&
2351 <                     U.compareAndSwapInt(this, SIZECTL, sc, -2))
2352 <                transfer(tab, null);
2350 >            else if (tab == table) {
2351 >                int rs = resizeStamp(n);
2352 >                if (sc < 0) {
2353 >                    Node<K,V>[] nt;
2354 >                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2355 >                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2356 >                        transferIndex <= 0)
2357 >                        break;
2358 >                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2359 >                        transfer(tab, nt);
2360 >                }
2361 >                else if (U.compareAndSwapInt(this, SIZECTL, sc,
2362 >                                             (rs << RESIZE_STAMP_SHIFT) + 2))
2363 >                    transfer(tab, null);
2364 >            }
2365          }
2366      }
2367  
# Line 2326 | Line 2376 | public class ConcurrentHashMapV8<K,V> ex
2376          if (nextTab == null) {            // initiating
2377              try {
2378                  @SuppressWarnings("unchecked")
2379 <                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2379 >                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2380                  nextTab = nt;
2381              } catch (Throwable ex) {      // try to cope with OOME
2382                  sizeCtl = Integer.MAX_VALUE;
2383                  return;
2384              }
2385              nextTable = nextTab;
2336            transferOrigin = n;
2386              transferIndex = n;
2338            ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2339            for (int k = n; k > 0;) {    // progressively reveal ready slots
2340                int nextk = (k > stride) ? k - stride : 0;
2341                for (int m = nextk; m < k; ++m)
2342                    nextTab[m] = rev;
2343                for (int m = n + nextk; m < n + k; ++m)
2344                    nextTab[m] = rev;
2345                U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2346            }
2387          }
2388          int nextn = nextTab.length;
2389          ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2390          boolean advance = true;
2391          boolean finishing = false; // to ensure sweep before committing nextTab
2392          for (int i = 0, bound = 0;;) {
2393 <            int nextIndex, nextBound, fh; Node<K,V> f;
2393 >            Node<K,V> f; int fh;
2394              while (advance) {
2395 +                int nextIndex, nextBound;
2396                  if (--i >= bound || finishing)
2397                      advance = false;
2398 <                else if ((nextIndex = transferIndex) <= transferOrigin) {
2398 >                else if ((nextIndex = transferIndex) <= 0) {
2399                      i = -1;
2400                      advance = false;
2401                  }
# Line 2368 | Line 2409 | public class ConcurrentHashMapV8<K,V> ex
2409                  }
2410              }
2411              if (i < 0 || i >= n || i + n >= nextn) {
2412 +                int sc;
2413                  if (finishing) {
2414                      nextTable = null;
2415                      table = nextTab;
2416                      sizeCtl = (n << 1) - (n >>> 1);
2417                      return;
2418                  }
2419 <                for (int sc;;) {
2420 <                    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2421 <                        if (sc != -1)
2422 <                            return;
2423 <                        finishing = advance = true;
2382 <                        i = n; // recheck before commit
2383 <                        break;
2384 <                    }
2385 <                }
2386 <            }
2387 <            else if ((f = tabAt(tab, i)) == null) {
2388 <                if (casTabAt(tab, i, null, fwd)) {
2389 <                    setTabAt(nextTab, i, null);
2390 <                    setTabAt(nextTab, i + n, null);
2391 <                    advance = true;
2419 >                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2420 >                    if ((sc - 2) != resizeStamp(n))
2421 >                        return;
2422 >                    finishing = advance = true;
2423 >                    i = n; // recheck before commit
2424                  }
2425              }
2426 +            else if ((f = tabAt(tab, i)) == null)
2427 +                advance = casTabAt(tab, i, null, fwd);
2428              else if ((fh = f.hash) == MOVED)
2429                  advance = true; // already processed
2430              else {
# Line 2477 | Line 2511 | public class ConcurrentHashMapV8<K,V> ex
2511      private final void treeifyBin(Node<K,V>[] tab, int index) {
2512          Node<K,V> b; int n, sc;
2513          if (tab != null) {
2514 <            if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2515 <                if (tab == table && (sc = sizeCtl) >= 0 &&
2482 <                    U.compareAndSwapInt(this, SIZECTL, sc, -2))
2483 <                    transfer(tab, null);
2484 <            }
2514 >            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2515 >                tryPresize(n << 1);
2516              else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2517                  synchronized (b) {
2518                      if (tabAt(tab, index) == b) {
# Line 2679 | Line 2710 | public class ConcurrentHashMapV8<K,V> ex
2710          private final void contendedLock() {
2711              boolean waiting = false;
2712              for (int s;;) {
2713 <                if (((s = lockState) & WRITER) == 0) {
2713 >                if (((s = lockState) & ~WAITER) == 0) {
2714                      if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2715                          if (waiting)
2716                              waiter = null;
# Line 2702 | Line 2733 | public class ConcurrentHashMapV8<K,V> ex
2733           * using tree comparisons from root, but continues linear
2734           * search when lock not available.
2735           */
2736 < final Node<K,V> find(int h, Object k) {
2736 >        final Node<K,V> find(int h, Object k) {
2737              if (k != null) {
2738 <                for (Node<K,V> e = first; e != null; e = e.next) {
2738 >                for (Node<K,V> e = first; e != null; ) {
2739                      int s; K ek;
2740                      if (((s = lockState) & (WAITER|WRITER)) != 0) {
2741                          if (e.hash == h &&
2742                              ((ek = e.key) == k || (ek != null && k.equals(ek))))
2743                              return e;
2744 +                        e = e.next;
2745                      }
2746                      else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2747                                                   s + READER)) {
# Line 3128 | Line 3160 | final Node<K,V> find(int h, Object k) {
3160      /* ----------------Table Traversal -------------- */
3161  
3162      /**
3163 +     * Records the table, its length, and current traversal index for a
3164 +     * traverser that must process a region of a forwarded table before
3165 +     * proceeding with current table.
3166 +     */
3167 +    static final class TableStack<K,V> {
3168 +        int length;
3169 +        int index;
3170 +        Node<K,V>[] tab;
3171 +        TableStack<K,V> next;
3172 +    }
3173 +
3174 +    /**
3175       * Encapsulates traversal for methods such as containsValue; also
3176       * serves as a base class for other iterators and spliterators.
3177       *
# Line 3151 | Line 3195 | final Node<K,V> find(int h, Object k) {
3195      static class Traverser<K,V> {
3196          Node<K,V>[] tab;        // current table; updated if resized
3197          Node<K,V> next;         // the next entry to use
3198 +        TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3199          int index;              // index of bin to use next
3200          int baseIndex;          // current index of initial table
3201          int baseLimit;          // index bound for initial table
# Line 3172 | Line 3217 | final Node<K,V> find(int h, Object k) {
3217              if ((e = next) != null)
3218                  e = e.next;
3219              for (;;) {
3220 <                Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3220 >                Node<K,V>[] t; int i, n;  // must use locals in checks
3221                  if (e != null)
3222                      return next = e;
3223                  if (baseIndex >= baseLimit || (t = tab) == null ||
3224                      (n = t.length) <= (i = index) || i < 0)
3225                      return next = null;
3226 <                if ((e = tabAt(t, index)) != null && e.hash < 0) {
3226 >                if ((e = tabAt(t, i)) != null && e.hash < 0) {
3227                      if (e instanceof ForwardingNode) {
3228                          tab = ((ForwardingNode<K,V>)e).nextTable;
3229                          e = null;
3230 +                        pushState(t, i, n);
3231                          continue;
3232                      }
3233                      else if (e instanceof TreeBin)
# Line 3189 | Line 3235 | final Node<K,V> find(int h, Object k) {
3235                      else
3236                          e = null;
3237                  }
3238 <                if ((index += baseSize) >= n)
3239 <                    index = ++baseIndex;    // visit upper slots if present
3238 >                if (stack != null)
3239 >                    recoverState(n);
3240 >                else if ((index = i + baseSize) >= n)
3241 >                    index = ++baseIndex; // visit upper slots if present
3242 >            }
3243 >        }
3244 >
3245 >        /**
3246 >         * Saves traversal state upon encountering a forwarding node.
3247 >         */
3248 >        private void pushState(Node<K,V>[] t, int i, int n) {
3249 >            TableStack<K,V> s = spare;  // reuse if possible
3250 >            if (s != null)
3251 >                spare = s.next;
3252 >            else
3253 >                s = new TableStack<K,V>();
3254 >            s.tab = t;
3255 >            s.length = n;
3256 >            s.index = i;
3257 >            s.next = stack;
3258 >            stack = s;
3259 >        }
3260 >
3261 >        /**
3262 >         * Possibly pops traversal state.
3263 >         *
3264 >         * @param n length of current table
3265 >         */
3266 >        private void recoverState(int n) {
3267 >            TableStack<K,V> s; int len;
3268 >            while ((s = stack) != null && (index += (len = s.length)) >= n) {
3269 >                n = len;
3270 >                index = s.index;
3271 >                tab = s.tab;
3272 >                s.tab = null;
3273 >                TableStack<K,V> next = s.next;
3274 >                s.next = spare; // save for reuse
3275 >                stack = next;
3276 >                spare = s;
3277              }
3278 +            if (s == null && (index += baseSize) >= n)
3279 +                index = ++baseIndex;
3280          }
3281      }
3282  
# Line 6159 | Line 6244 | final Node<K,V> find(int h, Object k) {
6244      private static final sun.misc.Unsafe U;
6245      private static final long SIZECTL;
6246      private static final long TRANSFERINDEX;
6162    private static final long TRANSFERORIGIN;
6247      private static final long BASECOUNT;
6248      private static final long CELLSBUSY;
6249      private static final long CELLVALUE;
# Line 6174 | Line 6258 | final Node<K,V> find(int h, Object k) {
6258                  (k.getDeclaredField("sizeCtl"));
6259              TRANSFERINDEX = U.objectFieldOffset
6260                  (k.getDeclaredField("transferIndex"));
6177            TRANSFERORIGIN = U.objectFieldOffset
6178                (k.getDeclaredField("transferOrigin"));
6261              BASECOUNT = U.objectFieldOffset
6262                  (k.getDeclaredField("baseCount"));
6263              CELLSBUSY = U.objectFieldOffset

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines