«1. Обзор

В этом руководстве мы собираемся сравнить производительность некоторых популярных библиотек примитивных списков в Java.

Для этого мы протестируем методы add(), get() и contains() для каждой библиотеки.

2. Сравнение производительности

Теперь давайте выясним, какая библиотека предлагает быстродействующий API коллекций примитивов.

Для этого сравним аналоги List от Trove, Fastutil и Colt. Мы будем использовать инструмент JMH (Java Microbenchmark Harness) для написания тестов производительности.

2.1. Параметры JMH

Мы запустим тесты со следующими параметрами: 

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

Здесь мы хотим измерить время выполнения для каждого метода тестирования. Кроме того, мы хотим отображать наши результаты в миллисекундах.

Аннотация @State указывает, что переменные, объявленные в классе, не будут участвовать в выполнении тестов производительности. Однако затем мы можем использовать их в наших методах тестирования.

Кроме того, давайте определим и инициализируем наши списки примитивов: 

public static class PrimitivesListPerformance {
    private List<Integer> arrayList = new ArrayList<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
    private TIntArrayList tList = new TIntArrayList(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
    private cern.colt.list.IntArrayList coltList = new cern.colt.list.IntArrayList(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
    private IntArrayList fastUtilList = new IntArrayList(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9});

    private int getValue = 4;
}

Теперь мы готовы написать наши тесты.

3. add()

Во-первых, давайте проверим добавление элементов в наши примитивные списки. Мы также добавим один для ArrayList в качестве нашего элемента управления.

3.1. Сравнительные тесты

Первый микротест для метода add() в ArrayList: 

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

Аналогично, для TIntArrayList.add() от Trove: 

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

Аналогично, для IntArrayList от Colt. add() выглядит так: 

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

А для библиотеки Fastutil тест метода IntArrayList.add() будет выглядеть так: 

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

3.2. Результаты тестирования

Теперь запустим и сравним результаты: 

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

Из результатов ясно видно, что add() в ArrayList является самым медленным вариантом.

Это логично, как мы объяснили в статье о библиотеках примитивных списков, ArrayList будет использовать упаковку/автоупаковку для хранения значений int внутри коллекции. Поэтому у нас здесь значительное замедление.

С другой стороны, методы add() для Colt и Fastutil были самыми быстрыми.

Под капотом все три библиотеки хранят значения внутри int[]. Так почему же у нас разное время выполнения их методов add()?

Ответ заключается в том, как они увеличивают int[], когда емкость по умолчанию заполнена:

    Colt будет увеличивать свой внутренний int[] только тогда, когда он заполняется. Напротив, Trove и Fastutil будут использовать некоторые дополнительные вычисления при расширении емкости. int[] container

Вот почему Colt побеждает в результатах наших тестов.

4. get()

Теперь давайте добавим микротест операции get().

4.1. Сравнительные тесты

Во-первых, для операции get() ArrayList: 

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

Аналогично, для TIntArrayList Trove у нас будет: 

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

И для Colt cern.colt.list.IntArrayList, метод get() будет таким: 

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

Наконец, для IntArrayList Fastutil мы протестируем операцию getInt(): 

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

4.2. Результаты тестирования

После этого мы запускаем тесты и видим результаты: 

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

Хотя разница в баллах невелика, мы можем заметить, что getArrayList() работает медленнее.

Для остальных библиотек у нас почти идентичные реализации метода get(). Они будут немедленно извлекать значение из int[] без какой-либо дополнительной работы. Вот почему Colt, Fastutil и Trove имеют одинаковые характеристики для операции get().

5. contains()

Наконец, давайте протестируем метод contains() для каждого типа списка.

5.1. Сравнительные тесты

Давайте добавим первый микротест для метода contains() в ArrayList: 

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

Аналогично, для TIntArrayList Trove тест contains() будет: 

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

Аналогично, тест для cern.colt.list.IntArrayList.contains() от Colt: 

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

А для IntArrayList от Fastutil тест метода contains() выглядит так: 

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

5.2. Результаты тестов

Наконец, мы запускаем наши тесты и сравниваем результаты: 

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

Как обычно, метод containsArrayList имеет наихудшую производительность. Напротив, Trove, Colt и Fastutil имеют более высокую производительность по сравнению с основным решением Java.

На этот раз выбор библиотеки зависит от разработчика. Результаты для всех трех библиотек достаточно близки, чтобы считать их идентичными.

«6. Заключение

В этой статье мы исследовали фактическую производительность примитивных списков во время выполнения с помощью эталонных тестов JVM. Кроме того, мы сравнили результаты теста с ArrayList JDK.

Кроме того, имейте в виду, что цифры, которые мы представляем здесь, являются просто результатами тестов JMH — всегда тестируйте в рамках данной системы и среды выполнения.

Как обычно, полный код этой статьи доступен на GitHub.