Является ли мелкая копия массива дешевой, независимо от размера?

Я тестирую 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

Таким образом, инициализация массива объясняет большую часть разницы.

Я не уверен, что понимаю вашу логику. Как вы думаете, почему копирование 20 вещей должно занимать столько же времени, сколько копирование 800 вещей? Даже если это всего лишь поверхностная копия, вы все равно делаете что-то 20 раз против 800 раз.

Sweeper 14.02.2023 05:09

Я не предполагал, что они займут одинаковое количество времени, но ожидал меньшей разницы, чем та, которую я получил от теста. Причина в том, что: элементы в массиве находятся в непрерывной области памяти (отныне это всего лишь мои предположения) arrayCopy просто берет часть этой области памяти в соответствии с размером, а затем пусть новый объект массива указать на это. Это похоже на разрезание торта, отрезание небольшой части от разрезания большой части не должно сильно отличаться? Конечно, результаты показали, что с моим пониманием что-то не так.

waynewingorc 14.02.2023 05:16
Лучшая компания по разработке спортивных приложений
Лучшая компания по разработке спортивных приложений
Ищете лучшую компанию по разработке спортивных приложений? Этот список, несомненно, облегчит вашу работу!
Blibli Automation Journey - Как захватить сетевой трафик с помощью утилиты HAR в Selenium 4
Blibli Automation Journey - Как захватить сетевой трафик с помощью утилиты HAR в Selenium 4
Если вы являетесь веб-разработчиком или тестировщиком, вы можете быть знакомы с Selenium, популярным инструментом для автоматизации работы...
Фото ️🔁 Radek Jedynak 🔃 on ️🔁 Unsplash 🔃
Фото ️🔁 Radek Jedynak 🔃 on ️🔁 Unsplash 🔃
Что такое Java 8 Streams API? Java 8 Stream API
Деревья поиска (Алгоритм4 Заметки к учебнику)
Деревья поиска (Алгоритм4 Заметки к учебнику)
(1) Двоичные деревья поиска: среднее lgN, наихудшее N для вставки и поиска.
0
2
55
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Короткий ответ: нет. Стоимость arraycopy пропорциональна размеру копируемого массива.

Действительно, ваш последний тест демонстрирует, что это правда.

Честно говоря, нет физического (электрического) смысла в том, чтобы копирование массива из N элементов было лучше, чем O(N). Это не то, как работает аппаратная память компьютера.

На низком уровне (под всей конвейерной обработкой, кэшированием и т. д.) копирование массива в память включает чтение ОЗУ из одной серии местоположений и запись ОЗУ в другую серию местоположений. Аппаратное обеспечение ОЗУ способно считывать/записывать только 8 или 16 (или что-то) байтов (давайте назовем число W) за операцию, потому что шина данных памяти имеет ширину всего 64 или 128 (или что-то) бит. Следовательно, копирование N байтов занимает N/W операций с памятью, что делает копирование O(N) тактовых циклов.

Другие вопросы по теме