Есть одна вещь, которая не упоминалась на этом пути, это «погоня за указателем», которая связана с частью «распаковки».Для массива такого небольшого размера то, используете ли вы timsort или quicksort, не должно иметь существенного значения (для примитивных массивов с текущими скоростями ЦП это, скорее всего, не то, что убивает вашу скорость).
Хотя бокс непроизойдет за пределами инициализации в вашем примере, большая разница происходит, когда данные читаются.
Поскольку целые числа являются примитивами, int [] - это просто непрерывный фрагмент памяти, который содержит сами данные, целое число [] представляет собой непрерывный фрагмент памяти, который содержит ссылки (то есть указатели) на отдельные объекты данных, а сами объекты Integer могут быть разбросаны по всей памяти.
Так что для операции сортировки в int [] ЦП будетполучить кусок памяти и может работать с этим напрямую.Но для Integer [] ЦП должен преследовать указатель для каждого отдельного объекта и получать его из памяти, прежде чем он сможет сравнить его, а затем обработать тот кусок памяти, который является массивом, и переставить его.Это называется «погоня за указателем».
Это не так много, что Integer [] требует больше операций для каждого фрагмента данных, таких как чтение значения, добавление длины заголовка к базовому адресу и получение значения изтам (центральный процессор выполняет эти инструкции очень хорошо, и это скрывает большую часть его влияния), задержка памяти убивает вас.Извлечение каждого отдельного объекта Integer из случайной ячейки памяти делает почти все различия.
Обычно это не имеет большого значения, так как обычно вы инициализируете довольно небольшое количество Integer [] в узком цикле, и естьв фоновом режиме ничего особенного не происходит, поэтому объекты Integer, вероятно, находятся в непосредственной близости в памяти и могут быть извлечены в кэш и доступны оттуда довольно быстро, но для огромных массивов и списков, которые создаются и изменяются во всех загруженных приложениях, этоможет иметь существенное значение и может привести к неожиданным всплескам задержки.Вы захотите избежать этого, если вам нужны надежные, низкие задержки.Однако для огромного числа приложений, если сортировка занимает несколько миллисекунд, никто не замечает.
[EDIT]
Как вы и просили в комментарии, вот код дляпокажите, что речь идет не о Timsort vs quicksort:
import java.util.Arrays;
import java.util.Random;
public class Pointerchasing1 {
public static void main(String[] args) {
//use the exact same algorithm implementation (insertionSort), to show that slowness is not caused by timsort vs quicksort.
//expect that the object-version is slower.
final int[] direct = new int[1024];
final Integer[] refs = new Integer[direct.length];
final Random rnd = new Random(0);
for (int t = 0; t < 1000; ++t) {
Arrays.setAll(direct, index -> rnd.nextInt());
Arrays.setAll(refs, index -> direct[index]); // boxing happens here
//measure direct:
long t1 = System.nanoTime();
insertionSortPrimitive(direct);
long e1 = System.nanoTime()-t1;
//measure refs:
long t2 = System.nanoTime();
insertionSortObjects(refs);
long e2 = System.nanoTime()-t2;
// use results, so compiler can't eliminate the loops
System.out.println(Arrays.toString(direct));
System.out.println(Arrays.toString(refs));
System.out.println("-");
System.out.println(e1);
System.out.println(e2);
System.out.println("--");
}
}
private static void insertionSortPrimitive(final int[] arr) {
int i, key, j;
for (i = 1; i < arr.length; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
private static void insertionSortObjects(final Integer[] arr) {
int i, key, j;
for (i = 1; i < arr.length; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
}
Этот «тест» оставляет распаковку как возможного виновника.
[EDIT2]
Теперь этот тест должен показать, что«распаковка» не проблема.Распаковка - это просто добавление нескольких байтов заголовка объекта к адресу (из-за непорядочного выполнения и конвейерной обработки эти затраты практически исчезают) и получение значения из этого местоположения.В этом тесте я использую два примитивных массива, один для ссылки и один для значения.Таким образом, каждый доступ является косвенным.Это очень похоже на распаковку, просто без добавления нескольких дополнительных байтов для заголовка объекта.Основное отличие состоит в том, что «косвенной» версии не нужно гоняться за указателем для каждого значения в куче, она может загружать как массивы, так и индексы из массива refs в массив значений.
Если погрешность указателя имеет значение, а не распаковывать, то косвенная версия должна быть быстрее, чем версия объектов, которая распаковывает.
import java.util.Arrays;
import java.util.Random;
public class Pointerchasing2 {
public static void main(String[] args) {
// use indirect access (like unboxing, but just chasing a single array pointer) vs. Integer objects (chasing every object's pointer).
// expect that the object-version is still slower.
final int[] values = new int[1024];
final int[] refs = new int[1024];
final Integer[] objects = new Integer[values.length];
final Random rnd = new Random(0);
for (int t = 0; t < 1000; ++t) {
Arrays.setAll(values, index -> rnd.nextInt());
Arrays.setAll(refs, index -> index);
Arrays.setAll(objects, index -> values[index]); // boxing happens here
// measure indirect:
long t1 = System.nanoTime();
insertionSortPrimitiveIndirect(refs, values);
long e1 = System.nanoTime() - t1;
// measure objects:
long t2 = System.nanoTime();
insertionSortObjects(objects);
long e2 = System.nanoTime() - t2;
// use results, so compiler can't eliminate the loops
System.out.println(Arrays.toString(indirectResult(refs, values)));
System.out.println(Arrays.toString(objects));
System.out.println("-");
System.out.println(e1);
System.out.println(e2);
System.out.println("--");
}
}
private static void insertionSortPrimitiveIndirect(final int[] refs, int[] values) {
int i, keyIndex, j;
for (i = 1; i < refs.length; i++) {
keyIndex = refs[i];
j = i - 1;
while (j >= 0 && values[refs[j]] > values[keyIndex]) {
refs[j + 1] = refs[j];
j = j - 1;
}
refs[j + 1] = keyIndex;
}
}
private static void insertionSortObjects(final Integer[] arr) {
int i, key, j;
for (i = 1; i < arr.length; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
private static int[] indirectResult(final int[] refs, int[] values) {
final int[] result = new int[1024];
Arrays.setAll(result, index -> values[refs[index]]);
return result;
}
}
Результат: в обоих этих тестах«примитивные» и «косвенные» версии быстрее, чем доступ к объектам в куче.Следует ожидать, что распаковка не убивает скорость, а задержку памяти из-за погони за указателем.
Смотрите также это видео о проекте Valhalla: («Типы значений и общая специализация в JVM обещают нам лучшую JIT»код, локальность данных и удалить тиранию погони указателя. ") https://vimeo.com/289667280