commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Adrian Nistor (JIRA)" <>
Subject [jira] [Created] (COLLECTIONS-417) AbstractLinkedList.retainAll() is very slow
Date Fri, 29 Jun 2012 22:02:42 GMT
Adrian Nistor created COLLECTIONS-417:

             Summary: AbstractLinkedList.retainAll() is very slow
                 Key: COLLECTIONS-417
             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
AbstractLinkedList.retainAll().  It appears in version 3.2.1 and also
in revision 1355448.  I 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 158X speedup.

To run the test, just do:

$ java Test

The output for the un-patched version is:
Time is 5531

The output for the patched version is:
Time is 35

As the patch shows, the problem is that
"AbstractLinkedList.retainAll(Collection<?> coll)" performs
"coll.contains(" for each element in the AbstractLinkedList,
which can be very expensive if "coll.contains()" is expensive, e.g.,
when "coll" is a list.

The one-line patch I attached puts the elements of "coll" in a HashSet
(which has very fast "contains()"), if "coll" is not already a set:

"if (!(coll instanceof java.util.Set<?>)) coll = new java.util.HashSet<Object>(coll);"

Is this a bug, or am I misunderstanding the intended behavior? If so,
can you please confirm that 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