Perché l'elaborazione di una matrice ordinata è più lenta di una matrice non ordinata?

Question

Ho una lista di 500000 generate casualmente Tuple<long,long,string> oggetti su cui sto effettuando un semplice "tra" ricerca:

var data = new List<Tuple<long,long,string>>(500000); 
... 
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x); 

Quando ho generare il mio allineamento casuale e corro la mia ricerca di 100 valori generati casualmente di x, il ricerche completate in circa quattro secondi. Conoscendo il numero great wonders that sorting does to searching, tuttavia, ho deciso di ordinare i miei dati - prima con Item1, poi con Item2 e infine con Item3 - prima di eseguire le mie 100 ricerche. Mi aspettavo che la versione ordinata si svolgesse un po 'più velocemente a causa della previsione del ramo: ho pensato che una volta arrivati ​​al punto in cui Item1 == x, tutti gli ulteriori controlli di t.Item1 <= x avrebbero previsto correttamente il ramo come "non prendere", accelerando la porzione di coda della ricerca. Con mia grande sorpresa, le ricerche sono durate il doppio su un array ordinato!

Ho provato a cambiare l'ordine in cui eseguivo i miei esperimenti e ho utilizzato seme diverso per il generatore di numeri casuali, ma l'effetto è stato lo stesso: le ricerche in un array non ordinato sono quasi il doppio delle ricerche nel stesso array, ma ordinato!

Qualcuno ha una buona spiegazione di questo strano effetto? Segue il codice sorgente dei miei test; Sto usando .NET 4.0.

---

private const int TotalCount = 500000; 
private const int TotalQueries = 100; 
private static long NextLong(Random r) { 
    var data = new byte[8]; 
    r.NextBytes(data); 
    return BitConverter.ToInt64(data, 0); 
} 
private class TupleComparer : IComparer<Tuple<long,long,string>> { 
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) { 
     var res = x.Item1.CompareTo(y.Item1); 
     if (res != 0) return res; 
     res = x.Item2.CompareTo(y.Item2); 
     return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3); 
    } 
} 
static void Test(bool doSort) { 
    var data = new List<Tuple<long,long,string>>(TotalCount); 
    var random = new Random(1000000007); 
    var sw = new Stopwatch(); 
    sw.Start(); 
    for (var i = 0 ; i != TotalCount ; i++) { 
     var a = NextLong(random); 
     var b = NextLong(random); 
     if (a > b) { 
      var tmp = a; 
      a = b; 
      b = tmp; 
     } 
     var s = string.Format("{0}-{1}", a, b); 
     data.Add(Tuple.Create(a, b, s)); 
    } 
    sw.Stop(); 
    if (doSort) { 
     data.Sort(new TupleComparer()); 
    } 
    Console.WriteLine("Populated in {0}", sw.Elapsed); 
    sw.Reset(); 
    var total = 0L; 
    sw.Start(); 
    for (var i = 0 ; i != TotalQueries ; i++) { 
     var x = NextLong(random); 
     var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x); 
     total += cnt; 
    } 
    sw.Stop(); 
    Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted"); 
} 
static void Main() { 
    Test(false); 
    Test(true); 
    Test(false); 
    Test(true); 
} 

---

Populated in 00:00:01.3176257 
Found 15614281 matches in 00:00:04.2463478 (Unsorted) 
Populated in 00:00:01.3345087 
Found 15614281 matches in 00:00:08.5393730 (Sorted) 
Populated in 00:00:01.3665681 
Found 15614281 matches in 00:00:04.1796578 (Unsorted) 
Populated in 00:00:01.3326378 
Found 15614281 matches in 00:00:08.6027886 (Sorted) 

Answer 1

Quando si utilizza la lista non ordinata tutte le tuple sono accessibili in memoria ordine. Sono stati assegnati consecutivamente nella RAM. Le CPU amano accedere alla memoria in modo sequenziale perché possono richiedere in modo speculativo la riga della cache successiva in modo che sia sempre presente quando necessario.

Quando si ordina l'elenco, lo si inserisce in in ordine casuale perché le chiavi di ordinamento vengono generate casualmente. Ciò significa che la memoria che accede ai membri della tupla è imprevedibile. La CPU non può precaricare la memoria e quasi ogni accesso a una tupla è un errore di cache.

Questo è un bell'esempio per uno specifico vantaggio della gestione della memoria GC : le strutture di dati che sono state allocate insieme e sono utilizzate insieme funzionano molto bene. Hanno un'ottima località di riferimento.

La penalità dalla cache mancante a supera la penalità di previsione di diramazione salvata in questo caso.

Provare a passare a un struct -tuplo. Ciò ripristinerà le prestazioni perché non è necessario che si verifichi il puntatore-dereferenziazione in runtime per accedere ai membri della tupla.

Note di Chris Sinclair nei commenti che "per TotalCount circa 10.000 o meno, la versione ordinata esegue più veloce". Questo perché un piccolo elenco si inserisce interamente nella cache della CPU. Gli accessi alla memoria potrebbero essere imprevedibili ma la destinazione è sempre nella cache. Credo che ci sia ancora una piccola penalità perché anche un carico dalla cache richiede alcuni cicli.Ma questo non sembra essere un problema perché la CPU può destreggiarsi tra più carichi in sospeso, aumentando così il throughput. Ogni volta che la CPU raggiunge un'attesa per la memoria, continuerà comunque ad avanzare nel flusso di istruzioni per accodare quante più operazioni di memoria possibile. Questa tecnica è usata per nascondere la latenza.

Questo tipo di comportamento mostra quanto sia difficile prevedere le prestazioni delle moderne CPU. Il fatto che siamo solo 2x più lenti passando da accesso sequenziale a memoria casuale dimmi quanto sta succedendo sotto le copertine per nascondere la latenza della memoria. Un accesso alla memoria può arrestare la CPU per 50-200 cicli. Dato che il numero uno potrebbe aspettarsi che il programma diventi> 10 volte più lento quando introduce accessi casuali alla memoria.

Answer 2

LINQ non sa se l'elenco è ordinato o meno.

Poiché Count con parametro predicato è il metodo di estensione per tutti gli oggetti IEnumerables, penso che non sappia nemmeno se sta eseguendo la raccolta con un accesso casuale efficiente. Quindi, controlla semplicemente ogni elemento e Usr ha spiegato perché le prestazioni sono diminuite.

Per sfruttare i vantaggi prestazionali dell'array ordinato (come la ricerca binaria), è necessario eseguire un po 'più di codifica.