changeset 42319:0193886267c3

8143577: optimize ArrayList.removeIf 8169679: ArrayList.subList().iterator().forEachRemaining() off-by-one-error 8167202: ArrayDeque improvements 8164793: new ArrayDeque(2**N) allocates backing array of size 2**(N+1) 8169739: LinkedBlockingDeque spliterator needs to support node self-linking 8169738: CopyOnWriteArrayList subList needs more synchronization Reviewed-by: martin, smarks, psandoz, forax
author dl
date Mon, 28 Nov 2016 23:36:11 -0800
parents 35806bea1e90
children bfc781c5078f
files jdk/src/java.base/share/classes/java/util/ArrayDeque.java jdk/src/java.base/share/classes/java/util/ArrayList.java jdk/src/java.base/share/classes/java/util/Vector.java jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java jdk/test/java/util/ArrayList/IteratorMicroBenchmark.java jdk/test/java/util/Collection/CollectionDefaults.java jdk/test/java/util/Collection/IteratorMicroBenchmark.java jdk/test/java/util/Collection/RemoveMicroBenchmark.java jdk/test/java/util/Vector/LastIndexOf.java jdk/test/java/util/concurrent/ArrayBlockingQueue/IteratorConsistency.java jdk/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java jdk/test/java/util/concurrent/tck/ArrayBlockingQueueTest.java jdk/test/java/util/concurrent/tck/ArrayDeque8Test.java jdk/test/java/util/concurrent/tck/ArrayDequeTest.java jdk/test/java/util/concurrent/tck/ArrayListTest.java jdk/test/java/util/concurrent/tck/Collection8Test.java jdk/test/java/util/concurrent/tck/CollectionTest.java jdk/test/java/util/concurrent/tck/CopyOnWriteArrayListTest.java jdk/test/java/util/concurrent/tck/CountedCompleter8Test.java jdk/test/java/util/concurrent/tck/CountedCompleterTest.java jdk/test/java/util/concurrent/tck/DelayQueueTest.java jdk/test/java/util/concurrent/tck/JSR166TestCase.java jdk/test/java/util/concurrent/tck/LinkedBlockingDequeTest.java jdk/test/java/util/concurrent/tck/LinkedBlockingQueueTest.java jdk/test/java/util/concurrent/tck/LinkedListTest.java jdk/test/java/util/concurrent/tck/VectorTest.java
diffstat 28 files changed, 3958 insertions(+), 1337 deletions(-) [+]
line wrap: on
line diff
--- a/jdk/src/java.base/share/classes/java/util/ArrayDeque.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/ArrayDeque.java	Mon Nov 28 23:36:11 2016 -0800
@@ -36,6 +36,8 @@
 
 import java.io.Serializable;
 import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
 
 /**
  * Resizable-array implementation of the {@link Deque} interface.  Array
@@ -87,81 +89,89 @@
 public class ArrayDeque<E> extends AbstractCollection<E>
                            implements Deque<E>, Cloneable, Serializable
 {
+    /*
+     * VMs excel at optimizing simple array loops where indices are
+     * incrementing or decrementing over a valid slice, e.g.
+     *
+     * for (int i = start; i < end; i++) ... elements[i]
+     *
+     * Because in a circular array, elements are in general stored in
+     * two disjoint such slices, we help the VM by writing unusual
+     * nested loops for all traversals over the elements.  Having only
+     * one hot inner loop body instead of two or three eases human
+     * maintenance and encourages VM loop inlining into the caller.
+     */
+
     /**
      * The array in which the elements of the deque are stored.
-     * The capacity of the deque is the length of this array, which is
-     * always a power of two. The array is never allowed to become
-     * full, except transiently within an addX method where it is
-     * resized (see doubleCapacity) immediately upon becoming full,
-     * thus avoiding head and tail wrapping around to equal each
-     * other.  We also guarantee that all array cells not holding
-     * deque elements are always null.
+     * All array cells not holding deque elements are always null.
+     * The array always has at least one null slot (at tail).
      */
-    transient Object[] elements; // non-private to simplify nested class access
+    transient Object[] elements;
 
     /**
      * The index of the element at the head of the deque (which is the
      * element that would be removed by remove() or pop()); or an
-     * arbitrary number equal to tail if the deque is empty.
+     * arbitrary number 0 <= head < elements.length equal to tail if
+     * the deque is empty.
      */
     transient int head;
 
     /**
      * The index at which the next element would be added to the tail
-     * of the deque (via addLast(E), add(E), or push(E)).
+     * of the deque (via addLast(E), add(E), or push(E));
+     * elements[tail] is always null.
      */
     transient int tail;
 
     /**
-     * The minimum capacity that we'll use for a newly created deque.
-     * Must be a power of 2.
+     * The maximum size of array to allocate.
+     * Some VMs reserve some header words in an array.
+     * Attempts to allocate larger arrays may result in
+     * OutOfMemoryError: Requested array size exceeds VM limit
      */
-    private static final int MIN_INITIAL_CAPACITY = 8;
-
-    // ******  Array allocation and resizing utilities ******
+    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
     /**
-     * Allocates empty array to hold the given number of elements.
+     * Increases the capacity of this deque by at least the given amount.
      *
-     * @param numElements  the number of elements to hold
+     * @param needed the required minimum extra capacity; must be positive
      */
-    private void allocateElements(int numElements) {
-        int initialCapacity = MIN_INITIAL_CAPACITY;
-        // Find the best power of two to hold elements.
-        // Tests "<=" because arrays aren't kept full.
-        if (numElements >= initialCapacity) {
-            initialCapacity = numElements;
-            initialCapacity |= (initialCapacity >>>  1);
-            initialCapacity |= (initialCapacity >>>  2);
-            initialCapacity |= (initialCapacity >>>  4);
-            initialCapacity |= (initialCapacity >>>  8);
-            initialCapacity |= (initialCapacity >>> 16);
-            initialCapacity++;
-
-            if (initialCapacity < 0)    // Too many elements, must back off
-                initialCapacity >>>= 1; // Good luck allocating 2^30 elements
+    private void grow(int needed) {
+        // overflow-conscious code
+        final int oldCapacity = elements.length;
+        int newCapacity;
+        // Double capacity if small; else grow by 50%
+        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
+        if (jump < needed
+            || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
+            newCapacity = newCapacity(needed, jump);
+        elements = Arrays.copyOf(elements, newCapacity);
+        // Exceptionally, here tail == head needs to be disambiguated
+        if (tail < head || (tail == head && elements[head] != null)) {
+            // wrap around; slide first leg forward to end of array
+            int newSpace = newCapacity - oldCapacity;
+            System.arraycopy(elements, head,
+                             elements, head + newSpace,
+                             oldCapacity - head);
+            Arrays.fill(elements, head, head + newSpace, null);
+            head += newSpace;
         }
-        elements = new Object[initialCapacity];
     }
 
-    /**
-     * Doubles the capacity of this deque.  Call only when full, i.e.,
-     * when head and tail have wrapped around to become equal.
-     */
-    private void doubleCapacity() {
-        assert head == tail;
-        int p = head;
-        int n = elements.length;
-        int r = n - p; // number of elements to the right of p
-        int newCapacity = n << 1;
-        if (newCapacity < 0)
-            throw new IllegalStateException("Sorry, deque too big");
-        Object[] a = new Object[newCapacity];
-        System.arraycopy(elements, p, a, 0, r);
-        System.arraycopy(elements, 0, a, r, p);
-        elements = a;
-        head = 0;
-        tail = n;
+    /** Capacity calculation for edge conditions, especially overflow. */
+    private int newCapacity(int needed, int jump) {
+        final int oldCapacity = elements.length, minCapacity;
+        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
+            if (minCapacity < 0)
+                throw new IllegalStateException("Sorry, deque too big");
+            return Integer.MAX_VALUE;
+        }
+        if (needed > jump)
+            return minCapacity;
+        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
+            ? oldCapacity + jump
+            : MAX_ARRAY_SIZE;
     }
 
     /**
@@ -176,10 +186,13 @@
      * Constructs an empty array deque with an initial capacity
      * sufficient to hold the specified number of elements.
      *
-     * @param numElements  lower bound on initial capacity of the deque
+     * @param numElements lower bound on initial capacity of the deque
      */
     public ArrayDeque(int numElements) {
-        allocateElements(numElements);
+        elements =
+            new Object[(numElements < 1) ? 1 :
+                       (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
+                       numElements + 1];
     }
 
     /**
@@ -193,10 +206,71 @@
      * @throws NullPointerException if the specified collection is null
      */
     public ArrayDeque(Collection<? extends E> c) {
-        allocateElements(c.size());
+        this(c.size());
         addAll(c);
     }
 
+    /**
+     * Increments i, mod modulus.
+     * Precondition and postcondition: 0 <= i < modulus.
+     */
+    static final int inc(int i, int modulus) {
+        if (++i >= modulus) i = 0;
+        return i;
+    }
+
+    /**
+     * Decrements i, mod modulus.
+     * Precondition and postcondition: 0 <= i < modulus.
+     */
+    static final int dec(int i, int modulus) {
+        if (--i < 0) i = modulus - 1;
+        return i;
+    }
+
+    /**
+     * Circularly adds the given distance to index i, mod modulus.
+     * Precondition: 0 <= i < modulus, 0 <= distance <= modulus.
+     * @return index 0 <= i < modulus
+     */
+    static final int add(int i, int distance, int modulus) {
+        if ((i += distance) - modulus >= 0) i -= modulus;
+        return i;
+    }
+
+    /**
+     * Subtracts j from i, mod modulus.
+     * Index i must be logically ahead of index j.
+     * Precondition: 0 <= i < modulus, 0 <= j < modulus.
+     * @return the "circular distance" from j to i; corner case i == j
+     * is diambiguated to "empty", returning 0.
+     */
+    static final int sub(int i, int j, int modulus) {
+        if ((i -= j) < 0) i += modulus;
+        return i;
+    }
+
+    /**
+     * Returns element at array index i.
+     * This is a slight abuse of generics, accepted by javac.
+     */
+    @SuppressWarnings("unchecked")
+    static final <E> E elementAt(Object[] es, int i) {
+        return (E) es[i];
+    }
+
+    /**
+     * A version of elementAt that checks for null elements.
+     * This check doesn't catch all possible comodifications,
+     * but does catch ones that corrupt traversal.
+     */
+    static final <E> E nonNullElementAt(Object[] es, int i) {
+        @SuppressWarnings("unchecked") E e = (E) es[i];
+        if (e == null)
+            throw new ConcurrentModificationException();
+        return e;
+    }
+
     // The main insertion and extraction methods are addFirst,
     // addLast, pollFirst, pollLast. The other methods are defined in
     // terms of these.
@@ -210,9 +284,10 @@
     public void addFirst(E e) {
         if (e == null)
             throw new NullPointerException();
-        elements[head = (head - 1) & (elements.length - 1)] = e;
+        final Object[] es = elements;
+        es[head = dec(head, es.length)] = e;
         if (head == tail)
-            doubleCapacity();
+            grow(1);
     }
 
     /**
@@ -226,9 +301,29 @@
     public void addLast(E e) {
         if (e == null)
             throw new NullPointerException();
-        elements[tail] = e;
-        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
-            doubleCapacity();
+        final Object[] es = elements;
+        es[tail] = e;
+        if (head == (tail = inc(tail, es.length)))
+            grow(1);
+    }
+
+    /**
+     * Adds all of the elements in the specified collection at the end
+     * of this deque, as if by calling {@link #addLast} on each one,
+     * in the order that they are returned by the collection's
+     * iterator.
+     *
+     * @param c the elements to be inserted into this deque
+     * @return {@code true} if this deque changed as a result of the call
+     * @throws NullPointerException if the specified collection or any
+     *         of its elements are null
+     */
+    public boolean addAll(Collection<? extends E> c) {
+        final int s, needed;
+        if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
+            grow(needed);
+        c.forEach(this::addLast);
+        return size() > s;
     }
 
     /**
@@ -259,78 +354,70 @@
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E removeFirst() {
-        E x = pollFirst();
-        if (x == null)
+        E e = pollFirst();
+        if (e == null)
             throw new NoSuchElementException();
-        return x;
+        return e;
     }
 
     /**
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E removeLast() {
-        E x = pollLast();
-        if (x == null)
+        E e = pollLast();
+        if (e == null)
             throw new NoSuchElementException();
-        return x;
+        return e;
     }
 
     public E pollFirst() {
-        final Object[] elements = this.elements;
-        final int h = head;
-        @SuppressWarnings("unchecked")
-        E result = (E) elements[h];
-        // Element is null if deque empty
-        if (result != null) {
-            elements[h] = null; // Must null out slot
-            head = (h + 1) & (elements.length - 1);
+        final Object[] es;
+        final int h;
+        E e = elementAt(es = elements, h = head);
+        if (e != null) {
+            es[h] = null;
+            head = inc(h, es.length);
         }
-        return result;
+        return e;
     }
 
     public E pollLast() {
-        final Object[] elements = this.elements;
-        final int t = (tail - 1) & (elements.length - 1);
-        @SuppressWarnings("unchecked")
-        E result = (E) elements[t];
-        if (result != null) {
-            elements[t] = null;
-            tail = t;
-        }
-        return result;
+        final Object[] es;
+        final int t;
+        E e = elementAt(es = elements, t = dec(tail, es.length));
+        if (e != null)
+            es[tail = t] = null;
+        return e;
     }
 
     /**
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E getFirst() {
-        @SuppressWarnings("unchecked")
-        E result = (E) elements[head];
-        if (result == null)
+        E e = elementAt(elements, head);
+        if (e == null)
             throw new NoSuchElementException();
-        return result;
+        return e;
     }
 
     /**
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E getLast() {
-        @SuppressWarnings("unchecked")
-        E result = (E) elements[(tail - 1) & (elements.length - 1)];
-        if (result == null)
+        final Object[] es = elements;
+        E e = elementAt(es, dec(tail, es.length));
+        if (e == null)
             throw new NoSuchElementException();
-        return result;
+        return e;
     }
 
-    @SuppressWarnings("unchecked")
     public E peekFirst() {
-        // elements[head] is null if deque empty
-        return (E) elements[head];
+        return elementAt(elements, head);
     }
 
-    @SuppressWarnings("unchecked")
     public E peekLast() {
-        return (E) elements[(tail - 1) & (elements.length - 1)];
+        final Object[] es;
+        return elementAt(es = elements, dec(tail, es.length));
     }
 
     /**
@@ -347,13 +434,15 @@
      */
     public boolean removeFirstOccurrence(Object o) {
         if (o != null) {
-            int mask = elements.length - 1;
-            int i = head;
-            for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
-                if (o.equals(x)) {
-                    delete(i);
-                    return true;
-                }
+            final Object[] es = elements;
+            for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+                 ; i = 0, to = end) {
+                for (; i < to; i++)
+                    if (o.equals(es[i])) {
+                        delete(i);
+                        return true;
+                    }
+                if (to == end) break;
             }
         }
         return false;
@@ -373,13 +462,15 @@
      */
     public boolean removeLastOccurrence(Object o) {
         if (o != null) {
-            int mask = elements.length - 1;
-            int i = (tail - 1) & mask;
-            for (Object x; (x = elements[i]) != null; i = (i - 1) & mask) {
-                if (o.equals(x)) {
-                    delete(i);
-                    return true;
-                }
+            final Object[] es = elements;
+            for (int i = tail, end = head, to = (i >= end) ? end : 0;
+                 ; i = es.length, to = end) {
+                for (i--; i > to - 1; i--)
+                    if (o.equals(es[i])) {
+                        delete(i);
+                        return true;
+                    }
+                if (to == end) break;
             }
         }
         return false;
@@ -499,59 +590,47 @@
         return removeFirst();
     }
 
-    private void checkInvariants() {
-        assert elements[tail] == null;
-        assert head == tail ? elements[head] == null :
-            (elements[head] != null &&
-             elements[(tail - 1) & (elements.length - 1)] != null);
-        assert elements[(head - 1) & (elements.length - 1)] == null;
-    }
-
     /**
-     * Removes the element at the specified position in the elements array,
-     * adjusting head and tail as necessary.  This can result in motion of
-     * elements backwards or forwards in the array.
+     * Removes the element at the specified position in the elements array.
+     * This can result in forward or backwards motion of array elements.
+     * We optimize for least element motion.
      *
      * <p>This method is called delete rather than remove to emphasize
      * that its semantics differ from those of {@link List#remove(int)}.
      *
-     * @return true if elements moved backwards
+     * @return true if elements near tail moved backwards
      */
     boolean delete(int i) {
-        checkInvariants();
-        final Object[] elements = this.elements;
-        final int mask = elements.length - 1;
-        final int h = head;
-        final int t = tail;
-        final int front = (i - h) & mask;
-        final int back  = (t - i) & mask;
-
-        // Invariant: head <= i < tail mod circularity
-        if (front >= ((t - h) & mask))
-            throw new ConcurrentModificationException();
-
-        // Optimize for least element motion
+        final Object[] es = elements;
+        final int capacity = es.length;
+        final int h, t;
+        // number of elements before to-be-deleted elt
+        final int front = sub(i, h = head, capacity);
+        // number of elements after to-be-deleted elt
+        final int back = sub(t = tail, i, capacity) - 1;
         if (front < back) {
+            // move front elements forwards
             if (h <= i) {
-                System.arraycopy(elements, h, elements, h + 1, front);
+                System.arraycopy(es, h, es, h + 1, front);
             } else { // Wrap around
-                System.arraycopy(elements, 0, elements, 1, i);
-                elements[0] = elements[mask];
-                System.arraycopy(elements, h, elements, h + 1, mask - h);
+                System.arraycopy(es, 0, es, 1, i);
+                es[0] = es[capacity - 1];
+                System.arraycopy(es, h, es, h + 1, front - (i + 1));
             }
-            elements[h] = null;
-            head = (h + 1) & mask;
+            es[h] = null;
+            head = inc(h, capacity);
             return false;
         } else {
-            if (i < t) { // Copy the null tail as well
-                System.arraycopy(elements, i + 1, elements, i, back);
-                tail = t - 1;
+            // move back elements backwards
+            tail = dec(t, capacity);
+            if (i <= tail) {
+                System.arraycopy(es, i + 1, es, i, back);
             } else { // Wrap around
-                System.arraycopy(elements, i + 1, elements, i, mask - i);
-                elements[mask] = elements[0];
-                System.arraycopy(elements, 1, elements, 0, t);
-                tail = (t - 1) & mask;
+                System.arraycopy(es, i + 1, es, i, capacity - (i + 1));
+                es[capacity - 1] = es[0];
+                System.arraycopy(es, 1, es, 0, t - 1);
             }
+            es[tail] = null;
             return true;
         }
     }
@@ -564,7 +643,7 @@
      * @return the number of elements in this deque
      */
     public int size() {
-        return (tail - head) & (elements.length - 1);
+        return sub(tail, head, elements.length);
     }
 
     /**
@@ -593,101 +672,317 @@
     }
 
     private class DeqIterator implements Iterator<E> {
-        /**
-         * Index of element to be returned by subsequent call to next.
-         */
-        private int cursor = head;
+        /** Index of element to be returned by subsequent call to next. */
+        int cursor;
 
-        /**
-         * Tail recorded at construction (also in remove), to stop
-         * iterator and also to check for comodification.
-         */
-        private int fence = tail;
+        /** Number of elements yet to be returned. */
+        int remaining = size();
 
         /**
          * Index of element returned by most recent call to next.
          * Reset to -1 if element is deleted by a call to remove.
          */
-        private int lastRet = -1;
+        int lastRet = -1;
 
-        public boolean hasNext() {
-            return cursor != fence;
+        DeqIterator() { cursor = head; }
+
+        public final boolean hasNext() {
+            return remaining > 0;
         }
 
         public E next() {
-            if (cursor == fence)
+            if (remaining <= 0)
                 throw new NoSuchElementException();
-            @SuppressWarnings("unchecked")
-            E result = (E) elements[cursor];
-            // This check doesn't catch all possible comodifications,
-            // but does catch the ones that corrupt traversal
-            if (tail != fence || result == null)
-                throw new ConcurrentModificationException();
-            lastRet = cursor;
-            cursor = (cursor + 1) & (elements.length - 1);
-            return result;
+            final Object[] es = elements;
+            E e = nonNullElementAt(es, cursor);
+            cursor = inc(lastRet = cursor, es.length);
+            remaining--;
+            return e;
         }
 
-        public void remove() {
+        void postDelete(boolean leftShifted) {
+            if (leftShifted)
+                cursor = dec(cursor, elements.length);
+        }
+
+        public final void remove() {
             if (lastRet < 0)
                 throw new IllegalStateException();
-            if (delete(lastRet)) { // if left-shifted, undo increment in next()
-                cursor = (cursor - 1) & (elements.length - 1);
-                fence = tail;
-            }
+            postDelete(delete(lastRet));
             lastRet = -1;
         }
 
         public void forEachRemaining(Consumer<? super E> action) {
             Objects.requireNonNull(action);
-            Object[] a = elements;
-            int m = a.length - 1, f = fence, i = cursor;
-            cursor = f;
-            while (i != f) {
-                @SuppressWarnings("unchecked") E e = (E)a[i];
-                i = (i + 1) & m;
-                if (e == null)
-                    throw new ConcurrentModificationException();
-                action.accept(e);
+            int r;
+            if ((r = remaining) <= 0)
+                return;
+            remaining = 0;
+            final Object[] es = elements;
+            if (es[cursor] == null || sub(tail, cursor, es.length) != r)
+                throw new ConcurrentModificationException();
+            for (int i = cursor, end = tail, to = (i <= end) ? end : es.length;
+                 ; i = 0, to = end) {
+                for (; i < to; i++)
+                    action.accept(elementAt(es, i));
+                if (to == end) {
+                    if (end != tail)
+                        throw new ConcurrentModificationException();
+                    lastRet = dec(end, es.length);
+                    break;
+                }
+            }
+        }
+    }
+
+    private class DescendingIterator extends DeqIterator {
+        DescendingIterator() { cursor = dec(tail, elements.length); }
+
+        public final E next() {
+            if (remaining <= 0)
+                throw new NoSuchElementException();
+            final Object[] es = elements;
+            E e = nonNullElementAt(es, cursor);
+            cursor = dec(lastRet = cursor, es.length);
+            remaining--;
+            return e;
+        }
+
+        void postDelete(boolean leftShifted) {
+            if (!leftShifted)
+                cursor = inc(cursor, elements.length);
+        }
+
+        public final void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            int r;
+            if ((r = remaining) <= 0)
+                return;
+            remaining = 0;
+            final Object[] es = elements;
+            if (es[cursor] == null || sub(cursor, head, es.length) + 1 != r)
+                throw new ConcurrentModificationException();
+            for (int i = cursor, end = head, to = (i >= end) ? end : 0;
+                 ; i = es.length - 1, to = end) {
+                // hotspot generates faster code than for: i >= to !
+                for (; i > to - 1; i--)
+                    action.accept(elementAt(es, i));
+                if (to == end) {
+                    if (end != head)
+                        throw new ConcurrentModificationException();
+                    lastRet = end;
+                    break;
+                }
             }
         }
     }
 
     /**
-     * This class is nearly a mirror-image of DeqIterator, using tail
-     * instead of head for initial cursor, and head instead of tail
-     * for fence.
+     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
+     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
+     * deque.
+     *
+     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
+     * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
+     * {@link Spliterator#NONNULL}.  Overriding implementations should document
+     * the reporting of additional characteristic values.
+     *
+     * @return a {@code Spliterator} over the elements in this deque
+     * @since 1.8
      */
-    private class DescendingIterator implements Iterator<E> {
-        private int cursor = tail;
-        private int fence = head;
-        private int lastRet = -1;
+    public Spliterator<E> spliterator() {
+        return new DeqSpliterator();
+    }
 
-        public boolean hasNext() {
-            return cursor != fence;
+    final class DeqSpliterator implements Spliterator<E> {
+        private int fence;      // -1 until first use
+        private int cursor;     // current index, modified on traverse/split
+
+        /** Constructs late-binding spliterator over all elements. */
+        DeqSpliterator() {
+            this.fence = -1;
         }
 
-        public E next() {
-            if (cursor == fence)
-                throw new NoSuchElementException();
-            cursor = (cursor - 1) & (elements.length - 1);
-            @SuppressWarnings("unchecked")
-            E result = (E) elements[cursor];
-            if (head != fence || result == null)
-                throw new ConcurrentModificationException();
-            lastRet = cursor;
-            return result;
+        /** Constructs spliterator over the given range. */
+        DeqSpliterator(int origin, int fence) {
+            // assert 0 <= origin && origin < elements.length;
+            // assert 0 <= fence && fence < elements.length;
+            this.cursor = origin;
+            this.fence = fence;
         }
 
-        public void remove() {
-            if (lastRet < 0)
-                throw new IllegalStateException();
-            if (!delete(lastRet)) {
-                cursor = (cursor + 1) & (elements.length - 1);
-                fence = head;
+        /** Ensures late-binding initialization; then returns fence. */
+        private int getFence() { // force initialization
+            int t;
+            if ((t = fence) < 0) {
+                t = fence = tail;
+                cursor = head;
             }
-            lastRet = -1;
+            return t;
         }
+
+        public DeqSpliterator trySplit() {
+            final Object[] es = elements;
+            final int i, n;
+            return ((n = sub(getFence(), i = cursor, es.length) >> 1) <= 0)
+                ? null
+                : new DeqSpliterator(i, cursor = add(i, n, es.length));
+        }
+
+        public void forEachRemaining(Consumer<? super E> action) {
+            if (action == null)
+                throw new NullPointerException();
+            final int end = getFence(), cursor = this.cursor;
+            final Object[] es = elements;
+            if (cursor != end) {
+                this.cursor = end;
+                // null check at both ends of range is sufficient
+                if (es[cursor] == null || es[dec(end, es.length)] == null)
+                    throw new ConcurrentModificationException();
+                for (int i = cursor, to = (i <= end) ? end : es.length;
+                     ; i = 0, to = end) {
+                    for (; i < to; i++)
+                        action.accept(elementAt(es, i));
+                    if (to == end) break;
+                }
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            final Object[] es = elements;
+            if (fence < 0) { fence = tail; cursor = head; } // late-binding
+            final int i;
+            if ((i = cursor) == fence)
+                return false;
+            E e = nonNullElementAt(es, i);
+            cursor = inc(i, es.length);
+            action.accept(e);
+            return true;
+        }
+
+        public long estimateSize() {
+            return sub(getFence(), cursor, elements.length);
+        }
+
+        public int characteristics() {
+            return Spliterator.NONNULL
+                | Spliterator.ORDERED
+                | Spliterator.SIZED
+                | Spliterator.SUBSIZED;
+        }
+    }
+
+    public void forEach(Consumer<? super E> action) {
+        Objects.requireNonNull(action);
+        final Object[] es = elements;
+        for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+             ; i = 0, to = end) {
+            for (; i < to; i++)
+                action.accept(elementAt(es, i));
+            if (to == end) {
+                if (end != tail) throw new ConcurrentModificationException();
+                break;
+            }
+        }
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public boolean removeIf(Predicate<? super E> filter) {
+        Objects.requireNonNull(filter);
+        return bulkRemove(filter);
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public boolean removeAll(Collection<?> c) {
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> c.contains(e));
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public boolean retainAll(Collection<?> c) {
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> !c.contains(e));
+    }
+
+    /** Implementation of bulk remove methods. */
+    private boolean bulkRemove(Predicate<? super E> filter) {
+        final Object[] es = elements;
+        // Optimize for initial run of survivors
+        for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+             ; i = 0, to = end) {
+            for (; i < to; i++)
+                if (filter.test(elementAt(es, i)))
+                    return bulkRemoveModified(filter, i);
+            if (to == end) {
+                if (end != tail) throw new ConcurrentModificationException();
+                break;
+            }
+        }
+        return false;
+    }
+
+    // A tiny bit set implementation
+
+    private static long[] nBits(int n) {
+        return new long[((n - 1) >> 6) + 1];
+    }
+    private static void setBit(long[] bits, int i) {
+        bits[i >> 6] |= 1L << i;
+    }
+    private static boolean isClear(long[] bits, int i) {
+        return (bits[i >> 6] & (1L << i)) == 0;
+    }
+
+    /**
+     * Helper for bulkRemove, in case of at least one deletion.
+     * Tolerate predicates that reentrantly access the collection for
+     * read (but writers still get CME), so traverse once to find
+     * elements to delete, a second pass to physically expunge.
+     *
+     * @param beg valid index of first element to be deleted
+     */
+    private boolean bulkRemoveModified(
+        Predicate<? super E> filter, final int beg) {
+        final Object[] es = elements;
+        final int capacity = es.length;
+        final int end = tail;
+        final long[] deathRow = nBits(sub(end, beg, capacity));
+        deathRow[0] = 1L;   // set bit 0
+        for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+             ; i = 0, to = end, k -= capacity) {
+            for (; i < to; i++)
+                if (filter.test(elementAt(es, i)))
+                    setBit(deathRow, i - k);
+            if (to == end) break;
+        }
+        // a two-finger traversal, with hare i reading, tortoise w writing
+        int w = beg;
+        for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+             ; w = 0) { // w rejoins i on second leg
+            // In this loop, i and w are on the same leg, with i > w
+            for (; i < to; i++)
+                if (isClear(deathRow, i - k))
+                    es[w++] = es[i];
+            if (to == end) break;
+            // In this loop, w is on the first leg, i on the second
+            for (i = 0, to = end, k -= capacity; i < to && w < capacity; i++)
+                if (isClear(deathRow, i - k))
+                    es[w++] = es[i];
+            if (i >= to) {
+                if (w == capacity) w = 0; // "corner" case
+                break;
+            }
+        }
+        if (end != tail) throw new ConcurrentModificationException();
+        circularClear(es, tail = w, end);
+        return true;
     }
 
     /**
@@ -700,11 +995,13 @@
      */
     public boolean contains(Object o) {
         if (o != null) {
-            int mask = elements.length - 1;
-            int i = head;
-            for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
-                if (o.equals(x))
-                    return true;
+            final Object[] es = elements;
+            for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+                 ; i = 0, to = end) {
+                for (; i < to; i++)
+                    if (o.equals(es[i]))
+                        return true;
+                if (to == end) break;
             }
         }
         return false;
@@ -732,16 +1029,18 @@
      * The deque will be empty after this call returns.
      */
     public void clear() {
-        int h = head;
-        int t = tail;
-        if (h != t) { // clear all cells
-            head = tail = 0;
-            int i = h;
-            int mask = elements.length - 1;
-            do {
-                elements[i] = null;
-                i = (i + 1) & mask;
-            } while (i != t);
+        circularClear(elements, head, tail);
+        head = tail = 0;
+    }
+
+    /**
+     * Nulls out slots starting at array index i, upto index end.
+     */
+    private static void circularClear(Object[] es, int i, int end) {
+        for (int to = (i <= end) ? end : es.length;
+             ; i = 0, to = end) {
+            Arrays.fill(es, i, to, null);
+            if (to == end) break;
         }
     }
 
@@ -759,13 +1058,23 @@
      * @return an array containing all of the elements in this deque
      */
     public Object[] toArray() {
-        final int head = this.head;
-        final int tail = this.tail;
-        boolean wrap = (tail < head);
-        int end = wrap ? tail + elements.length : tail;
-        Object[] a = Arrays.copyOfRange(elements, head, end);
-        if (wrap)
-            System.arraycopy(elements, 0, a, elements.length - head, tail);
+        return toArray(Object[].class);
+    }
+
+    private <T> T[] toArray(Class<T[]> klazz) {
+        final Object[] es = elements;
+        final T[] a;
+        final int head = this.head, tail = this.tail, end;
+        if ((end = tail + ((head <= tail) ? 0 : es.length)) >= 0) {
+            // Uses null extension feature of copyOfRange
+            a = Arrays.copyOfRange(es, head, end, klazz);
+        } else {
+            // integer overflow!
+            a = Arrays.copyOfRange(es, 0, end - head, klazz);
+            System.arraycopy(es, head, a, 0, es.length - head);
+        }
+        if (end != tail)
+            System.arraycopy(es, 0, a, es.length - head, tail);
         return a;
     }
 
@@ -807,22 +1116,17 @@
      */
     @SuppressWarnings("unchecked")
     public <T> T[] toArray(T[] a) {
-        final int head = this.head;
-        final int tail = this.tail;
-        boolean wrap = (tail < head);
-        int size = (tail - head) + (wrap ? elements.length : 0);
-        int firstLeg = size - (wrap ? tail : 0);
-        int len = a.length;
-        if (size > len) {
-            a = (T[]) Arrays.copyOfRange(elements, head, head + size,
-                                         a.getClass());
-        } else {
-            System.arraycopy(elements, head, a, 0, firstLeg);
-            if (size < len)
-                a[size] = null;
+        final int size;
+        if ((size = size()) > a.length)
+            return toArray((Class<T[]>) a.getClass());
+        final Object[] es = elements;
+        for (int i = head, j = 0, len = Math.min(size, es.length - i);
+             ; i = 0, len = tail) {
+            System.arraycopy(es, i, a, j, len);
+            if ((j += len) == size) break;
         }
-        if (wrap)
-            System.arraycopy(elements, 0, a, firstLeg, tail);
+        if (size < a.length)
+            a[size] = null;
         return a;
     }
 
@@ -863,9 +1167,13 @@
         s.writeInt(size());
 
         // Write out elements in order.
-        int mask = elements.length - 1;
-        for (int i = head; i != tail; i = (i + 1) & mask)
-            s.writeObject(elements[i]);
+        final Object[] es = elements;
+        for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+             ; i = 0, to = end) {
+            for (; i < to; i++)
+                s.writeObject(es[i]);
+            if (to == end) break;
+        }
     }
 
     /**
@@ -881,106 +1189,33 @@
 
         // Read in size and allocate array
         int size = s.readInt();
-        allocateElements(size);
-        head = 0;
-        tail = size;
+        elements = new Object[size + 1];
+        this.tail = size;
 
         // Read in all elements in the proper order.
         for (int i = 0; i < size; i++)
             elements[i] = s.readObject();
     }
 
-    /**
-     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
-     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
-     * deque.
-     *
-     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
-     * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
-     * {@link Spliterator#NONNULL}.  Overriding implementations should document
-     * the reporting of additional characteristic values.
-     *
-     * @return a {@code Spliterator} over the elements in this deque
-     * @since 1.8
-     */
-    public Spliterator<E> spliterator() {
-        return new DeqSpliterator<>(this, -1, -1);
-    }
-
-    static final class DeqSpliterator<E> implements Spliterator<E> {
-        private final ArrayDeque<E> deq;
-        private int fence;  // -1 until first use
-        private int index;  // current index, modified on traverse/split
-
-        /** Creates new spliterator covering the given array and range. */
-        DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
-            this.deq = deq;
-            this.index = origin;
-            this.fence = fence;
-        }
-
-        private int getFence() { // force initialization
-            int t;
-            if ((t = fence) < 0) {
-                t = fence = deq.tail;
-                index = deq.head;
-            }
-            return t;
-        }
-
-        public DeqSpliterator<E> trySplit() {
-            int t = getFence(), h = index, n = deq.elements.length;
-            if (h != t && ((h + 1) & (n - 1)) != t) {
-                if (h > t)
-                    t += n;
-                int m = ((h + t) >>> 1) & (n - 1);
-                return new DeqSpliterator<E>(deq, h, index = m);
-            }
-            return null;
-        }
-
-        public void forEachRemaining(Consumer<? super E> consumer) {
-            if (consumer == null)
-                throw new NullPointerException();
-            Object[] a = deq.elements;
-            int m = a.length - 1, f = getFence(), i = index;
-            index = f;
-            while (i != f) {
-                @SuppressWarnings("unchecked") E e = (E)a[i];
-                i = (i + 1) & m;
-                if (e == null)
-                    throw new ConcurrentModificationException();
-                consumer.accept(e);
-            }
-        }
-
-        public boolean tryAdvance(Consumer<? super E> consumer) {
-            if (consumer == null)
-                throw new NullPointerException();
-            Object[] a = deq.elements;
-            int m = a.length - 1, f = getFence(), i = index;
-            if (i != f) {
-                @SuppressWarnings("unchecked") E e = (E)a[i];
-                index = (i + 1) & m;
-                if (e == null)
-                    throw new ConcurrentModificationException();
-                consumer.accept(e);
-                return true;
-            }
-            return false;
-        }
-
-        public long estimateSize() {
-            int n = getFence() - index;
-            if (n < 0)
-                n += deq.elements.length;
-            return (long) n;
-        }
-
-        @Override
-        public int characteristics() {
-            return Spliterator.ORDERED | Spliterator.SIZED |
-                Spliterator.NONNULL | Spliterator.SUBSIZED;
+    /** debugging */
+    void checkInvariants() {
+        // Use head and tail fields with empty slot at tail strategy.
+        // head == tail disambiguates to "empty".
+        try {
+            int capacity = elements.length;
+            // assert 0 <= head && head < capacity;
+            // assert 0 <= tail && tail < capacity;
+            // assert capacity > 0;
+            // assert size() < capacity;
+            // assert head == tail || elements[head] != null;
+            // assert elements[tail] == null;
+            // assert head == tail || elements[dec(tail, capacity)] != null;
+        } catch (Throwable t) {
+            System.err.printf("head=%d tail=%d capacity=%d%n",
+                              head, tail, elements.length);
+            System.err.printf("elements=%s%n",
+                              Arrays.toString(elements));
+            throw t;
         }
     }
 
--- a/jdk/src/java.base/share/classes/java/util/ArrayList.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/ArrayList.java	Mon Nov 28 23:36:11 2016 -0800
@@ -104,7 +104,6 @@
  * @see     Vector
  * @since   1.2
  */
-
 public class ArrayList<E> extends AbstractList<E>
         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 {
@@ -424,6 +423,11 @@
         return (E) elementData[index];
     }
 
+    @SuppressWarnings("unchecked")
+    static <E> E elementAt(Object[] es, int index) {
+        return (E) es[index];
+    }
+
     /**
      * Returns the element at the specified position in this list.
      *
@@ -553,7 +557,7 @@
         return false;
     }
 
-    /*
+    /**
      * Private remove method that skips bounds checking and does not
      * return the value removed.
      */
@@ -572,11 +576,7 @@
      */
     public void clear() {
         modCount++;
-
-        // clear to let GC do its work
-        for (int i = 0; i < size; i++)
-            elementData[i] = null;
-
+        Arrays.fill(elementData, 0, size, null);
         size = 0;
     }
 
@@ -665,16 +665,10 @@
                     outOfBoundsMsg(fromIndex, toIndex));
         }
         modCount++;
-        int numMoved = size - toIndex;
-        System.arraycopy(elementData, toIndex, elementData, fromIndex,
-                         numMoved);
-
-        // clear to let GC do its work
-        int newSize = size - (toIndex-fromIndex);
-        for (int i = newSize; i < size; i++) {
-            elementData[i] = null;
-        }
-        size = newSize;
+        final Object[] es = elementData;
+        final int oldSize = size;
+        System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
+        Arrays.fill(es, size -= (toIndex - fromIndex), oldSize, null);
     }
 
     /**
@@ -717,8 +711,7 @@
      * @see Collection#contains(Object)
      */
     public boolean removeAll(Collection<?> c) {
-        Objects.requireNonNull(c);
-        return batchRemove(c, false);
+        return batchRemove(c, false, 0, size);
     }
 
     /**
@@ -738,34 +731,35 @@
      * @see Collection#contains(Object)
      */
     public boolean retainAll(Collection<?> c) {
-        Objects.requireNonNull(c);
-        return batchRemove(c, true);
+        return batchRemove(c, true, 0, size);
     }
 
-    private boolean batchRemove(Collection<?> c, boolean complement) {
-        final Object[] elementData = this.elementData;
-        int r = 0, w = 0;
-        boolean modified = false;
-        try {
-            for (; r < size; r++)
-                if (c.contains(elementData[r]) == complement)
-                    elementData[w++] = elementData[r];
-        } finally {
-            // Preserve behavioral compatibility with AbstractCollection,
-            // even if c.contains() throws.
-            if (r != size) {
-                System.arraycopy(elementData, r,
-                                 elementData, w,
-                                 size - r);
-                w += size - r;
-            }
-            if (w != size) {
-                // clear to let GC do its work
-                for (int i = w; i < size; i++)
-                    elementData[i] = null;
-                modCount += size - w;
-                size = w;
-                modified = true;
+    boolean batchRemove(Collection<?> c, boolean complement,
+                        final int from, final int end) {
+        Objects.requireNonNull(c);
+        final Object[] es = elementData;
+        final boolean modified;
+        int r;
+        // Optimize for initial run of survivors
+        for (r = from; r < end && c.contains(es[r]) == complement; r++)
+            ;
+        if (modified = (r < end)) {
+            int w = r++;
+            try {
+                for (Object e; r < end; r++)
+                    if (c.contains(e = es[r]) == complement)
+                        es[w++] = e;
+            } catch (Throwable ex) {
+                // Preserve behavioral compatibility with AbstractCollection,
+                // even if c.contains() throws.
+                System.arraycopy(es, r, es, w, end - r);
+                w += end - r;
+                throw ex;
+            } finally {
+                final int oldSize = size, deleted = end - w;
+                modCount += deleted;
+                System.arraycopy(es, end, es, w, oldSize - end);
+                Arrays.fill(es, size -= deleted, oldSize, null);
             }
         }
         return modified;
@@ -912,25 +906,21 @@
         }
 
         @Override
-        @SuppressWarnings("unchecked")
-        public void forEachRemaining(Consumer<? super E> consumer) {
-            Objects.requireNonNull(consumer);
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
             final int size = ArrayList.this.size;
             int i = cursor;
-            if (i >= size) {
-                return;
+            if (i < size) {
+                final Object[] es = elementData;
+                if (i >= es.length)
+                    throw new ConcurrentModificationException();
+                for (; i < size && modCount == expectedModCount; i++)
+                    action.accept(elementAt(es, i));
+                // update once at end to reduce heap write traffic
+                cursor = i;
+                lastRet = i - 1;
+                checkForComodification();
             }
-            final Object[] elementData = ArrayList.this.elementData;
-            if (i >= elementData.length) {
-                throw new ConcurrentModificationException();
-            }
-            while (i != size && modCount == expectedModCount) {
-                consumer.accept((E) elementData[i++]);
-            }
-            // update once at end of iteration to reduce heap write traffic
-            cursor = i;
-            lastRet = i - 1;
-            checkForComodification();
         }
 
         final void checkForComodification() {
@@ -1117,6 +1107,33 @@
             return true;
         }
 
+        public boolean removeAll(Collection<?> c) {
+            return batchRemove(c, false);
+        }
+
+        public boolean retainAll(Collection<?> c) {
+            return batchRemove(c, true);
+        }
+
+        private boolean batchRemove(Collection<?> c, boolean complement) {
+            checkForComodification();
+            int oldSize = root.size;
+            boolean modified =
+                root.batchRemove(c, complement, offset, offset + size);
+            if (modified)
+                updateSizeAndModCount(root.size - oldSize);
+            return modified;
+        }
+
+        public boolean removeIf(Predicate<? super E> filter) {
+            checkForComodification();
+            int oldSize = root.size;
+            boolean modified = root.removeIf(filter, offset, offset + size);
+            if (modified)
+                updateSizeAndModCount(root.size - oldSize);
+            return modified;
+        }
+
         public Iterator<E> iterator() {
             return listIterator();
         }
@@ -1164,24 +1181,21 @@
                     return (E) elementData[offset + (lastRet = i)];
                 }
 
-                @SuppressWarnings("unchecked")
-                public void forEachRemaining(Consumer<? super E> consumer) {
-                    Objects.requireNonNull(consumer);
+                public void forEachRemaining(Consumer<? super E> action) {
+                    Objects.requireNonNull(action);
                     final int size = SubList.this.size;
                     int i = cursor;
-                    if (i >= size) {
-                        return;
+                    if (i < size) {
+                        final Object[] es = root.elementData;
+                        if (offset + i >= es.length)
+                            throw new ConcurrentModificationException();
+                        for (; i < size && modCount == expectedModCount; i++)
+                            action.accept(elementAt(es, offset + i));
+                        // update once at end to reduce heap write traffic
+                        cursor = i;
+                        lastRet = i - 1;
+                        checkForComodification();
                     }
-                    final Object[] elementData = root.elementData;
-                    if (offset + i >= elementData.length) {
-                        throw new ConcurrentModificationException();
-                    }
-                    while (i != size && modCount == expectedModCount) {
-                        consumer.accept((E) elementData[offset + (i++)]);
-                    }
-                    // update once at end of iteration to reduce heap write traffic
-                    lastRet = cursor = i;
-                    checkForComodification();
                 }
 
                 public int nextIndex() {
@@ -1348,15 +1362,12 @@
     public void forEach(Consumer<? super E> action) {
         Objects.requireNonNull(action);
         final int expectedModCount = modCount;
-        @SuppressWarnings("unchecked")
-        final E[] elementData = (E[]) this.elementData;
+        final Object[] es = elementData;
         final int size = this.size;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            action.accept(elementData[i]);
-        }
-        if (modCount != expectedModCount) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
+            action.accept(elementAt(es, i));
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
     }
 
     /**
@@ -1417,7 +1428,7 @@
         private int fence; // -1 until used; then one past last index
         private int expectedModCount; // initialized when fence set
 
-        /** Create new spliterator covering the given  range */
+        /** Create new spliterator covering the given range */
         ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                              int expectedModCount) {
             this.list = list; // OK if null unless traversed
@@ -1495,61 +1506,73 @@
         }
     }
 
-    @Override
-    public boolean removeIf(Predicate<? super E> filter) {
-        Objects.requireNonNull(filter);
-        // figure out which elements are to be removed
-        // any exception thrown from the filter predicate at this stage
-        // will leave the collection unmodified
-        int removeCount = 0;
-        final BitSet removeSet = new BitSet(size);
-        final int expectedModCount = modCount;
-        final int size = this.size;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            @SuppressWarnings("unchecked")
-            final E element = (E) elementData[i];
-            if (filter.test(element)) {
-                removeSet.set(i);
-                removeCount++;
-            }
-        }
-        if (modCount != expectedModCount) {
-            throw new ConcurrentModificationException();
-        }
+    // A tiny bit set implementation
 
-        // shift surviving elements left over the spaces left by removed elements
-        final boolean anyToRemove = removeCount > 0;
-        if (anyToRemove) {
-            final int newSize = size - removeCount;
-            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
-                i = removeSet.nextClearBit(i);
-                elementData[j] = elementData[i];
-            }
-            for (int k=newSize; k < size; k++) {
-                elementData[k] = null;  // Let gc do its work
-            }
-            this.size = newSize;
-            if (modCount != expectedModCount) {
-                throw new ConcurrentModificationException();
-            }
-            modCount++;
-        }
-
-        return anyToRemove;
+    private static long[] nBits(int n) {
+        return new long[((n - 1) >> 6) + 1];
+    }
+    private static void setBit(long[] bits, int i) {
+        bits[i >> 6] |= 1L << i;
+    }
+    private static boolean isClear(long[] bits, int i) {
+        return (bits[i >> 6] & (1L << i)) == 0;
     }
 
     @Override
-    @SuppressWarnings("unchecked")
+    public boolean removeIf(Predicate<? super E> filter) {
+        return removeIf(filter, 0, size);
+    }
+
+    /**
+     * Removes all elements satisfying the given predicate, from index
+     * i (inclusive) to index end (exclusive).
+     */
+    boolean removeIf(Predicate<? super E> filter, int i, final int end) {
+        Objects.requireNonNull(filter);
+        int expectedModCount = modCount;
+        final Object[] es = elementData;
+        // Optimize for initial run of survivors
+        for (; i < end && !filter.test(elementAt(es, i)); i++)
+            ;
+        // Tolerate predicates that reentrantly access the collection for
+        // read (but writers still get CME), so traverse once to find
+        // elements to delete, a second pass to physically expunge.
+        if (i < end) {
+            final int beg = i;
+            final long[] deathRow = nBits(end - beg);
+            deathRow[0] = 1L;   // set bit 0
+            for (i = beg + 1; i < end; i++)
+                if (filter.test(elementAt(es, i)))
+                    setBit(deathRow, i - beg);
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            expectedModCount++;
+            modCount++;
+            int w = beg;
+            for (i = beg; i < end; i++)
+                if (isClear(deathRow, i - beg))
+                    es[w++] = es[i];
+            final int oldSize = size;
+            System.arraycopy(es, end, es, w, oldSize - end);
+            Arrays.fill(es, size -= (end - w), oldSize, null);
+            return true;
+        } else {
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            return false;
+        }
+    }
+
+    @Override
     public void replaceAll(UnaryOperator<E> operator) {
         Objects.requireNonNull(operator);
         final int expectedModCount = modCount;
+        final Object[] es = elementData;
         final int size = this.size;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            elementData[i] = operator.apply((E) elementData[i]);
-        }
-        if (modCount != expectedModCount) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
+            es[i] = operator.apply(elementAt(es, i));
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
     }
 
@@ -1558,9 +1581,13 @@
     public void sort(Comparator<? super E> c) {
         final int expectedModCount = modCount;
         Arrays.sort((E[]) elementData, 0, size, c);
-        if (modCount != expectedModCount) {
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
     }
+
+    void checkInvariants() {
+        // assert size >= 0;
+        // assert size == elementData.length || elementData[size] == null;
+    }
 }
--- a/jdk/src/java.base/share/classes/java/util/Vector.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/Vector.java	Mon Nov 28 23:36:11 2016 -0800
@@ -513,7 +513,7 @@
      * Returns the last component of the vector.
      *
      * @return  the last component of the vector, i.e., the component at index
-     *          <code>size()&nbsp;-&nbsp;1</code>.
+     *          {@code size() - 1}
      * @throws NoSuchElementException if this vector is empty
      */
     public synchronized E lastElement() {
@@ -675,10 +675,7 @@
      * method (which is part of the {@link List} interface).
      */
     public synchronized void removeAllElements() {
-        // Let gc do its work
-        for (int i = 0; i < elementCount; i++)
-            elementData[i] = null;
-
+        Arrays.fill(elementData, 0, elementCount, null);
         modCount++;
         elementCount = 0;
     }
@@ -693,7 +690,7 @@
     public synchronized Object clone() {
         try {
             @SuppressWarnings("unchecked")
-                Vector<E> v = (Vector<E>) super.clone();
+            Vector<E> v = (Vector<E>) super.clone();
             v.elementData = Arrays.copyOf(elementData, elementCount);
             v.modCount = 0;
             return v;
@@ -759,6 +756,11 @@
         return (E) elementData[index];
     }
 
+    @SuppressWarnings("unchecked")
+    static <E> E elementAt(Object[] es, int index) {
+        return (E) es[index];
+    }
+
     /**
      * Returns the element at the specified position in this Vector.
      *
@@ -855,10 +857,10 @@
      * Shifts any subsequent elements to the left (subtracts one from their
      * indices).  Returns the element that was removed from the Vector.
      *
+     * @param index the index of the element to be removed
+     * @return element that was removed
      * @throws ArrayIndexOutOfBoundsException if the index is out of range
      *         ({@code index < 0 || index >= size()})
-     * @param index the index of the element to be removed
-     * @return element that was removed
      * @since 1.2
      */
     public synchronized E remove(int index) {
@@ -949,8 +951,9 @@
      *         or if the specified collection is null
      * @since 1.2
      */
-    public synchronized boolean removeAll(Collection<?> c) {
-        return super.removeAll(c);
+    public boolean removeAll(Collection<?> c) {
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> c.contains(e));
     }
 
     /**
@@ -972,8 +975,62 @@
      *         or if the specified collection is null
      * @since 1.2
      */
-    public synchronized boolean retainAll(Collection<?> c) {
-        return super.retainAll(c);
+    public boolean retainAll(Collection<?> c) {
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> !c.contains(e));
+    }
+
+    @Override
+    public boolean removeIf(Predicate<? super E> filter) {
+        Objects.requireNonNull(filter);
+        return bulkRemove(filter);
+    }
+
+    // A tiny bit set implementation
+
+    private static long[] nBits(int n) {
+        return new long[((n - 1) >> 6) + 1];
+    }
+    private static void setBit(long[] bits, int i) {
+        bits[i >> 6] |= 1L << i;
+    }
+    private static boolean isClear(long[] bits, int i) {
+        return (bits[i >> 6] & (1L << i)) == 0;
+    }
+
+    private synchronized boolean bulkRemove(Predicate<? super E> filter) {
+        int expectedModCount = modCount;
+        final Object[] es = elementData;
+        final int end = elementCount;
+        int i;
+        // Optimize for initial run of survivors
+        for (i = 0; i < end && !filter.test(elementAt(es, i)); i++)
+            ;
+        // Tolerate predicates that reentrantly access the collection for
+        // read (but writers still get CME), so traverse once to find
+        // elements to delete, a second pass to physically expunge.
+        if (i < end) {
+            final int beg = i;
+            final long[] deathRow = nBits(end - beg);
+            deathRow[0] = 1L;   // set bit 0
+            for (i = beg + 1; i < end; i++)
+                if (filter.test(elementAt(es, i)))
+                    setBit(deathRow, i - beg);
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            expectedModCount++;
+            modCount++;
+            int w = beg;
+            for (i = beg; i < end; i++)
+                if (isClear(deathRow, i - beg))
+                    es[w++] = es[i];
+            Arrays.fill(es, elementCount = w, end, null);
+            return true;
+        } else {
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            return false;
+        }
     }
 
     /**
@@ -1095,15 +1152,12 @@
      * (If {@code toIndex==fromIndex}, this operation has no effect.)
      */
     protected synchronized void removeRange(int fromIndex, int toIndex) {
-        int numMoved = elementCount - toIndex;
-        System.arraycopy(elementData, toIndex, elementData, fromIndex,
-                         numMoved);
+        final Object[] es = elementData;
+        final int oldSize = elementCount;
+        System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
 
-        // Let gc do its work
         modCount++;
-        int newElementCount = elementCount - (toIndex-fromIndex);
-        while (elementCount != newElementCount)
-            elementData[--elementCount] = null;
+        Arrays.fill(es, elementCount -= (toIndex - fromIndex), oldSize, null);
     }
 
     /**
@@ -1212,14 +1266,11 @@
                 if (i >= size) {
                     return;
                 }
-        @SuppressWarnings("unchecked")
-                final E[] elementData = (E[]) Vector.this.elementData;
-                if (i >= elementData.length) {
+                final Object[] es = elementData;
+                if (i >= es.length)
                     throw new ConcurrentModificationException();
-                }
-                while (i != size && modCount == expectedModCount) {
-                    action.accept(elementData[i++]);
-                }
+                while (i < size && modCount == expectedModCount)
+                    action.accept(elementAt(es, i++));
                 // update once at end of iteration to reduce heap write traffic
                 cursor = i;
                 lastRet = i - 1;
@@ -1290,73 +1341,24 @@
     public synchronized void forEach(Consumer<? super E> action) {
         Objects.requireNonNull(action);
         final int expectedModCount = modCount;
-        @SuppressWarnings("unchecked")
-        final E[] elementData = (E[]) this.elementData;
-        final int elementCount = this.elementCount;
-        for (int i=0; modCount == expectedModCount && i < elementCount; i++) {
-            action.accept(elementData[i]);
-        }
-        if (modCount != expectedModCount) {
+        final Object[] es = elementData;
+        final int size = elementCount;
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
+            action.accept(elementAt(es, i));
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
     }
 
     @Override
-    @SuppressWarnings("unchecked")
-    public synchronized boolean removeIf(Predicate<? super E> filter) {
-        Objects.requireNonNull(filter);
-        // figure out which elements are to be removed
-        // any exception thrown from the filter predicate at this stage
-        // will leave the collection unmodified
-        int removeCount = 0;
-        final int size = elementCount;
-        final BitSet removeSet = new BitSet(size);
-        final int expectedModCount = modCount;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            @SuppressWarnings("unchecked")
-            final E element = (E) elementData[i];
-            if (filter.test(element)) {
-                removeSet.set(i);
-                removeCount++;
-            }
-        }
-        if (modCount != expectedModCount) {
-            throw new ConcurrentModificationException();
-        }
-
-        // shift surviving elements left over the spaces left by removed elements
-        final boolean anyToRemove = removeCount > 0;
-        if (anyToRemove) {
-            final int newSize = size - removeCount;
-            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
-                i = removeSet.nextClearBit(i);
-                elementData[j] = elementData[i];
-            }
-            for (int k=newSize; k < size; k++) {
-                elementData[k] = null;  // Let gc do its work
-            }
-            elementCount = newSize;
-            if (modCount != expectedModCount) {
-                throw new ConcurrentModificationException();
-            }
-            modCount++;
-        }
-
-        return anyToRemove;
-    }
-
-    @Override
-    @SuppressWarnings("unchecked")
     public synchronized void replaceAll(UnaryOperator<E> operator) {
         Objects.requireNonNull(operator);
         final int expectedModCount = modCount;
+        final Object[] es = elementData;
         final int size = elementCount;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            elementData[i] = operator.apply((E) elementData[i]);
-        }
-        if (modCount != expectedModCount) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
+            es[i] = operator.apply(elementAt(es, i));
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
     }
 
@@ -1365,9 +1367,8 @@
     public synchronized void sort(Comparator<? super E> c) {
         final int expectedModCount = modCount;
         Arrays.sort((E[]) elementData, 0, elementCount, c);
-        if (modCount != expectedModCount) {
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
     }
 
@@ -1397,7 +1398,7 @@
         private int fence; // -1 until used; then one past last index
         private int expectedModCount; // initialized when fence set
 
-        /** Create new spliterator covering the given  range */
+        /** Create new spliterator covering the given range */
         VectorSpliterator(Vector<E> list, Object[] array, int origin, int fence,
                           int expectedModCount) {
             this.list = list;
@@ -1410,7 +1411,7 @@
         private int getFence() { // initialize on first use
             int hi;
             if ((hi = fence) < 0) {
-                synchronized(list) {
+                synchronized (list) {
                     array = list.elementData;
                     expectedModCount = list.modCount;
                     hi = fence = list.elementCount;
@@ -1449,7 +1450,7 @@
                 throw new NullPointerException();
             if ((lst = list) != null) {
                 if ((hi = fence) < 0) {
-                    synchronized(lst) {
+                    synchronized (lst) {
                         expectedModCount = lst.modCount;
                         a = array = lst.elementData;
                         hi = fence = lst.elementCount;
@@ -1475,4 +1476,9 @@
             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
         }
     }
+
+    void checkInvariants() {
+        // assert elementCount >= 0;
+        // assert elementCount == elementData.length || elementData[elementCount] == null;
+    }
 }
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java	Mon Nov 28 23:36:11 2016 -0800
@@ -46,6 +46,8 @@
 import java.util.Spliterators;
 import java.util.concurrent.locks.Condition;
 import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
 
 /**
  * A bounded {@linkplain BlockingQueue blocking queue} backed by an
@@ -85,6 +87,11 @@
 public class ArrayBlockingQueue<E> extends AbstractQueue<E>
         implements BlockingQueue<E>, java.io.Serializable {
 
+    /*
+     * Much of the implementation mechanics, especially the unusual
+     * nested loops, are shared and co-maintained with ArrayDeque.
+     */
+
     /**
      * Serialization ID. This class relies on default serialization
      * even for the items array, which is default-serialized, even if
@@ -129,10 +136,21 @@
     // Internal helper methods
 
     /**
-     * Circularly decrements array index i.
+     * Increments i, mod modulus.
+     * Precondition and postcondition: 0 <= i < modulus.
      */
-    final int dec(int i) {
-        return ((i == 0) ? items.length : i) - 1;
+    static final int inc(int i, int modulus) {
+        if (++i >= modulus) i = 0;
+        return i;
+    }
+
+    /**
+     * Decrements i, mod modulus.
+     * Precondition and postcondition: 0 <= i < modulus.
+     */
+    static final int dec(int i, int modulus) {
+        if (--i < 0) i = modulus - 1;
+        return i;
     }
 
     /**
@@ -144,14 +162,24 @@
     }
 
     /**
+     * Returns element at array index i.
+     * This is a slight abuse of generics, accepted by javac.
+     */
+    @SuppressWarnings("unchecked")
+    static <E> E itemAt(Object[] items, int i) {
+        return (E) items[i];
+    }
+
+    /**
      * Inserts element at current put position, advances, and signals.
      * Call only when holding lock.
      */
-    private void enqueue(E x) {
+    private void enqueue(E e) {
+        // assert lock.isHeldByCurrentThread();
         // assert lock.getHoldCount() == 1;
         // assert items[putIndex] == null;
         final Object[] items = this.items;
-        items[putIndex] = x;
+        items[putIndex] = e;
         if (++putIndex == items.length) putIndex = 0;
         count++;
         notEmpty.signal();
@@ -162,18 +190,19 @@
      * Call only when holding lock.
      */
     private E dequeue() {
+        // assert lock.isHeldByCurrentThread();
         // assert lock.getHoldCount() == 1;
         // assert items[takeIndex] != null;
         final Object[] items = this.items;
         @SuppressWarnings("unchecked")
-        E x = (E) items[takeIndex];
+        E e = (E) items[takeIndex];
         items[takeIndex] = null;
         if (++takeIndex == items.length) takeIndex = 0;
         count--;
         if (itrs != null)
             itrs.elementDequeued();
         notFull.signal();
-        return x;
+        return e;
     }
 
     /**
@@ -182,6 +211,7 @@
      * Call only when holding lock.
      */
     void removeAt(final int removeIndex) {
+        // assert lock.isHeldByCurrentThread();
         // assert lock.getHoldCount() == 1;
         // assert items[removeIndex] != null;
         // assert removeIndex >= 0 && removeIndex < items.length;
@@ -267,6 +297,7 @@
         final ReentrantLock lock = this.lock;
         lock.lock(); // Lock only for visibility, not mutual exclusion
         try {
+            final Object[] items = this.items;
             int i = 0;
             try {
                 for (E e : c)
@@ -481,15 +512,16 @@
         try {
             if (count > 0) {
                 final Object[] items = this.items;
-                final int putIndex = this.putIndex;
-                int i = takeIndex;
-                do {
-                    if (o.equals(items[i])) {
-                        removeAt(i);
-                        return true;
-                    }
-                    if (++i == items.length) i = 0;
-                } while (i != putIndex);
+                for (int i = takeIndex, end = putIndex,
+                         to = (i < end) ? end : items.length;
+                     ; i = 0, to = end) {
+                    for (; i < to; i++)
+                        if (o.equals(items[i])) {
+                            removeAt(i);
+                            return true;
+                        }
+                    if (to == end) break;
+                }
             }
             return false;
         } finally {
@@ -512,13 +544,14 @@
         try {
             if (count > 0) {
                 final Object[] items = this.items;
-                final int putIndex = this.putIndex;
-                int i = takeIndex;
-                do {
-                    if (o.equals(items[i]))
-                        return true;
-                    if (++i == items.length) i = 0;
-                } while (i != putIndex);
+                for (int i = takeIndex, end = putIndex,
+                         to = (i < end) ? end : items.length;
+                     ; i = 0, to = end) {
+                    for (; i < to; i++)
+                        if (o.equals(items[i]))
+                            return true;
+                    if (to == end) break;
+                }
             }
             return false;
         } finally {
@@ -625,15 +658,9 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            int k = count;
-            if (k > 0) {
-                final Object[] items = this.items;
-                final int putIndex = this.putIndex;
-                int i = takeIndex;
-                do {
-                    items[i] = null;
-                    if (++i == items.length) i = 0;
-                } while (i != putIndex);
+            int k;
+            if ((k = count) > 0) {
+                circularClear(items, takeIndex, putIndex);
                 takeIndex = putIndex;
                 count = 0;
                 if (itrs != null)
@@ -647,6 +674,18 @@
     }
 
     /**
+     * Nulls out slots starting at array index i, upto index end.
+     * If i == end, the entire array is cleared!
+     */
+    private static void circularClear(Object[] items, int i, int end) {
+        for (int to = (i < end) ? end : items.length;
+             ; i = 0, to = end) {
+            Arrays.fill(items, i, to, null);
+            if (to == end) break;
+        }
+    }
+
+    /**
      * @throws UnsupportedOperationException {@inheritDoc}
      * @throws ClassCastException            {@inheritDoc}
      * @throws NullPointerException          {@inheritDoc}
@@ -678,8 +717,8 @@
             try {
                 while (i < n) {
                     @SuppressWarnings("unchecked")
-                    E x = (E) items[take];
-                    c.add(x);
+                    E e = (E) items[take];
+                    c.add(e);
                     items[take] = null;
                     if (++take == items.length) take = 0;
                     i++;
@@ -808,7 +847,7 @@
          * there is known to be at least one iterator to collect
          */
         void doSomeSweeping(boolean tryHarder) {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             // assert head != null;
             int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES;
             Node o, p;
@@ -864,7 +903,7 @@
          * Adds a new iterator to the linked list of tracked iterators.
          */
         void register(Itr itr) {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             head = new Node(itr, head);
         }
 
@@ -874,7 +913,7 @@
          * Notifies all iterators, and expunges any that are now stale.
          */
         void takeIndexWrapped() {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             cycles++;
             for (Node o = null, p = head; p != null;) {
                 final Itr it = p.get();
@@ -931,7 +970,7 @@
          * clears all weak refs, and unlinks the itrs datastructure.
          */
         void queueIsEmpty() {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             for (Node p = head; p != null; p = p.next) {
                 Itr it = p.get();
                 if (it != null) {
@@ -947,7 +986,7 @@
          * Called whenever an element has been dequeued (at takeIndex).
          */
         void elementDequeued() {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             if (count == 0)
                 queueIsEmpty();
             else if (takeIndex == 0)
@@ -1008,7 +1047,6 @@
         private static final int DETACHED = -3;
 
         Itr() {
-            // assert lock.getHoldCount() == 0;
             lastRet = NONE;
             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
             lock.lock();
@@ -1041,12 +1079,12 @@
         }
 
         boolean isDetached() {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             return prevTakeIndex < 0;
         }
 
         private int incCursor(int index) {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             if (++index == items.length) index = 0;
             if (index == putIndex) index = NONE;
             return index;
@@ -1071,7 +1109,7 @@
          * operation on this iterator.  Call only from iterating thread.
          */
         private void incorporateDequeues() {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             // assert itrs != null;
             // assert !isDetached();
             // assert count > 0;
@@ -1114,7 +1152,7 @@
          */
         private void detach() {
             // Switch to detached mode
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             // assert cursor == NONE;
             // assert nextIndex < 0;
             // assert lastRet < 0 || nextItem == null;
@@ -1134,7 +1172,6 @@
          * triggered by queue modifications.
          */
         public boolean hasNext() {
-            // assert lock.getHoldCount() == 0;
             if (nextItem != null)
                 return true;
             noNext();
@@ -1164,9 +1201,8 @@
         }
 
         public E next() {
-            // assert lock.getHoldCount() == 0;
-            final E x = nextItem;
-            if (x == null)
+            final E e = nextItem;
+            if (e == null)
                 throw new NoSuchElementException();
             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
             lock.lock();
@@ -1188,13 +1224,43 @@
             } finally {
                 lock.unlock();
             }
-            return x;
+            return e;
+        }
+
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            final ReentrantLock lock = ArrayBlockingQueue.this.lock;
+            lock.lock();
+            try {
+                final E e = nextItem;
+                if (e == null) return;
+                if (!isDetached())
+                    incorporateDequeues();
+                action.accept(e);
+                if (isDetached() || cursor < 0) return;
+                final Object[] items = ArrayBlockingQueue.this.items;
+                for (int i = cursor, end = putIndex,
+                         to = (i < end) ? end : items.length;
+                     ; i = 0, to = end) {
+                    for (; i < to; i++)
+                        action.accept(itemAt(items, i));
+                    if (to == end) break;
+                }
+            } finally {
+                // Calling forEachRemaining is a strong hint that this
+                // iteration is surely over; supporting remove() after
+                // forEachRemaining() is more trouble than it's worth
+                cursor = nextIndex = lastRet = NONE;
+                nextItem = lastItem = null;
+                detach();
+                lock.unlock();
+            }
         }
 
         public void remove() {
-            // assert lock.getHoldCount() == 0;
             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
             lock.lock();
+            // assert lock.getHoldCount() == 1;
             try {
                 if (!isDetached())
                     incorporateDequeues(); // might update lastRet or detach
@@ -1232,7 +1298,7 @@
          * from next(), as promised by returning true from hasNext().
          */
         void shutdown() {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             cursor = NONE;
             if (nextIndex >= 0)
                 nextIndex = REMOVED;
@@ -1260,7 +1326,7 @@
          * @return true if this iterator should be unlinked from itrs
          */
         boolean removedAt(int removedIndex) {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             if (isDetached())
                 return true;
 
@@ -1285,7 +1351,7 @@
                 }
                 else if (x > removedDistance) {
                     // assert cursor != prevTakeIndex;
-                    this.cursor = cursor = dec(cursor);
+                    this.cursor = cursor = dec(cursor, len);
                 }
             }
             int lastRet = this.lastRet;
@@ -1294,7 +1360,7 @@
                 if (x == removedDistance)
                     this.lastRet = lastRet = REMOVED;
                 else if (x > removedDistance)
-                    this.lastRet = lastRet = dec(lastRet);
+                    this.lastRet = lastRet = dec(lastRet, len);
             }
             int nextIndex = this.nextIndex;
             if (nextIndex >= 0) {
@@ -1302,7 +1368,7 @@
                 if (x == removedDistance)
                     this.nextIndex = nextIndex = REMOVED;
                 else if (x > removedDistance)
-                    this.nextIndex = nextIndex = dec(nextIndex);
+                    this.nextIndex = nextIndex = dec(nextIndex, len);
             }
             if (cursor < 0 && nextIndex < 0 && lastRet < 0) {
                 this.prevTakeIndex = DETACHED;
@@ -1317,7 +1383,7 @@
          * @return true if this iterator should be unlinked from itrs
          */
         boolean takeIndexWrapped() {
-            // assert lock.getHoldCount() == 1;
+            // assert lock.isHeldByCurrentThread();
             if (isDetached())
                 return true;
             if (itrs.cycles - prevCycles > 1) {
@@ -1366,4 +1432,170 @@
                     Spliterator.CONCURRENT));
     }
 
+    public void forEach(Consumer<? super E> action) {
+        Objects.requireNonNull(action);
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            if (count > 0) {
+                final Object[] items = this.items;
+                for (int i = takeIndex, end = putIndex,
+                         to = (i < end) ? end : items.length;
+                     ; i = 0, to = end) {
+                    for (; i < to; i++)
+                        action.accept(itemAt(items, i));
+                    if (to == end) break;
+                }
+            }
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public boolean removeIf(Predicate<? super E> filter) {
+        Objects.requireNonNull(filter);
+        return bulkRemove(filter);
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public boolean removeAll(Collection<?> c) {
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> c.contains(e));
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public boolean retainAll(Collection<?> c) {
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> !c.contains(e));
+    }
+
+    /** Implementation of bulk remove methods. */
+    private boolean bulkRemove(Predicate<? super E> filter) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            if (itrs == null) { // check for active iterators
+                if (count > 0) {
+                    final Object[] items = this.items;
+                    // Optimize for initial run of survivors
+                    for (int i = takeIndex, end = putIndex,
+                             to = (i < end) ? end : items.length;
+                         ; i = 0, to = end) {
+                        for (; i < to; i++)
+                            if (filter.test(itemAt(items, i)))
+                                return bulkRemoveModified(filter, i);
+                        if (to == end) break;
+                    }
+                }
+                return false;
+            }
+        } finally {
+            lock.unlock();
+        }
+        // Active iterators are too hairy!
+        // Punting (for now) to the slow n^2 algorithm ...
+        return super.removeIf(filter);
+    }
+
+    // A tiny bit set implementation
+
+    private static long[] nBits(int n) {
+        return new long[((n - 1) >> 6) + 1];
+    }
+    private static void setBit(long[] bits, int i) {
+        bits[i >> 6] |= 1L << i;
+    }
+    private static boolean isClear(long[] bits, int i) {
+        return (bits[i >> 6] & (1L << i)) == 0;
+    }
+
+    /**
+     * Returns circular distance from i to j, disambiguating i == j to
+     * items.length; never returns 0.
+     */
+    private int distanceNonEmpty(int i, int j) {
+        if ((j -= i) <= 0) j += items.length;
+        return j;
+    }
+
+    /**
+     * Helper for bulkRemove, in case of at least one deletion.
+     * Tolerate predicates that reentrantly access the collection for
+     * read (but not write), so traverse once to find elements to
+     * delete, a second pass to physically expunge.
+     *
+     * @param beg valid index of first element to be deleted
+     */
+    private boolean bulkRemoveModified(
+        Predicate<? super E> filter, final int beg) {
+        final Object[] es = items;
+        final int capacity = items.length;
+        final int end = putIndex;
+        final long[] deathRow = nBits(distanceNonEmpty(beg, putIndex));
+        deathRow[0] = 1L;   // set bit 0
+        for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+             ; i = 0, to = end, k -= capacity) {
+            for (; i < to; i++)
+                if (filter.test(itemAt(es, i)))
+                    setBit(deathRow, i - k);
+            if (to == end) break;
+        }
+        // a two-finger traversal, with hare i reading, tortoise w writing
+        int w = beg;
+        for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+             ; w = 0) { // w rejoins i on second leg
+            // In this loop, i and w are on the same leg, with i > w
+            for (; i < to; i++)
+                if (isClear(deathRow, i - k))
+                    es[w++] = es[i];
+            if (to == end) break;
+            // In this loop, w is on the first leg, i on the second
+            for (i = 0, to = end, k -= capacity; i < to && w < capacity; i++)
+                if (isClear(deathRow, i - k))
+                    es[w++] = es[i];
+            if (i >= to) {
+                if (w == capacity) w = 0; // "corner" case
+                break;
+            }
+        }
+        count -= distanceNonEmpty(w, end);
+        circularClear(es, putIndex = w, end);
+        return true;
+    }
+
+    /** debugging */
+    void checkInvariants() {
+        // meta-assertions
+        // assert lock.isHeldByCurrentThread();
+        try {
+            // Unlike ArrayDeque, we have a count field but no spare slot.
+            // We prefer ArrayDeque's strategy (and the names of its fields!),
+            // but our field layout is baked into the serial form, and so is
+            // too annoying to change.
+            //
+            // putIndex == takeIndex must be disambiguated by checking count.
+            int capacity = items.length;
+            // assert capacity > 0;
+            // assert takeIndex >= 0 && takeIndex < capacity;
+            // assert putIndex >= 0 && putIndex < capacity;
+            // assert count <= capacity;
+            // assert takeIndex == putIndex || items[takeIndex] != null;
+            // assert count == capacity || items[putIndex] == null;
+            // assert takeIndex == putIndex || items[dec(putIndex, capacity)] != null;
+        } catch (Throwable t) {
+            System.err.printf("takeIndex=%d putIndex=%d count=%d capacity=%d%n",
+                              takeIndex, putIndex, count, items.length);
+            System.err.printf("items=%s%n",
+                              Arrays.toString(items));
+            throw t;
+        }
+    }
+
 }
--- a/jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Mon Nov 28 23:36:11 2016 -0800
@@ -380,7 +380,7 @@
     // Positional Access Operations
 
     @SuppressWarnings("unchecked")
-    private E get(Object[] a, int index) {
+    static <E> E elementAt(Object[] a, int index) {
         return (E) a[index];
     }
 
@@ -394,7 +394,7 @@
      * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public E get(int index) {
-        return get(getArray(), index);
+        return elementAt(getArray(), index);
     }
 
     /**
@@ -406,7 +406,7 @@
     public E set(int index, E element) {
         synchronized (lock) {
             Object[] elements = getArray();
-            E oldValue = get(elements, index);
+            E oldValue = elementAt(elements, index);
 
             if (oldValue != element) {
                 int len = elements.length;
@@ -477,7 +477,7 @@
         synchronized (lock) {
             Object[] elements = getArray();
             int len = elements.length;
-            E oldValue = get(elements, index);
+            E oldValue = elementAt(elements, index);
             int numMoved = len - index - 1;
             if (numMoved == 0)
                 setArray(Arrays.copyOf(elements, len - 1));
@@ -644,34 +644,16 @@
      * @return {@code true} if this list changed as a result of the call
      * @throws ClassCastException if the class of an element of this list
      *         is incompatible with the specified collection
-     * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>)
+     * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
      * @throws NullPointerException if this list contains a null element and the
      *         specified collection does not permit null elements
-     * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>),
+     * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>),
      *         or if the specified collection is null
      * @see #remove(Object)
      */
     public boolean removeAll(Collection<?> c) {
-        if (c == null) throw new NullPointerException();
-        synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
-            if (len != 0) {
-                // temp array holds those elements we know we want to keep
-                int newlen = 0;
-                Object[] temp = new Object[len];
-                for (int i = 0; i < len; ++i) {
-                    Object element = elements[i];
-                    if (!c.contains(element))
-                        temp[newlen++] = element;
-                }
-                if (newlen != len) {
-                    setArray(Arrays.copyOf(temp, newlen));
-                    return true;
-                }
-            }
-            return false;
-        }
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> c.contains(e));
     }
 
     /**
@@ -683,34 +665,16 @@
      * @return {@code true} if this list changed as a result of the call
      * @throws ClassCastException if the class of an element of this list
      *         is incompatible with the specified collection
-     * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>)
+     * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
      * @throws NullPointerException if this list contains a null element and the
      *         specified collection does not permit null elements
-     * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>),
+     * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>),
      *         or if the specified collection is null
      * @see #remove(Object)
      */
     public boolean retainAll(Collection<?> c) {
-        if (c == null) throw new NullPointerException();
-        synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
-            if (len != 0) {
-                // temp array holds those elements we know we want to keep
-                int newlen = 0;
-                Object[] temp = new Object[len];
-                for (int i = 0; i < len; ++i) {
-                    Object element = elements[i];
-                    if (c.contains(element))
-                        temp[newlen++] = element;
-                }
-                if (newlen != len) {
-                    setArray(Arrays.copyOf(temp, newlen));
-                    return true;
-                }
-            }
-            return false;
-        }
+        Objects.requireNonNull(c);
+        return bulkRemove(e -> !c.contains(e));
     }
 
     /**
@@ -839,55 +803,90 @@
 
     public boolean removeIf(Predicate<? super E> filter) {
         if (filter == null) throw new NullPointerException();
+        return bulkRemove(filter);
+    }
+
+    // A tiny bit set implementation
+
+    private static long[] nBits(int n) {
+        return new long[((n - 1) >> 6) + 1];
+    }
+    private static void setBit(long[] bits, int i) {
+        bits[i >> 6] |= 1L << i;
+    }
+    private static boolean isClear(long[] bits, int i) {
+        return (bits[i >> 6] & (1L << i)) == 0;
+    }
+
+    private boolean bulkRemove(Predicate<? super E> filter) {
         synchronized (lock) {
-            final Object[] elements = getArray();
-            final int len = elements.length;
-            int i;
-            for (i = 0; i < len; i++) {
-                @SuppressWarnings("unchecked") E e = (E) elements[i];
-                if (filter.test(e)) {
-                    int newlen = i;
-                    final Object[] newElements = new Object[len - 1];
-                    System.arraycopy(elements, 0, newElements, 0, newlen);
-                    for (i++; i < len; i++) {
-                        @SuppressWarnings("unchecked") E x = (E) elements[i];
-                        if (!filter.test(x))
-                            newElements[newlen++] = x;
-                    }
-                    setArray((newlen == len - 1)
-                             ? newElements // one match => one copy
-                             : Arrays.copyOf(newElements, newlen));
-                    return true;
+            return bulkRemove(filter, 0, getArray().length);
+        }
+    }
+
+    boolean bulkRemove(Predicate<? super E> filter, int i, int end) {
+        // assert Thread.holdsLock(lock);
+        final Object[] es = getArray();
+        // Optimize for initial run of survivors
+        for (; i < end && !filter.test(elementAt(es, i)); i++)
+            ;
+        if (i < end) {
+            final int beg = i;
+            final long[] deathRow = nBits(end - beg);
+            int deleted = 1;
+            deathRow[0] = 1L;   // set bit 0
+            for (i = beg + 1; i < end; i++)
+                if (filter.test(elementAt(es, i))) {
+                    setBit(deathRow, i - beg);
+                    deleted++;
                 }
-            }
-            return false;       // zero matches => zero copies
+            // Did filter reentrantly modify the list?
+            if (es != getArray())
+                throw new ConcurrentModificationException();
+            final Object[] newElts = Arrays.copyOf(es, es.length - deleted);
+            int w = beg;
+            for (i = beg; i < end; i++)
+                if (isClear(deathRow, i - beg))
+                    newElts[w++] = es[i];
+            System.arraycopy(es, i, newElts, w, es.length - i);
+            setArray(newElts);
+            return true;
+        } else {
+            if (es != getArray())
+                throw new ConcurrentModificationException();
+            return false;
         }
     }
 
     public void replaceAll(UnaryOperator<E> operator) {
         if (operator == null) throw new NullPointerException();
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
-            Object[] newElements = Arrays.copyOf(elements, len);
-            for (int i = 0; i < len; ++i) {
-                @SuppressWarnings("unchecked") E e = (E) elements[i];
-                newElements[i] = operator.apply(e);
-            }
-            setArray(newElements);
+            replaceAll(operator, 0, getArray().length);
         }
     }
 
+    void replaceAll(UnaryOperator<E> operator, int i, int end) {
+        // assert Thread.holdsLock(lock);
+        final Object[] es = getArray().clone();
+        for (; i < end; i++)
+            es[i] = operator.apply(elementAt(es, i));
+        setArray(es);
+    }
+
     public void sort(Comparator<? super E> c) {
         synchronized (lock) {
-            Object[] elements = getArray();
-            Object[] newElements = Arrays.copyOf(elements, elements.length);
-            @SuppressWarnings("unchecked") E[] es = (E[])newElements;
-            Arrays.sort(es, c);
-            setArray(newElements);
+            sort(c, 0, getArray().length);
         }
     }
 
+    @SuppressWarnings("unchecked")
+    void sort(Comparator<? super E> c, int i, int end) {
+        // assert Thread.holdsLock(lock);
+        final Object[] es = getArray().clone();
+        Arrays.sort(es, i, end, (Comparator<Object>)c);
+        setArray(es);
+    }
+
     /**
      * Saves this list to a stream (that is, serializes it).
      *
@@ -1167,18 +1166,6 @@
 
     /**
      * Sublist for CopyOnWriteArrayList.
-     * This class extends AbstractList merely for convenience, to
-     * avoid having to define addAll, etc. This doesn't hurt, but
-     * is wasteful.  This class does not need or use modCount
-     * mechanics in AbstractList, but does need to check for
-     * concurrent modification using similar mechanics.  On each
-     * operation, the array that we expect the backing list to use
-     * is checked and updated.  Since we do this for all of the
-     * base operations invoked by those defined in AbstractList,
-     * all is well.  While inefficient, this is not worth
-     * improving.  The kinds of list operations inherited from
-     * AbstractList are already so slow on COW sublists that
-     * adding a bit more space/time doesn't seem even noticeable.
      */
     private static class COWSubList<E>
         extends AbstractList<E>
@@ -1206,6 +1193,14 @@
                 throw new ConcurrentModificationException();
         }
 
+        private Object[] getArrayChecked() {
+            // assert Thread.holdsLock(l.lock);
+            Object[] a = l.getArray();
+            if (a != expectedArray)
+                throw new ConcurrentModificationException();
+            return a;
+        }
+
         // only call this holding l's lock
         private void rangeCheck(int index) {
             // assert Thread.holdsLock(l.lock);
@@ -1217,7 +1212,7 @@
             synchronized (l.lock) {
                 rangeCheck(index);
                 checkForComodification();
-                E x = l.set(index+offset, element);
+                E x = l.set(offset + index, element);
                 expectedArray = l.getArray();
                 return x;
             }
@@ -1227,7 +1222,7 @@
             synchronized (l.lock) {
                 rangeCheck(index);
                 checkForComodification();
-                return l.get(index+offset);
+                return l.get(offset + index);
             }
         }
 
@@ -1238,22 +1233,41 @@
             }
         }
 
+        public boolean add(E element) {
+            synchronized (l.lock) {
+                checkForComodification();
+                l.add(offset + size, element);
+                expectedArray = l.getArray();
+                size++;
+            }
+            return true;
+        }
+
         public void add(int index, E element) {
             synchronized (l.lock) {
                 checkForComodification();
                 if (index < 0 || index > size)
                     throw new IndexOutOfBoundsException
                         (outOfBounds(index, size));
-                l.add(index+offset, element);
+                l.add(offset + index, element);
                 expectedArray = l.getArray();
                 size++;
             }
         }
 
+        public boolean addAll(Collection<? extends E> c) {
+            synchronized (l.lock) {
+                final Object[] oldArray = getArrayChecked();
+                boolean modified = l.addAll(offset + size, c);
+                size += (expectedArray = l.getArray()).length - oldArray.length;
+                return modified;
+            }
+        }
+
         public void clear() {
             synchronized (l.lock) {
                 checkForComodification();
-                l.removeRange(offset, offset+size);
+                l.removeRange(offset, offset + size);
                 expectedArray = l.getArray();
                 size = 0;
             }
@@ -1263,7 +1277,7 @@
             synchronized (l.lock) {
                 rangeCheck(index);
                 checkForComodification();
-                E result = l.remove(index+offset);
+                E result = l.remove(offset + index);
                 expectedArray = l.getArray();
                 size--;
                 return result;
@@ -1271,11 +1285,14 @@
         }
 
         public boolean remove(Object o) {
-            int index = indexOf(o);
-            if (index == -1)
-                return false;
-            remove(index);
-            return true;
+            synchronized (l.lock) {
+                checkForComodification();
+                int index = indexOf(o);
+                if (index == -1)
+                    return false;
+                remove(index);
+                return true;
+            }
         }
 
         public Iterator<E> iterator() {
@@ -1307,174 +1324,63 @@
 
         public void forEach(Consumer<? super E> action) {
             if (action == null) throw new NullPointerException();
-            int lo = offset;
-            int hi = offset + size;
-            Object[] a = expectedArray;
-            if (l.getArray() != a)
-                throw new ConcurrentModificationException();
-            if (lo < 0 || hi > a.length)
-                throw new IndexOutOfBoundsException();
-            for (int i = lo; i < hi; ++i) {
-                @SuppressWarnings("unchecked") E e = (E) a[i];
-                action.accept(e);
+            int i, end; final Object[] es;
+            synchronized (l.lock) {
+                es = getArrayChecked();
+                i = offset;
+                end = i + size;
             }
+            for (; i < end; i++)
+                action.accept(elementAt(es, i));
         }
 
         public void replaceAll(UnaryOperator<E> operator) {
             if (operator == null) throw new NullPointerException();
             synchronized (l.lock) {
-                int lo = offset;
-                int hi = offset + size;
-                Object[] elements = expectedArray;
-                if (l.getArray() != elements)
-                    throw new ConcurrentModificationException();
-                int len = elements.length;
-                if (lo < 0 || hi > len)
-                    throw new IndexOutOfBoundsException();
-                Object[] newElements = Arrays.copyOf(elements, len);
-                for (int i = lo; i < hi; ++i) {
-                    @SuppressWarnings("unchecked") E e = (E) elements[i];
-                    newElements[i] = operator.apply(e);
-                }
-                l.setArray(expectedArray = newElements);
+                checkForComodification();
+                l.replaceAll(operator, offset, offset + size);
+                expectedArray = l.getArray();
             }
         }
 
         public void sort(Comparator<? super E> c) {
             synchronized (l.lock) {
-                int lo = offset;
-                int hi = offset + size;
-                Object[] elements = expectedArray;
-                if (l.getArray() != elements)
-                    throw new ConcurrentModificationException();
-                int len = elements.length;
-                if (lo < 0 || hi > len)
-                    throw new IndexOutOfBoundsException();
-                Object[] newElements = Arrays.copyOf(elements, len);
-                @SuppressWarnings("unchecked") E[] es = (E[])newElements;
-                Arrays.sort(es, lo, hi, c);
-                l.setArray(expectedArray = newElements);
+                checkForComodification();
+                l.sort(c, offset, offset + size);
+                expectedArray = l.getArray();
             }
         }
 
         public boolean removeAll(Collection<?> c) {
-            if (c == null) throw new NullPointerException();
-            boolean removed = false;
-            synchronized (l.lock) {
-                int n = size;
-                if (n > 0) {
-                    int lo = offset;
-                    int hi = offset + n;
-                    Object[] elements = expectedArray;
-                    if (l.getArray() != elements)
-                        throw new ConcurrentModificationException();
-                    int len = elements.length;
-                    if (lo < 0 || hi > len)
-                        throw new IndexOutOfBoundsException();
-                    int newSize = 0;
-                    Object[] temp = new Object[n];
-                    for (int i = lo; i < hi; ++i) {
-                        Object element = elements[i];
-                        if (!c.contains(element))
-                            temp[newSize++] = element;
-                    }
-                    if (newSize != n) {
-                        Object[] newElements = new Object[len - n + newSize];
-                        System.arraycopy(elements, 0, newElements, 0, lo);
-                        System.arraycopy(temp, 0, newElements, lo, newSize);
-                        System.arraycopy(elements, hi, newElements,
-                                         lo + newSize, len - hi);
-                        size = newSize;
-                        removed = true;
-                        l.setArray(expectedArray = newElements);
-                    }
-                }
-            }
-            return removed;
+            Objects.requireNonNull(c);
+            return bulkRemove(e -> c.contains(e));
         }
 
         public boolean retainAll(Collection<?> c) {
-            if (c == null) throw new NullPointerException();
-            boolean removed = false;
-            synchronized (l.lock) {
-                int n = size;
-                if (n > 0) {
-                    int lo = offset;
-                    int hi = offset + n;
-                    Object[] elements = expectedArray;
-                    if (l.getArray() != elements)
-                        throw new ConcurrentModificationException();
-                    int len = elements.length;
-                    if (lo < 0 || hi > len)
-                        throw new IndexOutOfBoundsException();
-                    int newSize = 0;
-                    Object[] temp = new Object[n];
-                    for (int i = lo; i < hi; ++i) {
-                        Object element = elements[i];
-                        if (c.contains(element))
-                            temp[newSize++] = element;
-                    }
-                    if (newSize != n) {
-                        Object[] newElements = new Object[len - n + newSize];
-                        System.arraycopy(elements, 0, newElements, 0, lo);
-                        System.arraycopy(temp, 0, newElements, lo, newSize);
-                        System.arraycopy(elements, hi, newElements,
-                                         lo + newSize, len - hi);
-                        size = newSize;
-                        removed = true;
-                        l.setArray(expectedArray = newElements);
-                    }
-                }
-            }
-            return removed;
+            Objects.requireNonNull(c);
+            return bulkRemove(e -> !c.contains(e));
         }
 
         public boolean removeIf(Predicate<? super E> filter) {
-            if (filter == null) throw new NullPointerException();
-            boolean removed = false;
+            Objects.requireNonNull(filter);
+            return bulkRemove(filter);
+        }
+
+        private boolean bulkRemove(Predicate<? super E> filter) {
             synchronized (l.lock) {
-                int n = size;
-                if (n > 0) {
-                    int lo = offset;
-                    int hi = offset + n;
-                    Object[] elements = expectedArray;
-                    if (l.getArray() != elements)
-                        throw new ConcurrentModificationException();
-                    int len = elements.length;
-                    if (lo < 0 || hi > len)
-                        throw new IndexOutOfBoundsException();
-                    int newSize = 0;
-                    Object[] temp = new Object[n];
-                    for (int i = lo; i < hi; ++i) {
-                        @SuppressWarnings("unchecked") E e = (E) elements[i];
-                        if (!filter.test(e))
-                            temp[newSize++] = e;
-                    }
-                    if (newSize != n) {
-                        Object[] newElements = new Object[len - n + newSize];
-                        System.arraycopy(elements, 0, newElements, 0, lo);
-                        System.arraycopy(temp, 0, newElements, lo, newSize);
-                        System.arraycopy(elements, hi, newElements,
-                                         lo + newSize, len - hi);
-                        size = newSize;
-                        removed = true;
-                        l.setArray(expectedArray = newElements);
-                    }
-                }
+                final Object[] oldArray = getArrayChecked();
+                boolean modified = l.bulkRemove(filter, offset, offset + size);
+                size += (expectedArray = l.getArray()).length - oldArray.length;
+                return modified;
             }
-            return removed;
         }
 
         public Spliterator<E> spliterator() {
-            int lo = offset;
-            int hi = offset + size;
-            Object[] a = expectedArray;
-            if (l.getArray() != a)
-                throw new ConcurrentModificationException();
-            if (lo < 0 || hi > a.length)
-                throw new IndexOutOfBoundsException();
-            return Spliterators.spliterator
-                (a, lo, hi, Spliterator.IMMUTABLE | Spliterator.ORDERED);
+            synchronized (l.lock) {
+                return Spliterators.spliterator(
+                        getArrayChecked(), offset, offset + size,
+                        Spliterator.IMMUTABLE | Spliterator.ORDERED);
+            }
         }
 
     }
--- a/jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java	Mon Nov 28 23:36:11 2016 -0800
@@ -1127,40 +1127,35 @@
     }
 
     /** A customized variant of Spliterators.IteratorSpliterator */
-    static final class LBDSpliterator<E> implements Spliterator<E> {
+    private final class LBDSpliterator implements Spliterator<E> {
         static final int MAX_BATCH = 1 << 25;  // max batch array size;
-        final LinkedBlockingDeque<E> queue;
         Node<E> current;    // current node; null until initialized
         int batch;          // batch size for splits
         boolean exhausted;  // true when no more nodes
         long est;           // size estimate
-        LBDSpliterator(LinkedBlockingDeque<E> queue) {
-            this.queue = queue;
-            this.est = queue.size();
-        }
+
+        LBDSpliterator() { est = size(); }
 
         public long estimateSize() { return est; }
 
         public Spliterator<E> trySplit() {
             Node<E> h;
-            final LinkedBlockingDeque<E> q = this.queue;
             int b = batch;
             int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
             if (!exhausted &&
-                ((h = current) != null || (h = q.first) != null) &&
-                h.next != null) {
+                (((h = current) != null && h != h.next)
+                 || (h = first) != null)
+                && h.next != null) {
                 Object[] a = new Object[n];
-                final ReentrantLock lock = q.lock;
+                final ReentrantLock lock = LinkedBlockingDeque.this.lock;
                 int i = 0;
                 Node<E> p = current;
                 lock.lock();
                 try {
-                    if (p != null || (p = q.first) != null) {
-                        do {
-                            if ((a[i] = p.item) != null)
-                                ++i;
-                        } while ((p = p.next) != null && i < n);
-                    }
+                    if (((p != null && p != p.next) || (p = first) != null)
+                        && p.item != null)
+                        for (; p != null && i < n; p = p.next)
+                            a[i++] = p.item;
                 } finally {
                     lock.unlock();
                 }
@@ -1183,64 +1178,55 @@
 
         public void forEachRemaining(Consumer<? super E> action) {
             if (action == null) throw new NullPointerException();
-            final LinkedBlockingDeque<E> q = this.queue;
-            final ReentrantLock lock = q.lock;
-            if (!exhausted) {
-                exhausted = true;
-                Node<E> p = current;
-                do {
-                    E e = null;
-                    lock.lock();
-                    try {
-                        if (p == null)
-                            p = q.first;
-                        while (p != null) {
-                            e = p.item;
-                            p = p.next;
-                            if (e != null)
-                                break;
-                        }
-                    } finally {
-                        lock.unlock();
+            if (exhausted)
+                return;
+            exhausted = true;
+            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+            Node<E> p = current;
+            current = null;
+            do {
+                E e = null;
+                lock.lock();
+                try {
+                    if ((p != null && p != p.next) || (p = first) != null) {
+                        e = p.item;
+                        p = p.next;
                     }
-                    if (e != null)
-                        action.accept(e);
-                } while (p != null);
-            }
+                } finally {
+                    lock.unlock();
+                }
+                if (e != null)
+                    action.accept(e);
+            } while (p != null);
         }
 
         public boolean tryAdvance(Consumer<? super E> action) {
             if (action == null) throw new NullPointerException();
-            final LinkedBlockingDeque<E> q = this.queue;
-            final ReentrantLock lock = q.lock;
-            if (!exhausted) {
-                E e = null;
-                lock.lock();
-                try {
-                    if (current == null)
-                        current = q.first;
-                    while (current != null) {
-                        e = current.item;
-                        current = current.next;
-                        if (e != null)
-                            break;
-                    }
-                } finally {
-                    lock.unlock();
+            if (exhausted)
+                return false;
+            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+            Node<E> p = current;
+            E e = null;
+            lock.lock();
+            try {
+                if ((p != null && p != p.next) || (p = first) != null) {
+                    e = p.item;
+                    p = p.next;
                 }
-                if (current == null)
-                    exhausted = true;
-                if (e != null) {
-                    action.accept(e);
-                    return true;
-                }
+            } finally {
+                lock.unlock();
             }
-            return false;
+            exhausted = ((current = p) == null);
+            if (e == null)
+                return false;
+            action.accept(e);
+            return true;
         }
 
         public int characteristics() {
-            return Spliterator.ORDERED | Spliterator.NONNULL |
-                Spliterator.CONCURRENT;
+            return (Spliterator.ORDERED |
+                    Spliterator.NONNULL |
+                    Spliterator.CONCURRENT);
         }
     }
 
@@ -1261,7 +1247,7 @@
      * @since 1.8
      */
     public Spliterator<E> spliterator() {
-        return new LBDSpliterator<E>(this);
+        return new LBDSpliterator();
     }
 
     /**
@@ -1312,4 +1298,14 @@
         }
     }
 
+    void checkInvariants() {
+        // assert lock.isHeldByCurrentThread();
+        // Nodes may get self-linked or lose their item, but only
+        // after being unlinked and becoming unreachable from first.
+        for (Node<E> p = first; p != null; p = p.next) {
+            // assert p.next != p;
+            // assert p.item != null;
+        }
+    }
+
 }
--- a/jdk/test/java/util/ArrayList/IteratorMicroBenchmark.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/ArrayList/IteratorMicroBenchmark.java	Mon Nov 28 23:36:11 2016 -0800
@@ -22,21 +22,36 @@
  */
 
 /*
- * This is not a regression test, but a micro-benchmark.
- * Be patient; this runs for half an hour!
+ * @test
+ * @summary micro-benchmark correctness mode
+ * @run main IteratorMicroBenchmark iterations=1 size=8 warmup=0
+ */
+
+import java.lang.ref.WeakReference;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Enumeration;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.Spliterator;
+import java.util.Vector;
+import java.util.concurrent.ConcurrentSkipListMap;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.regex.Pattern;
+
+/**
+ * Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
  *
- * I have run this as follows:
- *
- * for f in -client -server; do mergeBench dolphin . jr -dsa -da $f IteratorMicroBenchmark.java; done
- *
+ * To run this in micro-benchmark mode, simply run as a normal java program.
+ * Be patient; this program runs for a very long time.
+ * For faster runs, restrict execution using command line args.
  *
  * @author Martin Buchholz
  */
-
-import java.util.*;
-import java.util.concurrent.*;
-import java.util.regex.Pattern;
-
 public class IteratorMicroBenchmark {
     abstract static class Job {
         private final String name;
@@ -45,17 +60,28 @@
         public abstract void work() throws Throwable;
     }
 
-    private static void collectAllGarbage() {
-        final java.util.concurrent.CountDownLatch drained
-            = new java.util.concurrent.CountDownLatch(1);
+    static double warmupSeconds;
+    static long warmupNanos;
+
+    // --------------- GC finalization infrastructure ---------------
+
+    /** No guarantees, but effective in practice. */
+    static void forceFullGc() {
+        CountDownLatch finalizeDone = new CountDownLatch(1);
+        WeakReference<?> ref = new WeakReference<Object>(new Object() {
+            protected void finalize() { finalizeDone.countDown(); }});
         try {
-            System.gc();        // enqueue finalizable objects
-            new Object() { protected void finalize() {
-                drained.countDown(); }};
-            System.gc();        // enqueue detector
-            drained.await();    // wait for finalizer queue to drain
-            System.gc();        // cleanup finalized objects
-        } catch (InterruptedException e) { throw new Error(e); }
+            for (int i = 0; i < 10; i++) {
+                System.gc();
+                if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+                    System.runFinalization(); // try to pick up stragglers
+                    return;
+                }
+            }
+        } catch (InterruptedException unexpected) {
+            throw new AssertionError("unexpected InterruptedException");
+        }
+        throw new AssertionError("failed to do a \"full\" gc");
     }
 
     /**
@@ -65,23 +91,22 @@
      * Returns array of average times per job per run.
      */
     private static long[] time0(Job ... jobs) throws Throwable {
-        final long warmupNanos = 10L * 1000L * 1000L * 1000L;
         long[] nanoss = new long[jobs.length];
         for (int i = 0; i < jobs.length; i++) {
-            collectAllGarbage();
-            long t0 = System.nanoTime();
-            long t;
-            int j = 0;
-            do { jobs[i].work(); j++; }
-            while ((t = System.nanoTime() - t0) < warmupNanos);
-            nanoss[i] = t/j;
+            if (warmupNanos > 0) forceFullGc();
+            Job job = jobs[i];
+            long totalTime;
+            int runs = 0;
+            long startTime = System.nanoTime();
+            do { job.work(); runs++; }
+            while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
+            nanoss[i] = totalTime/runs;
         }
         return nanoss;
     }
 
     private static void time(Job ... jobs) throws Throwable {
-
-        long[] warmup = time0(jobs); // Warm up run
+        if (warmupSeconds > 0.0) time0(jobs); // Warm up run
         long[] nanoss = time0(jobs); // Real timing run
         long[] milliss = new long[jobs.length];
         double[] ratios = new double[jobs.length];
@@ -126,12 +151,17 @@
 
     private static int intArg(String[] args, String keyword, int defaultValue) {
         String val = keywordValue(args, keyword);
-        return val == null ? defaultValue : Integer.parseInt(val);
+        return (val == null) ? defaultValue : Integer.parseInt(val);
+    }
+
+    private static double doubleArg(String[] args, String keyword, double defaultValue) {
+        String val = keywordValue(args, keyword);
+        return (val == null) ? defaultValue : Double.parseDouble(val);
     }
 
     private static Pattern patternArg(String[] args, String keyword) {
         String val = keywordValue(args, keyword);
-        return val == null ? null : Pattern.compile(val);
+        return (val == null) ? null : Pattern.compile(val);
     }
 
     private static Job[] filter(Pattern filter, Job[] jobs) {
@@ -166,26 +196,33 @@
                     public void remove()     {        it.remove(); }};}};
     }
 
-    /**
-     * Usage: [iterations=N] [size=N] [filter=REGEXP]
-     */
     public static void main(String[] args) throws Throwable {
-        final int iterations = intArg(args, "iterations", 100000);
+        final int iterations = intArg(args, "iterations", 100_000);
         final int size       = intArg(args, "size", 1000);
+        warmupSeconds        = doubleArg(args, "warmup", 7.0);
         final Pattern filter = patternArg(args, "filter");
 
+        warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L));
+
+//         System.out.printf(
+//             "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
+//             iterations, size, warmupSeconds, filter);
+
         final ConcurrentSkipListMap<Integer,Integer> m
             = new ConcurrentSkipListMap<Integer,Integer>();
-        final Vector<Integer> v = new Vector<Integer>(size);
         final ArrayList<Integer> al = new ArrayList<Integer>(size);
 
         // Populate collections with random data
-        final Random rnd = new Random();
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
         for (int i = 0; i < size; i++) {
             m.put(rnd.nextInt(size), rnd.nextInt(size));
-            v.add(rnd.nextInt(size));
+            al.add(rnd.nextInt(size));
         }
-        al.addAll(v);
+        final Vector<Integer> v = new Vector<Integer>(al);
+        final ArrayDeque<Integer> ad = new ArrayDeque<Integer>(al);
+        // shuffle ArrayDeque elements so they wrap
+        for (int i = 0, n = rnd.nextInt(size); i < n; i++)
+            ad.addLast(ad.removeFirst());
 
         // Also test "short" collections
         final int shortSize = 5;
@@ -222,6 +259,15 @@
                         for (int j = 0; j < size; ++j)
                             sum += a[j];
                         check.sum(sum);}}},
+            new Job("descending array loop") {
+                public void work() throws Throwable {
+                    Integer[] a = al.toArray(new Integer[0]);
+                    for (int i = 0; i < iterations; i++) {
+                        int sum = 0;
+                        int size = a.length;
+                        for (int j = size - 1; j >= 0; j--)
+                            sum += a[j];
+                        check.sum(sum);}}},
             new Job("Vector get loop") {
                 public void work() throws Throwable {
                     for (int i = 0; i < iterations; i++) {
@@ -334,6 +380,13 @@
                         for (Integer n : al)
                             sum += n;
                         check.sum(sum);}}},
+            new Job("ArrayDeque iterate for loop") {
+                public void work() throws Throwable {
+                    for (int i = 0; i < iterations; i++) {
+                        int sum = 0;
+                        for (Integer n : ad)
+                            sum += n;
+                        check.sum(sum);}}},
             new Job("ArrayList descending listIterator loop") {
                 public void work() throws Throwable {
                     for (int i = 0; i < iterations; i++) {
@@ -350,6 +403,137 @@
                         while (it.hasNext())
                             sum += it.next();
                         check.sum(sum);}}},
+            new Job("ArrayDeque.descendingIterator() loop") {
+                public void work() throws Throwable {
+                    for (int i = 0; i < iterations; i++) {
+                        int sum = 0;
+                        Iterator<Integer> it = ad.descendingIterator();
+                        while (it.hasNext())
+                            sum += it.next();
+                        check.sum(sum);}}},
+            new Job("ArrayList.forEach") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        al.forEach(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("ArrayDeque.forEach") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        ad.forEach(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("Vector.forEach") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        v.forEach(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("ArrayList.iterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        al.iterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("ArrayDeque.descendingIterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        ad.descendingIterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("ArrayDeque.iterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        ad.iterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("Vector.iterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        v.iterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("ArrayList.spliterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        al.spliterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("ArrayDeque.spliterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        ad.spliterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("Vector.spliterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        v.spliterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job("ArrayList.spliterator().tryAdvance()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        Spliterator<Integer> spliterator = al.spliterator();
+                        do {} while (spliterator.tryAdvance(n -> sum[0] += n));
+                        check.sum(sum[0]);}}},
+            new Job("ArrayDeque.spliterator().tryAdvance()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        Spliterator<Integer> spliterator = ad.spliterator();
+                        do {} while (spliterator.tryAdvance(n -> sum[0] += n));
+                        check.sum(sum[0]);}}},
+            new Job("Vector.spliterator().tryAdvance()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        Spliterator<Integer> spliterator = v.spliterator();
+                        do {} while (spliterator.tryAdvance(n -> sum[0] += n));
+                        check.sum(sum[0]);}}},
+            new Job("ArrayList.removeIf") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        al.removeIf(n -> { sum[0] += n; return false; });
+                        check.sum(sum[0]);}}},
+            new Job("ArrayDeque.removeIf") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        ad.removeIf(n -> { sum[0] += n; return false; });
+                        check.sum(sum[0]);}}},
+            new Job("Vector.removeIf") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        v.removeIf(n -> { sum[0] += n; return false; });
+                        check.sum(sum[0]);}}},
+            new Job("ArrayList subList .removeIf") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    List<Integer> sl = asSubList(al);
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        sl.removeIf(n -> { sum[0] += n; return false; });
+                        check.sum(sum[0]);}}},
             new Job("ArrayList subList get loop") {
                 public void work() throws Throwable {
                     List<Integer> sl = asSubList(al);
@@ -442,7 +626,61 @@
                         int sum = 0;
                         for (Map.Entry<Integer,Integer> e : m.entrySet())
                             sum += e.getKey();
-                        deoptimize(sum);}}}
+                        deoptimize(sum);}}},
+            new Job("ArrayList.toArray()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        for (Object o : al.toArray())
+                            sum[0] += (Integer) o;
+                        check.sum(sum[0]);}}},
+            new Job("ArrayList.toArray(a)") {
+                public void work() throws Throwable {
+                    Integer[] a = new Integer[size];
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        al.toArray(a);
+                        for (Object o : a)
+                            sum[0] += (Integer) o;
+                        check.sum(sum[0]);}}},
+            new Job("ArrayDeque.toArray()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        for (Object o : ad.toArray())
+                            sum[0] += (Integer) o;
+                        check.sum(sum[0]);}}},
+            new Job("ArrayDeque.toArray(a)") {
+                public void work() throws Throwable {
+                    Integer[] a = new Integer[size];
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        ad.toArray(a);
+                        for (Object o : a)
+                            sum[0] += (Integer) o;
+                        check.sum(sum[0]);}}},
+            new Job("Vector.toArray()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        for (Object o : v.toArray())
+                            sum[0] += (Integer) o;
+                        check.sum(sum[0]);}}},
+            new Job("Vector.toArray(a)") {
+                public void work() throws Throwable {
+                    Integer[] a = new Integer[size];
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        v.toArray(a);
+                        for (Object o : a)
+                            sum[0] += (Integer) o;
+                        check.sum(sum[0]);}}},
         };
 
         time(filter(filter, jobs));
--- a/jdk/test/java/util/Collection/CollectionDefaults.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/Collection/CollectionDefaults.java	Mon Nov 28 23:36:11 2016 -0800
@@ -60,9 +60,19 @@
     public static final Predicate<Integer> pEven = x -> 0 == x % 2;
     public static final Predicate<Integer> pOdd = x -> 1 == x % 2;
 
+    private static final int SIZE = 100;
+
     private static final List<Function<Collection<Integer>, Collection<Integer>>> TEST_SUPPLIERS = Arrays.asList(
             // Collection
             ExtendsAbstractCollection<Integer>::new,
+            java.util.ArrayDeque<Integer>::new,
+            java.util.concurrent.ConcurrentLinkedDeque<Integer>::new,
+            java.util.concurrent.ConcurrentLinkedQueue<Integer>::new,
+            java.util.concurrent.LinkedBlockingDeque<Integer>::new,
+            java.util.concurrent.LinkedBlockingQueue<Integer>::new,
+            java.util.concurrent.LinkedTransferQueue<Integer>::new,
+            (coll) -> new java.util.concurrent.ArrayBlockingQueue<Integer>(
+                3 * SIZE, false, coll),
 
             // Lists
             java.util.ArrayList<Integer>::new,
@@ -80,8 +90,6 @@
             ExtendsAbstractSet<Integer>::new
        );
 
-    private static final int SIZE = 100;
-
     @DataProvider(name="setProvider", parallel=true)
     public static Iterator<Object[]> setCases() {
         final List<Object[]> cases = new LinkedList<>();
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Collection/IteratorMicroBenchmark.java	Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,404 @@
+/*
+ * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @summary micro-benchmark correctness mode
+ * @run main IteratorMicroBenchmark iterations=1 size=8 warmup=0
+ */
+
+import static java.util.stream.Collectors.summingInt;
+
+import java.lang.ref.WeakReference;
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.Enumeration;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Spliterator;
+import java.util.Vector;
+import java.util.concurrent.ArrayBlockingQueue;
+import java.util.concurrent.ConcurrentLinkedDeque;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.LinkedBlockingDeque;
+import java.util.concurrent.LinkedBlockingQueue;
+import java.util.concurrent.LinkedTransferQueue;
+import java.util.concurrent.PriorityBlockingQueue;
+import java.util.concurrent.ConcurrentSkipListMap;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.regex.Pattern;
+
+/**
+ * Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
+ *
+ * To run this in micro-benchmark mode, simply run as a normal java program.
+ * Be patient; this program runs for a very long time.
+ * For faster runs, restrict execution using command line args.
+ *
+ * This is an interface based version of ArrayList/IteratorMicroBenchmark
+ *
+ * @author Martin Buchholz
+ */
+public class IteratorMicroBenchmark {
+    abstract static class Job {
+        private final String name;
+        public Job(String name) { this.name = name; }
+        public String name() { return name; }
+        public abstract void work() throws Throwable;
+    }
+
+    final int iterations;
+    final int size;             // number of elements in collections
+    final double warmupSeconds;
+    final long warmupNanos;
+    final Pattern filter;       // select subset of Jobs to run
+    final boolean reverse;      // reverse order of Jobs
+    final boolean shuffle;      // randomize order of Jobs
+
+    IteratorMicroBenchmark(String[] args) {
+        iterations    = intArg(args, "iterations", 10_000);
+        size          = intArg(args, "size", 1000);
+        warmupSeconds = doubleArg(args, "warmup", 7.0);
+        filter        = patternArg(args, "filter");
+        reverse       = booleanArg(args, "reverse");
+        shuffle       = booleanArg(args, "shuffle");
+
+        warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L));
+    }
+
+    // --------------- GC finalization infrastructure ---------------
+
+    /** No guarantees, but effective in practice. */
+    static void forceFullGc() {
+        CountDownLatch finalizeDone = new CountDownLatch(1);
+        WeakReference<?> ref = new WeakReference<Object>(new Object() {
+            protected void finalize() { finalizeDone.countDown(); }});
+        try {
+            for (int i = 0; i < 10; i++) {
+                System.gc();
+                if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+                    System.runFinalization(); // try to pick up stragglers
+                    return;
+                }
+            }
+        } catch (InterruptedException unexpected) {
+            throw new AssertionError("unexpected InterruptedException");
+        }
+        throw new AssertionError("failed to do a \"full\" gc");
+    }
+
+    /**
+     * Runs each job for long enough that all the runtime compilers
+     * have had plenty of time to warm up, i.e. get around to
+     * compiling everything worth compiling.
+     * Returns array of average times per job per run.
+     */
+    long[] time0(List<Job> jobs) throws Throwable {
+        final int size = jobs.size();
+        long[] nanoss = new long[size];
+        for (int i = 0; i < size; i++) {
+            if (warmupNanos > 0) forceFullGc();
+            Job job = jobs.get(i);
+            long totalTime;
+            int runs = 0;
+            long startTime = System.nanoTime();
+            do { job.work(); runs++; }
+            while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
+            nanoss[i] = totalTime/runs;
+        }
+        return nanoss;
+    }
+
+    void time(List<Job> jobs) throws Throwable {
+        if (warmupNanos > 0) time0(jobs); // Warm up run
+        final int size = jobs.size();
+        final long[] nanoss = time0(jobs); // Real timing run
+        final long[] milliss = new long[size];
+        final double[] ratios = new double[size];
+
+        final String nameHeader   = "Method";
+        final String millisHeader = "Millis";
+        final String ratioHeader  = "Ratio";
+
+        int nameWidth   = nameHeader.length();
+        int millisWidth = millisHeader.length();
+        int ratioWidth  = ratioHeader.length();
+
+        for (int i = 0; i < size; i++) {
+            nameWidth = Math.max(nameWidth, jobs.get(i).name().length());
+
+            milliss[i] = nanoss[i]/(1000L * 1000L);
+            millisWidth = Math.max(millisWidth,
+                                   String.format("%d", milliss[i]).length());
+
+            ratios[i] = (double) nanoss[i] / (double) nanoss[0];
+            ratioWidth = Math.max(ratioWidth,
+                                  String.format("%.3f", ratios[i]).length());
+        }
+
+        String format = String.format("%%-%ds %%%dd %%%d.3f%%n",
+                                      nameWidth, millisWidth, ratioWidth);
+        String headerFormat = String.format("%%-%ds %%%ds %%%ds%%n",
+                                            nameWidth, millisWidth, ratioWidth);
+        System.out.printf(headerFormat, "Method", "Millis", "Ratio");
+
+        // Print out absolute and relative times, calibrated against first job
+        for (int i = 0; i < size; i++)
+            System.out.printf(format, jobs.get(i).name(), milliss[i], ratios[i]);
+    }
+
+    private static String keywordValue(String[] args, String keyword) {
+        for (String arg : args)
+            if (arg.startsWith(keyword))
+                return arg.substring(keyword.length() + 1);
+        return null;
+    }
+
+    private static int intArg(String[] args, String keyword, int defaultValue) {
+        String val = keywordValue(args, keyword);
+        return (val == null) ? defaultValue : Integer.parseInt(val);
+    }
+
+    private static double doubleArg(String[] args, String keyword, double defaultValue) {
+        String val = keywordValue(args, keyword);
+        return (val == null) ? defaultValue : Double.parseDouble(val);
+    }
+
+    private static Pattern patternArg(String[] args, String keyword) {
+        String val = keywordValue(args, keyword);
+        return (val == null) ? null : Pattern.compile(val);
+    }
+
+    private static boolean booleanArg(String[] args, String keyword) {
+        String val = keywordValue(args, keyword);
+        if (val == null || val.equals("false")) return false;
+        if (val.equals("true")) return true;
+        throw new IllegalArgumentException(val);
+    }
+
+    private static List<Job> filter(Pattern filter, List<Job> jobs) {
+        if (filter == null) return jobs;
+        ArrayList<Job> newJobs = new ArrayList<>();
+        for (Job job : jobs)
+            if (filter.matcher(job.name()).find())
+                newJobs.add(job);
+        return newJobs;
+    }
+
+    private static void deoptimize(int sum) {
+        if (sum == 42)
+            System.out.println("the answer");
+    }
+
+    private static <T> List<T> asSubList(List<T> list) {
+        return list.subList(0, list.size());
+    }
+
+    private static <T> Iterable<T> backwards(final List<T> list) {
+        return new Iterable<T>() {
+            public Iterator<T> iterator() {
+                return new Iterator<T>() {
+                    final ListIterator<T> it = list.listIterator(list.size());
+                    public boolean hasNext() { return it.hasPrevious(); }
+                    public T next()          { return it.previous(); }
+                    public void remove()     {        it.remove(); }};}};
+    }
+
+    // Checks for correctness *and* prevents loop optimizations
+    class Check {
+        private int sum;
+        public void sum(int sum) {
+            if (this.sum == 0)
+                this.sum = sum;
+            if (this.sum != sum)
+                throw new AssertionError("Sum mismatch");
+        }
+    }
+    volatile Check check = new Check();
+
+    public static void main(String[] args) throws Throwable {
+        new IteratorMicroBenchmark(args).run();
+    }
+
+    void run() throws Throwable {
+//         System.out.printf(
+//             "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
+//             iterations, size, warmupSeconds, filter);
+
+        final ArrayList<Integer> al = new ArrayList<Integer>(size);
+
+        // Populate collections with random data
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        for (int i = 0; i < size; i++)
+            al.add(rnd.nextInt(size));
+
+        final ArrayDeque<Integer> ad = new ArrayDeque<>(al);
+        final ArrayBlockingQueue<Integer> abq = new ArrayBlockingQueue<>(al.size());
+        abq.addAll(al);
+
+        // shuffle circular array elements so they wrap
+        for (int i = 0, n = rnd.nextInt(size); i < n; i++) {
+            ad.addLast(ad.removeFirst());
+            abq.add(abq.remove());
+        }
+
+        ArrayList<Job> jobs = new ArrayList<>(Arrays.asList());
+
+        List.of(al, ad, abq,
+                new LinkedList<>(al),
+                new PriorityQueue<>(al),
+                new Vector<>(al),
+                new ConcurrentLinkedQueue<>(al),
+                new ConcurrentLinkedDeque<>(al),
+                new LinkedBlockingQueue<>(al),
+                new LinkedBlockingDeque<>(al),
+                new LinkedTransferQueue<>(al),
+                new PriorityBlockingQueue<>(al))
+            .stream()
+            .forEach(x -> {
+                         jobs.addAll(collectionJobs(x));
+                         if (x instanceof Deque)
+                             jobs.addAll(dequeJobs((Deque<Integer>)x));
+                     });
+
+        if (reverse) Collections.reverse(jobs);
+        if (shuffle) Collections.shuffle(jobs);
+
+        time(filter(filter, jobs));
+    }
+
+    List<Job> collectionJobs(Collection<Integer> x) {
+        String klazz = x.getClass().getSimpleName();
+        return List.of(
+            new Job(klazz + " iterate for loop") {
+                public void work() throws Throwable {
+                    for (int i = 0; i < iterations; i++) {
+                        int sum = 0;
+                        for (Integer n : x)
+                            sum += n;
+                        check.sum(sum);}}},
+            new Job(klazz + " .iterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.iterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " .spliterator().tryAdvance()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        Spliterator<Integer> spliterator = x.spliterator();
+                        do {} while (spliterator.tryAdvance(n -> sum[0] += n));
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " .spliterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.spliterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " .removeIf") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.removeIf(n -> { sum[0] += n; return false; });
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " .forEach") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.forEach(n -> sum[0] += n);
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " .toArray()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        for (Object o : x.toArray())
+                            sum[0] += (Integer) o;
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " .toArray(a)") {
+                public void work() throws Throwable {
+                    Integer[] a = new Integer[x.size()];
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.toArray(a);
+                        for (Object o : a)
+                            sum[0] += (Integer) o;
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " .toArray(empty)") {
+                public void work() throws Throwable {
+                    Integer[] empty = new Integer[0];
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        for (Integer o : x.toArray(empty))
+                            sum[0] += o;
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " .stream().collect") {
+                public void work() throws Throwable {
+                    for (int i = 0; i < iterations; i++) {
+                        check.sum(x.stream()
+                                  .collect(summingInt(e -> e)));}}},
+            new Job(klazz + " .parallelStream().collect") {
+                public void work() throws Throwable {
+                    for (int i = 0; i < iterations; i++) {
+                        check.sum(x.parallelStream()
+                                  .collect(summingInt(e -> e)));}}});
+    }
+
+    List<Job> dequeJobs(Deque<Integer> x) {
+        String klazz = x.getClass().getSimpleName();
+        return List.of(
+            new Job(klazz + " .descendingIterator() loop") {
+                public void work() throws Throwable {
+                    for (int i = 0; i < iterations; i++) {
+                        int sum = 0;
+                        Iterator<Integer> it = x.descendingIterator();
+                        while (it.hasNext())
+                            sum += it.next();
+                        check.sum(sum);}}},
+            new Job(klazz + " .descendingIterator().forEachRemaining()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.descendingIterator().forEachRemaining(n -> sum[0] += n);
+                        check.sum(sum[0]);}}});
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Collection/RemoveMicroBenchmark.java	Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,504 @@
+/*
+ * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @summary micro-benchmark correctness mode
+ * @run main RemoveMicroBenchmark iterations=1 size=8 warmup=0
+ */
+
+import java.lang.ref.WeakReference;
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.Enumeration;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Queue;
+import java.util.Spliterator;
+import java.util.Vector;
+import java.util.concurrent.ArrayBlockingQueue;
+import java.util.concurrent.BlockingDeque;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.ConcurrentLinkedDeque;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.LinkedBlockingDeque;
+import java.util.concurrent.LinkedBlockingQueue;
+import java.util.concurrent.LinkedTransferQueue;
+import java.util.concurrent.PriorityBlockingQueue;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.regex.Pattern;
+import java.util.function.Supplier;
+
+/**
+ * Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
+ *
+ * To run this in micro-benchmark mode, simply run as a normal java program.
+ * Be patient; this program runs for a very long time.
+ * For faster runs, restrict execution using command line args.
+ *
+ * @author Martin Buchholz
+ */
+public class RemoveMicroBenchmark {
+    abstract static class Job {
+        private final String name;
+        public Job(String name) { this.name = name; }
+        public String name() { return name; }
+        public abstract void work() throws Throwable;
+    }
+
+    final int iterations;
+    final int size;             // number of elements in collections
+    final double warmupSeconds;
+    final long warmupNanos;
+    final Pattern filter;       // select subset of Jobs to run
+    final boolean reverse;      // reverse order of Jobs
+    final boolean shuffle;      // randomize order of Jobs
+
+    RemoveMicroBenchmark(String[] args) {
+        iterations    = intArg(args, "iterations", 10_000);
+        size          = intArg(args, "size", 1000);
+        warmupSeconds = doubleArg(args, "warmup", 7.0);
+        filter        = patternArg(args, "filter");
+        reverse       = booleanArg(args, "reverse");
+        shuffle       = booleanArg(args, "shuffle");
+
+        warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L));
+    }
+
+    // --------------- GC finalization infrastructure ---------------
+
+    /** No guarantees, but effective in practice. */
+    static void forceFullGc() {
+        CountDownLatch finalizeDone = new CountDownLatch(1);
+        WeakReference<?> ref = new WeakReference<Object>(new Object() {
+            protected void finalize() { finalizeDone.countDown(); }});
+        try {
+            for (int i = 0; i < 10; i++) {
+                System.gc();
+                if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+                    System.runFinalization(); // try to pick up stragglers
+                    return;
+                }
+            }
+        } catch (InterruptedException unexpected) {
+            throw new AssertionError("unexpected InterruptedException");
+        }
+        throw new AssertionError("failed to do a \"full\" gc");
+    }
+
+    /**
+     * Runs each job for long enough that all the runtime compilers
+     * have had plenty of time to warm up, i.e. get around to
+     * compiling everything worth compiling.
+     * Returns array of average times per job per run.
+     */
+    long[] time0(List<Job> jobs) throws Throwable {
+        final int size = jobs.size();
+        long[] nanoss = new long[size];
+        for (int i = 0; i < size; i++) {
+            if (warmupNanos > 0) forceFullGc();
+            Job job = jobs.get(i);
+            long totalTime;
+            int runs = 0;
+            long startTime = System.nanoTime();
+            do { job.work(); runs++; }
+            while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
+            nanoss[i] = totalTime/runs;
+        }
+        return nanoss;
+    }
+
+    void time(List<Job> jobs) throws Throwable {
+        if (warmupNanos > 0) time0(jobs); // Warm up run
+        final int size = jobs.size();
+        final long[] nanoss = time0(jobs); // Real timing run
+        final long[] milliss = new long[size];
+        final double[] ratios = new double[size];
+
+        final String nameHeader   = "Method";
+        final String millisHeader = "Millis";
+        final String ratioHeader  = "Ratio";
+
+        int nameWidth   = nameHeader.length();
+        int millisWidth = millisHeader.length();
+        int ratioWidth  = ratioHeader.length();
+
+        for (int i = 0; i < size; i++) {
+            nameWidth = Math.max(nameWidth, jobs.get(i).name().length());
+
+            milliss[i] = nanoss[i]/(1000L * 1000L);
+            millisWidth = Math.max(millisWidth,
+                                   String.format("%d", milliss[i]).length());
+
+            ratios[i] = (double) nanoss[i] / (double) nanoss[0];
+            ratioWidth = Math.max(ratioWidth,
+                                  String.format("%.3f", ratios[i]).length());
+        }
+
+        String format = String.format("%%-%ds %%%dd %%%d.3f%%n",
+                                      nameWidth, millisWidth, ratioWidth);
+        String headerFormat = String.format("%%-%ds %%%ds %%%ds%%n",
+                                            nameWidth, millisWidth, ratioWidth);
+        System.out.printf(headerFormat, "Method", "Millis", "Ratio");
+
+        // Print out absolute and relative times, calibrated against first job
+        for (int i = 0; i < size; i++)
+            System.out.printf(format, jobs.get(i).name(), milliss[i], ratios[i]);
+    }
+
+    private static String keywordValue(String[] args, String keyword) {
+        for (String arg : args)
+            if (arg.startsWith(keyword))
+                return arg.substring(keyword.length() + 1);
+        return null;
+    }
+
+    private static int intArg(String[] args, String keyword, int defaultValue) {
+        String val = keywordValue(args, keyword);
+        return (val == null) ? defaultValue : Integer.parseInt(val);
+    }
+
+    private static double doubleArg(String[] args, String keyword, double defaultValue) {
+        String val = keywordValue(args, keyword);
+        return (val == null) ? defaultValue : Double.parseDouble(val);
+    }
+
+    private static Pattern patternArg(String[] args, String keyword) {
+        String val = keywordValue(args, keyword);
+        return (val == null) ? null : Pattern.compile(val);
+    }
+
+    private static boolean booleanArg(String[] args, String keyword) {
+        String val = keywordValue(args, keyword);
+        if (val == null || val.equals("false")) return false;
+        if (val.equals("true")) return true;
+        throw new IllegalArgumentException(val);
+    }
+
+    private static List<Job> filter(Pattern filter, List<Job> jobs) {
+        if (filter == null) return jobs;
+        ArrayList<Job> newJobs = new ArrayList<>();
+        for (Job job : jobs)
+            if (filter.matcher(job.name()).find())
+                newJobs.add(job);
+        return newJobs;
+    }
+
+    private static void deoptimize(int sum) {
+        if (sum == 42)
+            System.out.println("the answer");
+    }
+
+    private static <T> List<T> asSubList(List<T> list) {
+        return list.subList(0, list.size());
+    }
+
+    private static <T> Iterable<T> backwards(final List<T> list) {
+        return new Iterable<T>() {
+            public Iterator<T> iterator() {
+                return new Iterator<T>() {
+                    final ListIterator<T> it = list.listIterator(list.size());
+                    public boolean hasNext() { return it.hasPrevious(); }
+                    public T next()          { return it.previous(); }
+                    public void remove()     {        it.remove(); }};}};
+    }
+
+    // Checks for correctness *and* prevents loop optimizations
+    class Check {
+        private int sum;
+        public void sum(int sum) {
+            if (this.sum == 0)
+                this.sum = sum;
+            if (this.sum != sum)
+                throw new AssertionError("Sum mismatch");
+        }
+    }
+    volatile Check check = new Check();
+
+    public static void main(String[] args) throws Throwable {
+        new RemoveMicroBenchmark(args).run();
+    }
+
+    void run() throws Throwable {
+//         System.out.printf(
+//             "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
+//             iterations, size, warmupSeconds, filter);
+
+        final ArrayList<Integer> al = new ArrayList<Integer>(size);
+
+        // Populate collections with random data
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        for (int i = 0; i < size; i++)
+            al.add(rnd.nextInt(size));
+
+        ArrayList<Job> jobs = new ArrayList<>();
+
+        List.<Collection<Integer>>of(
+            new ArrayList<>(),
+            new LinkedList<>(),
+            new Vector<>(),
+            new ArrayDeque<>(),
+            new PriorityQueue<>(),
+            new ArrayBlockingQueue<>(al.size()),
+            new ConcurrentLinkedQueue<>(),
+            new ConcurrentLinkedDeque<>(),
+            new LinkedBlockingQueue<>(),
+            new LinkedBlockingDeque<>(),
+            new LinkedTransferQueue<>(),
+            new PriorityBlockingQueue<>())
+            .stream().forEach(
+                x -> {
+                    String klazz = x.getClass().getSimpleName();
+                    jobs.addAll(collectionJobs(klazz, () -> x, al));
+                    if (x instanceof Queue) {
+                        Queue<Integer> queue = (Queue<Integer>) x;
+                        jobs.addAll(queueJobs(klazz, () -> queue, al));
+                    }
+                    if (x instanceof Deque) {
+                        Deque<Integer> deque = (Deque<Integer>) x;
+                        jobs.addAll(dequeJobs(klazz, () -> deque, al));
+                    }
+                    if (x instanceof BlockingQueue) {
+                        BlockingQueue<Integer> q = (BlockingQueue<Integer>) x;
+                        jobs.addAll(blockingQueueJobs(klazz, () -> q, al));
+                    }
+                    if (x instanceof BlockingDeque) {
+                        BlockingDeque<Integer> q = (BlockingDeque<Integer>) x;
+                        jobs.addAll(blockingDequeJobs(klazz, () -> q, al));
+                    }
+                    if (x instanceof List) {
+                        List<Integer> list = (List<Integer>) x;
+                        jobs.addAll(
+                            collectionJobs(
+                                klazz + " subList",
+                                () -> list.subList(0, x.size()),
+                                al));
+                    }
+                });
+
+        if (reverse) Collections.reverse(jobs);
+        if (shuffle) Collections.shuffle(jobs);
+
+        time(filter(filter, jobs));
+    }
+
+    Collection<Integer> universeRecorder(int[] sum) {
+        return new ArrayList<>() {
+            public boolean contains(Object x) {
+                sum[0] += (Integer) x;
+                return true;
+            }};
+    }
+
+    Collection<Integer> emptyRecorder(int[] sum) {
+        return new ArrayList<>() {
+            public boolean contains(Object x) {
+                sum[0] += (Integer) x;
+                return false;
+            }};
+    }
+
+    List<Job> collectionJobs(
+        String description,
+        Supplier<Collection<Integer>> supplier,
+        ArrayList<Integer> al) {
+        return List.of(
+            new Job(description + " .removeIf") {
+                public void work() throws Throwable {
+                    Collection<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        x.removeIf(n -> { sum[0] += n; return true; });
+                        check.sum(sum[0]);}}},
+            new Job(description + " .removeAll") {
+                public void work() throws Throwable {
+                    Collection<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    Collection<Integer> universe = universeRecorder(sum);
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        x.removeAll(universe);
+                        check.sum(sum[0]);}}},
+            new Job(description + " .retainAll") {
+                public void work() throws Throwable {
+                    Collection<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    Collection<Integer> empty = emptyRecorder(sum);
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        x.retainAll(empty);
+                        check.sum(sum[0]);}}},
+            new Job(description + " Iterator.remove") {
+                public void work() throws Throwable {
+                    Collection<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        Iterator<Integer> it = x.iterator();
+                        while (it.hasNext()) {
+                            sum[0] += it.next();
+                            it.remove();
+                        }
+                        check.sum(sum[0]);}}},
+            new Job(description + " clear") {
+                public void work() throws Throwable {
+                    Collection<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        x.forEach(e -> sum[0] += e);
+                        x.clear();
+                        check.sum(sum[0]);}}});
+    }
+
+    List<Job> queueJobs(
+        String description,
+        Supplier<Queue<Integer>> supplier,
+        ArrayList<Integer> al) {
+        return List.of(
+            new Job(description + " poll()") {
+                public void work() throws Throwable {
+                    Queue<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        for (Integer e; (e = x.poll()) != null; )
+                            sum[0] += e;
+                        check.sum(sum[0]);}}});
+    }
+
+    List<Job> dequeJobs(
+        String description,
+        Supplier<Deque<Integer>> supplier,
+        ArrayList<Integer> al) {
+        return List.of(
+            new Job(description + " descendingIterator().remove") {
+                public void work() throws Throwable {
+                    Deque<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        Iterator<Integer> it = x.descendingIterator();
+                        while (it.hasNext()) {
+                            sum[0] += it.next();
+                            it.remove();
+                        }
+                        check.sum(sum[0]);}}},
+            new Job(description + " pollFirst()") {
+                public void work() throws Throwable {
+                    Deque<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        for (Integer e; (e = x.pollFirst()) != null; )
+                            sum[0] += e;
+                        check.sum(sum[0]);}}},
+            new Job(description + " pollLast()") {
+                public void work() throws Throwable {
+                    Deque<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        for (Integer e; (e = x.pollLast()) != null; )
+                            sum[0] += e;
+                        check.sum(sum[0]);}}});
+    }
+
+    List<Job> blockingQueueJobs(
+        String description,
+        Supplier<BlockingQueue<Integer>> supplier,
+        ArrayList<Integer> al) {
+        return List.of(
+            new Job(description + " drainTo(sink)") {
+                public void work() throws Throwable {
+                    BlockingQueue<Integer> x = supplier.get();
+                    ArrayList<Integer> sink = new ArrayList<>();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        sink.clear();
+                        x.addAll(al);
+                        x.drainTo(sink);
+                        sink.forEach(e -> sum[0] += e);
+                        check.sum(sum[0]);}}},
+            new Job(description + " drainTo(sink, n)") {
+                public void work() throws Throwable {
+                    BlockingQueue<Integer> x = supplier.get();
+                    ArrayList<Integer> sink = new ArrayList<>();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        sink.clear();
+                        x.addAll(al);
+                        x.drainTo(sink, al.size());
+                        sink.forEach(e -> sum[0] += e);
+                        check.sum(sum[0]);}}});
+    }
+
+    List<Job> blockingDequeJobs(
+        String description,
+        Supplier<BlockingDeque<Integer>> supplier,
+        ArrayList<Integer> al) {
+        return List.of(
+            new Job(description + " timed pollFirst()") {
+                public void work() throws Throwable {
+                    BlockingDeque<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        for (Integer e; (e = x.pollFirst(0L, TimeUnit.DAYS)) != null; )
+                            sum[0] += e;
+                        check.sum(sum[0]);}}},
+            new Job(description + " timed pollLast()") {
+                public void work() throws Throwable {
+                    BlockingDeque<Integer> x = supplier.get();
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(al);
+                        for (Integer e; (e = x.pollLast(0L, TimeUnit.DAYS)) != null; )
+                            sum[0] += e;
+                        check.sum(sum[0]);}}});
+    }
+}
--- a/jdk/test/java/util/Vector/LastIndexOf.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/Vector/LastIndexOf.java	Mon Nov 28 23:36:11 2016 -0800
@@ -22,10 +22,10 @@
  */
 
 /*
-   @test
-   @bug 4271588
-   @summary Vector.lastIndex(Object, int) used to let you look outside the
-            valid range in the backing array
+ * @test
+ * @bug 4271588
+ * @summary Vector.lastIndex(Object, int) used to let you look outside the
+ *          valid range in the backing array
  */
 
 import java.util.*;
--- a/jdk/test/java/util/concurrent/ArrayBlockingQueue/IteratorConsistency.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/ArrayBlockingQueue/IteratorConsistency.java	Mon Nov 28 23:36:11 2016 -0800
@@ -42,9 +42,9 @@
 import java.util.List;
 import java.util.NoSuchElementException;
 import java.util.Queue;
-import java.util.Random;
 import java.util.concurrent.ArrayBlockingQueue;
 import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ThreadLocalRandom;
 
 /*
  * @test
@@ -53,12 +53,12 @@
  */
 
 /**
- * Highly coupled to the implementation of ArrayBlockingQueue.
+ * Tightly coupled to the implementation of ArrayBlockingQueue.
  * Uses reflection to inspect queue and iterator state.
  */
 @SuppressWarnings({"unchecked", "rawtypes"})
 public class IteratorConsistency {
-    final Random rnd = new Random();
+    final ThreadLocalRandom rnd = ThreadLocalRandom.current();
     final int CAPACITY = 20;
     Field itrsField;
     Field itemsField;
@@ -144,6 +144,10 @@
             check(!it.hasNext());
             check(isDetached(it));
         }
+        if (rnd.nextBoolean()) {
+            it.forEachRemaining(e -> { throw new AssertionError(); });
+            checkDetached(it);
+        }
         if (rnd.nextBoolean())
             try { it.next(); fail("should throw"); }
             catch (NoSuchElementException success) {}
--- a/jdk/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java	Mon Nov 28 23:36:11 2016 -0800
@@ -44,7 +44,6 @@
 import java.util.List;
 import java.util.NoSuchElementException;
 import java.util.Queue;
-import java.util.Random;
 import java.util.concurrent.ArrayBlockingQueue;
 import java.util.concurrent.BlockingQueue;
 import java.util.concurrent.ConcurrentLinkedDeque;
@@ -52,10 +51,11 @@
 import java.util.concurrent.LinkedBlockingDeque;
 import java.util.concurrent.LinkedBlockingQueue;
 import java.util.concurrent.LinkedTransferQueue;
+import java.util.concurrent.ThreadLocalRandom;
 
 @SuppressWarnings({"unchecked", "rawtypes"})
 public class IteratorWeakConsistency {
-    final Random rnd = new Random();
+    final ThreadLocalRandom rnd = ThreadLocalRandom.current();
 
     void test(String[] args) throws Throwable {
         test(new LinkedBlockingQueue());
@@ -72,6 +72,9 @@
         if (rnd.nextBoolean()) {
             check(!it.hasNext());
         }
+        if (rnd.nextBoolean()) {
+            it.forEachRemaining(e -> { throw new AssertionError(); });
+        }
         if (rnd.nextBoolean())
             try { it.next(); fail("should throw"); }
             catch (NoSuchElementException success) {}
--- a/jdk/test/java/util/concurrent/tck/ArrayBlockingQueueTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/ArrayBlockingQueueTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -38,6 +38,7 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.Queue;
@@ -46,45 +47,78 @@
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.Executors;
 import java.util.concurrent.ExecutorService;
+import java.util.concurrent.ThreadLocalRandom;
 
 import junit.framework.Test;
 
 public class ArrayBlockingQueueTest extends JSR166TestCase {
 
-    public static class Fair extends BlockingQueueTest {
-        protected BlockingQueue emptyCollection() {
-            return new ArrayBlockingQueue(SIZE, true);
-        }
-    }
-
-    public static class NonFair extends BlockingQueueTest {
-        protected BlockingQueue emptyCollection() {
-            return new ArrayBlockingQueue(SIZE, false);
-        }
-    }
-
     public static void main(String[] args) {
         main(suite(), args);
     }
 
     public static Test suite() {
-        return newTestSuite(ArrayBlockingQueueTest.class,
-                            new Fair().testSuite(),
-                            new NonFair().testSuite());
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return ArrayBlockingQueue.class; }
+            public Collection emptyCollection() {
+                boolean fair = ThreadLocalRandom.current().nextBoolean();
+                return populatedQueue(0, SIZE, 2 * SIZE, fair);
+            }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNulls() { return false; }
+        }
+
+        return newTestSuite(
+            ArrayBlockingQueueTest.class,
+            new Fair().testSuite(),
+            new NonFair().testSuite(),
+            CollectionTest.testSuite(new Implementation()));
+    }
+
+    public static class Fair extends BlockingQueueTest {
+        protected BlockingQueue emptyCollection() {
+            return populatedQueue(0, SIZE, 2 * SIZE, true);
+        }
+    }
+
+    public static class NonFair extends BlockingQueueTest {
+        protected BlockingQueue emptyCollection() {
+            return populatedQueue(0, SIZE, 2 * SIZE, false);
+        }
     }
 
     /**
      * Returns a new queue of given size containing consecutive
-     * Integers 0 ... n.
+     * Integers 0 ... n - 1.
      */
-    private ArrayBlockingQueue<Integer> populatedQueue(int n) {
-        ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<Integer>(n);
+    static ArrayBlockingQueue<Integer> populatedQueue(int n) {
+        return populatedQueue(n, n, n, false);
+    }
+
+    /**
+     * Returns a new queue of given size containing consecutive
+     * Integers 0 ... n - 1, with given capacity range and fairness.
+     */
+    static ArrayBlockingQueue<Integer> populatedQueue(
+        int size, int minCapacity, int maxCapacity, boolean fair) {
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        int capacity = rnd.nextInt(minCapacity, maxCapacity + 1);
+        ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(capacity);
         assertTrue(q.isEmpty());
-        for (int i = 0; i < n; i++)
-            assertTrue(q.offer(new Integer(i)));
-        assertFalse(q.isEmpty());
-        assertEquals(0, q.remainingCapacity());
-        assertEquals(n, q.size());
+        // shuffle circular array elements so they wrap
+        {
+            int n = rnd.nextInt(capacity);
+            for (int i = 0; i < n; i++) q.add(42);
+            for (int i = 0; i < n; i++) q.remove();
+        }
+        for (int i = 0; i < size; i++)
+            assertTrue(q.offer((Integer) i));
+        assertEquals(size == 0, q.isEmpty());
+        assertEquals(capacity - size, q.remainingCapacity());
+        assertEquals(size, q.size());
+        if (size > 0)
+            assertEquals((Integer) 0, q.peek());
         return q;
     }
 
@@ -98,17 +132,25 @@
     /**
      * Constructor throws IAE if capacity argument nonpositive
      */
-    public void testConstructor2() {
-        try {
-            new ArrayBlockingQueue(0);
-            shouldThrow();
-        } catch (IllegalArgumentException success) {}
+    public void testConstructor_nonPositiveCapacity() {
+        for (int i : new int[] { 0, -1, Integer.MIN_VALUE }) {
+            try {
+                new ArrayBlockingQueue(i);
+                shouldThrow();
+            } catch (IllegalArgumentException success) {}
+            for (boolean fair : new boolean[] { true, false }) {
+                try {
+                    new ArrayBlockingQueue(i, fair);
+                    shouldThrow();
+                } catch (IllegalArgumentException success) {}
+            }
+        }
     }
 
     /**
      * Initializing from null Collection throws NPE
      */
-    public void testConstructor3() {
+    public void testConstructor_nullCollection() {
         try {
             new ArrayBlockingQueue(1, true, null);
             shouldThrow();
@@ -143,13 +185,13 @@
     /**
      * Initializing from too large collection throws IAE
      */
-    public void testConstructor6() {
-        Integer[] ints = new Integer[SIZE];
-        for (int i = 0; i < SIZE; ++i)
-            ints[i] = i;
-        Collection<Integer> elements = Arrays.asList(ints);
+    public void testConstructor_collectionTooLarge() {
+        // just barely fits - succeeds
+        new ArrayBlockingQueue(SIZE, false,
+                               Collections.nCopies(SIZE, ""));
         try {
-            new ArrayBlockingQueue(SIZE - 1, false, elements);
+            new ArrayBlockingQueue(SIZE - 1, false,
+                                   Collections.nCopies(SIZE, ""));
             shouldThrow();
         } catch (IllegalArgumentException success) {}
     }
@@ -171,12 +213,12 @@
      * Queue transitions from empty to full when elements added
      */
     public void testEmptyFull() {
-        ArrayBlockingQueue q = new ArrayBlockingQueue(2);
+        BlockingQueue q = populatedQueue(0, 2, 2, false);
         assertTrue(q.isEmpty());
         assertEquals(2, q.remainingCapacity());
         q.add(one);
         assertFalse(q.isEmpty());
-        q.add(two);
+        assertTrue(q.offer(two));
         assertFalse(q.isEmpty());
         assertEquals(0, q.remainingCapacity());
         assertFalse(q.offer(three));
@@ -186,15 +228,18 @@
      * remainingCapacity decreases on add, increases on remove
      */
     public void testRemainingCapacity() {
-        BlockingQueue q = populatedQueue(SIZE);
-        for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, q.remainingCapacity());
-            assertEquals(SIZE, q.size() + q.remainingCapacity());
+        int size = ThreadLocalRandom.current().nextInt(1, SIZE);
+        BlockingQueue q = populatedQueue(size, size, 2 * size, false);
+        int spare = q.remainingCapacity();
+        int capacity = spare + size;
+        for (int i = 0; i < size; i++) {
+            assertEquals(spare + i, q.remainingCapacity());
+            assertEquals(capacity, q.size() + q.remainingCapacity());
             assertEquals(i, q.remove());
         }
-        for (int i = 0; i < SIZE; ++i) {
-            assertEquals(SIZE - i, q.remainingCapacity());
-            assertEquals(SIZE, q.size() + q.remainingCapacity());
+        for (int i = 0; i < size; i++) {
+            assertEquals(capacity - i, q.remainingCapacity());
+            assertEquals(capacity, q.size() + q.remainingCapacity());
             assertTrue(q.add(i));
         }
     }
@@ -213,12 +258,10 @@
      */
     public void testAdd() {
         ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);
-        for (int i = 0; i < SIZE; ++i) {
-            assertTrue(q.add(new Integer(i)));
-        }
+        for (int i = 0; i < SIZE; i++) assertTrue(q.add((Integer) i));
         assertEquals(0, q.remainingCapacity());
         try {
-            q.add(new Integer(SIZE));
+            q.add((Integer) SIZE);
             shouldThrow();
         } catch (IllegalStateException success) {}
     }
@@ -252,13 +295,17 @@
     /**
      * addAll throws ISE if not enough room
      */
-    public void testAddAll4() {
-        ArrayBlockingQueue q = new ArrayBlockingQueue(1);
-        Integer[] ints = new Integer[SIZE];
-        for (int i = 0; i < SIZE; ++i)
-            ints[i] = new Integer(i);
+    public void testAddAll_insufficientSpace() {
+        int size = ThreadLocalRandom.current().nextInt(1, SIZE);
+        ArrayBlockingQueue q = populatedQueue(0, size, size, false);
+        // Just fits:
+        q.addAll(populatedQueue(size, size, 2 * size, false));
+        assertEquals(0, q.remainingCapacity());
+        assertEquals(size, q.size());
+        assertEquals(0, q.peek());
         try {
-            q.addAll(Arrays.asList(ints));
+            q = populatedQueue(0, size, size, false);
+            q.addAll(Collections.nCopies(size + 1, 42));
             shouldThrow();
         } catch (IllegalStateException success) {}
     }
@@ -545,8 +592,10 @@
      * contains(x) reports true when elements added but not yet removed
      */
     public void testContains() {
-        ArrayBlockingQueue q = populatedQueue(SIZE);
-        for (int i = 0; i < SIZE; ++i) {
+        int size = ThreadLocalRandom.current().nextInt(1, SIZE);
+        ArrayBlockingQueue q = populatedQueue(size, size, 2 * size, false);
+        assertFalse(q.contains(null));
+        for (int i = 0; i < size; ++i) {
             assertTrue(q.contains(new Integer(i)));
             assertEquals(i, q.poll());
             assertFalse(q.contains(new Integer(i)));
@@ -557,11 +606,13 @@
      * clear removes all elements
      */
     public void testClear() {
-        ArrayBlockingQueue q = populatedQueue(SIZE);
+        int size = ThreadLocalRandom.current().nextInt(1, 5);
+        ArrayBlockingQueue q = populatedQueue(size, size, 2 * size, false);
+        int capacity = size + q.remainingCapacity();
         q.clear();
         assertTrue(q.isEmpty());
         assertEquals(0, q.size());
-        assertEquals(SIZE, q.remainingCapacity());
+        assertEquals(capacity, q.remainingCapacity());
         q.add(one);
         assertFalse(q.isEmpty());
         assertTrue(q.contains(one));
@@ -618,103 +669,75 @@
         }
     }
 
-    void checkToArray(ArrayBlockingQueue q) {
+    void checkToArray(ArrayBlockingQueue<Integer> q) {
         int size = q.size();
-        Object[] o = q.toArray();
-        assertEquals(size, o.length);
+        Object[] a1 = q.toArray();
+        assertEquals(size, a1.length);
+        Integer[] a2 = q.toArray(new Integer[0]);
+        assertEquals(size, a2.length);
+        Integer[] a3 = q.toArray(new Integer[Math.max(0, size - 1)]);
+        assertEquals(size, a3.length);
+        Integer[] a4 = new Integer[size];
+        assertSame(a4, q.toArray(a4));
+        Integer[] a5 = new Integer[size + 1];
+        Arrays.fill(a5, 42);
+        assertSame(a5, q.toArray(a5));
+        Integer[] a6 = new Integer[size + 2];
+        Arrays.fill(a6, 42);
+        assertSame(a6, q.toArray(a6));
+        Object[][] as = { a1, a2, a3, a4, a5, a6 };
+        for (Object[] a : as) {
+            if (a.length > size) assertNull(a[size]);
+            if (a.length > size + 1) assertEquals(42, a[size + 1]);
+        }
         Iterator it = q.iterator();
+        Integer s = q.peek();
         for (int i = 0; i < size; i++) {
             Integer x = (Integer) it.next();
-            assertEquals((Integer)o[0] + i, (int) x);
-            assertSame(o[i], x);
+            assertEquals(s + i, (int) x);
+            for (Object[] a : as)
+                assertSame(a1[i], x);
         }
     }
 
     /**
-     * toArray() contains all elements in FIFO order
+     * toArray() and toArray(a) contain all elements in FIFO order
      */
     public void testToArray() {
-        ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);
-        for (int i = 0; i < SIZE; i++) {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        final int size = rnd.nextInt(6);
+        final int capacity = Math.max(1, size + rnd.nextInt(size + 1));
+        ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(capacity);
+        for (int i = 0; i < size; i++) {
             checkToArray(q);
             q.add(i);
         }
         // Provoke wraparound
-        for (int i = 0; i < SIZE; i++) {
+        int added = size * 2;
+        for (int i = 0; i < added; i++) {
             checkToArray(q);
-            assertEquals(i, q.poll());
+            assertEquals((Integer) i, q.poll());
+            q.add(size + i);
+        }
+        for (int i = 0; i < size; i++) {
             checkToArray(q);
-            q.add(SIZE + i);
-        }
-        for (int i = 0; i < SIZE; i++) {
-            checkToArray(q);
-            assertEquals(SIZE + i, q.poll());
-        }
-    }
-
-    void checkToArray2(ArrayBlockingQueue q) {
-        int size = q.size();
-        Integer[] a1 = (size == 0) ? null : new Integer[size - 1];
-        Integer[] a2 = new Integer[size];
-        Integer[] a3 = new Integer[size + 2];
-        if (size > 0) Arrays.fill(a1, 42);
-        Arrays.fill(a2, 42);
-        Arrays.fill(a3, 42);
-        Integer[] b1 = (size == 0) ? null : (Integer[]) q.toArray(a1);
-        Integer[] b2 = (Integer[]) q.toArray(a2);
-        Integer[] b3 = (Integer[]) q.toArray(a3);
-        assertSame(a2, b2);
-        assertSame(a3, b3);
-        Iterator it = q.iterator();
-        for (int i = 0; i < size; i++) {
-            Integer x = (Integer) it.next();
-            assertSame(b1[i], x);
-            assertEquals(b1[0] + i, (int) x);
-            assertSame(b2[i], x);
-            assertSame(b3[i], x);
-        }
-        assertNull(a3[size]);
-        assertEquals(42, (int) a3[size + 1]);
-        if (size > 0) {
-            assertNotSame(a1, b1);
-            assertEquals(size, b1.length);
-            for (int i = 0; i < a1.length; i++) {
-                assertEquals(42, (int) a1[i]);
-            }
-        }
-    }
-
-    /**
-     * toArray(a) contains all elements in FIFO order
-     */
-    public void testToArray2() {
-        ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);
-        for (int i = 0; i < SIZE; i++) {
-            checkToArray2(q);
-            q.add(i);
-        }
-        // Provoke wraparound
-        for (int i = 0; i < SIZE; i++) {
-            checkToArray2(q);
-            assertEquals(i, q.poll());
-            checkToArray2(q);
-            q.add(SIZE + i);
-        }
-        for (int i = 0; i < SIZE; i++) {
-            checkToArray2(q);
-            assertEquals(SIZE + i, q.poll());
+            assertEquals((Integer) (added + i), q.poll());
         }
     }
 
     /**
      * toArray(incompatible array type) throws ArrayStoreException
      */
-    public void testToArray1_BadArg() {
+    public void testToArray_incompatibleArrayType() {
         ArrayBlockingQueue q = populatedQueue(SIZE);
         try {
             q.toArray(new String[10]);
             shouldThrow();
         } catch (ArrayStoreException success) {}
+        try {
+            q.toArray(new String[0]);
+            shouldThrow();
+        } catch (ArrayStoreException success) {}
     }
 
     /**
@@ -943,8 +966,8 @@
      */
     public void testNeverContainsNull() {
         Collection<?>[] qs = {
-            new ArrayBlockingQueue<Object>(10),
-            populatedQueue(2),
+            populatedQueue(0, 1, 10, false),
+            populatedQueue(2, 2, 10, true),
         };
 
         for (Collection<?> q : qs) {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/ArrayDeque8Test.java	Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,125 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+import java.util.ArrayDeque;
+import java.util.Collections;
+import java.util.Spliterator;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class ArrayDeque8Test extends JSR166TestCase {
+    public static void main(String[] args) {
+        main(suite(), args);
+    }
+
+    public static Test suite() {
+        return newTestSuite(ArrayDeque8Test.class);
+    }
+
+    /**
+     * Spliterator.getComparator always throws IllegalStateException
+     */
+    public void testSpliterator_getComparator() {
+        assertThrows(IllegalStateException.class,
+                     () -> new ArrayDeque().spliterator().getComparator());
+    }
+
+    /**
+     * Spliterator characteristics are as advertised
+     */
+    public void testSpliterator_characteristics() {
+        ArrayDeque q = new ArrayDeque();
+        Spliterator s = q.spliterator();
+        int characteristics = s.characteristics();
+        int required = Spliterator.NONNULL
+            | Spliterator.ORDERED
+            | Spliterator.SIZED
+            | Spliterator.SUBSIZED;
+        assertEquals(required, characteristics & required);
+        assertTrue(s.hasCharacteristics(required));
+        assertEquals(0, characteristics
+                     & (Spliterator.CONCURRENT
+                        | Spliterator.DISTINCT
+                        | Spliterator.IMMUTABLE
+                        | Spliterator.SORTED));
+    }
+
+    /**
+     * Handle capacities near Integer.MAX_VALUE.
+     * ant -Dvmoptions='-Xms28g -Xmx28g' -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ArrayDeque8Test -Djsr166.methodFilter=testHugeCapacity tck
+     */
+    public void testHugeCapacity() {
+        if (! (testImplementationDetails
+               && expensiveTests
+               && Runtime.getRuntime().maxMemory() > 24L * (1 << 30)))
+            return;
+
+        final Integer e = 42;
+        final int maxArraySize = Integer.MAX_VALUE - 8;
+
+        assertThrows(OutOfMemoryError.class,
+                     () -> new ArrayDeque(Integer.MAX_VALUE));
+
+        {
+            ArrayDeque q = new ArrayDeque(maxArraySize - 1);
+            assertEquals(0, q.size());
+            assertTrue(q.isEmpty());
+            q = null;
+        }
+
+        {
+            ArrayDeque q = new ArrayDeque();
+            assertTrue(q.addAll(Collections.nCopies(maxArraySize - 3, e)));
+            assertEquals(e, q.peekFirst());
+            assertEquals(e, q.peekLast());
+            assertEquals(maxArraySize - 3, q.size());
+            q.addFirst((Integer) 0);
+            q.addLast((Integer) 1);
+            assertEquals((Integer) 0, q.peekFirst());
+            assertEquals((Integer) 1, q.peekLast());
+            assertEquals(maxArraySize - 1, q.size());
+
+            ArrayDeque qq = q;
+            ArrayDeque smallish = new ArrayDeque(
+                Collections.nCopies(Integer.MAX_VALUE - q.size() + 1, e));
+            assertThrows(
+                IllegalStateException.class,
+                () -> qq.addAll(qq),
+                () -> qq.addAll(smallish),
+                () -> smallish.addAll(qq));
+        }
+    }
+
+}
--- a/jdk/test/java/util/concurrent/tck/ArrayDequeTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/ArrayDequeTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -26,19 +26,22 @@
  * However, the following notice accompanied the original version of this
  * file:
  *
- * Written by Doug Lea with assistance from members of JCP JSR-166
- * Expert Group and released to the public domain, as explained at
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
 import java.util.ArrayDeque;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Deque;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.Queue;
 import java.util.Random;
+import java.util.concurrent.ThreadLocalRandom;
 
 import junit.framework.Test;
 import junit.framework.TestSuite;
@@ -49,20 +52,60 @@
     }
 
     public static Test suite() {
-        return new TestSuite(ArrayDequeTest.class);
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return ArrayDeque.class; }
+            public Collection emptyCollection() { return populatedDeque(0); }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return false; }
+            public boolean permitsNulls() { return false; }
+        }
+        return newTestSuite(ArrayDequeTest.class,
+                            CollectionTest.testSuite(new Implementation()));
     }
 
     /**
      * Returns a new deque of given size containing consecutive
-     * Integers 0 ... n.
+     * Integers 0 ... n - 1.
      */
-    private ArrayDeque<Integer> populatedDeque(int n) {
-        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
+    private static ArrayDeque<Integer> populatedDeque(int n) {
+        // Randomize various aspects of memory layout, including
+        // capacity slop and wraparound.
+        final ArrayDeque<Integer> q;
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        switch (rnd.nextInt(6)) {
+        case 0: q = new ArrayDeque<Integer>();      break;
+        case 1: q = new ArrayDeque<Integer>(0);     break;
+        case 2: q = new ArrayDeque<Integer>(1);     break;
+        case 3: q = new ArrayDeque<Integer>(Math.max(0, n - 1)); break;
+        case 4: q = new ArrayDeque<Integer>(n);     break;
+        case 5: q = new ArrayDeque<Integer>(n + 1); break;
+        default: throw new AssertionError();
+        }
+        switch (rnd.nextInt(3)) {
+        case 0:
+            q.addFirst(42);
+            assertEquals((Integer) 42, q.removeLast());
+            break;
+        case 1:
+            q.addLast(42);
+            assertEquals((Integer) 42, q.removeFirst());
+            break;
+        case 2: /* do nothing */ break;
+        default: throw new AssertionError();
+        }
         assertTrue(q.isEmpty());
-        for (int i = 0; i < n; ++i)
-            assertTrue(q.offerLast(new Integer(i)));
-        assertFalse(q.isEmpty());
+        if (rnd.nextBoolean())
+            for (int i = 0; i < n; i++)
+                assertTrue(q.offerLast((Integer) i));
+        else
+            for (int i = n; --i >= 0; )
+                q.addFirst((Integer) i);
         assertEquals(n, q.size());
+        if (n > 0) {
+            assertFalse(q.isEmpty());
+            assertEquals((Integer) 0, q.peekFirst());
+            assertEquals((Integer) (n - 1), q.peekLast());
+        }
         return q;
     }
 
@@ -556,30 +599,48 @@
      * removeFirstOccurrence(x) removes x and returns true if present
      */
     public void testRemoveFirstOccurrence() {
-        ArrayDeque q = populatedDeque(SIZE);
+        Deque<Integer> q = populatedDeque(SIZE);
+        assertFalse(q.removeFirstOccurrence(null));
         for (int i = 1; i < SIZE; i += 2) {
-            assertTrue(q.removeFirstOccurrence(new Integer(i)));
+            assertTrue(q.removeFirstOccurrence(i));
+            assertFalse(q.contains(i));
         }
         for (int i = 0; i < SIZE; i += 2) {
-            assertTrue(q.removeFirstOccurrence(new Integer(i)));
-            assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
+            assertTrue(q.removeFirstOccurrence(i));
+            assertFalse(q.removeFirstOccurrence(i + 1));
+            assertFalse(q.contains(i));
+            assertFalse(q.contains(i + 1));
         }
         assertTrue(q.isEmpty());
+        assertFalse(q.removeFirstOccurrence(null));
+        assertFalse(q.removeFirstOccurrence(42));
+        q = new ArrayDeque();
+        assertFalse(q.removeFirstOccurrence(null));
+        assertFalse(q.removeFirstOccurrence(42));
     }
 
     /**
      * removeLastOccurrence(x) removes x and returns true if present
      */
     public void testRemoveLastOccurrence() {
-        ArrayDeque q = populatedDeque(SIZE);
+        Deque<Integer> q = populatedDeque(SIZE);
+        assertFalse(q.removeLastOccurrence(null));
         for (int i = 1; i < SIZE; i += 2) {
-            assertTrue(q.removeLastOccurrence(new Integer(i)));
+            assertTrue(q.removeLastOccurrence(i));
+            assertFalse(q.contains(i));
         }
         for (int i = 0; i < SIZE; i += 2) {
-            assertTrue(q.removeLastOccurrence(new Integer(i)));
-            assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
+            assertTrue(q.removeLastOccurrence(i));
+            assertFalse(q.removeLastOccurrence(i + 1));
+            assertFalse(q.contains(i));
+            assertFalse(q.contains(i + 1));
         }
         assertTrue(q.isEmpty());
+        assertFalse(q.removeLastOccurrence(null));
+        assertFalse(q.removeLastOccurrence(42));
+        q = new ArrayDeque();
+        assertFalse(q.removeLastOccurrence(null));
+        assertFalse(q.removeLastOccurrence(42));
     }
 
     /**
@@ -652,89 +713,57 @@
         }
     }
 
-    void checkToArray(ArrayDeque q) {
+    void checkToArray(ArrayDeque<Integer> q) {
         int size = q.size();
-        Object[] o = q.toArray();
-        assertEquals(size, o.length);
+        Object[] a1 = q.toArray();
+        assertEquals(size, a1.length);
+        Integer[] a2 = q.toArray(new Integer[0]);
+        assertEquals(size, a2.length);
+        Integer[] a3 = q.toArray(new Integer[Math.max(0, size - 1)]);
+        assertEquals(size, a3.length);
+        Integer[] a4 = new Integer[size];
+        assertSame(a4, q.toArray(a4));
+        Integer[] a5 = new Integer[size + 1];
+        Arrays.fill(a5, 42);
+        assertSame(a5, q.toArray(a5));
+        Integer[] a6 = new Integer[size + 2];
+        Arrays.fill(a6, 42);
+        assertSame(a6, q.toArray(a6));
+        Object[][] as = { a1, a2, a3, a4, a5, a6 };
+        for (Object[] a : as) {
+            if (a.length > size) assertNull(a[size]);
+            if (a.length > size + 1) assertEquals(42, a[size + 1]);
+        }
         Iterator it = q.iterator();
+        Integer s = q.peekFirst();
         for (int i = 0; i < size; i++) {
             Integer x = (Integer) it.next();
-            assertEquals((Integer)o[0] + i, (int) x);
-            assertSame(o[i], x);
+            assertEquals(s + i, (int) x);
+            for (Object[] a : as)
+                assertSame(a1[i], x);
         }
     }
 
     /**
-     * toArray() contains all elements in FIFO order
+     * toArray() and toArray(a) contain all elements in FIFO order
      */
     public void testToArray() {
-        ArrayDeque q = new ArrayDeque();
-        for (int i = 0; i < SIZE; i++) {
+        final int size = ThreadLocalRandom.current().nextInt(10);
+        ArrayDeque<Integer> q = new ArrayDeque<>(size);
+        for (int i = 0; i < size; i++) {
             checkToArray(q);
             q.addLast(i);
         }
         // Provoke wraparound
-        for (int i = 0; i < SIZE; i++) {
+        int added = size * 2;
+        for (int i = 0; i < added; i++) {
             checkToArray(q);
-            assertEquals(i, q.poll());
-            q.addLast(SIZE + i);
+            assertEquals((Integer) i, q.poll());
+            q.addLast(size + i);
         }
-        for (int i = 0; i < SIZE; i++) {
+        for (int i = 0; i < size; i++) {
             checkToArray(q);
-            assertEquals(SIZE + i, q.poll());
-        }
-    }
-
-    void checkToArray2(ArrayDeque q) {
-        int size = q.size();
-        Integer[] a1 = (size == 0) ? null : new Integer[size - 1];
-        Integer[] a2 = new Integer[size];
-        Integer[] a3 = new Integer[size + 2];
-        if (size > 0) Arrays.fill(a1, 42);
-        Arrays.fill(a2, 42);
-        Arrays.fill(a3, 42);
-        Integer[] b1 = (size == 0) ? null : (Integer[]) q.toArray(a1);
-        Integer[] b2 = (Integer[]) q.toArray(a2);
-        Integer[] b3 = (Integer[]) q.toArray(a3);
-        assertSame(a2, b2);
-        assertSame(a3, b3);
-        Iterator it = q.iterator();
-        for (int i = 0; i < size; i++) {
-            Integer x = (Integer) it.next();
-            assertSame(b1[i], x);
-            assertEquals(b1[0] + i, (int) x);
-            assertSame(b2[i], x);
-            assertSame(b3[i], x);
-        }
-        assertNull(a3[size]);
-        assertEquals(42, (int) a3[size + 1]);
-        if (size > 0) {
-            assertNotSame(a1, b1);
-            assertEquals(size, b1.length);
-            for (int i = 0; i < a1.length; i++) {
-                assertEquals(42, (int) a1[i]);
-            }
-        }
-    }
-
-    /**
-     * toArray(a) contains all elements in FIFO order
-     */
-    public void testToArray2() {
-        ArrayDeque q = new ArrayDeque();
-        for (int i = 0; i < SIZE; i++) {
-            checkToArray2(q);
-            q.addLast(i);
-        }
-        // Provoke wraparound
-        for (int i = 0; i < SIZE; i++) {
-            checkToArray2(q);
-            assertEquals(i, q.poll());
-            q.addLast(SIZE + i);
-        }
-        for (int i = 0; i < SIZE; i++) {
-            checkToArray2(q);
-            assertEquals(SIZE + i, q.poll());
+            assertEquals((Integer) (added + i), q.poll());
         }
     }
 
@@ -753,13 +782,17 @@
     /**
      * toArray(incompatible array type) throws ArrayStoreException
      */
-    public void testToArray1_BadArg() {
+    public void testToArray_incompatibleArrayType() {
         ArrayDeque l = new ArrayDeque();
         l.add(new Integer(5));
         try {
             l.toArray(new String[10]);
             shouldThrow();
         } catch (ArrayStoreException success) {}
+        try {
+            l.toArray(new String[0]);
+            shouldThrow();
+        } catch (ArrayStoreException success) {}
     }
 
     /**
@@ -917,6 +950,25 @@
         assertNotSame(y, x);
         assertEquals(x.size(), y.size());
         assertEquals(x.toString(), y.toString());
+        assertEquals(Arrays.toString(x.toArray()), Arrays.toString(y.toArray()));
+        assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+        while (!x.isEmpty()) {
+            assertFalse(y.isEmpty());
+            assertEquals(x.remove(), y.remove());
+        }
+        assertTrue(y.isEmpty());
+    }
+
+    /**
+     * A cloned deque has same elements in same order
+     */
+    public void testClone() throws Exception {
+        ArrayDeque<Integer> x = populatedDeque(SIZE);
+        ArrayDeque<Integer> y = x.clone();
+
+        assertNotSame(y, x);
+        assertEquals(x.size(), y.size());
+        assertEquals(x.toString(), y.toString());
         assertTrue(Arrays.equals(x.toArray(), y.toArray()));
         while (!x.isEmpty()) {
             assertFalse(y.isEmpty());
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/ArrayListTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,66 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class ArrayListTest extends JSR166TestCase {
+    public static void main(String[] args) {
+        main(suite(), args);
+    }
+
+    public static Test suite() {
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return ArrayList.class; }
+            public List emptyCollection() { return new ArrayList(); }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return false; }
+            public boolean permitsNulls() { return true; }
+        }
+        class SubListImplementation extends Implementation {
+            public List emptyCollection() {
+                return super.emptyCollection().subList(0, 0);
+            }
+        }
+        return newTestSuite(
+                // ArrayListTest.class,
+                CollectionTest.testSuite(new Implementation()),
+                CollectionTest.testSuite(new SubListImplementation()));
+    }
+
+}
--- a/jdk/test/java/util/concurrent/tck/Collection8Test.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/Collection8Test.java	Mon Nov 28 23:36:11 2016 -0800
@@ -32,18 +32,35 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
+import static java.util.concurrent.TimeUnit.HOURS;
 import static java.util.concurrent.TimeUnit.MILLISECONDS;
 
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Queue;
+import java.util.Spliterator;
+import java.util.concurrent.BlockingDeque;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.ConcurrentLinkedQueue;
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.Executors;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Future;
+import java.util.concurrent.Phaser;
+import java.util.concurrent.ThreadLocalRandom;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.concurrent.atomic.AtomicLong;
+import java.util.concurrent.atomic.AtomicReference;
 import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
 
 import junit.framework.Test;
 
@@ -66,16 +83,422 @@
                                       impl);
     }
 
+    Object bomb() {
+        return new Object() {
+                public boolean equals(Object x) { throw new AssertionError(); }
+                public int hashCode() { throw new AssertionError(); }
+            };
+    }
+
+    /** Checks properties of empty collections. */
+    public void testEmptyMeansEmpty() throws Throwable {
+        Collection c = impl.emptyCollection();
+        emptyMeansEmpty(c);
+
+        if (c instanceof java.io.Serializable) {
+            try {
+                emptyMeansEmpty(serialClonePossiblyFailing(c));
+            } catch (java.io.NotSerializableException ex) {
+                // excusable when we have a serializable wrapper around
+                // a non-serializable collection, as can happen with:
+                // Vector.subList() => wrapped AbstractList$RandomAccessSubList
+                if (testImplementationDetails
+                    && (! c.getClass().getName().matches(
+                                "java.util.Collections.*")))
+                    throw ex;
+            }
+        }
+
+        Collection clone = cloneableClone(c);
+        if (clone != null)
+            emptyMeansEmpty(clone);
+    }
+
+    void emptyMeansEmpty(Collection c) throws InterruptedException {
+        assertTrue(c.isEmpty());
+        assertEquals(0, c.size());
+        assertEquals("[]", c.toString());
+        {
+            Object[] a = c.toArray();
+            assertEquals(0, a.length);
+            assertSame(Object[].class, a.getClass());
+        }
+        {
+            Object[] a = new Object[0];
+            assertSame(a, c.toArray(a));
+        }
+        {
+            Integer[] a = new Integer[0];
+            assertSame(a, c.toArray(a));
+        }
+        {
+            Integer[] a = { 1, 2, 3};
+            assertSame(a, c.toArray(a));
+            assertNull(a[0]);
+            assertSame(2, a[1]);
+            assertSame(3, a[2]);
+        }
+        assertIteratorExhausted(c.iterator());
+        Consumer alwaysThrows = e -> { throw new AssertionError(); };
+        c.forEach(alwaysThrows);
+        c.iterator().forEachRemaining(alwaysThrows);
+        c.spliterator().forEachRemaining(alwaysThrows);
+        assertFalse(c.spliterator().tryAdvance(alwaysThrows));
+        if (c.spliterator().hasCharacteristics(Spliterator.SIZED))
+            assertEquals(0, c.spliterator().estimateSize());
+        assertFalse(c.contains(bomb()));
+        assertFalse(c.remove(bomb()));
+        if (c instanceof Queue) {
+            Queue q = (Queue) c;
+            assertNull(q.peek());
+            assertNull(q.poll());
+        }
+        if (c instanceof Deque) {
+            Deque d = (Deque) c;
+            assertNull(d.peekFirst());
+            assertNull(d.peekLast());
+            assertNull(d.pollFirst());
+            assertNull(d.pollLast());
+            assertIteratorExhausted(d.descendingIterator());
+            d.descendingIterator().forEachRemaining(alwaysThrows);
+            assertFalse(d.removeFirstOccurrence(bomb()));
+            assertFalse(d.removeLastOccurrence(bomb()));
+        }
+        if (c instanceof BlockingQueue) {
+            BlockingQueue q = (BlockingQueue) c;
+            assertNull(q.poll(0L, MILLISECONDS));
+        }
+        if (c instanceof BlockingDeque) {
+            BlockingDeque q = (BlockingDeque) c;
+            assertNull(q.pollFirst(0L, MILLISECONDS));
+            assertNull(q.pollLast(0L, MILLISECONDS));
+        }
+    }
+
+    public void testNullPointerExceptions() throws InterruptedException {
+        Collection c = impl.emptyCollection();
+        assertThrows(
+            NullPointerException.class,
+            () -> c.addAll(null),
+            () -> c.containsAll(null),
+            () -> c.retainAll(null),
+            () -> c.removeAll(null),
+            () -> c.removeIf(null),
+            () -> c.forEach(null),
+            () -> c.iterator().forEachRemaining(null),
+            () -> c.spliterator().forEachRemaining(null),
+            () -> c.spliterator().tryAdvance(null),
+            () -> c.toArray(null));
+
+        if (!impl.permitsNulls()) {
+            assertThrows(
+                NullPointerException.class,
+                () -> c.add(null));
+        }
+        if (!impl.permitsNulls() && c instanceof Queue) {
+            Queue q = (Queue) c;
+            assertThrows(
+                NullPointerException.class,
+                () -> q.offer(null));
+        }
+        if (!impl.permitsNulls() && c instanceof Deque) {
+            Deque d = (Deque) c;
+            assertThrows(
+                NullPointerException.class,
+                () -> d.addFirst(null),
+                () -> d.addLast(null),
+                () -> d.offerFirst(null),
+                () -> d.offerLast(null),
+                () -> d.push(null),
+                () -> d.descendingIterator().forEachRemaining(null));
+        }
+        if (c instanceof BlockingQueue) {
+            BlockingQueue q = (BlockingQueue) c;
+            assertThrows(
+                NullPointerException.class,
+                () -> {
+                    try { q.offer(null, 1L, HOURS); }
+                    catch (InterruptedException ex) {
+                        throw new AssertionError(ex);
+                    }},
+                () -> {
+                    try { q.put(null); }
+                    catch (InterruptedException ex) {
+                        throw new AssertionError(ex);
+                    }});
+        }
+        if (c instanceof BlockingDeque) {
+            BlockingDeque q = (BlockingDeque) c;
+            assertThrows(
+                NullPointerException.class,
+                () -> {
+                    try { q.offerFirst(null, 1L, HOURS); }
+                    catch (InterruptedException ex) {
+                        throw new AssertionError(ex);
+                    }},
+                () -> {
+                    try { q.offerLast(null, 1L, HOURS); }
+                    catch (InterruptedException ex) {
+                        throw new AssertionError(ex);
+                    }},
+                () -> {
+                    try { q.putFirst(null); }
+                    catch (InterruptedException ex) {
+                        throw new AssertionError(ex);
+                    }},
+                () -> {
+                    try { q.putLast(null); }
+                    catch (InterruptedException ex) {
+                        throw new AssertionError(ex);
+                    }});
+        }
+    }
+
+    public void testNoSuchElementExceptions() {
+        Collection c = impl.emptyCollection();
+        assertThrows(
+            NoSuchElementException.class,
+            () -> c.iterator().next());
+
+        if (c instanceof Queue) {
+            Queue q = (Queue) c;
+            assertThrows(
+                NoSuchElementException.class,
+                () -> q.element(),
+                () -> q.remove());
+        }
+        if (c instanceof Deque) {
+            Deque d = (Deque) c;
+            assertThrows(
+                NoSuchElementException.class,
+                () -> d.getFirst(),
+                () -> d.getLast(),
+                () -> d.removeFirst(),
+                () -> d.removeLast(),
+                () -> d.pop(),
+                () -> d.descendingIterator().next());
+        }
+    }
+
+    public void testRemoveIf() {
+        Collection c = impl.emptyCollection();
+        boolean ordered =
+            c.spliterator().hasCharacteristics(Spliterator.ORDERED);
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        int n = rnd.nextInt(6);
+        for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
+        AtomicReference threwAt = new AtomicReference(null);
+        List orig = rnd.nextBoolean()
+            ? new ArrayList(c)
+            : Arrays.asList(c.toArray());
+
+        // Merely creating an iterator can change ArrayBlockingQueue behavior
+        Iterator it = rnd.nextBoolean() ? c.iterator() : null;
+
+        ArrayList survivors = new ArrayList();
+        ArrayList accepts = new ArrayList();
+        ArrayList rejects = new ArrayList();
+
+        Predicate randomPredicate = e -> {
+            assertNull(threwAt.get());
+            switch (rnd.nextInt(3)) {
+            case 0: accepts.add(e); return true;
+            case 1: rejects.add(e); return false;
+            case 2: threwAt.set(e); throw new ArithmeticException();
+            default: throw new AssertionError();
+            }
+        };
+        try {
+            try {
+                boolean modified = c.removeIf(randomPredicate);
+                assertNull(threwAt.get());
+                assertEquals(modified, accepts.size() > 0);
+                assertEquals(modified, rejects.size() != n);
+                assertEquals(accepts.size() + rejects.size(), n);
+                if (ordered) {
+                    assertEquals(rejects,
+                                 Arrays.asList(c.toArray()));
+                } else {
+                    assertEquals(new HashSet(rejects),
+                                 new HashSet(Arrays.asList(c.toArray())));
+                }
+            } catch (ArithmeticException ok) {
+                assertNotNull(threwAt.get());
+                assertTrue(c.contains(threwAt.get()));
+            }
+            if (it != null && impl.isConcurrent())
+                // check for weakly consistent iterator
+                while (it.hasNext()) assertTrue(orig.contains(it.next()));
+            switch (rnd.nextInt(4)) {
+            case 0: survivors.addAll(c); break;
+            case 1: survivors.addAll(Arrays.asList(c.toArray())); break;
+            case 2: c.forEach(survivors::add); break;
+            case 3: for (Object e : c) survivors.add(e); break;
+            }
+            assertTrue(orig.containsAll(accepts));
+            assertTrue(orig.containsAll(rejects));
+            assertTrue(orig.containsAll(survivors));
+            assertTrue(orig.containsAll(c));
+            assertTrue(c.containsAll(rejects));
+            assertTrue(c.containsAll(survivors));
+            assertTrue(survivors.containsAll(rejects));
+            if (threwAt.get() == null) {
+                assertEquals(n - accepts.size(), c.size());
+                for (Object x : accepts) assertFalse(c.contains(x));
+            } else {
+                // Two acceptable behaviors: entire removeIf call is one
+                // transaction, or each element processed is one transaction.
+                assertTrue(n == c.size() || n == c.size() + accepts.size());
+                int k = 0;
+                for (Object x : accepts) if (c.contains(x)) k++;
+                assertTrue(k == accepts.size() || k == 0);
+            }
+        } catch (Throwable ex) {
+            System.err.println(impl.klazz());
+            // c is at risk of corruption if we got here, so be lenient
+            try { System.err.printf("c=%s%n", c); }
+            catch (Throwable t) { t.printStackTrace(); }
+            System.err.printf("n=%d%n", n);
+            System.err.printf("orig=%s%n", orig);
+            System.err.printf("accepts=%s%n", accepts);
+            System.err.printf("rejects=%s%n", rejects);
+            System.err.printf("survivors=%s%n", survivors);
+            System.err.printf("threwAt=%s%n", threwAt.get());
+            throw ex;
+        }
+    }
+
+    /**
+     * Various ways of traversing a collection yield same elements
+     */
+    public void testIteratorEquivalence() {
+        Collection c = impl.emptyCollection();
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        int n = rnd.nextInt(6);
+        for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
+        ArrayList iterated = new ArrayList();
+        ArrayList iteratedForEachRemaining = new ArrayList();
+        ArrayList tryAdvanced = new ArrayList();
+        ArrayList spliterated = new ArrayList();
+        ArrayList splitonced = new ArrayList();
+        ArrayList forEached = new ArrayList();
+        ArrayList streamForEached = new ArrayList();
+        ConcurrentLinkedQueue parallelStreamForEached = new ConcurrentLinkedQueue();
+        ArrayList removeIfed = new ArrayList();
+        for (Object x : c) iterated.add(x);
+        c.iterator().forEachRemaining(iteratedForEachRemaining::add);
+        for (Spliterator s = c.spliterator();
+             s.tryAdvance(tryAdvanced::add); ) {}
+        c.spliterator().forEachRemaining(spliterated::add);
+        {                       // trySplit returns "strict prefix"
+            Spliterator s1 = c.spliterator(), s2 = s1.trySplit();
+            if (s2 != null) s2.forEachRemaining(splitonced::add);
+            s1.forEachRemaining(splitonced::add);
+        }
+        c.forEach(forEached::add);
+        c.stream().forEach(streamForEached::add);
+        c.parallelStream().forEach(parallelStreamForEached::add);
+        c.removeIf(e -> { removeIfed.add(e); return false; });
+        boolean ordered =
+            c.spliterator().hasCharacteristics(Spliterator.ORDERED);
+        if (c instanceof List || c instanceof Deque)
+            assertTrue(ordered);
+        HashSet cset = new HashSet(c);
+        assertEquals(cset, new HashSet(parallelStreamForEached));
+        if (ordered) {
+            assertEquals(iterated, iteratedForEachRemaining);
+            assertEquals(iterated, tryAdvanced);
+            assertEquals(iterated, spliterated);
+            assertEquals(iterated, splitonced);
+            assertEquals(iterated, forEached);
+            assertEquals(iterated, streamForEached);
+            assertEquals(iterated, removeIfed);
+        } else {
+            assertEquals(cset, new HashSet(iterated));
+            assertEquals(cset, new HashSet(iteratedForEachRemaining));
+            assertEquals(cset, new HashSet(tryAdvanced));
+            assertEquals(cset, new HashSet(spliterated));
+            assertEquals(cset, new HashSet(splitonced));
+            assertEquals(cset, new HashSet(forEached));
+            assertEquals(cset, new HashSet(streamForEached));
+            assertEquals(cset, new HashSet(removeIfed));
+        }
+        if (c instanceof Deque) {
+            Deque d = (Deque) c;
+            ArrayList descending = new ArrayList();
+            ArrayList descendingForEachRemaining = new ArrayList();
+            for (Iterator it = d.descendingIterator(); it.hasNext(); )
+                descending.add(it.next());
+            d.descendingIterator().forEachRemaining(
+                e -> descendingForEachRemaining.add(e));
+            Collections.reverse(descending);
+            Collections.reverse(descendingForEachRemaining);
+            assertEquals(iterated, descending);
+            assertEquals(iterated, descendingForEachRemaining);
+        }
+    }
+
+    /**
+     * Calling Iterator#remove() after Iterator#forEachRemaining
+     * should (maybe) remove last element
+     */
+    public void testRemoveAfterForEachRemaining() {
+        Collection c = impl.emptyCollection();
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        testCollection: {
+            int n = 3 + rnd.nextInt(2);
+            for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
+            Iterator it = c.iterator();
+            assertTrue(it.hasNext());
+            assertEquals(impl.makeElement(0), it.next());
+            assertTrue(it.hasNext());
+            assertEquals(impl.makeElement(1), it.next());
+            it.forEachRemaining(e -> assertTrue(c.contains(e)));
+            if (testImplementationDetails) {
+                if (c instanceof java.util.concurrent.ArrayBlockingQueue) {
+                    assertIteratorExhausted(it);
+                } else {
+                    try { it.remove(); }
+                    catch (UnsupportedOperationException ok) {
+                        break testCollection;
+                    }
+                    assertEquals(n - 1, c.size());
+                    for (int i = 0; i < n - 1; i++)
+                        assertTrue(c.contains(impl.makeElement(i)));
+                    assertFalse(c.contains(impl.makeElement(n - 1)));
+                }
+            }
+        }
+        if (c instanceof Deque) {
+            Deque d = (Deque) impl.emptyCollection();
+            int n = 3 + rnd.nextInt(2);
+            for (int i = 0; i < n; i++) d.add(impl.makeElement(i));
+            Iterator it = d.descendingIterator();
+            assertTrue(it.hasNext());
+            assertEquals(impl.makeElement(n - 1), it.next());
+            assertTrue(it.hasNext());
+            assertEquals(impl.makeElement(n - 2), it.next());
+            it.forEachRemaining(e -> assertTrue(c.contains(e)));
+            if (testImplementationDetails) {
+                it.remove();
+                assertEquals(n - 1, d.size());
+                for (int i = 1; i < n; i++)
+                    assertTrue(d.contains(impl.makeElement(i)));
+                assertFalse(d.contains(impl.makeElement(0)));
+            }
+        }
+    }
+
     /**
      * stream().forEach returns elements in the collection
      */
-    public void testForEach() throws Throwable {
+    public void testStreamForEach() throws Throwable {
         final Collection c = impl.emptyCollection();
         final AtomicLong count = new AtomicLong(0L);
         final Object x = impl.makeElement(1);
         final Object y = impl.makeElement(2);
         final ArrayList found = new ArrayList();
-        Consumer<Object> spy = (o) -> { found.add(o); };
+        Consumer<Object> spy = o -> found.add(o);
         c.stream().forEach(spy);
         assertTrue(found.isEmpty());
 
@@ -96,7 +519,7 @@
         assertTrue(found.isEmpty());
     }
 
-    public void testForEachConcurrentStressTest() throws Throwable {
+    public void testStreamForEachConcurrentStressTest() throws Throwable {
         if (!impl.isConcurrent()) return;
         final Collection c = impl.emptyCollection();
         final long testDurationMillis = timeoutMillis();
@@ -109,7 +532,7 @@
             Runnable checkElt = () -> {
                 threadsStarted.countDown();
                 while (!done.get())
-                    c.stream().forEach((x) -> { assertSame(x, elt); }); };
+                    c.stream().forEach(x -> assertSame(x, elt)); };
             Runnable addRemove = () -> {
                 threadsStarted.countDown();
                 while (!done.get()) {
@@ -124,5 +547,144 @@
         assertNull(f2.get(0L, MILLISECONDS));
     }
 
-    // public void testCollection8DebugFail() { fail(); }
+    /**
+     * collection.forEach returns elements in the collection
+     */
+    public void testForEach() throws Throwable {
+        final Collection c = impl.emptyCollection();
+        final AtomicLong count = new AtomicLong(0L);
+        final Object x = impl.makeElement(1);
+        final Object y = impl.makeElement(2);
+        final ArrayList found = new ArrayList();
+        Consumer<Object> spy = o -> found.add(o);
+        c.forEach(spy);
+        assertTrue(found.isEmpty());
+
+        assertTrue(c.add(x));
+        c.forEach(spy);
+        assertEquals(Collections.singletonList(x), found);
+        found.clear();
+
+        assertTrue(c.add(y));
+        c.forEach(spy);
+        assertEquals(2, found.size());
+        assertTrue(found.contains(x));
+        assertTrue(found.contains(y));
+        found.clear();
+
+        c.clear();
+        c.forEach(spy);
+        assertTrue(found.isEmpty());
+    }
+
+    /**
+     * Motley crew of threads concurrently randomly hammer the collection.
+     */
+    public void testDetectRaces() throws Throwable {
+        if (!impl.isConcurrent()) return;
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        final Collection c = impl.emptyCollection();
+        final long testDurationMillis
+            = expensiveTests ? LONG_DELAY_MS : timeoutMillis();
+        final AtomicBoolean done = new AtomicBoolean(false);
+        final Object one = impl.makeElement(1);
+        final Object two = impl.makeElement(2);
+        final Consumer checkSanity = x -> assertTrue(x == one || x == two);
+        final Consumer<Object[]> checkArraySanity = array -> {
+            // assertTrue(array.length <= 2); // duplicates are permitted
+            for (Object x : array) assertTrue(x == one || x == two);
+        };
+        final Object[] emptyArray =
+            (Object[]) java.lang.reflect.Array.newInstance(one.getClass(), 0);
+        final List<Future<?>> futures;
+        final Phaser threadsStarted = new Phaser(1); // register this thread
+        final Runnable[] frobbers = {
+            () -> c.forEach(checkSanity),
+            () -> c.stream().forEach(checkSanity),
+            () -> c.parallelStream().forEach(checkSanity),
+            () -> c.spliterator().trySplit(),
+            () -> {
+                Spliterator s = c.spliterator();
+                s.tryAdvance(checkSanity);
+                s.trySplit();
+            },
+            () -> {
+                Spliterator s = c.spliterator();
+                do {} while (s.tryAdvance(checkSanity));
+            },
+            () -> { for (Object x : c) checkSanity.accept(x); },
+            () -> checkArraySanity.accept(c.toArray()),
+            () -> checkArraySanity.accept(c.toArray(emptyArray)),
+            () -> {
+                assertTrue(c.add(one));
+                assertTrue(c.contains(one));
+                assertTrue(c.remove(one));
+                assertFalse(c.contains(one));
+            },
+            () -> {
+                assertTrue(c.add(two));
+                assertTrue(c.contains(two));
+                assertTrue(c.remove(two));
+                assertFalse(c.contains(two));
+            },
+        };
+        final List<Runnable> tasks =
+            Arrays.stream(frobbers)
+            .filter(task -> rnd.nextBoolean()) // random subset
+            .map(task -> (Runnable) () -> {
+                     threadsStarted.arriveAndAwaitAdvance();
+                     while (!done.get())
+                         task.run();
+                 })
+            .collect(Collectors.toList());
+        final ExecutorService pool = Executors.newCachedThreadPool();
+        try (PoolCleaner cleaner = cleaner(pool, done)) {
+            threadsStarted.bulkRegister(tasks.size());
+            futures = tasks.stream()
+                .map(pool::submit)
+                .collect(Collectors.toList());
+            threadsStarted.arriveAndDeregister();
+            Thread.sleep(testDurationMillis);
+        }
+        for (Future future : futures)
+            assertNull(future.get(0L, MILLISECONDS));
+    }
+
+    /**
+     * Spliterators are either IMMUTABLE or truly late-binding or, if
+     * concurrent, use the same "late-binding style" of returning
+     * elements added between creation and first use.
+     */
+    public void testLateBindingStyle() {
+        if (!testImplementationDetails) return;
+        if (impl.klazz() == ArrayList.class) return; // for jdk8
+        // Immutable (snapshot) spliterators are exempt
+        if (impl.emptyCollection().spliterator()
+            .hasCharacteristics(Spliterator.IMMUTABLE))
+            return;
+        final Object one = impl.makeElement(1);
+        {
+            final Collection c = impl.emptyCollection();
+            final Spliterator split = c.spliterator();
+            c.add(one);
+            assertTrue(split.tryAdvance(e -> { assertSame(e, one); }));
+            assertFalse(split.tryAdvance(e -> { throw new AssertionError(); }));
+            assertTrue(c.contains(one));
+        }
+        {
+            final AtomicLong count = new AtomicLong(0);
+            final Collection c = impl.emptyCollection();
+            final Spliterator split = c.spliterator();
+            c.add(one);
+            split.forEachRemaining(
+                e -> { assertSame(e, one); count.getAndIncrement(); });
+            assertEquals(1L, count.get());
+            assertFalse(split.tryAdvance(e -> { throw new AssertionError(); }));
+            assertTrue(c.contains(one));
+        }
+    }
+
+//     public void testCollection8DebugFail() {
+//         fail(impl.klazz().getSimpleName());
+//     }
 }
--- a/jdk/test/java/util/concurrent/tck/CollectionTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/CollectionTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -32,8 +32,6 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
-import java.util.Collection;
-
 import junit.framework.Test;
 
 /**
@@ -58,11 +56,7 @@
                                         impl));
     }
 
-    /** A test of the CollectionImplementation implementation ! */
-    public void testEmptyMeansEmpty() {
-        assertTrue(impl.emptyCollection().isEmpty());
-        assertEquals(0, impl.emptyCollection().size());
-    }
-
-    // public void testCollectionDebugFail() { fail(); }
+//     public void testCollectionDebugFail() {
+//         fail(impl.klazz().getSimpleName());
+//     }
 }
--- a/jdk/test/java/util/concurrent/tck/CopyOnWriteArrayListTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/CopyOnWriteArrayListTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -53,7 +53,22 @@
     }
 
     public static Test suite() {
-        return new TestSuite(CopyOnWriteArrayListTest.class);
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return ArrayList.class; }
+            public List emptyCollection() { return new CopyOnWriteArrayList(); }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNulls() { return true; }
+        }
+        class SubListImplementation extends Implementation {
+            public List emptyCollection() {
+                return super.emptyCollection().subList(0, 0);
+            }
+        }
+        return newTestSuite(
+                CopyOnWriteArrayListTest.class,
+                CollectionTest.testSuite(new Implementation()),
+                CollectionTest.testSuite(new SubListImplementation()));
     }
 
     static CopyOnWriteArrayList<Integer> populatedArray(int n) {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/CountedCompleter8Test.java	Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,168 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
+import static java.util.concurrent.TimeUnit.SECONDS;
+
+import java.util.concurrent.CountedCompleter;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class CountedCompleter8Test extends JSR166TestCase {
+
+    public static void main(String[] args) {
+        main(suite(), args);
+    }
+
+    public static Test suite() {
+        return new TestSuite(CountedCompleter8Test.class);
+    }
+
+    /** CountedCompleter class javadoc code sample, version 1. */
+    public static <E> void forEach1(E[] array, Consumer<E> action) {
+        class Task extends CountedCompleter<Void> {
+            final int lo, hi;
+            Task(Task parent, int lo, int hi) {
+                super(parent); this.lo = lo; this.hi = hi;
+            }
+
+            public void compute() {
+                if (hi - lo >= 2) {
+                    int mid = (lo + hi) >>> 1;
+                    // must set pending count before fork
+                    setPendingCount(2);
+                    new Task(this, mid, hi).fork(); // right child
+                    new Task(this, lo, mid).fork(); // left child
+                }
+                else if (hi > lo)
+                    action.accept(array[lo]);
+                tryComplete();
+            }
+        }
+        new Task(null, 0, array.length).invoke();
+    }
+
+    /** CountedCompleter class javadoc code sample, version 2. */
+    public static <E> void forEach2(E[] array, Consumer<E> action) {
+        class Task extends CountedCompleter<Void> {
+            final int lo, hi;
+            Task(Task parent, int lo, int hi) {
+                super(parent); this.lo = lo; this.hi = hi;
+            }
+
+            public void compute() {
+                if (hi - lo >= 2) {
+                    int mid = (lo + hi) >>> 1;
+                    setPendingCount(1); // looks off by one, but correct!
+                    new Task(this, mid, hi).fork(); // right child
+                    new Task(this, lo, mid).compute(); // direct invoke
+                } else {
+                    if (hi > lo)
+                        action.accept(array[lo]);
+                    tryComplete();
+                }
+            }
+        }
+        new Task(null, 0, array.length).invoke();
+    }
+
+    /** CountedCompleter class javadoc code sample, version 3. */
+    public static <E> void forEach3(E[] array, Consumer<E> action) {
+        class Task extends CountedCompleter<Void> {
+            final int lo, hi;
+            Task(Task parent, int lo, int hi) {
+                super(parent); this.lo = lo; this.hi = hi;
+            }
+
+            public void compute() {
+                int n = hi - lo;
+                for (; n >= 2; n /= 2) {
+                    addToPendingCount(1);
+                    new Task(this, lo + n/2, lo + n).fork();
+                }
+                if (n > 0)
+                    action.accept(array[lo]);
+                propagateCompletion();
+            }
+        }
+        new Task(null, 0, array.length).invoke();
+    }
+
+    /** CountedCompleter class javadoc code sample, version 4. */
+    public static <E> void forEach4(E[] array, Consumer<E> action) {
+        class Task extends CountedCompleter<Void> {
+            final int lo, hi;
+            Task(Task parent, int lo, int hi) {
+                super(parent, 31 - Integer.numberOfLeadingZeros(hi - lo));
+                this.lo = lo; this.hi = hi;
+            }
+
+            public void compute() {
+                for (int n = hi - lo; n >= 2; n /= 2)
+                    new Task(this, lo + n/2, lo + n).fork();
+                action.accept(array[lo]);
+                propagateCompletion();
+            }
+        }
+        if (array.length > 0)
+            new Task(null, 0, array.length).invoke();
+    }
+
+    void testRecursiveDecomposition(
+        BiConsumer<Integer[], Consumer<Integer>> action) {
+        int n = ThreadLocalRandom.current().nextInt(8);
+        Integer[] a = new Integer[n];
+        for (int i = 0; i < n; i++) a[i] = i + 1;
+        AtomicInteger ai = new AtomicInteger(0);
+        action.accept(a, ai::addAndGet);
+        assertEquals(n * (n + 1) / 2, ai.get());
+    }
+
+    /**
+     * Variants of divide-by-two recursive decomposition into leaf tasks,
+     * as described in the CountedCompleter class javadoc code samples
+     */
+    public void testRecursiveDecomposition() {
+        testRecursiveDecomposition(CountedCompleter8Test::forEach1);
+        testRecursiveDecomposition(CountedCompleter8Test::forEach2);
+        testRecursiveDecomposition(CountedCompleter8Test::forEach3);
+        testRecursiveDecomposition(CountedCompleter8Test::forEach4);
+    }
+
+}
--- a/jdk/test/java/util/concurrent/tck/CountedCompleterTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/CountedCompleterTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -44,8 +44,6 @@
 import java.util.concurrent.TimeoutException;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
 
 import junit.framework.Test;
 import junit.framework.TestSuite;
@@ -1872,115 +1870,4 @@
         testInvokeOnPool(singletonPool(), a);
     }
 
-    /** CountedCompleter class javadoc code sample, version 1. */
-    public static <E> void forEach1(E[] array, Consumer<E> action) {
-        class Task extends CountedCompleter<Void> {
-            final int lo, hi;
-            Task(Task parent, int lo, int hi) {
-                super(parent); this.lo = lo; this.hi = hi;
-            }
-
-            public void compute() {
-                if (hi - lo >= 2) {
-                    int mid = (lo + hi) >>> 1;
-                    // must set pending count before fork
-                    setPendingCount(2);
-                    new Task(this, mid, hi).fork(); // right child
-                    new Task(this, lo, mid).fork(); // left child
-                }
-                else if (hi > lo)
-                    action.accept(array[lo]);
-                tryComplete();
-            }
-        }
-        new Task(null, 0, array.length).invoke();
-    }
-
-    /** CountedCompleter class javadoc code sample, version 2. */
-    public static <E> void forEach2(E[] array, Consumer<E> action) {
-        class Task extends CountedCompleter<Void> {
-            final int lo, hi;
-            Task(Task parent, int lo, int hi) {
-                super(parent); this.lo = lo; this.hi = hi;
-            }
-
-            public void compute() {
-                if (hi - lo >= 2) {
-                    int mid = (lo + hi) >>> 1;
-                    setPendingCount(1); // looks off by one, but correct!
-                    new Task(this, mid, hi).fork(); // right child
-                    new Task(this, lo, mid).compute(); // direct invoke
-                } else {
-                    if (hi > lo)
-                        action.accept(array[lo]);
-                    tryComplete();
-                }
-            }
-        }
-        new Task(null, 0, array.length).invoke();
-    }
-
-    /** CountedCompleter class javadoc code sample, version 3. */
-    public static <E> void forEach3(E[] array, Consumer<E> action) {
-        class Task extends CountedCompleter<Void> {
-            final int lo, hi;
-            Task(Task parent, int lo, int hi) {
-                super(parent); this.lo = lo; this.hi = hi;
-            }
-
-            public void compute() {
-                int n = hi - lo;
-                for (; n >= 2; n /= 2) {
-                    addToPendingCount(1);
-                    new Task(this, lo + n/2, lo + n).fork();
-                }
-                if (n > 0)
-                    action.accept(array[lo]);
-                propagateCompletion();
-            }
-        }
-        new Task(null, 0, array.length).invoke();
-    }
-
-    /** CountedCompleter class javadoc code sample, version 4. */
-    public static <E> void forEach4(E[] array, Consumer<E> action) {
-        class Task extends CountedCompleter<Void> {
-            final int lo, hi;
-            Task(Task parent, int lo, int hi) {
-                super(parent, 31 - Integer.numberOfLeadingZeros(hi - lo));
-                this.lo = lo; this.hi = hi;
-            }
-
-            public void compute() {
-                for (int n = hi - lo; n >= 2; n /= 2)
-                    new Task(this, lo + n/2, lo + n).fork();
-                action.accept(array[lo]);
-                propagateCompletion();
-            }
-        }
-        if (array.length > 0)
-            new Task(null, 0, array.length).invoke();
-    }
-
-    void testRecursiveDecomposition(
-        BiConsumer<Integer[], Consumer<Integer>> action) {
-        int n = ThreadLocalRandom.current().nextInt(8);
-        Integer[] a = new Integer[n];
-        for (int i = 0; i < n; i++) a[i] = i + 1;
-        AtomicInteger ai = new AtomicInteger(0);
-        action.accept(a, (x) -> ai.addAndGet(x));
-        assertEquals(n * (n + 1) / 2, ai.get());
-    }
-
-    /**
-     * Variants of divide-by-two recursive decomposition into leaf tasks,
-     * as described in the CountedCompleter class javadoc code samples
-     */
-    public void testRecursiveDecomposition() {
-        testRecursiveDecomposition(CountedCompleterTest::forEach1);
-        testRecursiveDecomposition(CountedCompleterTest::forEach2);
-        testRecursiveDecomposition(CountedCompleterTest::forEach3);
-        testRecursiveDecomposition(CountedCompleterTest::forEach4);
-    }
-
 }
--- a/jdk/test/java/util/concurrent/tck/DelayQueueTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/DelayQueueTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -66,8 +66,16 @@
     }
 
     public static Test suite() {
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return DelayQueue.class; }
+            public Collection emptyCollection() { return new DelayQueue(); }
+            public Object makeElement(int i) { return new PDelay(i); }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNulls() { return false; }
+        }
         return newTestSuite(DelayQueueTest.class,
-                            new Generic().testSuite());
+                            new Generic().testSuite(),
+                            CollectionTest.testSuite(new Implementation()));
     }
 
     /**
@@ -144,7 +152,7 @@
 
     /**
      * Returns a new queue of given size containing consecutive
-     * PDelays 0 ... n.
+     * PDelays 0 ... n - 1.
      */
     private DelayQueue<PDelay> populatedQueue(int n) {
         DelayQueue<PDelay> q = new DelayQueue<PDelay>();
@@ -156,6 +164,7 @@
         assertFalse(q.isEmpty());
         assertEquals(Integer.MAX_VALUE, q.remainingCapacity());
         assertEquals(n, q.size());
+        assertEquals(new PDelay(0), q.peek());
         return q;
     }
 
--- a/jdk/test/java/util/concurrent/tck/JSR166TestCase.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/JSR166TestCase.java	Mon Nov 28 23:36:11 2016 -0800
@@ -68,6 +68,7 @@
 import java.security.SecurityPermission;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.Date;
 import java.util.Enumeration;
@@ -474,6 +475,7 @@
             AbstractQueuedLongSynchronizerTest.suite(),
             ArrayBlockingQueueTest.suite(),
             ArrayDequeTest.suite(),
+            ArrayListTest.suite(),
             AtomicBooleanTest.suite(),
             AtomicIntegerArrayTest.suite(),
             AtomicIntegerFieldUpdaterTest.suite(),
@@ -496,6 +498,7 @@
             CopyOnWriteArrayListTest.suite(),
             CopyOnWriteArraySetTest.suite(),
             CountDownLatchTest.suite(),
+            CountedCompleterTest.suite(),
             CyclicBarrierTest.suite(),
             DelayQueueTest.suite(),
             EntryTest.suite(),
@@ -524,15 +527,17 @@
             TreeMapTest.suite(),
             TreeSetTest.suite(),
             TreeSubMapTest.suite(),
-            TreeSubSetTest.suite());
+            TreeSubSetTest.suite(),
+            VectorTest.suite());
 
         // Java8+ test classes
         if (atLeastJava8()) {
             String[] java8TestClassNames = {
+                "ArrayDeque8Test",
                 "Atomic8Test",
                 "CompletableFutureTest",
                 "ConcurrentHashMap8Test",
-                "CountedCompleterTest",
+                "CountedCompleter8Test",
                 "DoubleAccumulatorTest",
                 "DoubleAdderTest",
                 "ForkJoinPool8Test",
@@ -1850,12 +1855,22 @@
         }
     }
 
+    void assertImmutable(final Object o) {
+        if (o instanceof Collection) {
+            assertThrows(
+                UnsupportedOperationException.class,
+                new Runnable() { public void run() {
+                        ((Collection) o).add(null);}});
+        }
+    }
+
     @SuppressWarnings("unchecked")
     <T> T serialClone(T o) {
         try {
             ObjectInputStream ois = new ObjectInputStream
                 (new ByteArrayInputStream(serialBytes(o)));
             T clone = (T) ois.readObject();
+            if (o == clone) assertImmutable(o);
             assertSame(o.getClass(), clone.getClass());
             return clone;
         } catch (Throwable fail) {
@@ -1864,6 +1879,46 @@
         }
     }
 
+    /**
+     * A version of serialClone that leaves error handling (for
+     * e.g. NotSerializableException) up to the caller.
+     */
+    @SuppressWarnings("unchecked")
+    <T> T serialClonePossiblyFailing(T o)
+        throws ReflectiveOperationException, java.io.IOException {
+        ByteArrayOutputStream bos = new ByteArrayOutputStream();
+        ObjectOutputStream oos = new ObjectOutputStream(bos);
+        oos.writeObject(o);
+        oos.flush();
+        oos.close();
+        ObjectInputStream ois = new ObjectInputStream
+            (new ByteArrayInputStream(bos.toByteArray()));
+        T clone = (T) ois.readObject();
+        if (o == clone) assertImmutable(o);
+        assertSame(o.getClass(), clone.getClass());
+        return clone;
+    }
+
+    /**
+     * If o implements Cloneable and has a public clone method,
+     * returns a clone of o, else null.
+     */
+    @SuppressWarnings("unchecked")
+    <T> T cloneableClone(T o) {
+        if (!(o instanceof Cloneable)) return null;
+        final T clone;
+        try {
+            clone = (T) o.getClass().getMethod("clone").invoke(o);
+        } catch (NoSuchMethodException ok) {
+            return null;
+        } catch (ReflectiveOperationException unexpected) {
+            throw new Error(unexpected);
+        }
+        assertNotSame(o, clone); // not 100% guaranteed by spec
+        assertSame(o.getClass(), clone.getClass());
+        return clone;
+    }
+
     public void assertThrows(Class<? extends Throwable> expectedExceptionClass,
                              Runnable... throwingActions) {
         for (Runnable throwingAction : throwingActions) {
--- a/jdk/test/java/util/concurrent/tck/LinkedBlockingDequeTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/LinkedBlockingDequeTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -68,14 +68,22 @@
     }
 
     public static Test suite() {
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return LinkedBlockingDeque.class; }
+            public Collection emptyCollection() { return new LinkedBlockingDeque(); }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNulls() { return false; }
+        }
         return newTestSuite(LinkedBlockingDequeTest.class,
                             new Unbounded().testSuite(),
-                            new Bounded().testSuite());
+                            new Bounded().testSuite(),
+                            CollectionTest.testSuite(new Implementation()));
     }
 
     /**
      * Returns a new deque of given size containing consecutive
-     * Integers 0 ... n.
+     * Integers 0 ... n - 1.
      */
     private LinkedBlockingDeque<Integer> populatedDeque(int n) {
         LinkedBlockingDeque<Integer> q =
@@ -86,6 +94,8 @@
         assertFalse(q.isEmpty());
         assertEquals(0, q.remainingCapacity());
         assertEquals(n, q.size());
+        assertEquals((Integer) 0, q.peekFirst());
+        assertEquals((Integer) (n - 1), q.peekLast());
         return q;
     }
 
--- a/jdk/test/java/util/concurrent/tck/LinkedBlockingQueueTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/LinkedBlockingQueueTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -68,14 +68,22 @@
     }
 
     public static Test suite() {
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return LinkedBlockingQueue.class; }
+            public Collection emptyCollection() { return new LinkedBlockingQueue(); }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNulls() { return false; }
+        }
         return newTestSuite(LinkedBlockingQueueTest.class,
                             new Unbounded().testSuite(),
-                            new Bounded().testSuite());
+                            new Bounded().testSuite(),
+                            CollectionTest.testSuite(new Implementation()));
     }
 
     /**
      * Returns a new queue of given size containing consecutive
-     * Integers 0 ... n.
+     * Integers 0 ... n - 1.
      */
     private LinkedBlockingQueue<Integer> populatedQueue(int n) {
         LinkedBlockingQueue<Integer> q =
@@ -86,6 +94,7 @@
         assertFalse(q.isEmpty());
         assertEquals(0, q.remainingCapacity());
         assertEquals(n, q.size());
+        assertEquals((Integer) 0, q.peek());
         return q;
     }
 
--- a/jdk/test/java/util/concurrent/tck/LinkedListTest.java	Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/LinkedListTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -48,12 +48,27 @@
     }
 
     public static Test suite() {
-        return new TestSuite(LinkedListTest.class);
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return LinkedList.class; }
+            public Collection emptyCollection() { return new LinkedList(); }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return false; }
+            public boolean permitsNulls() { return true; }
+        }
+        class SubListImplementation extends Implementation {
+            public Collection emptyCollection() {
+                return new LinkedList().subList(0, 0);
+            }
+        }
+        return newTestSuite(
+                LinkedListTest.class,
+                CollectionTest.testSuite(new Implementation()),
+                CollectionTest.testSuite(new SubListImplementation()));
     }
 
     /**
      * Returns a new queue of given size containing consecutive
-     * Integers 0 ... n.
+     * Integers 0 ... n - 1.
      */
     private LinkedList<Integer> populatedQueue(int n) {
         LinkedList<Integer> q = new LinkedList<Integer>();
@@ -62,6 +77,8 @@
             assertTrue(q.offer(new Integer(i)));
         assertFalse(q.isEmpty());
         assertEquals(n, q.size());
+        assertEquals((Integer) 0, q.peekFirst());
+        assertEquals((Integer) (n - 1), q.peekLast());
         return q;
     }
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/VectorTest.java	Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,66 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+import java.util.Vector;
+import java.util.Collection;
+import java.util.List;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class VectorTest extends JSR166TestCase {
+    public static void main(String[] args) {
+        main(suite(), args);
+    }
+
+    public static Test suite() {
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return Vector.class; }
+            public List emptyCollection() { return new Vector(); }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return false; }
+            public boolean permitsNulls() { return true; }
+        }
+        class SubListImplementation extends Implementation {
+            public List emptyCollection() {
+                return super.emptyCollection().subList(0, 0);
+            }
+        }
+        return newTestSuite(
+                // VectorTest.class,
+                CollectionTest.testSuite(new Implementation()),
+                CollectionTest.testSuite(new SubListImplementation()));
+    }
+
+}