Optimizing ArrayList.removeAll

February 28, 2007

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(n^2)\). 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.

 1  public boolean removeAll(Collection c) {
 2    boolean modified = false;
 3    Iterator<?> e = iterator();
 4    while (e.hasNext()) {
 5      if (c.contains(e.next())) {
 6        e.remove();
 7        modified = true;
 8      }
 9    }
10    return modified;
11  }

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.

 1  public boolean removeAll(Collection c) {
 2  int x=0, i=0;
 3  for (i=0; i<size; i++) 
 4      if (!c.contains(elementData[i])) 
 5          elementData[x++] = elementData[i];
 6  if (x != i) {
 7      Arrays.fill(elementData, x, i, null);
 8      size = x;
 9      return true;
10  } else {
11      return false;
12  }
13  }

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.

 1  public boolean removeAll(Collection c) {
 2  int oldHi=0, newHi=0, top=0;
 3  for (int i=0; i<size; ++i) {
 4      if (c.contains(elementData[i])) {
 5          oldHi = newHi;
 6          newHi = i;
 7          
 8          // at the end of this loop newHi will be the non-inclusive
 9          // upper limit of the range to delete.
10          //
11          while (++newHi<size && c.contains(elementData[newHi]));
12          
13          final int length = i - oldHi;
14          System.arraycopy(elementData, oldHi, elementData, top, length);
15          i = newHi;
16          top += length;
17      }
18  }
19  if (newHi > 0) {
20      final int k = size - newHi;
21      System.arraycopy(elementData, newHi, elementData, top, k);
22      final int n = top + k;
23      Arrays.fill(elementData, n, size, null);
24      size = n;
25      return true;
26  } else {
27      return false;
28  }
29  }

Quantifying Performance

To justify the theoretical arguments above, we conclude by running a series of benchmarks to quantify the performance gains. You are invited to download these benchmarks and verify the claims yourself. Should you obtain significantly different results, or if you can provides results for a different platform (either OS or JDK level), please contact me so I can post them.

The benchmark is concerned with testing the speed of the default implementation and the two alternate implementations presented in this article. Five different tests constitute the benchmark:

1. Remove from head. Remove N items from the head of a list. This is a "worst case scenario" for the default implementation.
2. Remove from tail. Remove N items from the tail of a list. The default implementation should perform much better in this scenario.
3. Remove nothing. Remove 0 items from the list. In theory, all three implementations should show comparable performance on this test since nothing is being removed, and the entire operation consists of a single scan through this list's elements.
4. Remove interleaved from head. Remove N items located at positions 0, 2, 4, ..., N*2 in the list. This test is interesting because we would expect System.arraycopy to provide minimal, if not negative, benefit since it never copies more than a single element at a time.
5. Random. Remove N items at random from the list. The random items are precomputed and reused for all the implementations. This test is of interest as a simulation of the "average" real-world use case.

Arrays Tester v1.0
Java(TM) 2 Runtime Environment, Standard Edition
1.6.0-rc-b63

Several points in the results above are noteworthy. First, it would be inaccurate to claim that the O(n) solutions are "X times faster" than the default implementation since the difference in runtime performance varies as a function of the input size. Secondly, there is very little difference between the O(n) and tuned O(n) solutions. In fact, for standard use cases (of which random and interleaved are most representative), there is a slight performance loss. Essentially, the problem with the tuned O(n) algorithm is that it is tuned for a corner case: when a large, contiguous block of values is to be removed. Therefore, the first solution is probably preferable, especially when considering the added bonus of its simplicity.

Corrections

Thanks to Tobias Mattsson for catching a flaw in the initial implementation of the O(n) algorithms. The problem was, in his own words: "Don't forget to null out the remaining unused slots of the underlying array. Neglecting to do so will cause memory leaks."

Conclusion

Although it is surprising to see an egregious ArrayList.removeAll implementation in a JDK as mature as Sun's Java 6 JDK, it is understandable when one considers that J2EE business applications, which constitute the bread and butter of Java, rarely work with very large arrays, even more rarely use removeAll, and that, even when both these conditions are true, performance is virtually guaranteed to be dominated by remote calls, XML parsing, and other heavyweight activities.

As always, comments are welcome.

Resources

1. The source code for the benchmarks and optimized array lists.
2. An RFE related to this issue has been accepted by Sun.
3. Artima has a discussion about the performance of ArrayList.removeAll on its message boards..

Feedback

A few selected comments.