commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Adrian Nistor (JIRA)" <>
Subject [jira] [Created] (COLLECTIONS-407) ListOrderedSet.removeAll() is slow
Date Fri, 01 Jun 2012 17:56:23 GMT
Adrian Nistor created COLLECTIONS-407:

             Summary: ListOrderedSet.removeAll() is slow
                 Key: COLLECTIONS-407
             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


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);
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?



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