FULL PRODUCT VERSION :
java version "1.6.0_24"
Java(TM) SE Runtime Environment (build 1.6.0_24-b07)
Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Linux 3.0.0-12-generic #20-Ubuntu

A DESCRIPTION OF THE PROBLEM :
The method "AbstractCollection.retainAll(Collection<?> c)" is very
slow when the parameter "c" is empty (and "retainAll" should just
clear "this" collection). I attached a test that exposes this problem
and a one-line patch that fixes it. For this test, the patch provides
822X speedup on my machine.

The patch is very simple, just call:

if (c.isEmpty()) { clear(); return true; }

at the beginning of "retainAll".

  To run the test, do:

$ java Test

The output for the un-patched version is:
Time is 822

The output for the patched version is:
Time is 1

There are other ways to speed up "retainAll", but they are more
complex, e.g., bug 5028425, whereas the above one-line patch is
trivial and provides considerable speedup for certain usage scenarios.

The method "AbstractCollection.removeAll(Collection<?> c)" can be
similarly optimized by adding "if (c.isEmpty()) return false;", but
the speed up is not as dramatic as for "retainAll".

Can you please fix this behavior?


The patch is:
======================================================================
--- AbstractCollection.java 2012-07-23 14:04:13.525513594 -0500
+++ AbstractCollection_Fix.java 2012-07-23 14:20:49.725537261 -0500
@@ -363,6 +363,7 @@
      * @see #contains(Object)
      */
     public boolean retainAll(Collection<?> c) {
+ if (c.isEmpty()) { clear(); return true; }
  boolean modified = false;
  Iterator<E> e = iterator();
  while (e.hasNext()) {
======================================================================


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
$ java Test

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Time is 1
ACTUAL -
Time is 822

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> collection = new ArrayList<Integer>();
        for (int i = 0; i < 100000; i++) collection.add(i);
        ArrayList<Integer> other = new ArrayList<Integer>();
        
        long start = System.currentTimeMillis();
        collection.retainAll(other);
        System.out.println("Time is " + (System.currentTimeMillis() - start));
    }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
I realize one can solve this problem from the caller site,
replacing "collection.retainAll(other)" with something like:

if (other.isEmpty()) collection.clear();
else collection.retainAll(other);

However, this clutters the caller sites a lot.