--- jsr166/src/main/java/util/ArrayList.java	2016/10/17 21:46:27	1.33
+++ jsr166/src/main/java/util/ArrayList.java	2016/11/13 02:10:09	1.39
@@ -104,7 +104,6 @@ import java.util.function.UnaryOperator;
  * @see     Vector
  * @since   1.2
  */
-
 public class ArrayList<E> extends AbstractList<E>
         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 {
@@ -424,6 +423,11 @@ public class ArrayList<E> extends Abstra
         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.
      *
@@ -717,7 +721,6 @@ public class ArrayList<E> extends Abstra
      * @see Collection#contains(Object)
      */
     public boolean removeAll(Collection<?> c) {
-        Objects.requireNonNull(c);
         return batchRemove(c, false);
     }
 
@@ -738,34 +741,33 @@ public class ArrayList<E> extends Abstra
      * @see Collection#contains(Object)
      */
     public boolean retainAll(Collection<?> c) {
-        Objects.requireNonNull(c);
         return batchRemove(c, true);
     }
 
     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;
+        Objects.requireNonNull(c);
+        final Object[] es = elementData;
+        final int end = size;
+        final boolean modified;
+        int r;
+        // Optimize for initial run of survivors
+        for (r = 0; 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 {
+                modCount += end - w;
+                Arrays.fill(es, size = w, end, null);
             }
         }
         return modified;
@@ -1348,11 +1350,10 @@ public class ArrayList<E> extends Abstra
     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]);
+        for (int i = 0; modCount == expectedModCount && i < size; i++) {
+            action.accept(elementAt(es, i));
         }
         if (modCount != expectedModCount) {
             throw new ConcurrentModificationException();
@@ -1495,48 +1496,60 @@ public class ArrayList<E> extends Abstra
         }
     }
 
+    // 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;
+    }
+
     @Override
-    public boolean removeIf(Predicate<? super E> filter) {
+        public boolean removeIf(Predicate<? super E> filter) {
         Objects.requireNonNull(filter);
-        final int expectedModCount = modCount;
-        final Object[] elementData = this.elementData;
-        int r = 0, w = 0, remaining = size, deleted = 0;
-        try {
-            for (; remaining > 0; remaining--, r++) {
-                @SuppressWarnings("unchecked") E e = (E) elementData[r];
-                if (filter.test(e))
-                    deleted++;
-                else {
-                    if (r != w)
-                        elementData[w] = e;
-                    w++;
-                }
-            }
-            if (modCount != expectedModCount)
-                throw new ConcurrentModificationException();
-            return deleted > 0;
-        } catch (Throwable ex) {
-            for (; remaining > 0; remaining--, r++, w++)
-                elementData[w] = elementData[r];
-            throw ex;
-        } finally {
-            if (deleted > 0) {
-                modCount++;
-                size -= deleted;
-                while (--deleted >= 0)
-                    elementData[w++] = null;
-            }
+        int expectedModCount = modCount;
+        final Object[] es = elementData;
+        final int end = size;
+        final boolean modified;
+        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 (modified = (i < end)) {
+            expectedModCount++;
+            modCount++;
+            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);
+            int w = beg;
+            for (i = beg; i < end; i++)
+                if (isClear(deathRow, i - beg))
+                    es[w++] = es[i];
+            Arrays.fill(es, size = w, end, null);
         }
+        if (modCount != expectedModCount)
+            throw new ConcurrentModificationException();
+        return modified;
     }
 
     @Override
-    @SuppressWarnings("unchecked")
     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]);
+            es[i] = operator.apply(elementAt(es, i));
         }
         if (modCount != expectedModCount) {
             throw new ConcurrentModificationException();