commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Adrian Nistor (JIRA)" <>
Subject [jira] [Created] (COLLECTIONS-413) Performance problem in DualHashBidiMap
Date Thu, 21 Jun 2012 18:39:44 GMT
Adrian Nistor created COLLECTIONS-413:

             Summary: Performance problem in DualHashBidiMap
                 Key: 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:, patch.diff


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:


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(" for each element in the View.
"coll.contains(" can be very slow, e.g., if "coll" is a

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?



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