Такой подход хорошо работает на небольшом количестве элементов, поскольку, во-первых, при любой операции происходит autoboxing/autounboxing и во-вторых, в коллекции хранятся ссылки на объекты в heap. Объекты в heap не только вносят дополнительный overhead по памяти, но и создают нагрузку на GC.
Есть еще один неочевидный минус объектов в heap — кэширование в современных процессорах. Процессор загружает данные в кэш блоками. В случае последовательной обработки массива, в кэш загружается сразу несколько элементов. В случае же объектов разбросанных по heap, попаданий в кэш будет меньше. Подробнее про кэширование и иерархию памяти здесь.
Библиотека Trove представляет стандартный интерфейс коллекций для работы с примитивными типами. Для большинства применений, коллекции Trove работают быстрее и потребляют меньше памяти.
В набор коллекций входят:
В отличии от 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. Значения количества элементов при создании коллекций не были заданы намеренно.
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: 'You Say What You Like, Because They Like What You Say' - http://www.medialens.org/index.php/alerts/alert-archive/alerts-2013/731-you-say-what-you-like-because-they-like-what-you-say.html
Комментариев нет:
Отправить комментарий