I set out to test the following claim in the Javadoc for Collections::addAll:
The behavior of this convenience method is identical to that of
c.addAll(Arrays.asList(elements)), but this method is likely to run significantly faster under most implementations.
I've used the following code to test the runtime of addAll for ArrayList and LinkedList (as well as Collections on the current collection):
public static void main(String[] args) {
final String LIST_STRING = "ArrayList::addAll";
Tracker arrTracker = new Tracker(LIST_STRING);
Tracker colTracker = new Tracker("Collections::addAll");
final String GREEN = "\u001B[32m";
final String END_GREEN = "\u001B[0m";
TimeMeasurer elapsed = new TimeMeasurer();
Integer[] ints = new Integer[2_000_000];
for(int i = 0; i < ints.length; i++)
{
ints[i] = Integer.valueOf((int) (Math.random()*50_001)-25_000);
}
System.out.println("Array filled! "+elapsed);
List<Integer> collection = new ArrayList<>(List.of(1, 2, 3));
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
System.out.println("Created initial lists. "+elapsed);
for(int i = 0; i < 4; ++i)
Collections.addAll(collection,ints);
System.out.println(GREEN+"Collections::addAll. "+elapsed+END_GREEN);
collection.clear();
collection = null;
for(int i = 0; i < 5; i++)
System.gc();
System.out.println("Garbage collected. "+elapsed);
for(int i = 0; i < 4; ++i)
list.addAll(Arrays.asList(ints));
System.out.println(GREEN+LIST_STRING+". "+elapsed+END_GREEN);
list.clear();
list = null;
for(int i = 0; i < 5; i++)
System.gc();
System.out.println("Garbage collected. "+elapsed);
//redoing
for(int iter = 0; iter < 100; iter++)
{
System.out.println();
collection = new ArrayList<>(List.of(1, 2, 3));
list = new ArrayList<>(List.of(1, 2, 3));
System.out.println("Recreated initial lists. "+elapsed);
for(int i = 0; i < 4; ++i)
Collections.addAll(collection,ints);
System.out.println(GREEN+"Collections::addAll. "+colTracker.on(elapsed)+END_GREEN);
collection.clear();
collection = null;
for(int i = 0; i < 5; i++)
System.gc();
System.out.println("Garbage collected. "+elapsed);
for(int i = 0; i < 4; ++i)
list.addAll(Arrays.asList(ints));
System.out.println(GREEN+LIST_STRING+". "+arrTracker.on(elapsed)+END_GREEN);
list.clear();
list = null;
for(int i = 0; i < 5; i++)
System.gc();
System.out.println("Garbage collected. "+elapsed);
}
System.out.println();
System.out.println(colTracker.average());
System.out.println(arrTracker.average());
}
I ignore the first run for the purposes of warming up the JVM, and change = new ArrayList<>(...) to = new LinkedList(...) when testing for LinkedList runtimes. Each addition consists of 2 million random integers, repeated 4 times, for a total of 8 million integers being appended. Here are the final outputs from the time testing code for LinkedList:
Average milliseconds per run for Collections::addAll: 3586.153
Average milliseconds per run for LinkedList::addAll: 6900.910
Here are the final outputs from the time testing code for ArrayList:
Average milliseconds per run for Collections::addAll: 354.337
Average milliseconds per run for ArrayList::addAll: 272.990
So, here's what I'd like to know:
- Controlling for List type, why is LinkedList::addAll so much slower than Collections::addAll?
- Controlling for List type, why is ArrayList::addAll faster than Collections::addAll?
