Bug 53822 - performance of IdentityStack.containsAll()
Summary: performance of IdentityStack.containsAll()
Alias: None
Product: Ant
Classification: Unclassified
Component: Core (show other bugs)
Version: 1.9.1
Hardware: PC Linux
: P2 normal (vote)
Target Milestone: 1.9.4
Assignee: Ant Notifications List
Keywords: PatchAvailable
Depends on:
Reported: 2012-09-03 18:45 UTC by Adrian Nistor
Modified: 2014-01-02 14:38 UTC (History)
1 user (show)

patchSmall.diff (743 bytes, patch)
2012-09-03 18:45 UTC, Adrian Nistor
Details | Diff
patchFull.diff (1.03 KB, patch)
2012-09-03 18:45 UTC, Adrian Nistor
Details | Diff
test (649 bytes, text/x-java)
2012-09-03 18:46 UTC, Adrian Nistor

Note You need to log in before you can comment on or make changes to this bug.
Description Adrian Nistor 2012-09-03 18:45:37 UTC
Created attachment 29322 [details]

"IdentityStack.containsAll(Collection coll)" has a similar performance
problem as the previously fixed Bug 53622 (for
"VectorSet.retainAll(Collection coll)").  The problem is that
"containsAll(Collection coll)" performs "this.contains(e.next())",
which is slow because "this" is an IdentityStack, i.e., a Vector, and
therefore "contains" is linear.

I attached a patch (patchSmall.diff) similar to the one used by Jesse
Glick in Bug 53622.  I attached an improved patch (patchFull.diff)
that builds the IdentityHashMap lazily, which gives slightly better
performance than patchSmall.diff (which builds IdentityHashMap
eagerly).  I also attached a test that exposes this problem.  For this
test, patchSmall.diff provides a 676X speedup on my machine.

To run the test, just do:

$ java Test

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

The output for the patched version is:
Time is 26
Comment 1 Adrian Nistor 2012-09-03 18:45:58 UTC
Created attachment 29323 [details]
Comment 2 Adrian Nistor 2012-09-03 18:46:29 UTC
Created attachment 29324 [details]
Comment 3 Stefan Bodewig 2014-01-02 14:38:11 UTC
svn revision 1554813