[jira] [Created] (COLLECTIONS-548) Performance issue in CompositeCollection::retainAll

["Oswaldo Olivo (JIRA)" <ji...@apache.org>]

Oswaldo Olivo created COLLECTIONS-548:
-----------------------------------------

             Summary: Performance issue in CompositeCollection::retainAll
                 Key: COLLECTIONS-548
                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-548
             Project: Commons Collections
          Issue Type: Bug
          Components: Collection
    Affects Versions: 4.1
         Environment: Ubuntu 14.04
            Reporter: Oswaldo Olivo
            Priority: Minor


There seems to be a performance problem with the function retainAll of 
CompositeCollection.

The following is the code of the function:

{code}
 
    /**
     * Retains all the elements in the specified collection in this composite collection,
     * removing all others.
     * <p>
     * This implementation calls <code>retainAll()</code> on each collection.
     *
     * @param coll  the collection to remove
     * @return true if the collection was modified
     * @throws UnsupportedOperationException if retainAll is unsupported
     */
    public boolean retainAll(final Collection<?> coll) {
        boolean changed = false;
        for (final Collection<E> item : all) {
            changed |= item.retainAll(coll);
        }
        return changed;
    }


{code}

The performance problem occurs when the underlying collections in the current collection have a slow retainAll method. Whenever we're relying on Collection::retainAll, slow cases tend to occur when the parameter collection has a slow contains method.

The following test harness shows the performance degradation between 
using a list and using a set as a parameter, across different collection sizes.

{code}
 public static void 	compositeCollectionRetainAllTest(boolean original) {

	int N=500000;

	ArrayList<Integer> firstArrayList=new ArrayList<Integer>();
	ArrayList<Integer> secondArrayList=new ArrayList<Integer>();

	for(int i=0;i<N;++i) {

	    firstArrayList.add(new Integer(i));
	    secondArrayList.add(new Integer(N-1-i));
	    
	}
	CompositeCollection col = new CompositeCollection(firstArrayList);

	col.retainAll(original ? secondArrayList : (new HashSet<Integer>(secondArrayList)));
	

    }


{code}

In the following table "Original" corresponds to the time taken by 
the existing implementation of CompositeCollection::retainAll, "Repaired" to the time taken by the function invoked with the parameter converted into a set, and "Speed-up" to the speed-up obtained after the repair.

N		Original(s)	Repaired(s)	Speed-up(X)

10	         1.04		1.04		        1.00
100	         1.04		1.05		        0.99
1000	1.06		        1.06		        1.00
10000	1.12		        1.10		        1.01
100000	9.34		        1.15		        8.12
500000	> 300		1.29		        > 232.55


If it's unacceptable to convert the parameter into a set before calling 
retainsAll, a solution would be to include a warning to the user in the documentation that the parameter should have a fast contains method when possible.




--
This message was sent by Atlassian JIRA
(v6.3.4#6332)