Я тестирую System.arraycopy, который делает неглубокую копию, которую я полагаю дешевой, независимо от того, сколько элементов я хочу скопировать.
private static int[] randomInts = new int[800];
@Setup
public void setup() {
Random rand = new Random();
for (int i = 0; i < 800; i++) {
randomInts[i] = rand.nextInt(10000) + 1;
}
}
// Copy first 20 elements from randomInts
@Benchmark
public int[] testFirst20() {
final int[] toArray = new int[20];
System.arraycopy(randomInts, 0, toArray, 0, 20);
return toArray;
}
// Copy the whole randomInts
@Benchmark
public int[] testFull() {
final int[] toArray = new int[800];
System.arraycopy(randomInts, 0, toArray, 0, 800);
return toArray;
}
Полученные результаты:
Benchmark Mode Cnt Score Error Units
BenchAddToArray.testFirst20 thrpt 5 116484.035 ± 9793.886 ops/ms
BenchAddToArray.testFull thrpt 5 3348.843 ± 429.225 ops/ms
Так что я думаю, мы должны быть осторожны с производительностью, даже если это поверхностная копия. Я знал, что создание полной копии должно быть более масштабным, чем создание копии меньшего размера, но не ожидал, что разница будет такой большой. Может ли кто-нибудь дать мне некоторое представление о том, какая часть System.arraycopy привела к разнице между копированием массивов разной длины?
Благодаря комментарию @Sweeper, я также протестировал другую версию, в которой инициализация массива выполняется в @Setup, так что тест выполняется исключительно на arrayCopy. Получил следующие результаты:
Benchmark Mode Cnt Score Error Units
BenchAddToArray.testFirst20 thrpt 5 30061.031 ± 4521.763 ops/ms
BenchAddToArray.testFull thrpt 5 2753.594 ± 117.719 ops/ms
Таким образом, инициализация массива объясняет большую часть разницы.
Я не предполагал, что они займут одинаковое количество времени, но ожидал меньшей разницы, чем та, которую я получил от теста. Причина в том, что: элементы в массиве находятся в непрерывной области памяти (отныне это всего лишь мои предположения) arrayCopy просто берет часть этой области памяти в соответствии с размером, а затем пусть новый объект массива указать на это. Это похоже на разрезание торта, отрезание небольшой части от разрезания большой части не должно сильно отличаться? Конечно, результаты показали, что с моим пониманием что-то не так.
Короткий ответ: нет. Стоимость arraycopy пропорциональна размеру копируемого массива.
Действительно, ваш последний тест демонстрирует, что это правда.
Честно говоря, нет физического (электрического) смысла в том, чтобы копирование массива из N элементов было лучше, чем O(N). Это не то, как работает аппаратная память компьютера.
На низком уровне (под всей конвейерной обработкой, кэшированием и т. д.) копирование массива в память включает чтение ОЗУ из одной серии местоположений и запись ОЗУ в другую серию местоположений. Аппаратное обеспечение ОЗУ способно считывать/записывать только 8 или 16 (или что-то) байтов (давайте назовем число W) за операцию, потому что шина данных памяти имеет ширину всего 64 или 128 (или что-то) бит. Следовательно, копирование N байтов занимает N/W операций с памятью, что делает копирование O(N) тактовых циклов.
Я не уверен, что понимаю вашу логику. Как вы думаете, почему копирование 20 вещей должно занимать столько же времени, сколько копирование 800 вещей? Даже если это всего лишь поверхностная копия, вы все равно делаете что-то 20 раз против 800 раз.