Dlaczego przetwarzanie posortowanej tablicy * wolniej * niż nieposortowanej tablicy? (Java's ArrayList.indexOf)

Tytuł odnosi się do Dlaczego szybciej przetwarzać posortowaną tablicę niż nieposortowaną?

Czy to też jest efekt przewidywania gałęzi? Uwaga: tutaj przetwarzanie posortowanej tablicy jest wolniejsze !!

Rozważ następujący kod:

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);

    ...
}

Spowoduje to wyświetlenie wartości około 720 na moim komputerze.

Jeśli teraz aktywuję wywołanie sortowania kolekcji, ta wartość spadnie do 142. Dlaczego?!?

Wyniki są rozstrzygające, nie zmieniają się, jeśli zwiększę liczbę iteracji / czas.

Wersja Java to 1.8.0_71 (Oracle VM, 64 bit), działająca pod Windows 10, test JUnit w Eclipse Mars.

AKTUALIZACJA

Wydaje się, że jest związany z ciągłym dostępem do pamięci (podwójne obiekty dostępne w kolejności sekwencyjnej vs w kolejności losowej). Efekt zaczyna znikać dla mnie dla tablic o długości około 10k i mniej.

Dzięki asyliom za dostarczenie wyników :

/**
 * 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
 */

Wygląda na efekt buforowania / pobierania wstępnego.

Wskazówka jest taka, że ​​porównujesz dublety (obiekty), a nie dublety (prymitywy). Podczas przydzielania obiektów w jednym wątku są one zwykle przydzielane sekwencyjnie w pamięci. Więc kiedy indexOfskanuje listę, przechodzi przez kolejne adresy pamięci. Jest to dobre dla heurystyki wstępnego pobierania pamięci podręcznej procesora.

Ale po posortowaniu listy nadal musisz wykonać średnio tę samą liczbę wyszukiwań pamięci, ale tym razem dostęp do pamięci będzie w kolejności losowej.

AKTUALIZACJA

Oto punkt odniesienia do udowodnienia, że ​​kolejność przydzielonych obiektów ma znaczenie.

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

Myślę, że widzimy efekt chybień w pamięci podręcznej:

Podczas tworzenia nieposortowanej listy

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

wszystkie podwójne są najprawdopodobniej alokowane w ciągłym obszarze pamięci. Iterowanie przez to spowoduje kilka błędów pamięci podręcznej.

Z drugiej strony na posortowanej liście odniesienia wskazują na pamięć w sposób chaotyczny.

Teraz, jeśli utworzysz posortowaną listę z ciągłą pamięcią:

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

ta posortowana lista ma taką samą wydajność jak oryginalna (mój czas).

Jako prosty przykład, który potwierdza odpowiedź przez wero i odpowiedź przez apangin (+1!): Poniżej przedstawiono proste porównanie obu opcji:

• Tworzenie liczb losowych i sortowanie ich opcjonalnie
• Tworzenie kolejnych liczb i opcjonalne ich tasowanie

Nie jest również zaimplementowany jako benchmark JMH, ale podobny do oryginalnego kodu, z niewielkimi modyfikacjami, aby zaobserwować efekt:

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);
    }

}

Wynik na moim komputerze to

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

ładnie pokazując, że czasy są dokładnie przeciwieństwami innych: jeśli posortowane są liczby losowe, posortowana wersja jest wolniejsza. Jeśli kolejne numery są tasowane, wersja losowa jest wolniejsza.