You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Thomas Neidhart (JIRA)" <ji...@apache.org> on 2013/01/23 17:18:13 UTC
[jira] [Commented] (COLLECTIONS-429) Performance problem in
MultiValueMap
[ https://issues.apache.org/jira/browse/COLLECTIONS-429?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13560800#comment-13560800 ]
Thomas Neidhart commented on COLLECTIONS-429:
---------------------------------------------
Hi Adrian,
thanks for your patch, the performance improvement is really significant.
I was trying to improve the code snippets and came up with a rather elegant solution reusing existing methods in CollectionUtils:
{noformat}
@Override
public boolean containsAll(Collection<?> c) {
Collection<Object> result = CollectionUtils.<Object>intersection(this, c);
return result.size() == c.size();
}
{noformat}
This could also be added as a CollectionUtils.containsAll method, similar to the already existing containsAny.
The contract of containsAll should be fully supported by that snippet.
> Performance problem in MultiValueMap
> ------------------------------------
>
> Key: COLLECTIONS-429
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-429
> Project: Commons Collections
> Issue Type: Bug
> Affects Versions: 3.2.1
> Environment: java 1.6.0_24
> Ubuntu 11.10
> Reporter: Adrian Nistor
> Attachments: patchFull_AbstractHashedMap.diff, patchFull.diff, patchFull_StaticBucketMap.diff, patchSmall_AbstractHashedMap.diff, patchSmall.diff, patchSmall_StaticBucketMap.diff, Test_AbstractHashedMap.java, TestDifferentParameter.java, Test.java, Test_StaticBucketMap.java
>
>
> Hi,
> I am encountering a performance problem in MultiValueMap. It appears
> in version 3.2.1 and also in revision 1366088. I attached a test that
> exposes this problem and a patch that fixes it. On my machine, for
> this test, the patch provides a 1158X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 44040
> The output for the patched version is:
> Time is 38
> The attached test shows that, for a "MultiValueMap multi" object, the
> following operation is very slow:
> multi.values().containsAll(toContain);
> "MultiValueMap.values()" returns a "MultiValueMap.Values" object,
> which inherits containsAll() from "java.util.AbstractCollection",
> which has quadratic complexity.
> I attached two patches. Both patches override containsAll() and
> implement a linear time algorithm. patchSmall.diff populates a
> HashSet eagerly, and patchFull.diff populates a HashSet lazily.
> patchFull.diff is faster than patchSmall.diff when containsAll()
> returns false after inspecting only a few elements, though in most
> cases they are equally fast. I am including patchSmall.diff just in
> case you prefer smaller code.
> Note that this problem is different from COLLECTIONS-416. As
> established in the COLLECTIONS-416 discussion, there the user was
> responsible for using the proper data structures as argument for the
> method.
> For "MultiValueMap.values()", the problem is not related to the
> collection passed as parameter. The problem will always manifest for
> this method, irrespective of the parameter type. I attached a test
> (TestDifferentParameter.java) that shows that, even with a HashSet
> parameter, the current problem still manifests (which did not happen
> for COLLECTIONS-416).
> This problem also exists for the two other "Values" classes
> (AbstractHashedMap.Values, StaticBucketMap.Values). I attached tests
> and patches for these classes as well. If you want me to file
> separate reports, just let me know.
> Is this truly a performance problem, or am I misunderstanding the
> intended behavior? If so, can you please confirm that the patches are
> correct?
> Thanks,
> Adrian
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira