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

ListOrderedSet.addAll() is very slow

    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.addAll().
      It appears in version 3.2.1 and also in revision 1351465 (18 Jun
      2012). I have attached a test that exposes this problem and a
      three-line patch that fixes it. On my machine, for this test, the
      patch provides a 79X speedup.

      To run the test, just do:

      $ java Test

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

      The output for the patched version is:
      Time is 23

      As the patch shows, the problem is that
      ListOrderedSet.addAll(int index, Collection<? extends E> coll)
      performs:
      "setOrder.add(index++, e)" for each element in "coll". This is very
      expensive, because "setOrder" is an ArrayList, and inserting an
      element in the middle of an ArrayList shifts all the elements to the
      right.

      The patched version avoids this cost by inserting all the elements at
      once, thus performing only one insert.

      Is this a bug? If so, can you please confirm that the patch is
      correct?

      Thanks,

      Adrian

        Attachments

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

          Issue Links

            Activity

              People

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

                Dates

                • Created:
                  Updated:
                  Resolved: