Perché l'elaborazione di un array ordinato * più lento * rispetto a un array non ordinato? (Java's ArrayList.indexOf)

Question

Il titolo è in riferimento a Why is it faster to process a sorted array than an unsorted array?

È anche questo un effetto di previsione ramo? Attenzione: qui l'elaborazione per l'array ordinato è più lenta !!

Si consideri il seguente codice:

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

    ... 
} 

Questo stampa un valore di circa 720 sulla mia macchina.

Ora se si attiva la chiamata di ordinamento delle raccolte, tale valore scende a 142. Perché?!?

I risultati sono conclusivi, non cambiano se aumento il numero di iterazioni/ora.

La versione Java è 1.8.0_71 (Oracle VM, 64 bit), in esecuzione in Windows 10, JUnit test in Eclipse Mars.

UPDATE

sembra essere correlato all'accesso memoria contigua (oggetti doppie accede in ordine sequenziale vs in ordine casuale). L'effetto inizia a scomparire per me per lunghezze di array di circa 10k e inferiori.

Grazie a assylias per fornire the results:

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

Sembra un effetto di caching/prefetch.

L'indizio è che si confrontano i Doppi (oggetti), non i doppi (primitivi). Quando si assegnano oggetti in un thread, in genere vengono allocati in sequenza in memoria. Pertanto, quando indexOf esegue la scansione di un elenco, passa attraverso indirizzi di memoria sequenziali. Questo è utile per l'euristica di prefetching della cache della CPU.

Ma dopo aver ordinato l'elenco, si deve ancora fare lo stesso numero di ricerche di memoria in media, ma questa volta l'accesso alla memoria sarà in ordine casuale.

UPDATE

Here is the benchmark per dimostrare che l'ordine di oggetti questioni assegnate.

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

penso che stiamo vedendo l'effetto di cache miss memoria:

Quando si crea la lista non ordinata

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

tutto il doppio sono molto probabilmente allocati in un'area di memoria contigua. L'iterazione di questa operazione produrrà alcuni errori di cache.

D'altra parte nella lista ordinata i riferimenti puntano alla memoria in modo caotico.

Ora, se si crea un elenco ordinato con la 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())); 
} 

questa lista ordinata ha le stesse prestazioni di quella originale (il mio tempo).

Answer 3

Come semplice esempio che conferma la answer by wero e il answer by apangin (+1!): La seguente fa un semplice confronto di entrambe le opzioni:

• Creazione di numeri casuali, e lo smistamento opzionalmente
• Creazione di numeri sequenziali e mischiarli opzionalmente

Inoltre non è implementato come un benchmark JMH, ma simile a il codice originale, con solo lievi modifiche di osservare l'effetto:

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

} 

L'uscita sulla mia macchina è

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 

ben dimostrando che i tempi sono esattamente gli opposti di un altro: Se i numeri casuali sono ordinati , quindi la versione ordinata è più lenta. Se i numeri sequenziali vengono mescolati, la versione mescolata è più lenta.