xlix123 Jul 20 2013 at 17:59

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

4 min

21K

Programming*Java*

+25

Comments 40

vladimir_dolzhenko Jul 20 2013 at 21: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 Jul 20 2013 at 22:07

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

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

kzn Jul 20 2013 at 23:01

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

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

SamSol Jul 21 2013 at 00:08

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

xlix123 Jul 21 2013 at 00:15

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

SamSol Jul 21 2013 at 00: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-шные коллекции.
Не занимайтесь преждевременной оптимизацией.

-1

xlix123 Jul 21 2013 at 01:07

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

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

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

kzn Jul 21 2013 at 01:15

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

xlix123 Jul 21 2013 at 01:23

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

kzn Jul 21 2013 at 00:18

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

xlix123 Jul 21 2013 at 00:27

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

kzn Jul 21 2013 at 00:34

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

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

xlix123 Jul 21 2013 at 01:32

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

UFO just landed and posted this here

SamSol Jul 21 2013 at 00:03

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

-3

leventov Jul 22 2013 at 09:51

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

alexeyrom Jul 21 2013 at 00:55

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

leventov Jul 22 2013 at 09:57

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

eugenius_nsk Jul 22 2013 at 18:17

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

xlix123 Jul 22 2013 at 19:45

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

vladimir_dolzhenko Jul 20 2013 at 22:14

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

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

xlix123 Jul 20 2013 at 23: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 Jul 20 2013 at 23:43

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

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

xlix123 Jul 21 2013 at 00: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 Jul 21 2013 at 00:19

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

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

dborovikov Jul 21 2013 at 14:56

А может объекты вообще не доживают до old gen-а, и прибиваются копирующим сборщиком очень быстро.

kzn Jul 20 2013 at 23:02

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

alexeyrom Jul 21 2013 at 00:46

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

xlix123 Jul 21 2013 at 01: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 Jul 21 2013 at 01:50

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

dborovikov Jul 21 2013 at 14:52

1) Почитайте JMHSample_11_Loops.java. Вдимо неправильно использовать циклы в коде бенчмарка в явном виде (если только вы не хотите потестировать выигрыш от unrolling-а циклов). Нормальный способ — это использовать один вызов в одном тестовом методе jmh, а повторения конфигурировать через опции JMH.

2) Почитайте JMHSample_03_States.java. Вы храните состояние в статической перменной. В JMH для этого есть аннотация State и это не просто так сделано.

Я думаю вам стоит переписать бенчмарк согласно рекомендациям JMH и померить все заново.

xlix123 Jul 21 2013 at 15:26

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

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

dborovikov Jul 21 2013 at 15:59

State не только для написания multithread бенчмарков, но и для устранения оптимизации dead code. Из доков примера DCE:

«This can be prevented by always reading the inputs from the state, computing
the result based on that state, and the follow the rules to prevent DCE»

Однако у меня есть подозрение, что hot spot не делает DCE для static не final аргументов. Но я бы на это не закладывался, а всегда передавал аргументы через State

По поводу loops — количество вызовов не изменяется, но чем больше «батч», тем меньше будет среднее время выполняния одной операции за счет оптимизаций unrolling/pipelining. Это вполне приемлимо для бенчмарка Traverse — это именно то, что нам нужно в реальной жизни.

Для измерения стоимости операции вставки или поиска циклы не приемлимы.

xlix123 Jul 21 2013 at 16: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);
        }

dborovikov Jul 21 2013 at 16:40

Да, операций будет все равно INSERT_COUNT, но за счет того, что они идут подряд, суммарное время выполнения может уменьшиться (pipelining). И величина времения выполнения одной операции, которое <время выполнения> / INSERT_COUNT тоже уменьшиться. Пример JMHSample_11_Loops.java именно это и демонстрирует, операция одна, но с увелечением количества итераций она становитя как-будто бы быстрее.

xlix123 Jul 21 2013 at 17:17

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

dborovikov Jul 21 2013 at 17:42

Бенчмаркинг — это борьба с оптимизациями. А что если в одном варианте JVM решила соптимизировать, в другом — нет? Для этого и есть JMH.

dborovikov Jul 21 2013 at 17:58

И вообще я не понимаю зачем вы упираетесь и мы тут гаданиями какими-то занимаемся. Нужно переписать все согласно рекомендациям JMH и сравнить.

xlix123 Jul 21 2013 at 19:19

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

dborovikov Jul 21 2013 at 22:02

Вы все равно упираетесь. Я бы мог начать распинаться как правильно тестировать производительность в условиях, близких к реальным, но вижу что это не имеет смысла. Так что за сим откланяюсь.

Show the best of all time