¿Por qué el procesamiento de una matriz ordenada es más lento que una matriz no ordenada?

Tengo una lista de 500000 Tuple<long,long,string>objetos generados aleatoriamente en los que estoy realizando una simple búsqueda "entre":

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

Cuando genero mi matriz aleatoria y ejecuto mi búsqueda de 100 valores generados aleatoriamente x, las búsquedas se completan en aproximadamente cuatro segundos. Sin embargo, al conocer las grandes maravillas que la clasificación hace a la búsqueda , decidí ordenar mis datos, primero por Item1, luego por Item2y finalmente por Item3, antes de ejecutar mis 100 búsquedas. Esperaba que la versión ordenada funcionara un poco más rápido debido a la predicción de la rama: mi pensamiento ha sido que una vez que lleguemos al punto donde Item1 == x, todas las comprobaciones adicionales t.Item1 <= xpredecirían la rama correctamente como "no tomar", acelerando la porción de la cola de la cola. buscar. Para mi sorpresa, ¡ las búsquedas tomaron el doble de tiempo en una matriz ordenada !

Intenté cambiar el orden en el que realicé mis experimentos y utilicé diferentes semillas para el generador de números aleatorios, pero el efecto ha sido el mismo: las búsquedas en una matriz sin clasificar se ejecutaron casi el doble de rápido que las búsquedas en la misma matriz, pero ordenado!

¿Alguien tiene una buena explicación de este extraño efecto? El código fuente de mis pruebas sigue; Estoy 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)

Cuando utiliza la lista sin clasificar, se accede a todas las tuplas en orden de memoria . Han sido asignados consecutivamente en RAM. A las CPU les encanta acceder a la memoria secuencialmente porque pueden solicitar especulativamente la siguiente línea de caché para que siempre esté presente cuando sea necesario.

Cuando ordena la lista, la coloca en orden aleatorio porque sus claves de clasificación se generan aleatoriamente. Esto significa que los accesos de memoria a los miembros de la tupla son impredecibles. La CPU no puede recuperar previamente la memoria y casi todos los accesos a una tupla son una falta de caché.

Este es un buen ejemplo de una ventaja específica de la gestión de memoria del GC : las estructuras de datos que se han asignado juntas y se usan juntas funcionan muy bien. Tienen gran localidad de referencia .

La penalización por errores de caché supera la penalización de predicción de rama guardada en este caso.

Intente cambiar a una structtupla. Esto restaurará el rendimiento porque no es necesario que se produzca una desreferencia de puntero en tiempo de ejecución para acceder a los miembros de la tupla.

Chris Sinclair señala en los comentarios que "para TotalCount alrededor de 10,000 o menos, la versión ordenada funciona más rápido ". Esto se debe a que una pequeña lista se ajusta completamente al caché de la CPU . Los accesos a la memoria pueden ser impredecibles, pero el destino siempre está en caché. Creo que todavía hay una pequeña penalización porque incluso una carga de caché toma algunos ciclos. Pero eso no parece ser un problema porque la CPU puede hacer malabarismos con múltiples cargas pendientes , lo que aumenta el rendimiento. Siempre que la CPU llegue a esperar memoria, seguirá avanzando rápidamente en la secuencia de instrucciones para poner en cola tantas operaciones de memoria como sea posible. Esta técnica se usa para ocultar la latencia.

Este tipo de comportamiento muestra lo difícil que es predecir el rendimiento en las CPU modernas. El hecho de que solo somos 2 veces más lentos cuando pasamos de acceso secuencial a acceso aleatorio a la memoria me dice cuánto sucede debajo de las cubiertas para ocultar la latencia de la memoria. Un acceso a la memoria puede detener la CPU durante 50-200 ciclos. Dado que el número uno podría esperar que el programa sea> 10 veces más lento al introducir accesos aleatorios a la memoria.

LINQ no sabe si su lista está ordenada o no.

Dado que el parámetro Contar con predicado es un método de extensión para todos los IEnumerables, creo que ni siquiera sabe si se está ejecutando sobre la colección con acceso aleatorio eficiente. Entonces, simplemente verifica cada elemento y Usr explica por qué el rendimiento se redujo.

Para aprovechar los beneficios de rendimiento de la matriz ordenada (como la búsqueda binaria), tendrá que hacer un poco más de codificación.