Big performance hog with (Collection).removeAll ?

[Cyril Gambis]

Hi!

We have a strange performance hog in our application, in a thread which wake up every minute.

The culprit seems to be removeAll on a collection, which takes forever. This collection has about 16000 entries, and we remove nearly every entry in the operation.


I demonstrate the problem with the code below. removeAll takes 15 seconds, even if a simple loop with a simple "remove" takes only 30 ms.

Can "removeAll" be so broken in our case? (the lists of entries we remove and the list of entries in which we remove are nearly the same).

What do you think?

Thanks!
Cyril

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
 
 
 
 
public class Test {
 
private static final int NB_MAX = 16000;
 
public static void main(String[] args) {
List firstList = new ArrayList();
List secondList = new ArrayList();
List thirdList = new ArrayList();
Set theSet = new HashSet();
Set theSet2 = new HashSet();
Set theSet3 = new HashSet();
 
for (int i = 0; i < NB_MAX; i++) {
String string = "abmelkrj_qdfmjk" + i;
firstList.add(string);
secondList.add(string);
thirdList.add(string);
theSet.add(string);
theSet2.add(string);
theSet3.add(string);
}
 
System.out.println("****** Starting tests ******");
long before = new Date().getTime();
secondList.removeAll(firstList);
System.out.println(">>> secondList.removeAll(firstList): " + (new Date().getTime() - before));
 
before = new Date().getTime();
for (Iterator iterator = firstList.iterator(); iterator.hasNext()  :wink:   {
Object object = (Object) iterator.next();
thirdList.remove(object);
}
System.out.println(">>> thirdList.remove *" + NB_MAX + " (firstList): " + (new Date().getTime() - before));
 
before = new Date().getTime();
theSet.removeAll(firstList);
System.out.println(">>> theSet.removeAll(firstList): " + (new Date().getTime() - before));
 
before = new Date().getTime();
for (Iterator iterator = firstList.iterator(); iterator.hasNext()  :wink:   {
Object object = (Object) iterator.next();
theSet2.remove(object);
}
System.out.println(">>> theSet2.remove *" + NB_MAX + " (firstList): " + (new Date().getTime() - before));
 
 
before = new Date().getTime();
if (theSet3.size() > firstList.size()) {
for (Iterator i = firstList.iterator(); i.hasNext(); )
theSet3.remove(i.next());
} else {
for (Iterator i = theSet3.iterator(); i.hasNext(); ) {
if(firstList.contains(i.next())) {
i.remove();
}
}
}
System.out.println(">>> theSet3.removeAll handcoded(firstList): " + (new Date().getTime() - before));
}
}

[ February 29, 2008: Message edited by: Cyril Grao ]

[Nitesh Kant]

Hi Cyril,
Welcome to Javaranch.
(FYI: Code tags have square brackets and not angle brackets. More information here)

Yeah, your analysis is correct. The time taken by removeAll() is directly dependent on the size of the list to be removed. This is the code that it uses:

   
    public boolean removeAll(Collection<?> c) {
boolean modified = false;
Iterator<?> e = iterator();
while (e.hasNext()) {
    if ([B]c.contains(e.next())[/B]) {
e.remove();
modified = true;
    }
}
return modified;
    }

The code in bold is what removeAll() does in addition to what your simple removal does.
Since, the size of the passed collection is huge, the contains method call will take a long time and this time will be multiplied by the number of elements in the list that is being modified.

I suggest a few solutions (may not be the best possible):

If you are removing all the elements from the collection then clear() will be the best thing to do.

If you do not need the return value of the removeAll() operation, you can use the code that you have written i.e. do a simple iterate and call remove for all the items to be removed.

[Cyril Gambis]

Thanks for you answer!

Actually, I'm not really a newcomer of Java Ranch but I post rarely, and each time I forget my login and the mail account I used to register...

Your analysis is correct, and c.contains is probably the culprit. I can't use clean(), since there may be 2 or 3 items different in the real scenario of my point, but I'll go with the solution with the loop and the simple "remove".

Have a good day,

Cyril

[Ernest Friedman-Hill]

Rather than the messy handcoded loop, you could use something like

secondList.removeAll(new HashSet(firstList));

List.contains() is a slow operation (it takes time proportional to the size of the list), but HashSet.contains() is very fast (its runtime is insensitive to the set size.)

[Cyril Gambis]

Good solution, thanks!

The result is nearly as good as doing the remove by hand and the code is clearer.

Results:

****** Starting tests ******
>>> secondList.removeAll(firstList): 8266
>>> thirdList.remove *16000 (firstList): 343
>>> theSet.removeAll(firstList): 7625
>>> theSet2.remove *16000 (firstList): 16
>>> theSet3.removeAll handcoded(firstList): 7672
>>> theSet4.removeAll(new HashSet(firstList)): 31

Cheers,
Cyril
[ March 03, 2008: Message edited by: Cyril Gambis ]

[Stephane Clinckart]

The same code can be use for the removeAll on the List.

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
 
public class Test {
 
private static final int NB_MAX = 16000;
 
public static void main(String[] args) {
final List<String> list1 = new ArrayList<String>();
final ArrayList<String> list2 = new ArrayList<String>();
final ArrayList<String> list3 = new ArrayList<String>();
final ArrayList<String> list4 = new ArrayList<String>();
final Set<String> theSet = new HashSet<String>();
final Set<String> theSet2 = new HashSet<String>();
final Set<String> theSet3 = new HashSet<String>();
final Set<String> theSet4 = new HashSet<String>();
 
for (int i = 0; i < NB_MAX; i++) {
final String string = "abmelkrj_qdfmjk" + i;
list1.add(string);
list2.add(string);
list3.add(string);
list4.add(string);
theSet.add(string);
theSet2.add(string);
theSet3.add(string);
theSet4.add(string);
}
 
System.out.println("****** Starting tests ******");
 
long before = new Date().getTime();
list2.removeAll(list1);
System.out.println(">>> list2.removeAll(firstList): " + (new Date().getTime() - before));
 
before = new Date().getTime();
for (final Iterator iterator = list1.iterator(); iterator.hasNext()  :wink:   {
list3.remove(iterator.next());
}
System.out.println(">>> list3.remove *" + NB_MAX + " (firstList): " + (new Date().getTime() - before));
 
before = new Date().getTime();
list4.removeAll(new HashSet<String>(list1));
System.out.println(">>> list4.removeAll(new HashSet<String>(firstList)): " + (new Date().getTime() - before));
 
 
before = new Date().getTime();
theSet.removeAll(list1);
System.out.println(">>> theSet.removeAll(firstList): " + (new Date().getTime() - before));
 
before = new Date().getTime();
for (final Iterator iterator = list1.iterator(); iterator.hasNext()  :wink:   {
theSet2.remove(iterator.next());
}
System.out.println(">>> theSet2.remove *" + NB_MAX + " (firstList): " + (new Date().getTime() - before));
 
before = new Date().getTime();
if (theSet3.size() > list1.size()) {
for (final Iterator i = list1.iterator(); i.hasNext()  :wink:  
theSet3.remove(i.next());
} else {
for (final Iterator i = theSet3.iterator(); i.hasNext()  :wink:   {
if (list1.contains(i.next())) {
i.remove();
}
}
}
System.out.println(">>> theSet3.removeAll handcoded(firstList): " + (new Date().getTime() - before));
 
before = new Date().getTime();
theSet.removeAll(new HashSet<String>(list1));
System.out.println(">>> theSet4.removeAll(new HashSet(firstList)): " + (new Date().getTime() - before));
}
}

Results:
****** Starting tests ******
>>> list2.removeAll(firstList): 5717
>>> list3.remove *16000 (firstList): 120
>>> list4.removeAll(new HashSet<String>(firstList)): 151
>>> theSet.removeAll(firstList): 5581
>>> theSet2.remove *16000 (firstList): 3
>>> theSet3.removeAll handcoded(firstList): 5609
>>> theSet4.removeAll(new HashSet(firstList)): 5

Remark: I optimise little bit more the stuff by removing the class Cast and removing creation of object in loops.
[ March 11, 2008: Message edited by: Stephane Clinckart ]

[Stephane Clinckart]

I could not remove the smiley... also by using the code tags :-/
[ March 11, 2008: Message edited by: Stephane Clinckart ]

[Ilja Preuss]

Originally posted by Stephane Clinckart:
I could not remove the smiley... also by using the code tags :-/

[ March 11, 2008: Message edited by: Stephane Clinckart ]

Check the "Disable smilies in this post." checkbox under "options" in the edit screen...