I am encountering a performance problem in
AbstractLinkedList.removeAll(). It appears in version 3.2.1 and also
in revision 1355448. I attached a test that exposes this problem and
a one-line patch that fixes it. On my machine, for this test, the
patch provides a 226X speedup.
To run the test, just do:
$ java Test
The output for the un-patched version is:
Time is 5655
The output for the patched version is:
Time is 25
As the patch shows, the problem is that
"AbstractLinkedList.removeAll(Collection<?> coll)" performs
"coll.contains(it.next())" for each element in the AbstractLinkedList,
which can be very expensive if "coll.contains()" is expensive, e.g.,
when "coll" is a list.
The one-line patch I attached puts the elements of "coll" in a HashSet
(which has very fast "contains()"), if "coll" is not already a set:
"if (!(coll instanceof java.util.Set<?>)) coll = new java.util.HashSet<Object>(coll);"
Is this a bug, or am I misunderstanding the intended behavior? If so,
can you please confirm that the patch is correct?