Benchmarking Java Lists Performance

gowebing

Let's examine the performance characteristics of the 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. The results are presented below.

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 integers is created using the Random class and collecting them 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.

There are a couple of 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 the number of items increases.
  2. There's no perceptible difference between ArrayList and Vector.

arraylist linkedlist benchmark performance in create and add.

ArrayList Loop Performance

Let's 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

This is 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

This loop 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

This loop 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

This loop 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);
}

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 the ArrayList stream is less by about 20% than the other methods. Again, your mileage may vary.

arraylist benchmark performance in loop get

LinkedList Loop Performance

These are the same tests as above on a LinkedList, ranging in size from 100 items to 10,000 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 an O(1) performance for retrieval while LinkedList has an O(N) performance. It is reflected here.

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

linkedlist benchmark loop get

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).


If you enjoyed this article and want to learn more about Java Collections, check out this collection of tutorials and articles on all things Java Collections.

 

 

 

 

Top