Почему обработка отсортированного массива * медленнее*, чем несортированного массива? (Java ArrayList.indexOf)

название относится к тому, почему быстрее обрабатывать сортированный массив, чем несортированный массив?

это тоже эффект предсказания ветвей? Осторожно: здесь обработка для отсортированного массива медленнее!!

рассмотрим следующий код:

private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;

@Test
public void testBinarySearch() {
    Random r = new Random(0);
    List<Double> list = new ArrayList<>(LIST_LENGTH);
    for (int i = 0; i < LIST_LENGTH; i++) {
        list.add(r.nextDouble());
    }
    //Collections.sort(list);
    // remove possible artifacts due to the sorting call
    // and rebuild the list from scratch:
    list = new ArrayList<>(list);

    int nIterations = 0;
    long startTime = System.currentTimeMillis();
    do {
        int index = r.nextInt(LIST_LENGTH);
        assertEquals(index, list.indexOf(list.get(index)));
        nIterations++;
    } while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
    long duration = System.currentTimeMillis() - startTime;
    double slowFindsPerSec = (double) nIterations / duration * 1000;
    System.out.println(slowFindsPerSec);

    ...
}

это выводит значение около 720 на моей машине.

теперь, если я активирую вызов сортировки коллекций, это значение падает до 142. Зачем?!?

результаты are окончательно, они не меняются, если я увеличиваю количество итераций/время.

Java версия 1.8.0_71 (Oracle VM, 64 бит), работает под управлением Windows 10, JUnit test в Eclipse Mars.

обновление

похоже, связано с непрерывным доступом к памяти (двойные объекты, доступные в последовательном порядке против случайного порядка). Эффект начинает исчезать для меня для длины массива около 10k и меньше.

спасибо ассилии за обеспечение результаты:

/**
 * Benchmark                     Mode  Cnt  Score   Error  Units
 * SO35018999.shuffled           avgt   10  8.895 ± 1.534  ms/op
 * SO35018999.sorted             avgt   10  8.093 ± 3.093  ms/op
 * SO35018999.sorted_contiguous  avgt   10  1.665 ± 0.397  ms/op
 * SO35018999.unsorted           avgt   10  2.700 ± 0.302  ms/op
 */
3 78
javascript performance arraylist

3 ответа:

похоже на эффект кэширования / предварительной выборки.

ключ в том, что вы сравниваете двойники (объекты), а не двойники (примитивы). При выделении объектов в одном потоке они обычно выделяются последовательно в памяти. Так что когда indexOf просматривает список, он проходит через последовательные адреса памяти. Это хорошо для эвристики предварительной выборки кэша процессора.

но после сортировки списка, вы все равно должны сделать то же самое количество поисков памяти в среднем, но на этот раз доступ к памяти будет осуществляться в случайном порядке.

обновление

вот ссылка чтобы доказать, что порядок выделенных объектов вопросах.

Benchmark            (generator)  (length)  (postprocess)  Mode  Cnt  Score   Error  Units
ListIndexOf.indexOf       random   1000000           none  avgt   10  1,243 ± 0,031  ms/op
ListIndexOf.indexOf       random   1000000           sort  avgt   10  6,496 ± 0,456  ms/op
ListIndexOf.indexOf       random   1000000        shuffle  avgt   10  6,485 ± 0,412  ms/op
ListIndexOf.indexOf   sequential   1000000           none  avgt   10  1,249 ± 0,053  ms/op
ListIndexOf.indexOf   sequential   1000000           sort  avgt   10  1,247 ± 0,037  ms/op
ListIndexOf.indexOf   sequential   1000000        shuffle  avgt   10  6,579 ± 0,448  ms/op
85

Я думаю, что мы видим эффект промахов кэша памяти:

при создании несортированного списка

for (int i = 0; i < LIST_LENGTH; i++) {
    list.add(r.nextDouble());
}

все двойные, скорее всего, выделяются в смежной области памяти. Повторение этого приведет к нескольким промахам кэша.

С другой стороны, в отсортированном списке ссылки хаотично указывают на память.

теперь, если вы создадите сортированный список с непрерывной памятью:

Collection.sort(list);
List<Double> list2 = new ArrayList<>();
for (int i = 0; i < LIST_LENGTH; i++) {
    list2.add(new Double(list.get(i).doubleValue()));
}

этот отсортированный список та же производительность, что и в оригинале (мое время).

25

как простой пример, который подтверждает ответ wero и ответ apangin (+1!): Ниже приводится простое сравнение обоих вариантов:

  • создания случайных чисел и сортировка их по желанию
  • создание последовательных чисел и перетасовка их по желанию

Он также не реализован в качестве эталона JMH, но похож на исходный код, с небольшими изменениями для наблюдения эффект: 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SortedListTest
{
    private static final long SLOW_ITERATION_MILLIS = 1000L * 3L;

    public static void main(String[] args)
    {
        int size = 100000;
        testBinarySearchOriginal(size, true);
        testBinarySearchOriginal(size, false);
        testBinarySearchShuffled(size, true);
        testBinarySearchShuffled(size, false);
    }

    public static void testBinarySearchOriginal(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add(r.nextDouble());
        }
        if (sort)
        {
            Collections.sort(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

    public static void testBinarySearchShuffled(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add((double) i / size);
        }
        if (!sort)
        {
            Collections.shuffle(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

}

выход на моей машине составляет

Size   100000 sort  true iterations   8560,333 count      25681
Size   100000 sort false iterations  19358,667 count      58076
Size   100000 sort  true iterations  18554,000 count      55662
Size   100000 sort false iterations   8845,333 count      26536

красиво показывает, что тайминги точно противоположны друг другу: если случайные числа отсортированы, то сортированная версия медленнее. Если последовательные номера перемешиваются, то перемешанная версия медленнее.

8