Java ArrayList vs. OpenArrayList Performance
Jakob Jenkov |
Quite often Java applications keep objects in data structures that contain java.util.ArrayList
instances. When iterating the objects in those data structures we also have to iterate the objects stored
in the ArrayList instances. In this Java ArrayList performance tutorial I will take a closer
look at the performance of the different ways you can iterate an ArrayList. This tutorial
will also look at the performance of the OpenArrayList class - a class that mimics the
java.util.ArrayList but designed with performance in mind.
Three Ways to Iterate an ArrayList
There are basically three different ways to iterate the objects contained in an ArrayList:
- Using a for-loop.
- Using a for-each-loop.
- Using an Iterator.
There is not a big performance difference between these three ways of iterating an ArrayList, but
there is a little, and it's big enough that if your code is performance critical you might want to gain this
almost free performance gain. But first, let me show you the three ways to iterate an ArrayList.
The for Loop
Iterating an ArrayList using a standard Java for loop looks like this:
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
for(int i=0, n=arrayList.size(); i < n; i++){
Object element = arrayList.get(i);
}
As you can see, the for loop uses a standard counter to count through all the elements stored
in the ArrayList. Each element is obtained from the ArrayList instance using the
get() method.
The for-each Loop
The for-each loop uses the for construct added in Java 5. Here is how iterating an
ArrayList using a for-each loop looks:
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
for(Object obj : arrayList){
}
The Iterator
The third way to iterate an ArrayList is to use an java.util.Iterator obtained from the
ArrayList. Here is how iterating an ArrayList using an Iterator looks:
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
Iterator iterator = arrayList.iterator();
while(iterator.hasNext()) {
Object element = iterator.next();
}
ArrayList Iteration Benchmarks
In order to measure the iteration performance difference of the three different ways to iterate an
ArrayList I have implemented three different benchmark methods using
the Java Microbenchmark Harness . The code for these benchmarks is included at the end
of this text.
To get a more precise view of the iteration speed of each technique, I have measured the speed of iterating
an ArrayList of 10 and 100 elements. That way I believe I would get more nuanced picture of
the performance.
The elements in the ArrayList are Long elements which are summed. Thus, the benchmarks
really measure both the iteration and summation of 10 and 100 Long elements stored in an ArrayList.
The benchmarks were executed using JDK 1.8.0_u60 on a Intel Core i7-4770 Haswell server which was doing nothing but the benchmarks. The benchmarks were executed using the JMH defaults, meaning 20 warmup iterations, 20 iterations and 10 forks of each. Here are the benchmark results (the output from JMH):
Benchmark Mode Cnt Score Error Units OpenArrayListBenchmark.jdkArrayList100SumUsingGet thrpt 200 15838998.503 ± 1017.752 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingForEach thrpt 200 14068898.854 ± 946.976 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingIterator thrpt 200 14069990.330 ± 512.600 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingGet thrpt 200 77320532.538 ± 7421.267 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingForEach thrpt 200 69926532.927 ± 732112.779 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingIterator thrpt 200 69879781.630 ± 727551.844 ops/s
As you can see, iterating an ArrayList using the for-each loop and Iterator
yields pretty much the same performance. This was expected, as the for-each loop is probably
compiled into an iteration using an Iterator by the Java compiler.
You can also see that iterating an ArrayList using a standard Java for loop with a
counter, and obtaining each element by calling the ArrayList get() method is about
10% faster for an ArrayList with 10 elements, and around 12,5% faster when the ArrayList
contains 100 elements.
Exactly why there is such performance difference is hard to tell. Part of the difference is probably caused by
the creation of an Iterator object per iteration. However, you would expect that overhead to be
evened out (less noticeable) when the ArrayList contains more elements. But, instead it seems the
performance difference grows (from 10% at 10 elements to 12,5% at 100 elements). This might be caused by a more
optimized loop execution by the CPU for the for loop version, but I cannot say for sure.
OpenArrayList
The OpenArrayList class is a very simple imitation of the ArrayList which I have
implemented to see if it could iterate a collection of elements faster than an ArrayList .
Here is a scraped version of the OpenArrayList implementation:
public Object[] elements = null;
public int capacity = 0;
public int size = 0;
public OpenArrayList(){
}
public OpenArrayList(int capacity){
this.capacity = capacity;
this.elements = new Object[capacity];
}
public OpenArrayList(Object[] elements){
this.elements = elements;
this.capacity = elements.length;
}
public void add(Object element){
this.elements[this.size++] = element;
}
public boolean addIfCapacity(Object element){
if(this.size < this.capacity){
this.elements[this.size++] = element;
return true;
}
return false;
}
}
The first thing to notice is that all the OpenArrayList member variables are public. That is why
I have called it "Open". Its member variables are open to the outside world. I have made
the member variables public so that you can access the elements array directly when iterating the elements in the OpenArrayList.
This should be a tiny bit faster than calling the ArrayList get() method, although the JVM
could optimize the get() method call away.
Another advantage of making the elements array public is that you can write to it or copy from
it using System.arraycopy() which is very fast.
OpenArrayList Iteration Benchmarks
As with the ArrayList I have measured the summation of 10 and 100 Long objects stored
in an OpenArrayList. The benchmarks were executed using the same setup as the ArrayList
benchmarks.
Here are the OpenArrayList iteration benchmarks (with the ArrayList benchmarks below for
easy comparison):
Benchmark Mode Cnt Score Error Units OpenArrayListBenchmark.openArrayList100Sum thrpt 200 16040305.970 ± 1490.153 ops/s OpenArrayListBenchmark.openArrayList10Sum thrpt 200 81301297.431 ± 15104.301 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingGet thrpt 200 15838998.503 ± 1017.752 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingForEach thrpt 200 14068898.854 ± 946.976 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingIterator thrpt 200 14069990.330 ± 512.600 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingGet thrpt 200 77320532.538 ± 7421.267 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingForEach thrpt 200 69926532.927 ± 732112.779 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingIterator thrpt 200 69879781.630 ± 727551.844 ops/s
As you can see, the OpenArrayList iteration is about 1% faster when the ArrayList
contains 100 elements, and around 5% faster with 10 elements. Exactly why that performance difference exists
I cannot say for sure. The fact that the performance is so close is probably a sign that the JVM has
optimized the get() call away. But still interesting that there seems to be a larger performance
difference for smaller numbers of elements.
Iteration Benchmark Code
Here is the benchmark code used to measure the iteration speed of the different iteration techniques for both
ArrayList and OpenArrayList.
public class OpenArrayListBenchmark {
@State(Scope.Thread)
public static class BenchmarkState {
public ArrayList<Long> jdkArrayList10 = new ArrayList<>();
public ArrayList<Long> jdkArrayList100 = new ArrayList<>();
public OpenArrayList openArrayList10 = new OpenArrayList(10);
public OpenArrayList openArrayList100 = new OpenArrayList(100);
@Setup(Level.Trial)
public void toSetup() {
Object[] elements = openArrayList10.elements;
for(int i=0; i < openArrayList10.capacity; i++){
elements[i] = new Long(i);
jdkArrayList10.add(new Long(i));
}
openArrayList10.size = openArrayList10.capacity;
elements = openArrayList100.elements;
for(int i=0; i < openArrayList100.capacity; i++){
elements[i] = new Long(i);
jdkArrayList100.add(new Long(i));
}
openArrayList100.size = openArrayList100.capacity;
}
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long openArrayList10Sum(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Object[] elements = state.openArrayList10.elements;
for(int i=0; i<state.openArrayList10.size; i++){
sum += ((Long) elements[i]).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long openArrayList100Sum(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Object[] elements = state.openArrayList100.elements;
for(int i=0; i<state.openArrayList100.size; i++){
sum += ((Long) elements[i]).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingGet(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
ArrayList arrayList = state.jdkArrayList10;
for(int i=0, n=state.jdkArrayList10.size(); i < n; i++){
sum += ((Long) arrayList.get(i)).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingGet(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
ArrayList arrayList = state.jdkArrayList100;
for(int i=0, n=state.jdkArrayList100.size(); i < n; i++){
sum += ((Long) arrayList.get(i)).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingForEach(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
for(Long element : state.jdkArrayList10){
sum += element.longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingForEach(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
for(Long element : state.jdkArrayList100){
sum += element.longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingIterator(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Iterator<Long> iterator = state.jdkArrayList10.iterator();
while(iterator.hasNext()){
sum += iterator.next().longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingIterator(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Iterator<Long> iterator = state.jdkArrayList100.iterator();
while(iterator.hasNext()){
sum += iterator.next().longValue();
}
blackhole.consume(sum);
return sum;
}
}
| Tweet | |
Jakob Jenkov | |
