[Bug 53622] New: performance problem in VectorSet.retainAll()

[bu...@apache.org]

https://issues.apache.org/bugzilla/show_bug.cgi?id=53622

          Priority: P2
            Bug ID: 53622
          Assignee: notifications@ant.apache.org
           Summary: performance problem in VectorSet.retainAll()
          Severity: normal
    Classification: Unclassified
                OS: Linux
          Reporter: nistor1@illinois.edu
          Hardware: PC
            Status: NEW
           Version: 1.8.4
         Component: Core
           Product: Ant

Created attachment 29138
  --> https://issues.apache.org/bugzilla/attachment.cgi?id=29138&action=edit
patch

There is a performance problem in VectorSet.retainAll().  It appears
in version 1.8.4 and also in revision 1366777.  I attached a test that
exposes this problem and a patch that fixes it.  On my machine, for
this test, the patch provides a 319X speedup.

To run the test, just do:

$ java Test

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

The output for the patched version is:
Time is 25

The current implementation of "VectorSet.retainAll(Collection c)"
iterates over the elements in "VectorSet" and searches in "c", which
can be very slow, if for example "c" is a list.

The attached patch iterates over the elements of "c" and searched in
VectorSet, which is always very fast, because we can use the field
"HashSet set" in VectorSet.

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug 53622] performance problem in VectorSet.retainAll()

[bu...@apache.org]

https://issues.apache.org/bugzilla/show_bug.cgi?id=53622

Adrian Nistor <ni...@illinois.edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |nistor1@illinois.edu

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug 53622] performance problem in VectorSet.retainAll()

[bu...@apache.org]

https://issues.apache.org/bugzilla/show_bug.cgi?id=53622

--- Comment #1 from Adrian Nistor <ni...@illinois.edu> ---
Created attachment 29139
  --> https://issues.apache.org/bugzilla/attachment.cgi?id=29139&action=edit
test

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug 53622] performance problem in VectorSet.retainAll()

[bu...@apache.org]

https://issues.apache.org/bugzilla/show_bug.cgi?id=53622

Jesse Glick <jg...@apache.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |jglick@apache.org
         Resolution|---                         |FIXED
   Target Milestone|---                         |1.9.0

--- Comment #2 from Jesse Glick <jg...@apache.org> ---
I committed revision 1367736 with stronger tests but your patch does not even
pass the original testRetainAll: it does not preserve element order. (It also
failed to return the right value from retainAll in some cases.)

I committed a simpler patch (revision 1367741) which has at least improved
speed and which passes all tests.

-- 
You are receiving this mail because:
You are the assignee for the bug.