Generic Top

I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:

>> CHECK OUT THE COURSE

1. Overview

In this tutorial, we’re going to compare the performance of some popular primitive list libraries in Java.

For that, we’ll test the add(), get(), and contains() methods for each library.

2. Performance Comparison

Now, let’s find out which library offers a fast working primitive collections API.

For that, let’s compare the List analogs from Trove, Fastutil, and Colt. We’ll use the JMH (Java Microbenchmark Harness) tool to write our performance tests.

2.1. JMH Parameters

We’ll run our benchmark tests with the following parameters:

@BenchmarkMode(Mode.SingleShotTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Measurement(batchSize = 100000, iterations = 10)
@Warmup(batchSize = 100000, iterations = 10)
@State(Scope.Thread)
public class PrimitivesListPerformance {
}

Here, we want to measure the execution time for each benchmark method. Also, we want to display our results in milliseconds.

The @State annotation indicates that the variables declared in the class won’t be the part of running benchmark tests. However, we can then use them in our benchmark methods.

Additionally, let’s define our lists of primitives:

public static class PrimitivesListPerformance {
    private List<Integer> arrayList = new ArrayList<>();
    private TIntArrayList tList = new TIntArrayList();
    private cern.colt.list.IntArrayList coltList = new cern.colt.list.IntArrayList();
    private IntArrayList fastUtilList = new IntArrayList();

    private int getValue = 10;
}

Now, we’re ready to write our benchmarks.

3. add()

First, let’s test adding the elements into our primitive lists. We’ll also add one for ArrayList as our control.

3.1. Benchmark Tests

The first micro-benchmark is for the ArrayLists add() method:

@Benchmark
public boolean addArrayList() {
    return arrayList.add(getValue);
}

Similarly, for the Trove’s TIntArrayList.add():

@Benchmark
public boolean addTroveIntList() {
    return tList.add(getValue);
}

Likewise, Colt’s IntArrayList.add() looks like:

@Benchmark
public void addColtIntList() {
    coltList.add(getValue);
}

And, for Fastutil library, the IntArrayList.add() method benchmark will be:

@Benchmark
public boolean addFastUtilIntList() {
    return fastUtilList.add(getValue);
}

3.2. Test Results

Now, we run and compare results:

Benchmark           Mode  Cnt  Score   Error  Units
addArrayList          ss   10  4.527 ± 4.866  ms/op
addColtIntList        ss   10  1.823 ± 4.360  ms/op
addFastUtilIntList    ss   10  2.097 ± 2.329  ms/op
addTroveIntList       ss   10  3.069 ± 4.026  ms/op

From the results, we can clearly see that ArrayList’s add() is the slowest option.

This is logical, as we explained in the primitive list libraries article, ArrayList will use boxing/autoboxing to store the int values inside the collection. Therefore, we have significant slowdown here.

On the other hand, the add() methods for Colt and Fastutil were the fastest.

Under the hood, all three libraries store the values inside of an int[]. So why do we have different running times for their add() methods?

The answer is how they grow the int[] when the default capacity is full:

  • Colt will grow its internal int[] only when it becomes full
  • In contrast, Trove and Fastutil will use some additional calculations while expanding the int[] container

That’s why Colt is winning in our test results.

4. get()

Now, let’s add the get() operation micro-benchmark.

4.1. Benchmark Tests

First, for the ArrayList’s get() operation:

@Benchmark
public int getArrayList() {
    return arrayList.get(getValue);
}

Similarly, for the Trove’s TIntArrayList we’ll have:

@Benchmark
public int getTroveIntList() {
    return tList.get(getValue);
}

And, for Colt’s cern.colt.list.IntArrayList, the get() method will be:

@Benchmark
public int getColtIntList() {
    return coltList.get(getValue);
}

Finally, for the Fastutil’s IntArrayList we’ll test the getInt() operation:

@Benchmark
public int getFastUtilIntList() {
    return fastUtilList.getInt(getValue);
}

4.2. Test Results

After, we run the benchmarks and see the results:

Benchmark           Mode  Cnt  Score   Error  Units
getArrayList        ss     20  5.539 ± 0.552  ms/op
getColtIntList      ss     20  4.598 ± 0.825  ms/op
getFastUtilIntList  ss     20  4.585 ± 0.489  ms/op
getTroveIntList     ss     20  4.715 ± 0.751  ms/op

Although the score difference isn’t much, we can notice that getArrayList() works slower.

For the rest of the libraries, we have almost identical get() method implementations. They will retrieve the value immediately from the int[] without any further work. That’s why Colt, Fastutil, and Trove have similar performances for the get() operation.

5. contains()

Finally, let’s test the contains() method for each type of the list.

5.1. Benchmark Tests

Let’s add the first micro-benchmark for ArrayList’s contains() method:

@Benchmark
public boolean containsArrayList() {
    return arrayList.contains(getValue);
}

Similarly, for the Trove’s TIntArrayList the contains() benchmark will be:

@Benchmark
public boolean containsTroveIntList() {
    return tList.contains(getValue);
}

Likewise, the test for Colt’s cern.colt.list.IntArrayList.contains() is:

@Benchmark
public boolean containsColtIntList() {
    return coltList.contains(getValue);
}

And, for Fastutil’s IntArrayList, the contains() method test looks like:

@Benchmark
public boolean containsFastUtilIntList() {
    return fastUtilList.contains(getValue);
}

5.2. Test Results

Finally, we run our tests and compare the results:

Benchmark                  Mode  Cnt   Score    Error  Units
containsArrayList          ss     20   2.083  ± 1.585  ms/op
containsColtIntList        ss     20   1.623  ± 0.960  ms/op
containsFastUtilIntList    ss     20   1.406  ± 0.400  ms/op
containsTroveIntList       ss     20   1.512  ± 0.307  ms/op

As usual, the containsArrayList method has the worst performance. In contrast, Trove, Colt, and Fastutil have better performance compared to Java’s core solution.

This time, it’s up to the developer which library to choose. The results for all three libraries are close enough to consider them identical.

6. Conclusion

In this article, we investigated the actual runtime performance of primitive lists through the JVM benchmark tests. Moreover, we compared the test results with the JDK’s ArrayList.

Also, keep in mind that the numbers we present here are just JMH benchmark results – always test in the scope of a given system and runtime.

As usual, the complete code for this article is available over on GitHub.

Generic bottom

I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:

>> CHECK OUT THE COURSE