Recently, while working on the design of a high-performance data structure in Java, I made a startling discovery about the performance of ArrayList.removeAll(). Namely, that the average runtime performance of this method under Sun's Java 6 SDK is O(ns), where n is the size of the array list and s is the number of items to remove! Worst case performance is an even more dismal O(n2).

This short article explains the problem in detail, and illustrates two solutions with O(n) worst-case performance. Finally, a concrete performance test is presented to justify the theoretical discussion.

The Problem

The problem with ArrayList.removeAll was discovered in Sun's Java 6 SDK. ArrayList does not directly implement the removeAll() method: rather, it is implemented by its superclass AbstractCollection. The listing below shows the implementation of that method.

public boolean removeAll(Collection c) {
    boolean modified = false;
    Iterator e = iterator();
    while (e.hasNext()) {
      if (c.contains(e.next())) {
        e.remove();
        modified = true;
      }
    }
   return modified;
}

Two Solutions

Luckily, correcting the performance of removeAll() happens to be rather easy. Only a single pass through the array is required, and the algorithms are in-place to boot. The listing below shows a simple re-implementations of removeAll within the ArrayList class itself.

public boolean removeAll(Collection c) {
    int x=0;
    int i=0;
    for (i=0; i<size; i++) {
      if (!c.contains(elementData[i])) {
        elementData[x++] = elementData[i];
      }
    }
    size=x;
    return x != i;
 }

Note that this implementation also avoids unnecessary re-computation of a modified flag. The standard algorithm recomputes its modified flag for each item removed. This algorithm would be optimal if it weren't for the fact that most operating systems provide extremely fast native operations for moving blocks of memory around, and this algorithm doesn't manage to get in on the action.

To take advantage of fast memory copies, we need to utilize System.arraycopy() to move data around. This comes at the expense of a more complicated implementation.

public boolean removeAll(Collection c) {
    int oldHi=0, newHi=0, top=0;
    for (int i=0; i<size; ++i) {
        if (c.contains(elementData[i])) {
            oldHi = newHi;
            newHi = i;
    
           // at the end of this loop badHi will be the non-inclusive
           // upper limit of the range to delete.
           //
           while (++newHi<size && c.contains(elementData[newHi]));
      
           final int length = i - oldHi;
           System.arraycopy(elementData, oldHi, elementData, top, length);
           i = newHi;
           top += length;
       }
    }
    if (newHi > 0) {
      System.arraycopy(elementData, newHi, elementData, top, size - newHi);
      size += top - newHi;
      return true;
    } else {
      return false;
    }
}

The algorithm above represents my best effort at speed. It copies blocks rather than individual elements, and uses native code to move the data. Like the previous function, it doesn't waste time recomputing a modification flag.

A series of benchmarks and their results are available from the original source of this article at:

testing java.util.ArrayList
  removing 150 from head of list (size=2500) average time=10033207ns.
  removing 150 from tail of list (size=2500) average time=9554117ns.
  removing nothing from list (size=2500) average time=255920ns.
  removing 150 from interleaved every other with the first 300 of list (size=2500) average time=9841237ns.
  removing 150 random items from list (size=2500) average time=9800201ns.
testing org.ahmadsoft.arrays.ArrayList2
  removing 150 from head of list (size=2500) average time=9270435ns.
  removing 150 from tail of list (size=2500) average time=9104636ns.
  removing nothing from list (size=2500) average time=106303ns.
  removing 150 from interleaved every other with the first 300 of list (size=2500) average time=8959013ns.
  removing 150 random items from list (size=2500) average time=9193129ns.
testing org.ahmadsoft.arrays.ArrayList3
  removing 150 from head of list (size=2500) average time=8991530ns.
  removing 150 from tail of list (size=2500) average time=10572200ns.
  removing nothing from list (size=2500) average time=78511ns.
  removing 150 from interleaved every other with the first 300 of list (size=2500) average time=8503098ns.
  removing 150 random items from list (size=2500) average time=9291676ns.
testing org.ahmadsoft.arrays.ArrayList4
  removing 150 from head of list (size=2500) average time=212747ns.
  removing 150 from tail of list (size=2500) average time=209233ns.
  removing nothing from list (size=2500) average time=138670ns.
  removing 150 from interleaved every other with the first 300 of list (size=2500) average time=218966ns.
  removing 150 random items from list (size=2500) average time=230186ns.