¿Por qué procesar una matriz ordenada * es más lento * que una matriz no ordenada? (ArrayList.indexOf de Java)

El título hace referencia a ¿Por qué es más rápido procesar una matriz ordenada que una matriz no ordenada?

¿También es este un efecto de predicción de rama? Cuidado: aquí el procesamiento de la matriz ordenada es más lento !!

Considere el siguiente código:

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

    ...
}

Esto imprime un valor de alrededor de 720 en mi máquina.

Ahora, si activo la llamada de ordenación de colecciones, ese valor desciende a 142. ¿Por qué?!?

Los resultados son concluyentes, no cambian si aumento el número de iteraciones / tiempo.

La versión de Java es 1.8.0_71 (Oracle VM, 64 bits), que se ejecuta en Windows 10, prueba JUnit en Eclipse Mars.

ACTUALIZAR

Parece estar relacionado con el acceso a la memoria contigua (objetos dobles a los que se accede en orden secuencial frente a en orden aleatorio). El efecto comienza a desaparecer para mí para longitudes de matriz de alrededor de 10k y menos.

Gracias a Assylias por brindar los resultados :

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

Parece un efecto de caché / recuperación previa.

La pista es que comparas Dobles (objetos), no dobles (primitivas). Cuando asigna objetos en un subproceso, normalmente se asignan secuencialmente en la memoria. Entonces, cuando indexOfescanea una lista, pasa por direcciones de memoria secuenciales. Esto es bueno para la heurística de captación previa de caché de CPU.

Pero después de ordenar la lista, todavía tiene que hacer la misma cantidad de búsquedas de memoria en promedio, pero esta vez el acceso a la memoria será en orden aleatorio.

ACTUALIZAR

Aquí está el punto de referencia para demostrar que el orden de los objetos asignados es importante.

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

Creo que estamos viendo el efecto de fallas en la memoria caché:

Cuando crea la lista sin clasificar

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

lo más probable es que todos los dobles estén asignados en un área de memoria contigua. Iterar esto producirá pocas pérdidas de caché.

Por otro lado, en la lista ordenada las referencias apuntan a la memoria de manera caótica.

Ahora, si crea una lista ordenada con memoria contigua:

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

esta lista ordenada tiene el mismo rendimiento que la original (mi tiempo).

Como un ejemplo simple que confirma la respuesta de wero y la respuesta de apangin (¡+1!): Lo siguiente hace una comparación simple de ambas opciones:

• Crear números aleatorios y ordenarlos opcionalmente
• Crear números secuenciales y mezclarlos opcionalmente

Tampoco está implementado como un punto de referencia de JMH, pero es similar al código original, con solo ligeras modificaciones para observar el efecto:

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

}

La salida en mi máquina es

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

mostrando muy bien que los tiempos son exactamente los opuestos de otros: si se ordenan números aleatorios, la versión ordenada es más lenta. Si se barajan números secuenciales, la versión barajada es más lenta.