c# - ¿Por qué es más lento procesar una matriz clasificada que una matriz sin clasificar?

performance language-agnostic

Question

Tengo una lista de 500000 objetos Tuple<long,long,string> 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 por 100 valores de x generados aleatoriamente, las búsquedas se completan en aproximadamente cuatro segundos. Sin embargo, al conocer las grandes maravillas que la clasificación tiene para la búsqueda , decidí ordenar mis datos, primero por Item1 , luego por Item2 , y 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 de t.Item1 <= x predecirían la rama correctamente como "no tomar ", acelerando la parte de la cola de la búsqueda. Para mi sorpresa, ¡ las búsquedas tomaron el doble de tiempo en una matriz ordenada !

Intenté cambiar el orden en el que ejecuté mis experimentos, y usé 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ápidas 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)

Answer 1

Cuando está utilizando la lista sin clasificar, se accede a todas las tuplas en orden de memoria . Se han asignado consecutivamente en la memoria RAM. A las CPU les encanta acceder a la memoria de manera secuencial porque pueden solicitar de forma especulativa la siguiente línea de caché para que siempre esté presente cuando sea necesario.

Cuando clasifica la lista, la pone en orden aleatorio porque las claves de ordenación se generan aleatoriamente. Esto significa que los accesos de memoria a los miembros de la tupla son impredecibles. La CPU no puede recuperar la memoria y casi todos los accesos a una tupla son una falla de caché.

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

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

Intenta cambiar a una struct -tuple. Esto restaurará el rendimiento porque no es necesario que ocurra una diferencia de puntero en el 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 se realiza más rápido ". Esto se debe a que una pequeña lista encaja completamente en la memoria caché de la CPU . Los accesos a la memoria pueden ser impredecibles, pero el objetivo siempre está en el 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 malabares con múltiples cargas pendientes , lo que aumenta el rendimiento. Cada vez que la CPU espera una memoria, seguirá avanzando en el flujo de instrucciones para poner en cola tantas operaciones de memoria como sea posible. Esta técnica se utiliza 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 somos solo 2 veces más lentos cuando pasamos de acceso secuencial a acceso aleatorio a la memoria, me dice cuánto está pasando 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 de memoria aleatorios.

Answer 2

LINQ no sabe si tu 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 en la colección con acceso aleatorio eficiente. Entonces, simplemente verifica cada elemento y Usr explicó por qué el rendimiento bajó.

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.