[GROOVY-5739] performance problem in DefaultGroovyMethods.removeAll()

• 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
• Flags: Patch
• Assignee: Paul King
• Reporter: Adrian Nistor
• Created: 02/Oct/12 13:33
• Updated: 05/Apr/15 14:44
• Resolved: 04/Oct/12 06:16

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)