[ https://issues.apache.org/jira/browse/COLLECTIONS-413?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Adrian Nistor updated COLLECTIONS-413: -------------------------------------- Description: Hi, I am encountering a performance problem in DualHashBidiMap. It appears in version 3.2.1 and also in revision 1352574 (21 June 2012). I attached a test that exposes this problem and a patch that fixes it. On my machine, for this test, the patch provides a 173X speedup. To run the test, just do: $ java Test The output for the un-patched version is: Time is 5029 The output for the patched version is: Time is 29 The attached test shows that, for a "DualHashBidiMap bidi" object, the following operation is very slow: bidi.entrySet().removeAll(toRemove); DualHashBidiMap.entrySet() returns a "DualHashBidiMap.EntrySet" object, which inherits removeAll(Collection<?> coll) from "DualHashBidiMap.View". As the patch shows, the problem is that "DualHashBidiMap.View.removeAll(Collection<?> coll)" performs "coll.contains(it.next())" for each element in the View. "coll.contains(it.next())" can be very slow, e.g., if "coll" is a list. The patch avoids this cost by using remove(Object obj) (defined in "EntrySet<K, V>", "KeySet<K>", and "Values<V>"), which is fast because it uses only operations on sets. Is this a bug, or am I misunderstanding something? If so, can you please confirm that the patch is correct? Thanks, Adrian was: Hi, I am encountering a performance problem in DualHashBidiMap. It appears in version 3.2.1 and also in revision 1352574 (21 June 2012). I attached a test that exposes this problem and a patch that fixes it. On my machine, for this test, the patch provides a 173X speedup. To run the test, just do: $ java Test The output for the un-patched version is: Time is 5029 The output for the patched version is: Time is 29 The attached test shows that, for a "DualHashBidiMap bidi" object, the following operation is very slow: bidi.entrySet().removeAll(toRemove); DualHashBidiMap.entrySet() returns a "DualHashBidiMap.EntrySet" object, which inherits removeAll(Collection<?> coll) from "DualHashBidiMap.View". As the patch shows, the problem is that "DualHashBidiMap.View.removeAll(Collection<?> coll)" performs "coll.contains(it.next())" for each element in the View. "coll.contains(it.next())" can be very slow, e.g., if "coll" is a list. The patch avoids this cost by removing from decorate(), which is fast because decorate() is a set. Is this a bug, or am I misunderstanding something? If so, can you please confirm that the patch is correct? Thanks, Adrian > Performance problem in DualHashBidiMap > -------------------------------------- > > Key: COLLECTIONS-413 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-413 > Project: Commons Collections > Issue Type: Bug > Affects Versions: 3.2.1 > Environment: java 1.6.0_24 > Ubuntu 11.10 > Reporter: Adrian Nistor > Attachments: Test.java, removeAll.diff > > > Hi, > I am encountering a performance problem in DualHashBidiMap. It > appears in version 3.2.1 and also in revision 1352574 (21 June 2012). > I attached a test that exposes this problem and a patch that fixes it. > On my machine, for this test, the patch provides a 173X speedup. > To run the test, just do: > $ java Test > The output for the un-patched version is: > Time is 5029 > The output for the patched version is: > Time is 29 > The attached test shows that, for a "DualHashBidiMap bidi" object, the > following operation is very slow: > bidi.entrySet().removeAll(toRemove); > DualHashBidiMap.entrySet() returns a > "DualHashBidiMap.EntrySet" object, which inherits > removeAll(Collection<?> coll) from "DualHashBidiMap.View". > As the patch shows, the problem is that > "DualHashBidiMap.View.removeAll(Collection<?> coll)" performs > "coll.contains(it.next())" for each element in the View. > "coll.contains(it.next())" can be very slow, e.g., if "coll" is a > list. > The patch avoids this cost by using remove(Object obj) (defined in > "EntrySet<K, V>", "KeySet<K>", and "Values<V>"), which is fast because > it uses only operations on sets. > Is this a bug, or am I misunderstanding something? If so, can you > please confirm that 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira