[COLLECTIONS-409] ListOrderedSet.addAll() is very slow

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 3.2.1
• Fix Version/s: 4.0-alpha1, 4.0

Environment

java 1.6.0_24
Ubuntu 11.10

• Assignee: Unassigned
• Reporter: Adrian Nistor
• Created: 19/Jun/12 20:00
• Updated: 09/Nov/14 17:31
• Resolved: 19/Jun/12 23:52

Description

Hi,

I am encountering a performance problem in ListOrderedSet.addAll().
It appears in version 3.2.1 and also in revision 1351465 (18 Jun
2012). I have attached a test that exposes this problem and a
three-line patch that fixes it. On my machine, for this test, the
patch provides a 79X speedup.

To run the test, just do:

$ java Test

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

The output for the patched version is:
Time is 23

As the patch shows, the problem is that
ListOrderedSet.addAll(int index, Collection<? extends E> coll)
performs:
"setOrder.add(index++, e)" for each element in "coll". This is very
expensive, because "setOrder" is an ArrayList, and inserting an
element in the middle of an ArrayList shifts all the elements to the
right.

The patched version avoids this cost by inserting all the elements at
once, thus performing only one insert.

Is this a bug? If so, can you please confirm that the patch is
correct?

Thanks,

Adrian

Issue Links

• is related to: COLLECTIONS-407 ListOrderedSet.removeAll() is slow