Tech and Media Labs
This site uses cookies to improve the user experience.




Java ArrayList vs. OpenArrayList Performance

Jakob Jenkov
Last update: 2015-11-27

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;
    }
}

Jakob Jenkov




Copyright  Jenkov Aps
Close TOC