Comments 40
Стоит отметить, что trove'овские HashMap в отличии от j.u.HashMap используют размеры массивов равные простым числам, что снижает количество потенциальных коллиций в результате поиска индекса, т.е
j.u.HashMap использует тонкий момент — размер массива всегда 2k, что позволяет искать индекс проще
Что позвояет при некоторых обстоятельствах j.u.HashMap обходить trove.
int bucketIndex = hashCode % array.length;
j.u.HashMap использует тонкий момент — размер массива всегда 2k, что позволяет искать индекс проще
int bucketIndex = hashCode1 & (array.length - 1);
Что позвояет при некоторых обстоятельствах j.u.HashMap обходить trove.
Где-то в документации попадалась рекомендация использовать массивы примитивов (int[], long[], etc.) в случае, когда необходимо написать «числодробилку», и классы коллекций во всех остальных случаях.
Даже не могу себе представить когда может оказаться выгоднее использовать коллекции-похожие-на-sdk-шные вместо sdk-шных или вместо массивов примитивов.
Даже не могу себе представить когда может оказаться выгоднее использовать коллекции-похожие-на-sdk-шные вместо sdk-шных или вместо массивов примитивов.
У trove одно из весомых преимуществ — значительное снижение потребление памяти.
Коллекции, похожие на sdk удобно использовать когда заранее не знаешь, сколько элементов будет.
Коллекции, похожие на sdk удобно использовать когда заранее не знаешь, сколько элементов будет.
Если вы не знаете сколько будет элементов — используйте штатные коллекции.
В «числодробилках» необходимо знать «сколько будет элементов» чтобы построить эффективный алгоритм.
Все остальное — «преждевременная оптимизация».
В «числодробилках» необходимо знать «сколько будет элементов» чтобы построить эффективный алгоритм.
Все остальное — «преждевременная оптимизация».
Весьма спорное утверждение. Возьмем суммирование ряда — какая разница сколько элементов нужно просуммировать. И вполне возможно, что заранее неизвестно сколько элементов в ряду.
В суммировании ряда вам важнее будет задать правильный интерфейс.
Более эффективный интерфейс — первый. (И вот у вас уже известно сколько элементов).
Но второй вариант может быть обусловлен каким-то внешним требованием. Тогда:
И вот у вас снова массив примитивов, а первые два метода во-первых достаточно простые и прямолинейные чтобы не быть источниками багов и скорость их выполнения целиком на совести компилятора (и jit-компилятора).
Если пишете «числодробилку» — используйте массивы примитивов.
Если НЕ пишете «числодробилку» используйте штатные SDK-шные коллекции.
Не занимайтесь преждевременной оптимизацией.
// 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-шные коллекции.
Не занимайтесь преждевременной оптимизацией.
Только на это уйдет в 4 раза больше памяти, а так все нормально. Разумеется, все это актуально, когда данных много.
Если мы говорим о списках — элементы хранятся в массивах int[] для TIntArrayList, long[] для TLongArrayList. При добавлении элемента, в случае если в массиве нет места, будет создан новый массив, большего размера. Старый подберет GC. В случае массового добавления элементов он даже Eden Space покинуть не успеет.
UFO just landed and posted this here
Кавычки следовало вокруг плюсы поставить.
Не совсем. У хешей из Trove под 50 байт полей, но главное — дублирующий массив байтов состояний ячеек. Т. е., например, байтовый хеш (до 255 элементов, следовательно около 600 байт — максимальный размер таблицы) будет занимать как минимум на 58% больше памяти чем голый массив
byte[]
, которым в приложениях зачастую можно обойтись.КО: в документации так написано, потому что опции «использовать классы коллекций примитивов» в стандартной библиотеке нет и порекомендовать её нельзя.
Не могу себе представить, когда простая замена всех стандартных коллекций с числовыми объектами на коллекции Trove не ускорит приложение, при том что удобство уменьшится едва ли.
Удобство уменьшается при взаимодействии со сторонними библиотеками, которые про Trove ничего не знают и хотят Collection. (это если говорить про «всегда заменяем числовые коллекции на Trove»)
В этом случае можно воспользоваться декораторами для приведения интерфейса к стандартному интерфейсу коллекций.
Хорошо было бы прогнать тест с включённым и выключенным autoboxing'ом указав -Djava.lang.Integer.IntegerCache.high=N
И ещё одна рекомендация — таблицы цифр это хорошо, но наглядное представление в виде графиков в том же excel'е или google chart api сделают восприятие проще.
И ещё одна рекомендация — таблицы цифр это хорошо, но наглядное представление в виде графиков в том же excel'е или google chart api сделают восприятие проще.
-Djava.lang.Integer.IntegerCache.high=N не выключает механизм autoboxing'а полностью. Oн не создает новые объекты для Integer попадающих в промежуток (-128) — N, а возвращает ссылки на заранее сформированные объекты. Ключ -XX:+AggressiveOpts поднимает N до 20000, так что тест с 1тыс уже с «выключенным» autoboxing'ом
Рузультаты на 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
По поводу графиков — спасибо за рекомендацию, учту на будущее.
Я понимаю как работает механизм autoboxing и главная задача в том, чтобы избежать влияния GC на время работы benchmark-а. AggresiveOpts в разных случаях ведут себя по разному, но не знал, что среди прочего расширяют верхнюю границу кеша j.l.Integer.
Странно, что результаты выглядят почти всё то же самое, что и раньше — возможно, эффективно AggressiveOpts передавливает -XX:AutoBoxCacheMax=128 и стоит попробовать отключить AggressiveOpts и промерять на разных -Djava.lang.Integer.IntegerCache.high=N?
Странно, что результаты выглядят почти всё то же самое, что и раньше — возможно, эффективно AggressiveOpts передавливает -XX:AutoBoxCacheMax=128 и стоит попробовать отключить AggressiveOpts и промерять на разных -Djava.lang.Integer.IntegerCache.high=N?
проверил:
Установка AutoBoxCacheMax при включенном AggressiveOpts работает. Дело в том что создание объекта в Java — очень быстрая операция, поэтому и разница невелика. А GC работает в параллельном потоке и поскольку памяти хватает Full GC и STW не случается.
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 не случается.
Здорово! Еще было бы интересно почитать сравнение trove и fastutil.
Действительно ли IntListTroveTraverse на миллионе элементов в десять раз медленнее IntListJdkTraverse, а на тысяче — в десять раз быстрее?
для миллиона:
Jdk traverse 774 op/s, Trove traverse 3548 op/s. Вы видимо в колонку Mean error посмотрели. Кол-во операций в секунду в колонке Mean.
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.
UFO just landed and posted this here
По поводу States — это средство для per-thread/per-benchmark переменных в многопотоковых бенчмарках (для удобства).
По поводу Loops — я не тестирую свои методы, я тестирую методы библиотеки, и как бы не был сделан unrolling тестирующего метода, кол-во вызовов библиотечного метода от этого не изменится.
По поводу Loops — я не тестирую свои методы, я тестирую методы библиотеки, и как бы не был сделан unrolling тестирующего метода, кол-во вызовов библиотечного метода от этого не изменится.
UFO just landed and posted this here
не совсем понял про batch,
loop без unrolling'a:
loop с unrolling'om (грубо):
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);
}
UFO just landed and posted this here
Если мерять абсолютные показатели — то да.
Но в данном случае меряется производительность Trove варианта относительно jdk. В обоих случаях jvm позволено вносить любые оптимизации (и они будут примерно одинаковы — unroll + inline). Ассемблерный листинг это подтверждает.
Но в данном случае меряется производительность Trove варианта относительно jdk. В обоих случаях jvm позволено вносить любые оптимизации (и они будут примерно одинаковы — unroll + inline). Ассемблерный листинг это подтверждает.
UFO just landed and posted this here
UFO just landed and posted this here
Sign up to leave a comment.
Библиотека Trove. Коллекции примитивных типов в Java