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

ListOrderedSet.removeAll() is slow

Attach filesAttach ScreenshotVotersWatch issueWatchersCreate sub-taskLinkCloneUpdate Comment AuthorReplace String in CommentUpdate Comment VisibilityDelete Comments
    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • 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 ListOrderedSet.removeAll().
      It appears in version 3.2.1 and also in revision 1344775 (31 May
      2012). I have 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 317X speedup.

      To run the test, just do:

      $ java Test

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

      The output for the patched version is:
      Time is 12

      As the patch shows, the problem is in
      ListOrderedSet.remove(Object object). The code for this method is:

      boolean result = collection.remove(object);
      setOrder.remove(object);
      return result;

      The patch changes it to :

      boolean result = collection.remove(object);
      if (result) setOrder.remove(object);
      return result;

      The "setOrder.remove(object)" is not necessary if
      "collection.remove(object)" did not find the object.

      This small change speeds up
      ListOrderedSet.ListOrderedSet.removeAll(Collection<?> coll) because
      ListOrderedSet.ListOrderedSet.removeAll(Collection<?> coll) iterates
      over all the elements in "coll" and calls
      ListOrderedSet.remove(Object object). So the un-patched code has
      quadratic complexity, while the patched code has linear complexity.

      Is this truly a bug, or am I missing something here? If so, can you
      please confirm if the patch is correct?

      Thanks,

      Adrian

        Attachments

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

        Issue Links

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              adriannistor Adrian Nistor

              Dates

              • Created:
                Updated:
                Resolved:

                Issue deployment