1. Обзор
Язык программирования Java предоставляет массивы и коллекции для группировки объектов. В основном коллекция поддерживается массивом и моделируется набором методов для обработки содержащихся в ней элементов.
При разработке программного обеспечения довольно часто используются обе эти структуры данных. Следовательно, программистам нужен связующий механизм для преобразования этих элементов из одной формы в другую. Метод asList из класса Arrays и метод toArray интерфейса Collection образуют этот мост. ``
В этом уроке мы проведем глубокий анализ интересного аргумента: какой метод toArray использовать и почему? Мы также будем использовать бенчмаркинг с помощью JMH для подтверждения этих аргументов.
2. Кроличья нора toArray
Прежде чем бесцельно вызывать метод toArray , давайте разберемся, что внутри коробки. Интерфейс Collection предлагает два метода преобразования коллекции в массив:
Object[] toArray()
<T> T[] toArray(T[] a)
Оба метода возвращают массив, содержащий все элементы коллекции. Чтобы продемонстрировать это, давайте создадим список натуральных чисел:
List<Integer> naturalNumbers = IntStream
.range(1, 10000)
.boxed()
.collect(Collectors.toList());
2.1. Коллекция.toArray()
Метод toArray() выделяет в памяти новый массив с длиной, равной размеру коллекции. Внутри он вызывает Arrays.copyOf для базового массива, поддерживающего коллекцию . Поэтому возвращаемый массив не имеет ссылок на него и его можно безопасно использовать:
Object[] naturalNumbersArray = naturalNumbers.toArray();
Однако мы не можем просто преобразовать результат в Integer[]. Это приведет к ClassCastException .
2.2. <T> T[] Collection.toArray(T[] а)
В отличие от непараметризованного метода, этот принимает в качестве аргумента предварительно выделенный массив. Кроме того, использование Generics в определении метода требует наличия одного и того же типа для входных данных и возвращаемого массива. Это также решает ранее замеченную проблему перебора Object[] .
Этот вариант работает в зависимости от размера входного массива:
- Если длина предварительно выделенного массива меньше размера коллекции, выделяется новый массив необходимой длины и того же типа:
Integer[] naturalNumbersArray = naturalNumbers.toArray(new Integer[0]);
- Если входной массив достаточно велик, чтобы содержать элементы коллекции, он возвращается с этими элементами внутри:
Integer[] naturalNumbersArray = naturalNumbers.toArray(new Integer[naturalNumbers.size]);
Теперь давайте вернемся к исходному вопросу о выборе более быстрого и эффективного кандидата.
3. Испытания производительности
Давайте начнем с простого эксперимента, в котором сравниваются варианты нулевого размера ( toArray(new T[0] ) и предварительно заданного размера ( toArray(new T[size] ) ) . Мы будем использовать популярный ArrayList и набор TreeSet с поддержкой AbstractCollection для Кроме того, мы будем включать коллекции разного размера (маленькие, средние и большие), чтобы иметь широкий спектр выборочных данных. ``
3.1. Ориентир JMH
Затем давайте составим тест JMH (Java Microbenchmark Harness) для наших испытаний. Мы настроим параметры размера и типа коллекции для теста:
@Param({ "10", "10000", "10000000" })
private int size;
@Param({ "array-list", "tree-set" })
private String type;
Кроме того, мы определим методы тестирования для вариантов toArray с нулевым и предварительным размером :
@Benchmark
public String[] zero_sized() {
return collection.toArray(new String[0]);
}
@Benchmark
public String[] pre_sized() {
return collection.toArray(new String[collection.size()]);
}
3.2. Сравнительные результаты
Запуск приведенного выше теста на 8 виртуальных ЦП, 32 ГБ ОЗУ, виртуальной машине Linux x86_64 с JMH (v1.28) и JDK (1.8.0_292) дает результаты, показанные ниже. Оценка показывает среднее время выполнения в наносекундах на операцию для каждого из проверенных методов.
Чем меньше значение, тем лучше производительность:
Benchmark (size) (type) Mode Cnt Score Error Units
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
TestBenchmark.zero_sized 10 array-list avgt 15 24.939 ± 1.202 ns/op
TestBenchmark.pre_sized 10 array-list avgt 15 38.196 ± 3.767 ns/op
----------------------------------------------------------------------------------------------
TestBenchmark.zero_sized 10000 array-list avgt 15 15244.367 ± 238.676 ns/op
TestBenchmark.pre_sized 10000 array-list avgt 15 21263.225 ± 802.684 ns/op
----------------------------------------------------------------------------------------------
TestBenchmark.zero_sized 10000000 array-list avgt 15 82710389.163 ± 6616266.065 ns/op
TestBenchmark.pre_sized 10000000 array-list avgt 15 100426920.878 ± 10381964.911 ns/op
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
TestBenchmark.zero_sized 10 tree-set avgt 15 66.802 ± 5.667 ns/op
TestBenchmark.pre_sized 10 tree-set avgt 15 66.009 ± 4.504 ns/op
----------------------------------------------------------------------------------------------
TestBenchmark.zero_sized 10000 tree-set avgt 15 85141.622 ± 2323.420 ns/op
TestBenchmark.pre_sized 10000 tree-set avgt 15 89090.155 ± 4895.966 ns/op
----------------------------------------------------------------------------------------------
TestBenchmark.zero_sized 10000000 tree-set avgt 15 211896860.317 ± 21019102.769 ns/op
TestBenchmark.pre_sized 10000000 tree-set avgt 15 212882486.630 ± 20921740.965 ns/op
После тщательного наблюдения за приведенными выше результатами становится совершенно очевидным, что вызовы методов нулевого размера выигрывают все, для всех размеров и типов коллекций в этом испытании.
Пока эти цифры — просто данные. Чтобы иметь детальное представление, давайте копнем глубже и проанализируем их.
3.3. Скорость распределения
Гипотетически можно предположить, что вызовы метода toArray с нулевым размером работают лучше, чем вызовы с предварительным размером из-за оптимизированного распределения памяти на операцию . Давайте проясним это, выполнив еще один бенчмарк и оценив средние скорости выделения — память в байтах, выделенную на операцию — для тестируемых методов .
JMH предоставляет профилировщик GC ( -prof gc ), который внутренне использует ThreadMXBean#getThreadAllocatedBytes для расчета скорости выделения на @ Benchmark :
Benchmark (size) (type) Mode Cnt Score Error Units
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
TestBenchmark.zero_sized:·gc.alloc.rate.norm 10 array-list avgt 15 72.000 ± 0.001 B/op
TestBenchmark.pre_sized:·gc.alloc.rate.norm 10 array-list avgt 15 56.000 ± 0.001 B/op
---------------------------------------------------------------------------------------------------------------------------------
TestBenchmark.zero_sized:·gc.alloc.rate.norm 10000 array-list avgt 15 40032.007 ± 0.001 B/op
TestBenchmark.pre_sized:·gc.alloc.rate.norm 10000 array-list avgt 15 40016.010 ± 0.001 B/op
---------------------------------------------------------------------------------------------------------------------------------
TestBenchmark.zero_sized:·gc.alloc.rate.norm 10000000 array-list avgt 15 40000075.796 ± 8.882 B/op
TestBenchmark.pre_sized:·gc.alloc.rate.norm 10000000 array-list avgt 15 40000062.213 ± 4.739 B/op
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
TestBenchmark.zero_sized:·gc.alloc.rate.norm 10 tree-set avgt 15 56.000 ± 0.001 B/op
TestBenchmark.pre_sized:·gc.alloc.rate.norm 10 tree-set avgt 15 56.000 ± 0.001 B/op
---------------------------------------------------------------------------------------------------------------------------------
TestBenchmark.zero_sized:·gc.alloc.rate.norm 10000 tree-set avgt 15 40055.818 ± 16.723 B/op
TestBenchmark.pre_sized:·gc.alloc.rate.norm 10000 tree-set avgt 15 41069.423 ± 1644.717 B/op
---------------------------------------------------------------------------------------------------------------------------------
TestBenchmark.zero_sized:·gc.alloc.rate.norm 10000000 tree-set avgt 15 40000155.947 ± 9.416 B/op
TestBenchmark.pre_sized:·gc.alloc.rate.norm 10000000 tree-set avgt 15 40000138.987 ± 7.987 B/op
Очевидно, приведенные выше цифры доказывают, что скорость выделения более или менее одинакова для одинаковых размеров, независимо от типа коллекции или варианта toArray . Следовательно, это опровергает любые спекулятивные предположения о том, что варианты toArray с предварительным и нулевым размером работают по-разному из-за неравномерности их скорости выделения памяти `` .
3.4. Внутреннее устройство toArray (T[] a)
Чтобы еще больше выяснить причину проблемы, давайте углубимся во внутренности ArrayList :
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
В основном, в зависимости от длины предварительно выделенного массива, это либо Arrays.copyOf , либо собственный вызов метода System.arraycopy , который копирует базовые элементы коллекции в массив.
Кроме того, глядя на метод copyOf , становится очевидным, что сначала создается массив копий, длина которого равна размеру коллекции, а затем следует вызов System.arraycopy :
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
Когда и метод с нулевым размером, и метод с предварительным размером в конечном итоге вызывают собственный метод System.arraycopy , как вызов метода с нулевым размером быстрее?
Загадка заключается в прямых затратах процессорного времени, затрачиваемого на выполнение нулевых инициализаций для предварительно выделенных извне массивов, что делает метод toArray(new T[size]) намного медленнее.
4. Нулевые инициализации
Спецификация языка Java указывает, что только что созданные массивы и объекты должны иметь значения полей по умолчанию, а не нерегулярные остатки из памяти. Следовательно, среда выполнения должна обнулить предварительно выделенное хранилище. Сравнительные эксперименты доказали, что при вызовах метода массива нулевого размера удается избежать обнуления, а в случае предварительно заданного размера — нет.
Рассмотрим пару эталонов:
@Benchmark
public Foo[] arraycopy_srcLength() {
Object[] src = this.src;
Foo[] dst = new Foo[size];
System.arraycopy(src, 0, dst, 0, src.length);
return dst;
}
@Benchmark
public Foo[] arraycopy_dstLength() {
Object[] src = this.src;
Foo[] dst = new Foo[size];
System.arraycopy(src, 0, dst, 0, dst.length);
return dst;
}
Экспериментальные наблюдения показывают, что System.arraycopy сразу после выделения массива в бенчмарке arraycopy_srcLength способен избежать предварительного обнуления массива dst . Однако выполнение arraycopy_dstLength не могло избежать предварительного обнуления .
По совпадению, последний случай arraycopy_dstLength похож на метод массива предварительно заданного размера collection.toArray(new String[collection.size()]) , где обнуление невозможно устранить, отсюда и его медлительность.
5. Тесты на новых JDK
Наконец, давайте выполним исходный тест на недавно выпущенных JDK, а также настроим JVM для использования более нового и значительно улучшенного сборщика мусора G1 :
# VM version: JDK 11.0.2, OpenJDK 64-Bit Server VM, 11.0.2+9
-----------------------------------------------------------------------------------
Benchmark (size) (type) Mode Cnt Score Error Units
-----------------------------------------------------------------------------------
ToArrayBenchmark.zero_sized 100 array-list avgt 15 199.920 ± 11.309 ns/op
ToArrayBenchmark.pre_sized 100 array-list avgt 15 237.342 ± 14.166 ns/op
-----------------------------------------------------------------------------------
ToArrayBenchmark.zero_sized 100 tree-set avgt 15 819.306 ± 85.916 ns/op
ToArrayBenchmark.pre_sized 100 tree-set avgt 15 972.771 ± 69.743 ns/op
###################################################################################
# VM version: JDK 14.0.2, OpenJDK 64-Bit Server VM, 14.0.2+12-46
------------------------------------------------------------------------------------
Benchmark (size) (type) Mode Cnt Score Error Units
------------------------------------------------------------------------------------
ToArrayBenchmark.zero_sized 100 array-list avgt 15 158.344 ± 3.862 ns/op
ToArrayBenchmark.pre_sized 100 array-list avgt 15 214.340 ± 5.877 ns/op
------------------------------------------------------------------------------------
ToArrayBenchmark.zero_sized 100 tree-set avgt 15 877.289 ± 132.673 ns/op
ToArrayBenchmark.pre_sized 100 tree-set avgt 15 934.550 ± 148.660 ns/op
####################################################################################
# VM version: JDK 15.0.2, OpenJDK 64-Bit Server VM, 15.0.2+7-27
------------------------------------------------------------------------------------
Benchmark (size) (type) Mode Cnt Score Error Units
------------------------------------------------------------------------------------
ToArrayBenchmark.zero_sized 100 array-list avgt 15 147.925 ± 3.968 ns/op
ToArrayBenchmark.pre_sized 100 array-list avgt 15 213.525 ± 6.378 ns/op
------------------------------------------------------------------------------------
ToArrayBenchmark.zero_sized 100 tree-set avgt 15 820.853 ± 105.491 ns/op
ToArrayBenchmark.pre_sized 100 tree-set avgt 15 947.433 ± 123.782 ns/op
####################################################################################
# VM version: JDK 16, OpenJDK 64-Bit Server VM, 16+36-2231
------------------------------------------------------------------------------------
Benchmark (size) (type) Mode Cnt Score Error Units
------------------------------------------------------------------------------------
ToArrayBenchmark.zero_sized 100 array-list avgt 15 146.431 ± 2.639 ns/op
ToArrayBenchmark.pre_sized 100 array-list avgt 15 214.117 ± 3.679 ns/op
------------------------------------------------------------------------------------
ToArrayBenchmark.zero_sized 100 tree-set avgt 15 818.370 ± 104.643 ns/op
ToArrayBenchmark.pre_sized 100 tree-set avgt 15 964.072 ± 142.008 ns/op
####################################################################################
Интересно, что метод toArray(new T[0]) всегда работает быстрее, чем toArray(new T[size]) . Кроме того, его производительность постоянно улучшалась с каждым новым выпуском JDK.
5.1. Коллекция Java 11.toArray(IntFunction<T[]>)
В Java 11 интерфейс Collection представил новый метод toArray по умолчанию , который принимает генератор IntFunction <T[]> в качестве аргумента (тот, который будет генерировать новый массив желаемого типа и предоставленной длины).
Этот метод гарантирует инициализацию нового массива T[0] путем вызова функции генератора со значением нуля , тем самым гарантируя, что всегда будет выполняться более быстрый и лучший метод toArray(T[]) нулевого размера .
6. Заключение
В этой статье мы исследовали различные перегруженные методы toArray интерфейса Collection . Мы также провели испытания производительности с использованием инструмента микротестирования JMH в различных JDK.
Мы поняли необходимость и влияние обнуления и наблюдали, как внутренне выделенный массив устраняет обнуление, тем самым выигрывая гонку производительности. Наконец, мы можем твердо заключить, что вариант toArray(new T[0]) быстрее, чем toArray(new T[size]) и, следовательно, всегда должен быть предпочтительным вариантом, когда нам нужно преобразовать коллекцию в массив.
Как всегда, код, использованный в этой статье, можно найти на GitHub .