c# - net - ¿Por qué Parallel.ForEach es mucho más rápido que AsParallel(). ForAll() aunque MSDN sugiere lo contrario?

parallel vb net

Question

He estado investigando un poco para ver cómo podemos crear una aplicación multiproceso que se ejecute a través de un árbol.

Para encontrar cómo se puede implementar esto de la mejor manera, he creado una aplicación de prueba que se ejecuta en mi disco C: / y abre todos los directorios.

class Program
{
    static void Main(string[] args)
    {
        //var startDirectory = @"C:/The folder/RecursiveFolder";
        var startDirectory = @"C:/";

        var w = Stopwatch.StartNew();

        ThisIsARecursiveFunction(startDirectory);

        Console.WriteLine("Elapsed seconds: " + w.Elapsed.TotalSeconds);

        Console.ReadKey();
    }

    public static void ThisIsARecursiveFunction(String currentDirectory)
    {
        var lastBit = Path.GetFileName(currentDirectory);
        var depth = currentDirectory.Count(t => t == ''//');
        //Console.WriteLine(depth + ": " + currentDirectory);

        try
        {
            var children = Directory.GetDirectories(currentDirectory);

            //Edit this mode to switch what way of parallelization it should use
            int mode = 3;

            switch (mode)
            {
                case 1:
                    foreach (var child in children)
                    {
                        ThisIsARecursiveFunction(child);
                    }
                    break;
                case 2:
                    children.AsParallel().ForAll(t =>
                    {
                        ThisIsARecursiveFunction(t);
                    });
                    break;
                case 3:
                    Parallel.ForEach(children, t =>
                    {
                        ThisIsARecursiveFunction(t);
                    });
                    break;
                default:
                    break;
            }

        }
        catch (Exception eee)
        {
            //Exception might occur for directories that can''t be accessed.
        }
    }
}

Sin embargo, lo que he encontrado es que cuando ejecuto esto en modo 3 (Paralelo.ParaEach) el código se completa en alrededor de 2.5 segundos (sí, tengo un SSD;)). Ejecutando el código sin paralelización, se completa en unos 8 segundos. Y ejecutar el código en modo 2 (AsParalle.ForAll ()) lleva una cantidad de tiempo casi infinita.

Al registrarme en el explorador de procesos también encuentro algunos hechos extraños:

Mode1 (No Parallelization):
Cpu:     ~25%
Threads: 3
Time to complete: ~8 seconds

Mode2 (AsParallel().ForAll()):
Cpu:     ~0%
Threads: Increasing by one per second (I find this strange since it seems to be waiting on the other threads to complete or a second timeout.)
Time to complete: 1 second per node so about 3 days???

Mode3 (Parallel.ForEach()):
Cpu:     100%
Threads: At most 29-30
Time to complete: ~2.5 seconds

Lo que me parece especialmente extraño es que Parallel.ForEach parece ignorar cualquier subproceso / tarea principal que todavía se esté ejecutando mientras AsParallel (). ForAll () parece esperar a que se complete la Tarea anterior (que no lo hará pronto ya que todas las Tareas principales todavía están esperando que se completen sus tareas secundarias).

También lo que leí en MSDN fue: "Prefiero para todos para cada uno cuando sea posible"

Fuente: http://msdn.microsoft.com/en-us/library/dd997403(v=vs.110).aspx

¿Alguien tiene idea de por qué esto podría ser?

Editar 1:

Según lo solicitado por Matthew Watson, primero cargué el árbol en la memoria antes de recorrerlo. Ahora la carga del árbol se realiza de forma secuencial.

Sin embargo, los resultados son los mismos. Sin paralelo y Paralelo. Para cada uno ahora completa todo el árbol en aproximadamente 0.05 segundos mientras AsParallel (). Para todo aún solo va alrededor de 1 paso por segundo.

Código:

class Program
{
    private static DirWithSubDirs RootDir;

    static void Main(string[] args)
    {
        //var startDirectory = @"C:/The folder/RecursiveFolder";
        var startDirectory = @"C:/";

        Console.WriteLine("Loading file system into memory...");
        RootDir = new DirWithSubDirs(startDirectory);
        Console.WriteLine("Done");


        var w = Stopwatch.StartNew();

        ThisIsARecursiveFunctionInMemory(RootDir);

        Console.WriteLine("Elapsed seconds: " + w.Elapsed.TotalSeconds);

        Console.ReadKey();
    }        

    public static void ThisIsARecursiveFunctionInMemory(DirWithSubDirs currentDirectory)
    {
        var depth = currentDirectory.Path.Count(t => t == ''//');
        Console.WriteLine(depth + ": " + currentDirectory.Path);

        var children = currentDirectory.SubDirs;

        //Edit this mode to switch what way of parallelization it should use
        int mode = 2;

        switch (mode)
        {
            case 1:
                foreach (var child in children)
                {
                    ThisIsARecursiveFunctionInMemory(child);
                }
                break;
            case 2:
                children.AsParallel().ForAll(t =>
                {
                    ThisIsARecursiveFunctionInMemory(t);
                });
                break;
            case 3:
                Parallel.ForEach(children, t =>
                {
                    ThisIsARecursiveFunctionInMemory(t);
                });
                break;
            default:
                break;
        }
    }
}

class DirWithSubDirs
{
    public List<DirWithSubDirs> SubDirs = new List<DirWithSubDirs>();
    public String Path { get; private set; }

    public DirWithSubDirs(String path)
    {
        this.Path = path;
        try
        {
            SubDirs = Directory.GetDirectories(path).Select(t => new DirWithSubDirs(t)).ToList();
        }
        catch (Exception eee)
        {
            //Ignore directories that can''t be accessed
        }
    }
}

Edición 2:

Después de leer la actualización del comentario de Matthew, he intentado agregar el siguiente código al programa:

ThreadPool.SetMinThreads(4000, 16);
ThreadPool.SetMaxThreads(4000, 16);

Sin embargo, esto no cambia la forma en que se desempeña AsParallel. Aún así, los primeros 8 pasos se ejecutan en un instante antes de reducir la velocidad a 1 paso / segundo.

(Nota adicional, actualmente estoy ignorando las excepciones que ocurren cuando no puedo acceder a un Directorio por el bloque Try Catch alrededor del Directorio. GetDirectories ())

Edición 3:

También lo que más me interesa es la diferencia entre Parallel.ForEach y AsParallel.ForAll porque para mí es simplemente extraño que, por alguna razón, el segundo cree un subproceso por cada recursión que hace, mientras que el primero maneja todo en alrededor de 30 subprocesos max. (Y también por qué MSDN sugiere usar AsParallel a pesar de que crea tantos subprocesos con un tiempo de espera de ~ 1 segundo)

Edición 4:

Otra cosa extraña que descubrí: cuando trato de configurar MinThreads en el grupo de subprocesos por encima de 1023, parece ignorar el valor y volver a escalar a alrededor de 8 o 16: ThreadPool.SetMinThreads (1023, 16);

Aún así, cuando uso el 1023, hace los primeros 1023 elementos muy rápido, seguido por volver al ritmo lento que he estado experimentando todo el tiempo.

Nota: También se crean literalmente más de 1000 subprocesos (en comparación con 30 para todo el paralelo. Para cada uno).

¿Esto significa que Parallel.ForEach es mucho más inteligente en el manejo de tareas?

Más información, este código se imprime dos veces 8 - 8 cuando establece el valor por encima de 1023: (Cuando establece los valores en 1023 o menos, imprime el valor correcto)

        int threadsMin;
        int completionMin;
        ThreadPool.GetMinThreads(out threadsMin, out completionMin);
        Console.WriteLine("Cur min threads: " + threadsMin + " and the other thing: " + completionMin);

        ThreadPool.SetMinThreads(1023, 16);
        ThreadPool.SetMaxThreads(1023, 16);

        ThreadPool.GetMinThreads(out threadsMin, out completionMin);
        Console.WriteLine("Now min threads: " + threadsMin + " and the other thing: " + completionMin);

Editar 5:

A petición de Dean, he creado otro caso para crear tareas manualmente:

case 4:
    var taskList = new List<Task>();
    foreach (var todo in children)
    {
        var itemTodo = todo;
        taskList.Add(Task.Run(() => ThisIsARecursiveFunctionInMemory(itemTodo)));
    }
    Task.WaitAll(taskList.ToArray());
    break;

Esto también es tan rápido como el ciclo Parallel.ForEach (). Entonces todavía no tenemos la respuesta de por qué AsParallel (). ForAll () es mucho más lento.

Answer 1

Basado en la respuesta aceptada a ¿Cómo funciona exactamente AsParallel?

.AsParallel.ForAll() vuelve a IEnumerable antes de llamar a .ForAll()

entonces crea 1 nuevo hilo + N llamadas recursivas (cada una de las cuales genera un nuevo hilo).

Answer 2

Este problema es bastante depurable, un lujo poco común cuando tienes problemas con hilos. Su herramienta básica aquí es la ventana Debug> Windows> Threads depurador. Le muestra los hilos activos y le da un vistazo a su seguimiento de pila. Verá fácilmente que, una vez que se vuelve lento, tendrá docenas de hilos activos que están atascados. Su rastro de pila se ve igual:

    mscorlib.dll!System.Threading.Monitor.Wait(object obj, int millisecondsTimeout, bool exitContext) + 0x16 bytes  
    mscorlib.dll!System.Threading.Monitor.Wait(object obj, int millisecondsTimeout) + 0x7 bytes 
    mscorlib.dll!System.Threading.ManualResetEventSlim.Wait(int millisecondsTimeout, System.Threading.CancellationToken cancellationToken) + 0x182 bytes    
    mscorlib.dll!System.Threading.Tasks.Task.SpinThenBlockingWait(int millisecondsTimeout, System.Threading.CancellationToken cancellationToken) + 0x93 bytes   
    mscorlib.dll!System.Threading.Tasks.Task.InternalRunSynchronously(System.Threading.Tasks.TaskScheduler scheduler, bool waitForCompletion) + 0xba bytes  
    mscorlib.dll!System.Threading.Tasks.Task.RunSynchronously(System.Threading.Tasks.TaskScheduler scheduler) + 0x13 bytes  
    System.Core.dll!System.Linq.Parallel.SpoolingTask.SpoolForAll<ConsoleApplication1.DirWithSubDirs,int>(System.Linq.Parallel.QueryTaskGroupState groupState, System.Linq.Parallel.PartitionedStream<ConsoleApplication1.DirWithSubDirs,int> partitions, System.Threading.Tasks.TaskScheduler taskScheduler) Line 172  C#
// etc..

Cada vez que vea algo como esto, inmediatamente debe pensar en un problema de manguera contra incendios . Probablemente el tercer error más común con hilos, después de carreras y puntos muertos.

Lo que puede razonar, ahora que conoce la causa, el problema con el código es que cada subproceso que completa agrega N subprocesos más. Donde N es el número promedio de subdirectorios en un directorio. En efecto, el número de hilos crece exponencialmente , eso siempre es malo. Solo permanecerá en control si N = 1, eso por supuesto nunca sucede en un disco típico.

Tenga en cuenta que, como casi cualquier problema de enhebrado, este mal comportamiento tiende a repetirse mal. El SSD en su máquina tiende a ocultarlo. También lo hace la RAM en su máquina, el programa podría completarse rápidamente y sin problemas la segunda vez que lo ejecute. Como ahora leerá de la memoria caché del sistema de archivos en lugar del disco, muy rápido. Jugar con ThreadPool.SetMinThreads () también lo oculta, pero no puede solucionarlo. Nunca soluciona ningún problema, solo los oculta. Porque pase lo que pase, el número exponencial siempre abrumará el número mínimo establecido de subprocesos. Solo puede esperar que termine de terminar la iteración de la unidad antes de que eso suceda. Idle Hope para un usuario con un gran disco.

La diferencia entre ParallelEnumerable.ForAll () y Parallel.ForEach () ahora tal vez también se explique fácilmente. Se puede decir por el seguimiento de la pila que ForAll () hace algo malo, el método RunSynchronously () bloquea hasta que se completen todos los hilos. El bloqueo es algo que los subprocesos de grupo de subprocesos no deberían hacer, aglutina el grupo de subprocesos y no le permitirá programar el procesador para otro trabajo. Y tiene el efecto que observó, el grupo de subprocesos se abruma rápidamente con subprocesos que están esperando que se completen los N otros subprocesos. Lo que no está sucediendo, están esperando en el grupo y no se están programando porque ya hay muchos de ellos activos.

Este es un escenario de punto muerto, bastante común, pero el administrador de grupo de subprocesos tiene una solución alternativa. Observa los hilos del conjunto de subprocesos activos e interviene cuando no se completan de manera oportuna. Luego permite que se inicie un subproceso adicional , uno más que el mínimo establecido por SetMinThreads (). Pero no más que el máximo establecido por SetMaxThreads (), tener demasiados hilos de tp activos es arriesgado y es probable que active OOM. Esto resuelve el punto muerto, se completa una de las llamadas ForAll (). Pero esto sucede a un ritmo muy lento, el conjunto de subprocesos solo hace esto dos veces por segundo. Te quedarás sin paciencia antes de que se ponga al día.

Parallel.ForEach () no tiene este problema, no se bloquea, por lo que no engulle el grupo.

Parece ser la solución, pero tenga en cuenta que su programa todavía está protegiendo la memoria de su máquina, agregando cada vez más hilos de tp en espera al grupo. Esto también puede bloquear su programa, simplemente no es tan probable porque tiene mucha memoria y el conjunto de subprocesos no usa mucho para realizar un seguimiento de una solicitud. Sin embargo, algunos programadores logran eso también .

La solución es muy simple, simplemente no use hilos. Es dañino , no hay concurrencia cuando solo tiene un disco. Y no le gusta ser comandado por múltiples hilos. Especialmente malo en un accionamiento de husillo, las búsquedas de cabeza son muy, muy lentas. Los discos SSD lo hacen mucho mejor, sin embargo, todavía lleva unos 50 microsegundos fáciles, una sobrecarga que simplemente no desea ni necesita. El número ideal de subprocesos para acceder a un disco que de otro modo no se esperaría que se almacenara en caché es siempre uno .

Answer 3

Lo primero que debe tener en cuenta es que está tratando de paralelizar una operación vinculada a IO, lo que distorsionará significativamente los tiempos.

La segunda cosa a tener en cuenta es la naturaleza de las tareas paralelas: está descendiendo recursivamente un árbol de directorios. Si crea varios subprocesos para hacer esto, es probable que cada subproceso esté accediendo a una parte diferente del disco simultáneamente, lo que hará que el cabezal de lectura del disco salte por todo el lugar y ralentice considerablemente las cosas.

Intente cambiar su prueba para crear un árbol en memoria y, en su lugar, acceda a él con varios subprocesos. Entonces podrá comparar los tiempos correctamente sin que los resultados se distorsionen más allá de toda utilidad.

Además, puede estar creando una gran cantidad de subprocesos, y estos (por defecto) serán subprocesos de agrupación de subprocesos. Tener una gran cantidad de subprocesos en realidad ralentizará las cosas cuando excedan la cantidad de núcleos de procesador.

También tenga en cuenta que cuando excede los subprocesos mínimos del grupo de subprocesos (definidos por ThreadPool.GetMinThreads() ), el administrador del grupo de subprocesos introduce un retraso entre cada nueva creación de subprocesos de subprocesos. (Creo que esto es alrededor de 0.5s por nuevo hilo).

Además, si el número de subprocesos supera el valor devuelto por ThreadPool.GetMaxThreads() , el subproceso de creación se bloqueará hasta que uno de los otros subprocesos haya salido. Creo que esto puede estar sucediendo.

Puede probar esta hipótesis llamando a ThreadPool.SetMaxThreads() y ThreadPool.SetMinThreads() para aumentar estos valores y ver si hace alguna diferencia.

(Finalmente, tenga en cuenta que si realmente está tratando de descender recursivamente de C:/ , seguramente obtendrá una excepción de E / S cuando llegue a una carpeta protegida del sistema operativo).

NOTA: establezca los subprocesos de subprocesos máximo / mínimo de esta manera:

ThreadPool.SetMinThreads(4000, 16);
ThreadPool.SetMaxThreads(4000, 16);

Seguimiento

He intentado su código de prueba con los recuentos de subprocesos de conjunto de subprocesos establecidos como se describe anteriormente, con los siguientes resultados (no se ejecuta en toda mi unidad C: /, sino en un subconjunto más pequeño):

• El modo 1 tomó 06.5 segundos.
• El modo 2 tomó 15.7 segundos.
• El modo 3 tardó 16,4 segundos.

Esto está en línea con mis expectativas; agregar una carga de subprocesos para hacer esto en realidad lo hace más lento que un solo subproceso, y los dos enfoques paralelos tardan aproximadamente el mismo tiempo.

En caso de que alguien más quiera investigar esto, aquí hay un código de prueba determinante (el código del OP no es reproducible porque no conocemos su estructura de directorio).

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;

namespace Demo
{
    internal class Program
    {
        private static DirWithSubDirs RootDir;

        private static void Main()
        {
            Console.WriteLine("Loading file system into memory...");
            RootDir = new DirWithSubDirs("Root", 4, 4);
            Console.WriteLine("Done");

            //ThreadPool.SetMinThreads(4000, 16);
            //ThreadPool.SetMaxThreads(4000, 16);

            var w = Stopwatch.StartNew();
            ThisIsARecursiveFunctionInMemory(RootDir);

            Console.WriteLine("Elapsed seconds: " + w.Elapsed.TotalSeconds);
            Console.ReadKey();
        }

        public static void ThisIsARecursiveFunctionInMemory(DirWithSubDirs currentDirectory)
        {
            var depth = currentDirectory.Path.Count(t => t == ''//');
            Console.WriteLine(depth + ": " + currentDirectory.Path);

            var children = currentDirectory.SubDirs;

            //Edit this mode to switch what way of parallelization it should use
            int mode = 3;

            switch (mode)
            {
                case 1:
                    foreach (var child in children)
                    {
                        ThisIsARecursiveFunctionInMemory(child);
                    }
                    break;

                case 2:
                    children.AsParallel().ForAll(t =>
                    {
                        ThisIsARecursiveFunctionInMemory(t);
                    });
                    break;

                case 3:
                    Parallel.ForEach(children, t =>
                    {
                        ThisIsARecursiveFunctionInMemory(t);
                    });
                    break;

                default:
                    break;
            }
        }
    }

    internal class DirWithSubDirs
    {
        public List<DirWithSubDirs> SubDirs = new List<DirWithSubDirs>();

        public String Path { get; private set; }

        public DirWithSubDirs(String path, int width, int depth)
        {
            this.Path = path;

            if (depth > 0)
                for (int i = 0; i < width; ++i)
                    SubDirs.Add(new DirWithSubDirs(path + "//" + i, width, depth - 1));
        }
    }
}

Answer 4

Los métodos Parallel.For y .ForEach se implementan internamente como equivalentes a ejecutar iteraciones en Tareas, por ejemplo, un ciclo como:

Parallel.For(0, N, i => 
{ 
  DoWork(i); 
});

es equivalente a:

var tasks = new List<Task>(N); 
for(int i=0; i<N; i++) 
{ 
tasks.Add(Task.Factory.StartNew(state => DoWork((int)state), i)); 
} 
Task.WaitAll(tasks.ToArray());

Y desde la perspectiva de cada iteración que potencialmente se ejecuta en paralelo con cualquier otra iteración, este es un modelo mental aceptable, pero en realidad no sucede. Paralelo, de hecho, no necesariamente usa una Tarea por iteración, ya que es significativamente más sobrecarga de la necesaria. Parallel.ForEach intenta usar la cantidad mínima de tareas necesarias para completar el ciclo lo más rápido posible. Hace girar las tareas a medida que los subprocesos están disponibles para procesar esas tareas, y cada una de esas tareas participa en un esquema de administración (creo que se llama fragmentación): una tarea pide que se realicen múltiples iteraciones, las obtiene y luego procesa ese trabajo, y luego regresa por más. Los tamaños de los fragmentos varían según el número de tareas que participan, la carga en la máquina, etc.

.AsParallel () de PLINQ tiene una implementación diferente, pero ''puede'' igualmente recuperar múltiples iteraciones en un almacén temporal, hacer los cálculos en un hilo (pero no como una tarea) y colocar los resultados de la consulta en un pequeño búfer. (Obtiene algo basado en ParallelQuery, y luego las funciones .Whatever () se unen a un conjunto alternativo de métodos de extensión que proporcionan implementaciones paralelas).

Entonces, ahora que tenemos una pequeña idea de cómo funcionan estos dos mecanismos, intentaré responder a su pregunta original:

Entonces, ¿por qué .AsParallel () es más lento que Parallel.ForEach ? La razón se deriva de lo siguiente. Las tareas (o su implementación equivalente aquí) NO bloquean las llamadas de tipo E / S. ''Esperan'' y liberan la CPU para hacer otra cosa. Pero (citando el libro de resumen de C #): " PLINQ no puede realizar el trabajo vinculado a E / S sin bloquear hilos ". Las llamadas son sincrónicas . Fueron escritos con la intención de aumentar el grado de paralelismo si (y SOLO si) está haciendo cosas tales como descargar páginas web por tarea que no acaparan el tiempo de CPU.

Y la razón por la cual sus llamadas a funciones son exactamente análogas a las llamadas enlazadas de E / S es esta: uno de sus hilos (llámelo T) bloquea y no hace nada hasta que todos sus hilos secundarios hayan terminado, lo que puede ser un proceso lento aquí. T en sí no consume mucha CPU mientras espera a que los niños se desbloqueen, no está haciendo nada más que esperar . Por lo tanto, es idéntico a una llamada de función enlazada de E / S típica.