Uploaded image for project: 'Commons Collections'
  1. Commons Collections
  2. COLLECTIONS-419

Performance problem in AbstractDualBidiMap

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: 3.2.1
    • Fix Version/s: 4.0-alpha1, 4.0
    • Component/s: None
    • Labels:
      None
    • Environment:

      java 1.6.0_24
      Ubuntu 11.10

      Description

      Hi,

      I am encountering a performance problem in AbstractDualBidiMap. 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 130X speedup.

      To run the test, just do:

      $ java Test

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

      The output for the patched version is:
      Time is 42

      The attached test shows that, for a "DualHashBidiMap bidi" object, the
      following operation is very slow:

      bidi.keySet().retainAll(toRetain)

      DualHashBidiMap.keySet() returns a "DualHashBidiMap.KeySet" object,
      which inherits "retainAll(Collection<?> coll)" from
      "AbstractDualBidiMap.View". Similarly,

      bidi.values().retainAll(toRetain)
      bidi.entrySet().retainAll(toRetain)

      are also slow. This happens for both DualHashBidiMap and
      DualTreeBidiMap, which extend AbstractDualBidiMap.

      As the patch shows, the problem is that
      "AbstractDualBidiMap.View.retainAll(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 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 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?

      Thanks,

      Adrian

        Attachments

        1. patch.diff
          0.6 kB
          Adrian Nistor
        2. Test.java
          0.7 kB
          Adrian Nistor

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              adriannistor Adrian Nistor
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: