В стандартной библиотеке Java отсутствует возможность оперировать коллекциями примитивных типов, таких как int, long и т.д. Стандартный выход — использовать объекты классов Integer, Long и т.д.
Такой подход хорошо работает на небольшом количестве элементов, поскольку, во-первых, при любой операции происходит autoboxing/autounboxing и во-вторых, в коллекции хранятся ссылки на объекты в heap. Объекты в heap не только вносят дополнительный overhead по памяти, но и создают нагрузку на GC.
Есть еще один неочевидный минус объектов в heap — кэширование в современных процессорах. Процессор загружает данные в кэш блоками. В случае последовательной обработки массива, в кэш загружается сразу несколько элементов. В случае же объектов разбросанных по heap, попаданий в кэш будет меньше. Подробнее про кэширование и иерархию памяти здесь.
Библиотека Trove представляет стандартный интерфейс коллекций для работы с примитивными типами. Для большинства применений, коллекции Trove работают быстрее и потребляют меньше памяти.
В набор коллекций входят:
- List — ArrayList и LinkedList
- Map — HashMap
- Set — HashSet
- Stack — ArrayStack
В отличии от jdk, в Hash'ах Trove используется Open addressing метод разрешения коллизий.
Принцип именования — 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, задать 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, inverseGrep — формирование списка по условию (для TList...) и transformValues — inplace операции изменения над элементами коллекции.
Полезная возможность — в случае HashMap/HashSet c объектом (наследником Object) в качестве ключа, можно использовать свою hash функцию Interface HashingStrategy<T>.
Для бенчмаркинга использовался отличный benchmark tool jmh.
Было бы замечательно, если бы разработчики опубликовали его в maven repository.
Вывод пришлось слегка подредактировать, что бы сохранить форматирование, одна операция — 1млн элементов (полный отчет здесь):
$ 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.
PS. Значения количества элементов при создании коллекций не были заданы намеренно.
Автор: xlix123
