@xlix12320 июл 2013 в 13:59

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

4 мин

22K

Программирование * Java *

+25

Комментарии 40

@vladimir_dolzhenko 20 июл 2013 в 17:59

Стоит отметить, что trove'овские HashMap в отличии от j.u.HashMap используют размеры массивов равные простым числам, что снижает количество потенциальных коллиций в результате поиска индекса, т.е

int bucketIndex = hashCode % array.length;

j.u.HashMap использует тонкий момент — размер массива всегда 2^k, что позволяет искать индекс проще

int bucketIndex = hashCode1 & (array.length - 1);

Что позвояет при некоторых обстоятельствах j.u.HashMap обходить trove.

@SamSol 20 июл 2013 в 18:07

Где-то в документации попадалась рекомендация использовать массивы примитивов (int[], long[], etc.) в случае, когда необходимо написать «числодробилку», и классы коллекций во всех остальных случаях.

Даже не могу себе представить когда может оказаться выгоднее использовать коллекции-похожие-на-sdk-шные вместо sdk-шных или вместо массивов примитивов.

@kzn 20 июл 2013 в 19:01

У trove одно из весомых преимуществ — значительное снижение потребление памяти.

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

@SamSol 20 июл 2013 в 20:08

Если вы не знаете сколько будет элементов — используйте штатные коллекции.
В «числодробилках» необходимо знать «сколько будет элементов» чтобы построить эффективный алгоритм.
Все остальное — «преждевременная оптимизация».

@xlix123 20 июл 2013 в 20:15

Весьма спорное утверждение. Возьмем суммирование ряда — какая разница сколько элементов нужно просуммировать. И вполне возможно, что заранее неизвестно сколько элементов в ряду.

@SamSol 20 июл 2013 в 20:45

В суммировании ряда вам важнее будет задать правильный интерфейс.

// 1
int summarize(int[] values);
// 2
int summarize(List<Integer> values);

Более эффективный интерфейс — первый. (И вот у вас уже известно сколько элементов).

Но второй вариант может быть обусловлен каким-то внешним требованием. Тогда:

int summarize(List<Integer> values) {
    Integer[] a = values.toArray(new Integer[values.size()]);
    return summarize(a);
}

int summarize(Integer[] values) {
    int[] a = new int[values.length];
    for (int i = 0; i < values.length; i++) {
        a[i] = values[i];
    }
    return summarize(a);
}

int summarize(int[] values) {
    // Тут ваш суперскоростной код
}

И вот у вас снова массив примитивов, а первые два метода во-первых достаточно простые и прямолинейные чтобы не быть источниками багов и скорость их выполнения целиком на совести компилятора (и jit-компилятора).

Если пишете «числодробилку» — используйте массивы примитивов.
Если НЕ пишете «числодробилку» используйте штатные SDK-шные коллекции.
Не занимайтесь преждевременной оптимизацией.

@xlix123 20 июл 2013 в 21:07

Тогда в случае Trove:

int summarize(TIntList values) {
// вызовется  int summarize(int[] values)
    return summarize(values.toArray()); 
}

По сути списки Trove — не более чем удобная обертка вокруг массивов примитивов.

@kzn 20 июл 2013 в 21:15

BTW, так плохо делать, поскольку будет копирование массива. toArray() возвращает копию данных.

@xlix123 20 июл 2013 в 21:23

Это обусловлено тем что у нас есть «int summarize(int[] values)».
Если хочется inplace обработки — то forEach

@kzn 20 июл 2013 в 20:18

Только на это уйдет в 4 раза больше памяти, а так все нормально. Разумеется, все это актуально, когда данных много.

@xlix123 20 июл 2013 в 20:27

Если мы говорим о списках — элементы хранятся в массивах int[] для TIntArrayList, long[] для TLongArrayList. При добавлении элемента, в случае если в массиве нет места, будет создан новый массив, большего размера. Старый подберет GC. В случае массового добавления элементов он даже Eden Space покинуть не успеет.

@kzn 20 июл 2013 в 20:34

Когда я говорил про 4 раза, я говорил про случай List<Integer>

А про организацию — все ArrayList так устроены, как следует из названия :-)

@xlix123 20 июл 2013 в 21:32

Прошу прощения, неправильно понял :)

НЛО прилетело и опубликовало эту надпись здесь

@SamSol 20 июл 2013 в 20:03

Кавычки следовало вокруг плюсы поставить.

@leventov 22 июл 2013 в 05:51

Не совсем. У хешей из Trove под 50 байт полей, но главное — дублирующий массив байтов состояний ячеек. Т. е., например, байтовый хеш (до 255 элементов, следовательно около 600 байт — максимальный размер таблицы) будет занимать как минимум на 58% больше памяти чем голый массив byte[], которым в приложениях зачастую можно обойтись.

@alexeyrom 20 июл 2013 в 20:55

КО: в документации так написано, потому что опции «использовать классы коллекций примитивов» в стандартной библиотеке нет и порекомендовать её нельзя.

@leventov 22 июл 2013 в 05:57

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

@eugenius_nsk 22 июл 2013 в 14:17

Удобство уменьшается при взаимодействии со сторонними библиотеками, которые про Trove ничего не знают и хотят Collection. (это если говорить про «всегда заменяем числовые коллекции на Trove»)

@xlix123 22 июл 2013 в 15:45

В этом случае можно воспользоваться декораторами для приведения интерфейса к стандартному интерфейсу коллекций.

@vladimir_dolzhenko 20 июл 2013 в 18:14

Хорошо было бы прогнать тест с включённым и выключенным autoboxing'ом указав -Djava.lang.Integer.IntegerCache.high=N

И ещё одна рекомендация — таблицы цифр это хорошо, но наглядное представление в виде графиков в том же excel'е или google chart api сделают восприятие проще.

@xlix123 20 июл 2013 в 19:37

-Djava.lang.Integer.IntegerCache.high=N не выключает механизм autoboxing'а полностью. Oн не создает новые объекты для Integer попадающих в промежуток (-128) — N, а возвращает ссылки на заранее сформированные объекты. Ключ -XX:+AggressiveOpts поднимает N до 20000, так что тест с 1тыс уже с «выключенным» autoboxing'ом

java -server -XX:+AggressiveOpts -Xms2048m -Xmx2048m \
-XX:+UnlockDiagnosticVMOptions -XX:+PrintFlagsFinal | grep -i autobox
     intx AutoBoxCacheMax                           = 20000  {C2 product}
     bool EliminateAutoBox                          = true  {C2 diagnostic}

Рузультаты на 1тыс с «включенным» autoboxing'ом:

$ java -server  -XX:+AggressiveOpts -XX:AutoBoxCacheMax=128 \
-Xms2048m -Xmx2048m -jar target/microbenchmarks.jar ".*Trove.*" \
-i 3 -r 5s -prof gc

Benchmark                Mode Thr    Cnt  Sec         Mean   Mean error    Units
IntListJdkInsert        thrpt   1      3    5   176214.283      738.319  ops/sec
IntListJdkTraverse      thrpt   1      3    5  1327901.517     1426.723  ops/sec
IntListTroveInsert      thrpt   1      3    5   306144.428     2381.945  ops/sec
IntListTroveTraverse    thrpt   1      3    5  3628098.089     4848.035  ops/sec

По поводу графиков — спасибо за рекомендацию, учту на будущее.

@vladimir_dolzhenko 20 июл 2013 в 19:43

Я понимаю как работает механизм autoboxing и главная задача в том, чтобы избежать влияния GC на время работы benchmark-а. AggresiveOpts в разных случаях ведут себя по разному, но не знал, что среди прочего расширяют верхнюю границу кеша j.l.Integer.

Странно, что результаты выглядят почти всё то же самое, что и раньше — возможно, эффективно AggressiveOpts передавливает -XX:AutoBoxCacheMax=128 и стоит попробовать отключить AggressiveOpts и промерять на разных -Djava.lang.Integer.IntegerCache.high=N?

@xlix123 20 июл 2013 в 20:06

проверил:

java -server -XX:+AggressiveOpts -XX:AutoBoxCacheMax=128 \
-Xms2048m -Xmx2048m -XX:+UnlockDiagnosticVMOptions \
-XX:+PrintFlagsFinal | grep -i autobox
     intx AutoBoxCacheMax                          := 128  {C2 product}

Установка AutoBoxCacheMax при включенном AggressiveOpts работает. Дело в том что создание объекта в Java — очень быстрая операция, поэтому и разница невелика. А GC работает в параллельном потоке и поскольку памяти хватает Full GC и STW не случается.

@vladimir_dolzhenko 20 июл 2013 в 20:19

Спасибо за прояснение.

Но не только FullGC причина STW — в CMS это способен вызвать Remark.

НЛО прилетело и опубликовало эту надпись здесь

@kzn 20 июл 2013 в 19:02

Здорово! Еще было бы интересно почитать сравнение trove и fastutil.

@alexeyrom 20 июл 2013 в 20:46

Действительно ли IntListTroveTraverse на миллионе элементов в десять раз медленнее IntListJdkTraverse, а на тысяче — в десять раз быстрее?

@xlix123 20 июл 2013 в 21:16

для миллиона:

Benchmark                    Mode Thr    Cnt  Sec         Mean   Mean error    Units
IntListJdkTraverse          thrpt   1      3    5      774.100       71.809  ops/sec
IntListTroveTraverse        thrpt   1      3    5     3548.806        7.712  ops/sec

Jdk traverse 774 op/s, Trove traverse 3548 op/s. Вы видимо в колонку Mean error посмотрели. Кол-во операций в секунду в колонке Mean.

@alexeyrom 20 июл 2013 в 21:50

Да, действительно.

НЛО прилетело и опубликовало эту надпись здесь

@xlix123 21 июл 2013 в 11:26

По поводу States — это средство для per-thread/per-benchmark переменных в многопотоковых бенчмарках (для удобства).

По поводу Loops — я не тестирую свои методы, я тестирую методы библиотеки, и как бы не был сделан unrolling тестирующего метода, кол-во вызовов библиотечного метода от этого не изменится.

НЛО прилетело и опубликовало эту надпись здесь

@xlix123 21 июл 2013 в 12:23

не совсем понял про batch,
loop без unrolling'a:

for(long l = 0; l < INSERT_COUNT; ++l) {
            rvalue += jdkMap.get(l);
        }

loop с unrolling'om (грубо):

for(long l = 0; l < INSERT_COUNT; l += 4) {
            rvalue += jdkMap.get(l);
            rvalue += jdkMap.get(l + 1);
            rvalue += jdkMap.get(l + 2);
            rvalue += jdkMap.get(l + 3);
        }

НЛО прилетело и опубликовало эту надпись здесь

@xlix123 21 июл 2013 в 13:17

Если мерять абсолютные показатели — то да.
Но в данном случае меряется производительность Trove варианта относительно jdk. В обоих случаях jvm позволено вносить любые оптимизации (и они будут примерно одинаковы — unroll + inline). Ассемблерный листинг это подтверждает.

НЛО прилетело и опубликовало эту надпись здесь

@xlix123 21 июл 2013 в 15:19

Видимо я не вполне ясно выразил свою мысль. Цель была не посчитать конкретно сколько изолированно занимает каждый вызов, а оценить поведение in the wild.
То есть так, как это будет выглядеть в реальной программе, когда jit развернет циклы и заинлайнит библиотечные методы.

НЛО прилетело и опубликовало эту надпись здесь

Зарегистрируйтесь на Хабре, чтобы оставить комментарий