[
https://issues.apache.org/jira/browse/COLLECTIONS-427?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14291071#comment-14291071
]
Adrian Nistor commented on COLLECTIONS-427:
-------------------------------------------
Hi Thomas,
> A user can always solve the performance problem him/herself by
> putting the elements in a set and provide this as parameter to
> retainAll.
Yes, but:
(1) typically users spend (a lot) of time making the code work
correctly. Users don't want to spend time with optimizations if they
can avoid it.
(2) users needs to identify this call as a potential optimization
point, which is not easy if the buggy case is not triggered during
testing. Furthermore, if the program-wide slowdown is small but
non-negligible (e.g., 10%), users may view it as unfortunate but
legitimate, i.e., users may not realize it can be improved.
(3) the user needs figure out there is a easy and fast way to optimize
this code. This requires the user to look inside the method
implementation.
No user will do the above, so it is better to do it automatically if
we can. And in this case we can do it easily and transparently in the
library. If we can optimize something, we should do it.
> at the expense of additional space complexity.
Yes. But typically we have memory available, speed is more difficult
to get. And the additional space is linear in the size of c, whereas
the time improvement is huge. And the added memory is less than half
the memory used by the SetUniqueList and is very short lived. So the
added memory is not a problem.
> The described problem also applies to almost all collection types
Yes, but "others do it too" is not a reason for us to not improve if
we can.
Overall, it is your decision. I just feel that if we can help the
developers, we should do it. And if others don't do it, that's their
problem, not ours.
Best,
Adrian
> performance problem in SetUniqueList.retainAll()
> ------------------------------------------------
>
> Key: COLLECTIONS-427
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-427
> Project: Commons Collections
> Issue Type: Bug
> Affects Versions: 3.2.1
> Environment: java 1.6.0_24
> Ubuntu 11.10
> Reporter: Mert Guldur
> Fix For: 4.0-alpha1, 4.0
>
> Attachments: Test.java, patch.diff
>
>
> I am encountering a performance problem in SetUniqueList.retainAll().
> It appears in version 3.2.1 and also in revision 1365132. I attached
> a test that exposes this problem and a patch that fixes it. On my
> machine, for this test, the patch provides a 621X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 6215
> The output for the patched version is:
> Time is 10
> There are two problems here. First, "SetUniqueList.retainAll()"
> should have similar implementation with the current implementation of
> "ListOrderedSet.retainAll()", which is more optimized. Second, even
> "ListOrderedSet.retainAll()" has a performance problem, which was
> reported and explained in detail in COLLECTIONS-426.
> The attached patch has two parts. The first part (the first loop) is
> inspired from COLLECTIONS-426. The second part (everything after the
> first loop) is in fact the current implementation of
> "ListOrderedSet.retainAll()", with some minor changes to adapt it for
> the current code. Overall, the attached patch is very similar to the
> COLLECTIONS-426 patch.
> I will rehash some of the information from COLLECTIONS-426 (which
> describes "ListOrderedSet.retainAll()") for the current
> "SetUniqueList.retainAll()".
> The current code for "SetUniqueList.retainAll()" is:
> {code:java|borderStyle=solid}
> public boolean retainAll(Collection<?> coll) {
> boolean result = super.retainAll(coll);
> set.retainAll(coll);
> return result;
> }
> {code}
> where both "super.retainAll(coll)" and "set.retainAll(coll)" can have
> quadratic complexity, e.g., if "coll" is a List. Both these calls to
> "retainAll" are in fact calls to
> "java.util.AbstractCollection.retainAll()", which has the code:
> {code:java|borderStyle=solid}
> public boolean retainAll(Collection<?> c) {
> boolean modified = false;
> Iterator<E> e = iterator();
> while (e.hasNext()) {
> if (!c.contains(e.next())) {
> e.remove();
> modified = true;
> }
> }
> return modified;
> }
> {code}
> which iterates over "this" and calls "contains()" on "c". Mapping
> this code back to "SetUniqueList.retainAll()" means that the code
> iterates over "this" and "set" and calls "contains()" on "coll". If
> "coll" has slow "contains()" (e.g., if "coll" is a list), then
> "SetUniqueList.retainAll()" has quadratic complexity.
> The patch iterates over "coll" and calls "contains()" on "set", which
> we know is fast, because "set" is a Set. For a more detailed
> discussion of the patch and the problem, see the current
> implementation of "ListOrderedSet.retainAll()", the discussion for
> COLLECTIONS-426, and the patch for COLLECTIONS-426.
> Is this a bug, or am I misunderstanding the intended behavior? If so,
> can you please confirm if the patch is correct?
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
