Created attachment 29149 [details] patch There is a performance problem in VectorSet.allAll(). It appears in version 1.8.4 and also in revision 1367821. I attached a test that exposes this problem and a patch that fixes it. On my machine, the patch provides a 20X speedup for this test. To run the test, just do: $ java Test The output for the un-patched version is: Time is 439 The output for the patched version is: Time is 22 The current implementation of "VectorSet.addAll(int index, Collection c)" adds the elements of "c" one by one at "index" in the "elementData" array. These add operations are slow, because each of them requires shifting to the right all the elements after "index". The attached patch adds all the elements at once, and thus performs a single shift. The java.util.ArrayList "addAll(int index, Collection<? extends E> c)" implementation also performs a single shift (like the patch), and does not insert the elements one by one.
Created attachment 29150 [details] test
Did not make it into 1.9.0 but should be considered for 1.9.1.
svn revision 1554830