commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Adrian Nistor (JIRA)" <>
Subject [jira] [Commented] (COLLECTIONS-407) ListOrderedSet.removeAll() is slow
Date Tue, 19 Jun 2012 15:37:42 GMT


Adrian Nistor commented on COLLECTIONS-407:

Hi Thomas,

Thanks, it's great that the patch works.

java.util, Apache Commons Collections, Guava Libraries, all use on a
regular basis methods from the collections passed as parameters (over
which these three libraries have no control), just like in this case.
It's the normal thing to do, there must be hundreds of such examples,
and nobody tries to avoid them.

In fact, how can one use the collections passes as parameters
otherwise?  For example, the implementation of ListOrderedSet alone
(not to mention the other classes in Commons Collections, java.util,
and Guava Libraries) uses methods from "collection" 9 different times,
including the return value of "collection.retainAll" in the
implementation of "ListOrderedSet.retainAll(Collection<?> coll)".  It
would not be possible to implement Commons Collections otherwise.

> a bit slower

Quadratic vs linear complexity is a big difference.  This can get
really slow (e.g., two orders of magnitude) even for medium size data



> ListOrderedSet.removeAll() is slow
> ----------------------------------
>                 Key: COLLECTIONS-407
>                 URL:
>             Project: Commons Collections
>          Issue Type: Bug
>    Affects Versions: 3.2.1
>         Environment: java 1.6.0_24
> Ubuntu 11.10
>            Reporter: Adrian Nistor
>         Attachments:, patch.diff
> Hi,
> I am encountering a performance problem in ListOrderedSet.removeAll().
> It appears in version 3.2.1 and also in revision 1344775 (31 May
> 2012).  I have attached a test that exposes this problem and a
> one-line patch that fixes it.  On my machine, for this test, the patch
> provides a 317X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 3812
> The output for the patched version is:
> Time is 12
> As the patch shows, the problem is in 
> ListOrderedSet.remove(Object object).  The code for this method is:
> boolean result = collection.remove(object);
> setOrder.remove(object);
> return result;
> The patch changes it to :
> boolean result = collection.remove(object);
> if (result) setOrder.remove(object);
> return result;
> The "setOrder.remove(object)" is not necessary if 
> "collection.remove(object)" did not find the object.
> This small change speeds up
> ListOrderedSet.ListOrderedSet.removeAll(Collection<?> coll) because
> ListOrderedSet.ListOrderedSet.removeAll(Collection<?> coll) iterates
> over all the elements in "coll" and calls 
> ListOrderedSet.remove(Object object).  So the un-patched code has
> quadratic complexity, while the patched code has linear complexity.
> Is this truly a bug, or am I missing something here?  If so, can you
> please confirm if the patch is correct?
> Thanks,
> Adrian

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:!default.jspa
For more information on JIRA, see:


View raw message