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

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

Para encontrar cómo esto se puede implementar 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 al ejecutar esto en el modo 3 (Parallel.ForEach) el código se completa en alrededor de 2,5 segundos (sí, tengo un SSD;)). Al ejecutar el código sin paralelización, se completa en alrededor de 8 segundos. Y ejecutar el código en el modo 2 (AsParalle.ForAll ()) lleva una cantidad de tiempo casi infinita.

Al registrar el proceso de explorador, 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 resulta 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 la Tarea anterior se complete (lo que no sucederá pronto ya que todas las Tareas principales) todavía están esperando que completen sus tareas secundarias).

También lo que leí en MSDN fue: “Prefiero ForAll to ForEach When Is Possible”

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

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

Editar 1:

Como solicitó Matthew Watson, primero cargué el árbol en la memoria antes de recorrerlo. Ahora la carga del árbol se realiza secuencialmente.

Los resultados sin embargo son lo mismo. Incomparable y Paralelo.ForEach ahora completa todo el árbol en aproximadamente 0.05 segundos mientras AsParallel () .Todavía 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 SubDirs = new List(); 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 } } } 

Editar 2:

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

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

Sin embargo, esto no cambia la forma en que se ajusta el AsParallel. Sin embargo, los primeros 8 pasos se están ejecutando en un instante antes de disminuir a 1 paso / segundo.

(Nota extra, actualmente estoy ignorando las excepciones que ocurren cuando no puedo acceder a un directorio mediante el bloque Try Catch alrededor de Directory.GetDirectories ())

Editar 3:

Además, lo que más me interesa es la diferencia entre Parallel.ForEach y AsParallel.ForAll, porque para mí es extraño que, por alguna razón, el segundo cree un hilo por cada recursión que hace, mientras que el primero maneja todo en alrededor de 30 hilos. 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)

Editar 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 alrededor de 8 o 16: ThreadPool.SetMinThreads (1023, 16);

Aun así, cuando uso 1023, los primeros 1023 elementos son muy rápidos y luego vuelvo al ritmo lento que he estado experimentando todo el tiempo.

Nota: También literalmente se crearon más de 1000 hilos (en comparación con 30 para el Parallel.ForEach entero).

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

Algo más de información, este código imprime dos veces 8 – 8 cuando configura 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 partir de la solicitud de Dean, he creado otro caso para crear tareas manualmente:

 case 4: var taskList = new List(); 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 a por qué AsParallel (). ForAll () es mucho más lento.

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

  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(System.Linq.Parallel.QueryTaskGroupState groupState, System.Linq.Parallel.PartitionedStream partitions, System.Threading.Tasks.TaskScheduler taskScheduler) Line 172 C# // etc.. 

Cada vez que vea algo como esto, debería pensar inmediatamente en un problema con las mangueras de incendios . Probablemente el tercer error más común con los hilos, después de las carreras y los lockings.

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

Tenga cuidado, como casi cualquier problema de enhebrado, que esta mala conducta tiende a repetirse mal. El SSD en su máquina tiende a ocultarlo. También lo hace la RAM en su máquina, el progtwig podría completarse rápidamente y sin problemas la segunda vez que lo ejecute. Ya que ahora leerá desde la caché del sistema de archivos en lugar del disco, muy rápido. Jugando con ThreadPool.SetMinThreads () lo oculta también, pero no puede arreglarlo. Nunca soluciona ningún problema, solo los oculta. Porque pase lo que pase, el número exponencial siempre superará el número mínimo establecido de hilos. Solo puede esperar que termine de terminar la iteración de la unidad antes de que eso suceda. Esperanza inactiva para un usuario con una gran unidad.

La diferencia entre ParallelEnumerable.ForAll () y Parallel.ForEach () ahora también se explica fácilmente. Desde el rastro de la stack puede ver que ForAll () hace algo malo, el método RunSynchronously () bloquea hasta que se completan todos los hilos. El locking es algo que los subprocesos de subprocesos no deberían hacer, enciende el grupo de subprocesos y no le permitirá progtwigr el procesador para otro trabajo. Y tiene el efecto que observó, el grupo de subprocesos se ve abrumado rápidamente con los subprocesos que esperan los N otros subprocesos para completarse. Lo cual no está sucediendo, están esperando en el grupo y no se están progtwigndo porque ya hay muchos de ellos activos.

Este es un escenario de interlocking, bastante común, pero el administrador de subprocesos tiene una solución alternativa. Mira los hilos de subprocesos activos y los pasos cuando no se completan de manera oportuna. Luego permite que se inicie un hilo adicional , uno más que el mínimo establecido por SetMinThreads (). Pero no más que el máximo establecido por SetMaxThreads (), tener demasiados subprocesos tp activos es arriesgado y es probable que active OOM. Esto soluciona el punto muerto, obtiene una de las llamadas ForAll () para completarse. Pero esto ocurre a un ritmo muy lento, el subproceso solo lo hace dos veces por segundo. Se le acabará la paciencia antes de ponerse al día.

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

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

La solución es muy simple, simplemente no use el enhebrado. Es dañino , no hay concurrencia cuando tiene solo un disco. Y no le gusta ser comandado por múltiples hilos. Especialmente malo en un disco de husillo, las búsquedas de cabeza son muy, muy lentas. Las SSD lo hacen mucho mejor, sin embargo, aún requiere 50 microsegundos, una sobrecarga que simplemente no desea ni necesita. La cantidad ideal de subprocesos para acceder a un disco que de otra manera no se puede almacenar en caché es siempre la misma .

Lo primero que debe observar es que está tratando de paralelizar una operación ligada a IO, lo que distorsionará las temporizaciones de manera significativa.

Lo segundo a tener en cuenta es la naturaleza de las tareas paralelas: estás descendiendo recursivamente en un árbol de directorios. Si crea varios subprocesos para hacer esto, es probable que cada subproceso acceda a una parte diferente del disco simultáneamente, lo que hará que el encabezado de lectura del disco salte por todas partes y desacelere considerablemente.

Intente cambiar su prueba para crear un árbol en memoria, y acceda a eso con múltiples hilos en su lugar. Entonces podrás comparar los tiempos de forma adecuada sin que los resultados se distorsionen más allá de toda utilidad.

Además, puede estar creando una gran cantidad de subprocesos y, de forma predeterminada, serán subprocesos de subprocesos. Tener una gran cantidad de subprocesos ralentizará las cosas cuando excedan la cantidad de núcleos de procesador.

También tenga en cuenta que cuando supera 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 subproceso de subprocesos. (Creo que esto es alrededor de 0.5s por hilo nuevo).

Además, si el número de subprocesos excede el valor devuelto por ThreadPool.GetMaxThreads() , el hilo de creación se bloqueará hasta que uno de los otros subprocesos haya salido. Creo que esto es probable que esté sucediendo.

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

(Finalmente, tenga en cuenta que si realmente está tratando de descender recursivamente de C:\ , casi con seguridad recibirá una excepción de IO cuando llegue a una carpeta de sistema operativo protegida).

NOTA: Establezca los hilos de subprocesos de subprocesos max / min como este:

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

Seguir

Probé el código de prueba con los recuentos de subprocesos de subprocesos establecidos como se describió anteriormente, con los siguientes resultados (no se ejecutan en toda mi unidad C: \, sino en un subconjunto más pequeño):

  • El modo 1 tardó 06.5 segundos.
  • El modo 2 tardó 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 realmente lo hace más lento que un subproceso único, y los dos enfoques paralelos toman aproximadamente el mismo tiempo.


En caso de que alguien más quiera investigar esto, aquí hay un código de prueba determinativo (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 SubDirs = new List(); 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)); } } } 

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

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

es equivalente a:

 var tasks = new List(N); for(int i=0; i 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 no ocurre en realidad. Paralelo, de hecho, no necesariamente utiliza una Tarea por iteración, ya que es mucho más sobrecarga de lo necesario. Parallel.ForEach intenta usar la cantidad mínima de tareas necesarias para completar el ciclo lo más rápido posible. Da vueltas a las tareas a medida que los hilos se vuelven disponibles para procesar esas tareas, y cada una de esas tareas participa en un esquema de gestión (creo que se llama fragmentación): una tarea pide que se realicen múltiples iteraciones, las obtiene y luego los procesos funcionan; 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 ‘igualmente’ puede buscar iteraciones múltiples 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 buffer. (Obtienes algo basado en ParallelQuery, y luego 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é proporcionar una respuesta a su pregunta original:

Entonces, ¿por qué es .AsParallel () 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 similares a E / S. Ellos ‘aguardan’ y liberan la CPU para hacer otra cosa. Pero (citando el libro de shells C #): ” PLINQ no puede realizar el trabajo de E / S sin bloquear hilos “. Las llamadas son sincrónicas . Fueron escritos con la intención de boost el grado de paralelismo si (y SOLO si) estás haciendo cosas como descargar páginas web por tarea que no consume tiempo de CPU.

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

En función de la respuesta aceptada, ¿cómo funciona exactamente AsParallel?

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

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