Java ArrayList Benchmark

“Don’t mistake activity with achievement.”
― John Wooden

1. Introduction

Let us examine the performance characteristics of List Implementations – ArrayList and LinkedList. We perform the testing for a variety of list sizes from 100 items to 1M items. We use the JMH test harness to conduct the test on a single core machine. Results are presented below.

2. ArrayList Add Performance

This test measures the performance of creating the list and populating the list for a specified number of items. The test code is shown below. Nothing fancy. A specified number of integer are creating using the Random class and collected into a particular type of List. For this test, we have included ArrayList, LinkedList and Vector.

@State(Scope.Thread)
static public class MyState {
    @Param("100")
    public int NSIZE;
}

@Benchmark
public void test_createArrayList(MyState state) {
    Random random = new Random();
    List<Integer> list = random
	.ints(state.NSIZE)
	.collect(ArrayList::new, List::add, List::addAll);
}

@Benchmark
public void test_createLinkedList(MyState state) {
    Random random = new Random();
    List<Integer> list = random
	.ints(state.NSIZE)
	.collect(LinkedList::new, List::add, List::addAll);
}

@Benchmark
public void test_createVector(MyState state) {
    Random random = new Random();
    List<Integer> list = random
	.ints(state.NSIZE)
	.collect(Vector::new, List::add, List::addAll);
}

The performance of the operation is shown below. As mentioned before, we tested from 100 through 1M items as shown on the X-Axis. The Y-Axis is the throughput in ops per second and is shown in log scale since there is a steep drop-off as the size increases.

Conclusions we can draw from this graph. As always, results are specific for this run of the code. (In other words, your mileage may vary).

1. LinkedList adding is slower as number of items increase.
2. No perceptible difference between ArrayList and Vector

3. ArrayList Loop Performance

Let us now check the performance of the ArrayList in a loop. Since iterating over a List is one of the most important operations in programs in general, this aspect is quite important.

We have tested the following ways of iterating a list. The code loops over a List and fetches each item; thus it represents reasonably real-world code.

Enhanced for-each

A simple for-each loop. To prevent the JVM for optimizing the code out of existence, we maintain a loop variable, increment it each loop and return it.

@Benchmark
public int test_forEach(MyState state) {
    int n = 0 ;
    for (int num : state.list) {
	n++;
    }
    return n;
}

A regular indexed for loop

A loop which iterates over all elements in order and fetches each element.

@Benchmark
public int test_forLoop(MyState state) {
    int n = 0;
    for (int i = 0 ; i < state.list.size() ; i++) {
	int value = state.list.get(i);
	n++;
    }
    return n;
}

Loop with Iterator

Uses the normal Collection.iterator method to retrieve an iterator and fetches the item from it.

@Benchmark
public int test_iterator(MyState state) {
    int n = 0;
    for (Iterator<Integer> it=state.list.iterator(); it.hasNext(); ) {
	int num = it.next();
	n++;
    }
    return n;
}

Process Items in a Stream

Uses the new Java 8 streams facility with a lambda.

@Benchmark
public int test_stream(MyState state) {
    return state.list.stream().reduce(0, (x, y) -> x+y);
}

And here are the results. As before the X-Axis is the size of the ArrayList and the Y-Axis is the throughput in ops/s with a higher number indicating faster performance. Also note that the Y-Axis is log scale.

Nothing unusual here – the performance of the loop drops over the size of the list. A surprise here is that the performance of ArrayList stream is less by about 20% than the other methods. Again your mileage may vary.

4. LinkedList Loop Performance

The same tests as above on a LinkedList, ranging in size from 100 items to 10000 items.

A few observations are in order here. The for-loop is way slower than the other methods which is to be expected since the LinkedList is not a RandomAccess List. ArrayList has a O(1) performance for retrieval while LinkedList has a O(N) performance. It is reflected here.

Also the streams processing pipeline is slower by about 20% than the for-each and iterator methods.

Summary

In this article we examined some performance characteristics of the ArrayList and LinkedList including creation, adding and retrieval in a loop. The LinkedList is slightly slower with adding items to the end of the list. It is also slower when retrieving items with an index (random access).