Uploaded image for project: 'Groovy'
  1. Groovy
  2. GROOVY-5739

performance problem in DefaultGroovyMethods.removeAll()

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 2.0.4
    • Fix Version/s: 2.0.5, 2.1.0-beta-1, 1.8.9
    • Component/s: None
    • Labels:
      None
    • Flags:
      Patch

      Description

      There is a performance problem in "DefaultGroovyMethods.removeAll".
      It appears in version 2.0.4 and also in the latest revision
      (f8c7f25..). I attached a JUnit test that exposes this problem and a
      one-line patch (patchRemoveAll.diff) that fixes it. On my machine,
      for this test, the patch provides a 37X speedup.

      Running the JUnit test for the un-patched version is, the output is:
      Time is 2040

      The output for the patched version is:
      Time is 54

      The problem is that the current implementation of "removeAll" calls:

      "self.removeAll(Arrays.asList(items));"

      which typically (e.g., java.util.AbstractCollection and thus most
      collections) calls "contains" on the parameter (a list) for each
      element in "self". "contains" on a list has linear complexity, which
      is very slow when called many times.

      The patch uses a HashSet as a parameter, which has constant complexity
      for "contains".

      "DefaultGroovyMethods.retainAll" has a similar problem. I attached a
      second patch for it (patchRetainAll.diff)

        Attachments

          Activity

            People

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

              Dates

              • Created:
                Updated:
                Resolved: