Warum verarbeitet ein sortiertes Array * langsamer * als ein unsortiertes Array? (Javas ArrayList.indexOf)

Der Titel bezieht sich auf Warum ist es schneller, ein sortiertes Array zu verarbeiten als ein unsortiertes Array?

Ist dies auch ein Verzweigungsvorhersageeffekt? Achtung: Hier ist die Verarbeitung für das sortierte Array langsamer !!

Betrachten Sie den folgenden Code:

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

    ...
}

Dies druckt einen Wert von ungefähr 720 auf meinem Computer aus.

Wenn ich jetzt den Sortieraufruf für Sammlungen aktiviere, sinkt dieser Wert auf 142. Warum?!?

Die Ergebnisse sind schlüssig, sie ändern sich nicht, wenn ich die Anzahl der Iterationen / Zeit erhöhe.

Die Java-Version ist 1.8.0_71 (Oracle VM, 64 Bit) und läuft unter Windows 10, JUnit-Test in Eclipse Mars.

AKTUALISIEREN

Scheint mit einem zusammenhängenden Speicherzugriff verbunden zu sein (Doppelte Objekte, auf die in sequentieller Reihenfolge zugegriffen wird, vs. in zufälliger Reihenfolge). Der Effekt verschwindet für mich bei Array-Längen von ca. 10k und weniger.

Vielen Dank an assylias für die Bereitstellung der Ergebnisse :

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

Es sieht aus wie ein Caching / Prefetching-Effekt.

Der Hinweis ist, dass Sie Doubles (Objekte) vergleichen, nicht Doubles (Primitive). Wenn Sie Objekte in einem Thread zuweisen, werden sie normalerweise nacheinander im Speicher zugewiesen. Wenn also indexOfeine Liste gescannt wird, werden sequentielle Speicheradressen durchlaufen. Dies ist gut für Heuristiken zum Vorabrufen des CPU-Cache.

Nachdem Sie die Liste sortiert haben, müssen Sie im Durchschnitt immer noch die gleiche Anzahl von Speichersuchen durchführen, diesmal erfolgt der Speicherzugriff jedoch in zufälliger Reihenfolge.

AKTUALISIEREN

Hier ist der Benchmark, um zu beweisen, dass die Reihenfolge der zugewiesenen Objekte wichtig ist.

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

Ich denke, wir sehen den Effekt von Speicher-Cache-Fehlern:

Wenn Sie die unsortierte Liste erstellen

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

Alle Double werden höchstwahrscheinlich in einem zusammenhängenden Speicherbereich zugeordnet. Das Durchlaufen dieser Option führt zu wenigen Cache-Fehlern.

Andererseits verweisen die Referenzen in der sortierten Liste chaotisch auf das Gedächtnis.

Wenn Sie nun eine sortierte Liste mit zusammenhängendem Speicher erstellen:

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

Diese sortierte Liste hat die gleiche Leistung wie die ursprüngliche (mein Timing).

Als einfaches Beispiel, das die Antwort von wero und die Antwort von apangin (+1!) Bestätigt : Im Folgenden werden beide Optionen einfach verglichen:

• Zufallszahlen erstellen und optional sortieren
• Erstellen von fortlaufenden Nummern und optionales Mischen dieser Nummern

Es wird auch nicht als JMH-Benchmark implementiert, sondern ähnelt dem ursprünglichen Code mit nur geringfügigen Änderungen, um den Effekt zu beobachten:

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

}

Die Ausgabe auf meinem Computer ist

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

Dies zeigt deutlich, dass die Timings genau die Gegensätze eines anderen sind: Wenn Zufallszahlen sortiert werden, ist die sortierte Version langsamer. Wenn fortlaufende Nummern gemischt werden, ist die gemischte Version langsamer.