c# - sintaxis - que es linq

Optimización de consultas paralelas de Linq

Question

Desde hace un tiempo, he estado estructurando mi código en torno a métodos sin efectos secundarios con el fin de utilizar linq paralelo para acelerar las cosas. A lo largo del camino, en más de una ocasión he tropezado con una evaluación lenta que empeora las cosas en lugar de hacerlo mejor y me gustaría saber si hay alguna herramienta que ayude a optimizar las consultas de linq paralelos.

Lo pregunto porque recientemente refactoreé un código vergonzosamente paralelo al modificar algunos métodos y AsParallel en ciertos lugares clave. El tiempo de ejecución disminuyó de 2 minutos a 45 segundos, pero el monitor de rendimiento dejó en claro que había algunos lugares en los que no se estaban utilizando todos los núcleos de la CPU. Después de algunos inicios en falso ToArray algunas de las consultas a ejecutar usando ToArray y el tiempo de ejecución bajó aún más a 16 segundos. Se sintió bien reducir el tiempo de ejecución del código, pero también fue algo desconcertante porque no estaba claro en qué parte de las consultas de código debía forzarse con ToArray . Esperar hasta el último minuto para que se ejecutara la consulta no era la estrategia óptima, pero no estaba claro en absoluto en qué puntos del código debían forzarse algunas de las subconsultas para utilizar todos los núcleos de la CPU.

Tal como están las cosas, no tengo idea de cómo ToArray correctamente ToArray u otros métodos que obliguen a los cálculos de linq a ejecutarse para obtener la máxima utilización de la CPU. Entonces, ¿hay alguna guía general y herramientas para optimizar las consultas de linq paralelos?

Aquí hay una muestra de pseudo-código:

var firstQuery = someDictionary.SelectMany(FirstTransformation);
var secondQuery = firstQuery.Select(SecondTransformation);
var thirdQuery = secondQuery.Select(ThirdTransformation).Where(SomeConditionCheck);
var finalQuery = thirdQuery.Select(FinalTransformation).Where(x => x != null);

FirstTransformation , SecondTransformation , ThirdTransformation están vinculados a la CPU y, en términos de complejidad, son algunas multiplicaciones de matrices 3x3 y algunas ramas if . SomeConditionCheck es casi una verificación null . FinalTransformation es la parte más intensiva de CPU del código porque realizará un conjunto completo de intersecciones de línea-avión y controlará la contención de polígonos para esas intersecciones y luego extraerá la intersección más cercana a un cierto punto en la línea.

No tengo idea de por qué los lugares donde pongo AsParallel redujeron el tiempo de ejecución del código tanto como lo hizo. Ahora llegué a un mínimo local en términos de tiempo de ejecución, pero no tengo idea de por qué. Fue solo suerte que tropecé con eso. En caso de que se esté preguntando AsParallel colocar AsParallel son las primeras y las últimas líneas. Poner AsParallel cualquier otro lugar solo aumentará el tiempo de ejecución, a veces hasta 20 segundos. También hay un ToArray oculto escondido allí en la primera línea.

Answer 1

Hay un par de cosas pasando aquí:

1. PLINQ paraleliza colecciones más eficientemente que IEnumerables no contados. Si tiene una matriz, divide la longitud de la matriz por su número de núcleos de CPU y las asigna de manera uniforme. Pero si tiene un IEnumerable con una longitud desconocida, hace una especie de aumento exponencial ridículo, donde las tareas procesarán 1, 2, 4, 8, etc. elementos a la vez hasta que llegue al final de IEnumerable.
2. Al poner en paralelo todas sus consultas, está dividiendo el trabajo en pequeños trozos. Si tiene M consultas paralelas en N elementos, termina con M * N tareas. Hay más sobrecarga de hilos en esto que si simplemente paraleliza la última consulta, en cuyo caso terminaría con solo N tareas.
3. PLINQ funciona mejor cuando cada tarea toma aproximadamente la misma cantidad de tiempo para procesar. De esta forma, puede dividirlos de manera uniforme entre los núcleos. Al poner en paralelo cada una de sus consultas que tienen un comportamiento de rendimiento diferente, tiene tareas M * N que requieren distintas cantidades de tiempo, y PLINQ no puede programarlas de manera óptima (porque no sabe de antemano cuánto tiempo puede tomar cada una) )

Entonces, la guía general aquí es: asegúrese de que antes de comenzar tenga una matriz, si es posible, y solo coloque AsParallel en la última consulta antes de la evaluación. Entonces algo como lo siguiente debería funcionar bastante bien:

var firstQuery = someDictionary.SelectMany().ToArray().Select(FirstTransformation);
var secondQuery = firstQuery.Select(SecondTransformation);
var thirdQuery = secondQuery.Select(ThirdTransformation).AsParallel().Where(SomeConditionCheck).ToArray();
var finalQuery = thirdQuery.Select(FinalTransformation).AsParallel().Where(x => x != null);

Answer 2

Es casi imposible decir sin ver el código real. Pero como una guía general, debe considerar evitar P / LINQ durante el crujido de números complejos porque la sobrecarga delegado e IEnumerable es demasiado alta. Es muy probable que la velocidad que ganes usando hilos sea consumida por las prácticas abstracciones que proporciona LINQ.

Aquí hay un código que sí calcula la suma de 2 listas enteras que hace una comparación int a float y luego calcula el cos de la misma. Bastante básico que se puede hacer muy bien con LINQ, el operador .Zip ... o la forma antigua con un bucle for.

Actualización 1 con ParallelLinq actualizado en mi máquina central Haswell 8

• Linq 0,95s
• Linq Paralelo 0,19s
• Optimizado 0,45s
• Optimizado Paralelo 0,08s

Actualización 1 Fin

• LINQ 1,65s
• Optimizado 0,64s
• Optimizado Paralelo 0,40s

La diferencia de tiempo es casi un factor 3 debido a la pereza de IEnumerable y la sobrecarga de llamadas al método (utilicé el modo Release x32 Windows 7, .NET 4 dual core). Intenté utilizar AsParallel en la versión LINQ, pero realmente se volvió más lento (2,3 s). Si está basado en datos, debe usar el Paralelo.Para construir para obtener una buena escalabilidad. IEnumerable en sí mismo es un mal candidato para la paralelización desde

• No sabe cuántos trabajos tiene antes de enumerar hasta el final.
• No puede hacer fragmentados ansiosos porque no sabe qué tan rápido IEnumerable devolverá el siguiente elemento (podría ser una llamada de servicio web o un acceso de índice de matriz).

A continuación hay una muestra del código para ilustrar el punto. Si desea optimizar más hacia el metal desnudo, primero debe deshacerse de las abstracciones que cuestan demasiado por artículo. Un acceso de matriz es mucho más barato en comparación con MoveNext no en línea () y las llamadas al método actual.

    class Program
    {
        static void Main(string[] args)
        {
            var A = new List<int>(Enumerable.Range(0, 10*1000*1000));
            var B = new List<int>(Enumerable.Range(0, 10*1000*1000));

            double[] Actual = UseLinq(A, B);
            double[] pActual = UseLinqParallel(A, B);

            var other = Optimized(A, B);
            var pother = OptimizedParallel(A, B);
        }

        private static double[] UseLinq(List<int> A, List<int> B)
        {
            var sw = Stopwatch.StartNew();
            var Merged = A.Zip(B, (a, b) => a + b);
            var Converted = A.Select(a => (float)a);

            var Result = Merged.Zip(Converted, (m, c) => Math.Cos((double)m / ((double)c + 1)));

            double[] Actual = Result.ToArray();
            sw.Stop();

            Console.WriteLine("Linq {0:F2}s", sw.Elapsed.TotalSeconds);
            return Actual;
        }

    private static double[] UseLinqParallel(List<int> A, List<int> B)
    {
        var sw = Stopwatch.StartNew();
        var x = A.AsParallel();
        var y = B.AsParallel();

        var Merged = x.Zip(y, (a, b) => a + b);
        var Converted = x.Select(a => (float)a);

        var Result = Merged.Zip(Converted, (m, c) => Math.Cos((double)m / ((double)c + 1)));

        double[] Actual = Result.ToArray();
        sw.Stop();

        Console.WriteLine("Linq Parallel {0:F2}s", sw.Elapsed.TotalSeconds);
        return Actual;
    }        

        private static double[] OptimizedParallel(List<int> A, List<int> B)
        {
            double[] result = new double[A.Count];
            var sw = Stopwatch.StartNew();
            Parallel.For(0, A.Count, (i) =>
            {
                var sum = A[i] + B[i];
                result[i] = Math.Cos((double)sum / ((double)((float)A[i]) + 1));
            });
            sw.Stop();

            Console.WriteLine("Optimized Parallel {0:F2}s", sw.Elapsed.TotalSeconds);
            return result;
        }

        private static double[] Optimized(List<int> A, List<int> B)
        {
            double[] result = new double[A.Count];
            var sw = Stopwatch.StartNew();
            for(int i=0;i<A.Count;i++)
            {
                var sum = A[i] + B[i];
                result[i] = Math.Cos((double)sum / ((double)((float)A[i]) + 1));
            }
            sw.Stop();

            Console.WriteLine("Optimized {0:F2}s", sw.Elapsed.TotalSeconds);
            return result;
        }
    }
}