Библиотека Trove. Коллекции примитивных типов в Java

В стандартной библиотеке Java отсутствует возможность оперировать коллекциями ^[1] примитивных типов, таких как int, long и т.д. Стандартный выход — использовать объекты классов Integer, Long и т.д.

Такой подход хорошо работает на небольшом количестве элементов, поскольку, во-первых, при любой операции происходит autoboxing/autounboxing ^[2] и во-вторых, в коллекции хранятся ссылки на объекты в heap. Объекты в heap не только вносят дополнительный overhead ^[3] по памяти, но и создают нагрузку на GC.

Есть еще один неочевидный минус объектов в heap — кэширование в современных процессорах. Процессор загружает данные в кэш блоками. В случае последовательной обработки массива, в кэш загружается сразу несколько элементов. В случае же объектов разбросанных по heap, попаданий в кэш будет меньше. Подробнее про кэширование и иерархию памяти здесь ^[4].

Библиотека Trove ^[5] представляет стандартный интерфейс коллекций для работы с примитивными типами. Для большинства применений, коллекции Trove работают быстрее и потребляют меньше памяти.

В набор коллекций входят:

• List ^[6] — ArrayList ^[7] и LinkedList ^[8]
• Map ^[9] — HashMap ^[10]
• Set ^[11] — HashSet ^[12]
• Stack ^[13] — ArrayStack ^[14]

В отличии от jdk, в Hash'ах Trove используется Open addressing ^[15] метод разрешения коллизий.

Принцип именования — T<Type><CollectionType>.
Например:
Интерфейс TIntList — List of int, реализация TIntArrayList:

TIntList l = new TIntArrayList();

Интерфейс TLongLongMap — Map c ключами long и значениями long, реализация TLongLongHashMap:

TLongLongMap m = new TLongLongHashMap();

В jdk коллекциях, в случае если элемент не найден — возвращается null. В Trove возвращается «NoEntryValue», по умолчанию — 0. Узнать NoEntryValue ^[16], задать NoEntryValue можно при создании коллекции.

Плюсом коллекций Trove являются методы обработки — forEach,

    public static long troveEach() {
        final long [] rvalue = {0};
// troveMap - TLongLongHashMap
// TLongProcedure будет вызываться для каждого элемента коллекции, 
// пока не вернет false
// или не кончатся элементы
        troveMap.forEachValue(new TLongProcedure() {
            @Override
            public boolean execute(long value) {
                rvalue[0] += value;
                return true;
            }
        });
        return rvalue[0];
    }

grep ^[17], inverseGrep ^[18] — формирование списка по условию (для TList...) и transformValues ^[19] — inplace операции изменения над элементами коллекции.

Полезная возможность — в случае HashMap/HashSet c объектом (наследником Object) в качестве ключа, можно использовать свою hash функцию Interface HashingStrategy<T> ^[20].

Для бенчмаркинга использовался отличный benchmark tool jmh ^[21].
Было бы замечательно, если бы разработчики опубликовали его в maven repository.

Вывод пришлось слегка подредактировать, что бы сохранить форматирование, одна операция — 1млн элементов (полный отчет здесь ^[22]):

$ java -version
java version "1.7.0_21"
Java(TM) SE Runtime Environment (build 1.7.0_21-b11)
Java HotSpot(TM) 64-Bit Server VM (build 23.21-b01, mixed mode)

$ java -server -XX:+AggressiveOpts -Xms2048m 
  -Xmx2048m -jar microbenchmarks.jar ".*Trove.*" -prof gc -i 3 -r 5s

Benchmark                    Mode Thr    Cnt  Sec         Mean   Mean error    Units
// Вставка в List<Integer>
IntListJdkInsert            thrpt   1      3    5      104.950        6.756  ops/sec
// Полный перебор List<Integer>
IntListJdkTraverse          thrpt   1      3    5      774.100       71.809  ops/sec

// Вставка в TIntArrayList
IntListTroveInsert          thrpt   1      3    5      424.556       28.239  ops/sec
// Полный перебор TIntArrayList
IntListTroveTraverse        thrpt   1      3    5     3548.806        7.712  ops/sec

// Вставка в HashMap<Long, Long>
LongHashMapJdkInsert        thrpt   1      3    5       24.683        1.994  ops/sec
// поиск всех элементов в HashMap<Long, Long> по очереди
LongHashMapJdkSearch        thrpt   1      3    5       67.789        1.119  ops/sec
// полный перебор значений HashMap<Long, Long>
LongHashMapJdkTraverse      thrpt   1      3    5       99.761        0.882  ops/sec

// Вставка в TLongLongMap
LongHashMapTroveInsert      thrpt   1      3    5       28.750        0.165  ops/sec
// поиск всех элементов в TLongLongMap по очереди
LongHashMapTroveSearch      thrpt   1      3    5      145.933        0.416  ops/sec
// полный перебор значений TLongLongMap, с использованием forEach
LongHashMapTroveTraverse    thrpt   1      3    5      318.528        0.980  ops/sec

Количество занятой памяти подсчитать не так просто, но косвенный вывод можно сделать по активности GC:

Вставка jdк в List<Integer>:
Iteration   1 (5s in 1 thread): 103,950 ops/sec
 GC | wall time = 5,002 secs,  GC time = 0,331 secs, GC% = 6,62%, GC count = +24

Вставка Trove в TIntArrayList:
Iteration   1 (5s in 1 thread): 428,400 ops/sec
  GC | wall time = 5,002 secs,  GC time = 0,019 secs, GC% = 0,38%, GC count = +32

Если посмотреть в исходники TIntArrayList, то станет понятно откуда прирост производительности — данные хранятся в виде массива:

public class TIntArrayList implements TIntList, Externalizable {
	static final long serialVersionUID = 1L;

    /** the data of the list */
    protected int[] _data;

Скорость перебора TLongLongMap объясняется иcпользованием forEach — не создается временных объектов и исключен unboxing.

Тот же benchmark, но одна операция — 1тыс элементов:

Benchmark                    Mode Thr    Cnt  Sec         Mean   Mean error    Units
IntListJdkInsert            thrpt   1      3    5   239478.011      871.469  ops/sec
IntListJdkTraverse          thrpt   1      3    5  1326701.717     1649.389  ops/sec

IntListTroveInsert          thrpt   1      3    5   315562.594     2483.415  ops/sec
IntListTroveTraverse        thrpt   1      3    5  3630599.806    10822.903  ops/sec

LongHashMapJdkInsert        thrpt   1      3    5    45315.689       47.630  ops/sec
LongHashMapJdkSearch        thrpt   1      3    5   114759.789      424.996  ops/sec
LongHashMapJdkTraverse      thrpt   1      3    5   210012.550      139.001  ops/sec

LongHashMapTroveInsert      thrpt   1      3    5    33078.583      119.127  ops/sec
LongHashMapTroveSearch      thrpt   1      3    5   148311.567      267.613  ops/sec
LongHashMapTroveTraverse    thrpt   1      3    5   351955.550      901.902  ops/sec

Видно, что при сокращении количества элементов в коллекции, разрыв в производительности падает.

Можно сделать вывод о том, что если коллекции небольшие и используются нечасто, то включать в проект дополнительную зависимость особого смысла нет.
Но если в проекте массово используются большие коллекции примитивных типов, то применение Trove может быть оправдано.

Код проекта доступен на GitHub ^[23].

PS. Значения количества элементов при создании коллекций не были заданы намеренно.

Автор: xlix123

Источник ^[24]