Details
-
Bug
-
Status: Closed
-
Major
-
Resolution: Fixed
-
2.0.4
-
None
-
None
-
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)