Pourquoi traite un tableau trié * lente * qu’un tableau non trié ? (Java ' s ArrayList.indexOf)

Question

Le titre est en référence à Pourquoi le traitement d'un tableau trié de plus qu'un tableau non trié?

Est-ce une branche de prédiction de l'effet, trop? Attention: ici, le traitement pour le tableau trié est plus lent!!

Considérons le code suivant:

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

    ...
}

Ceci affiche une valeur de près de 720 sur ma machine.

Maintenant, si je activer les collections de tri appel, cette valeur descend à 142. Pourquoi?!?

Les résultats sont concluants, ils ne changent pas si j'augmente le nombre d'itérations/heure.

Version de Java est 1.8.0_71 (Oracle VM, 64 bits), fonctionnant sous Windows 10, de test JUnit dans Eclipse Mars.

Mise à JOUR

Semble être lié à la mémoire contiguë d'accès (Double les objets accessibles dans l'ordre séquentiel vs dans un ordre aléatoire). L'effet commence à disparaître pour moi pour le tableau des longueurs d'environ 10k et moins.

Grâce à assylias pour fournir les résultats:

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

Answer 1

Il ressemble à la mise en cache / pré-chargement effet.

L'idée est que vous comparez les Doubles (les objets), pas de doubles (primitives). Lorsque vous allouer des objets dans un thread, ils sont généralement attribuées de façon séquentielle dans la mémoire. Ainsi, lorsque indexOf scanne une liste, il passe par séquentielle des adresses de mémoire. C'est bon pour le CPU cache le pré-chargement de l'heuristique.

Mais après de trier la liste, il vous reste à faire le même nombre de mémoire de recherches dans la moyenne, mais cette fois, l'accès à la mémoire sera dans un ordre aléatoire.

Mise à JOUR

Ici est le point de référence pour prouver que l'ordre des objets alloués questions.

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

Answer 2

Je crois que nous assistons à l'effet de mémoire cache:

Lorsque vous créez la liste non triée

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

tous les doubles sont plus susceptibles affectés dans une zone mémoire contiguë. Une itération à travers cette volonté de produire quelques défauts de cache.

D'autre part, dans la liste triée, le point de références de la mémoire d'une manière chaotique.

Maintenant, si vous créez une liste triée avec mémoire contiguë:

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

cette liste a les mêmes performances que la version originale (à mon rythme).

Answer 3

Un simple exemple qui confirme la réponse par wero et la réponse par apangin (+1!): La suite n'est qu'une simple comparaison des deux options:

• La création de nombres aléatoires, et le tri en option
• La création de numéros séquentiels, et les mélanger éventuellement

Il n'est pas mis en œuvre comme un JMH indice de référence, mais semblable à l'original du code, avec seulement de légères modifications pour observer l'effet:

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 sortie sur ma machine est

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

joliment montrant que les timings sont exactement opposés de l'autre: Si les nombres aléatoires sont triés, puis triées version est plus lente. Si des numéros d'ordre sont mélangées, puis le mélangées version est plus lente.