[COLLECTIONS-534] Performance bug in CollectionBag::retainAll

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 4.0
• Fix Version/s: 4.1
• Component/s: Bag, Collection
• Labels: perfomance

Environment

Ubuntu 12.04

• Assignee: Unassigned
• Reporter: Oswaldo Olivo
• Created: 15/Oct/14 21:01
• Updated: 27/Nov/15 21:11
• Resolved: 19/Oct/14 12:44

Description

Hi,
There seems to be a performance bug in the method retainAll in the CollectionBag class.
The problem is that the code is checking containment over the parameter collection, which could be expensive for some types of collections like ArrayLists.
One solution could be to convert the Collection into a HashSet and check containment in the HashSet.
If this is done, then running retainAll on a 1,000,000 collection would take less than 2 seconds instead of 27 mins, according to my experiments.

____________________________________________
Here's a function to expose the bug:

public static void collectionBagRetainAllTest()

{ ArrayList<Integer> coll=new ArrayList<Integer>(); for(int i=0;i<=1000000;++i) coll.add(new Integer(i)); TreeBag<Integer> treeBag=new TreeBag<Integer>(coll); CollectionBag<Integer> bag = new CollectionBag<Integer>(treeBag); bag.retainAll(coll); }

_____________________________________

Here's a proposed patch:

public boolean retainAll(final Collection<?> coll) {
if (coll != null) {
boolean modified = false;
final Iterator<E> e = iterator();
HashSet<Object> set=new HashSet<Object>(coll);
while (e.hasNext()) {
if (!set.contains(e.next()))

{ e.remove(); modified = true; }

}
return modified;
} else

{ // let the decorated bag handle the case of null argument return decorated().retainAll(null); }

}
_____________________________________