java-list-primitive-performance

Posted on: 2019-10-08 2019-10-08
Tags: Java

Performance Comparison of Primitive Lists in Java

Java

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 ArrayList‘s 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.

getdocs

3043