¿Por qué usar más hilos lo hace más lento que usar menos hilos?

30

Intenté ejecutar el programa X con 8 subprocesos y terminó en n minutos .
Intenté ejecutar el mismo programa con 50 subprocesos y terminó en n * 10 minutos .

¿Por qué sucede esto y cómo puedo obtener el número óptimo de hilos que puedo usar?

PoGibas
fuente

Respuestas:

33

Esta es una pregunta complicada que estás haciendo. Sin saber más sobre la naturaleza de sus hilos es difícil de decir. Algunas cosas a tener en cuenta al diagnosticar el rendimiento del sistema:

Es el proceso / hilo

  • Encuadernado con CPU (necesita muchos recursos de CPU)
  • Memoria enlazada (necesita muchos recursos de RAM)
  • Enlace de E / S (recursos de red y / o disco duro)

Todos estos tres recursos son finitos y cualquiera puede limitar el rendimiento de un sistema. Debe ver cuál (podría ser 2 o 3 juntos) está consumiendo su situación particular.

Puede utilizar ntopy iostat, y vmstatpara diagnosticar lo que está pasando.

slm
fuente
8
El hardware también importa. Físico, virtual, número de núcleos, tipo de núcleo, caché L1 / L2 / L3, etc.
EightBitTony
46

"¿Por qué pasó esto?" Es un poco fácil de responder. Imagine que tiene un corredor en el que puede acomodar a cuatro personas, una al lado de la otra. Desea mover toda la basura de un extremo al otro. El número más eficiente de personas es 4.

Si tienes de 1 a 3 personas, te estás perdiendo el uso del espacio del pasillo. Si tiene 5 o más personas, entonces al menos una de esas personas está básicamente atrapada haciendo cola detrás de otra persona todo el tiempo. Agregar más y más personas simplemente obstruye el corredor, no acelera la actividad.

Por lo tanto, desea tener tantas personas como sea posible sin causar colas. ¿Por qué has cola (o cuellos de botella) depende de las preguntas de la respuesta de SLM.

OchoBitTony
fuente
1
Tu ejemplo es engañoso. Sería mejor decir algo como: "Usted tiene un corredor en el que puede acomodar a cuatro personas, uno al lado del otro, y usted y otras personas lo utilizan para diferentes tareas. Hay un árbitro que decide quién puede pasar por el corredor Entonces, el número más eficiente de personas es mayor que 4 y menor que algún número, donde su gente comienza a hacer cola [altamente dependiente del contexto] ". Por lo general, tener algunos subprocesos más que el número de CPU funciona mejor que usar exactamente 4 subprocesos. Si eres el único que usa la CPU, entonces 4es el mejor número.
Bakuriu
77
Gran ejemplo, +1. Bakuriu, es un ejemplo que ilustra el problema de un recurso compartido limitado. Está explicando el problema, no cómo encontrar el número óptimo de hilos.
Bananguin
1
También sería útil tener en cuenta que los hilos todavía tienen su propio tipo de cambio de contexto que continúa. Aumentar la cantidad de subprocesos no aumenta la capacidad de rendimiento (como usted señaló), pero también agota el tiempo de CPU al darle más trabajo al núcleo. Básicamente, hay rendimientos decrecientes en subprocesos y hacer demasiado provoca un rendimiento retrógrado.
Bratchley
9
Cada problema puede describirse en muchos niveles de complejidad. He ofrecido una aproximación del problema, que creo que es útil para explicar los conceptos básicos. Por supuesto, puede ser más refinado y más detallado, pero cuanto más detallado lo hagas, menos útil será como introducción al problema.
EightBitTony
Solo agregaría eso, en lugar de pasar mucho tiempo calculando el número óptimo de hilos, solo codifíquelo para que se pueda cambiar fácilmente. Cualquier combinación grande como esta requerirá numerosas ejecuciones de prueba (la mayoría con pequeños subconjuntos de sus datos) para perfeccionar. Aumente el número de subprocesos hasta que vea una gran caída en el rendimiento o el impacto en otra actividad del sistema es inaceptable.
DocSalvager
20

Una recomendación común es n + 1 subprocesos, n es el número de núcleos de CPU disponibles. De esa manera, n subprocesos pueden trabajar la CPU mientras 1 subproceso está esperando la E / S de disco. Tener menos subprocesos no utilizaría completamente el recurso de la CPU (en algún momento siempre habrá E / S para esperar), tener más subprocesos provocaría que los subprocesos peleen por el recurso de la CPU.

Los subprocesos no son gratuitos, pero con cambios generales como contexto y, si los datos tienen que intercambiarse entre subprocesos, que suele ser el caso, varios mecanismos de bloqueo. Esto solo vale el costo cuando en realidad tiene núcleos de CPU más dedicados para ejecutar el código. En una CPU de un solo núcleo, un solo proceso (sin hilos separados) suele ser más rápido que cualquier subproceso realizado. Los hilos no hacen que su CPU vaya mágicamente más rápido, solo significa trabajo extra.

Frostschutz
fuente
Esta debería ser la respuesta general dada la cantidad de información disponible en cuestión. no necesitamos una tesis y filosofía completas como otras respuestas
Allahjane
9

Como otros han señalado ( respuesta slm , respuesta EightBitTony ), esta es una pregunta complicada y más aún, ya que no describe lo que hizo y cómo lo hacen.

Pero arrojar definitivamente más hilos puede empeorar las cosas.

En el campo de la computación paralela, existe la ley de Amdahl que puede ser aplicable (o no, pero no describe los detalles de su problema, entonces ...) y puede dar una idea general sobre esta clase de problemas.

El punto de la ley de Amdahl es que en cualquier programa (en cualquier algoritmo) siempre hay un porcentaje que no se puede ejecutar en paralelo (la parte secuencial ) y hay otro porcentaje que se puede ejecutar en paralelo (la parte paralela ) [Obviamente estas dos porciones suman 100%].

Estas porciones se pueden expresar como un porcentaje del tiempo de ejecución. Por ejemplo, puede haber un 25% del tiempo invertido en operaciones estrictamente secuenciales, y el 75% restante del tiempo dedicado a la operación puede ejecutarse en paralelo.

Imagen de Wikipedia (Imagen de Wikipedia )

La ley de Amdahl predice que por cada porción paralela dada (p. Ej., 75%) de un programa, puede acelerar la ejecución solo hasta ahora (p. Ej., Como máximo 4 veces) incluso si usa más y más procesadores para hacer el trabajo.

Como regla general, cuanto más programa usted no pueda transformar en ejecución paralela, menos podrá obtener utilizando más unidades de ejecución (procesadores).

Dado que está utilizando subprocesos (y no procesadores físicos), la situación puede ser aún peor que esto. Recuerde que los subprocesos se pueden procesar (dependiendo de la implementación y el hardware disponible, por ejemplo, CPU / núcleos) que comparten el mismo procesador / núcleo físico (es una forma de multitarea, como se señala en otra respuesta).

Esta predicción teórica (sobre los tiempos de CPU) no considera otros cuellos de botella prácticos como

  1. Velocidad de E / S limitada (disco duro y "velocidad" de red)
  2. Límites de tamaño de memoria
  3. Otros

eso puede ser fácilmente el factor limitante en aplicaciones prácticas.

DavAlPi
fuente
Esta debe ser la respuesta seleccionada.
Eonil
6

El culpable aquí debería ser el "CONTEXTO DE CONMUTACIÓN". Es el proceso de guardar el estado del subproceso actual para comenzar a ejecutar otro subproceso. Si a varios subprocesos se les da la misma prioridad, deben cambiarse hasta que finalicen la ejecución.

En su caso, cuando hay 50 subprocesos, se produce una gran cantidad de cambios de contexto en comparación con solo ejecutar 10 subprocesos.

Esta sobrecarga introducida debido al cambio de contexto es lo que hace que su programa funcione lento

x-treme
fuente
Como no sabemos cuáles son los hilos, esto parece ser una suposición. Sí, el cambio de contexto agrega una sobrecarga, pero si los subprocesos están haciendo algún tipo de análisis de datos, el problema podría ser problemas de caché (es decir, no poder usar el caché porque cada vez que cambia los subprocesos tiene que vaciarlo).
EightBitTony
El cambio de contexto de subprocesos en sí mismo , a menos que estemos tratando con un gran número de cambios de contexto, probablemente no tendrá un impacto de orden de magnitud en el rendimiento. 50 subprocesos es alto pero no extremo (en mi caja en este momento, ps ax | wc -linforma 225 procesos, y de ninguna manera está muy cargado). Me inclino a ir con la suposición de @ EightBitTony; La invalidación de la memoria caché es probablemente un problema mayor, porque cada vez que vacía la memoria caché, la CPU tiene que esperar eones para obtener el código y los datos de la RAM.
un CVn
3

Para arreglar la metáfora de EightBitTony:

"¿Por qué pasó esto?" Es un poco fácil de responder. Imagine que tiene dos piscinas, una llena y otra vacía. Desea mover toda el agua de uno a otro y tener 4 cubos . El número más eficiente de personas es 4.

Si tiene de 1 a 3 personas, se está perdiendo el uso de algunos cubos . Si tienes 5 o más personas, al menos una de esas personas está atrapada esperando un balde . Agregar más y más personas ... no acelera la actividad.

Por lo tanto, desea tener tanta gente como pueda hacer algo de trabajo (use un cubo) simultáneamente .

Una persona aquí es un hilo, y un cubo representa cualquier recurso de ejecución que sea el cuello de botella. Agregar más hilos no ayuda si no pueden hacer nada. Además, debemos enfatizar que pasar un cubo de una persona a otra suele ser más lento que una sola persona que solo lleva el cubo la misma distancia. Es decir, dos subprocesos que se turnan en un núcleo generalmente realizan menos trabajo que un solo subproceso que se ejecuta el doble de tiempo: esto se debe al trabajo adicional realizado para cambiar entre los dos subprocesos.

Si el recurso de ejecución limitante (bucket) es una CPU, o un núcleo, o una canalización de instrucciones hiperhebra para sus propósitos, depende de qué parte de la arquitectura sea su factor limitante. Tenga en cuenta también que estamos asumiendo que los hilos son completamente independientes. Este es sólo el caso si comparten no hay datos (y evitar cualquier colisión de caché).

Como han sugerido un par de personas, para E / S, el recurso limitante podría ser la cantidad de operaciones de E / S útilmente en cola: esto podría depender de una gran cantidad de factores de hardware y kernel, pero fácilmente podría ser mucho mayor que la cantidad de núcleos Aquí, el cambio de contexto que es tan costoso en comparación con el código vinculado a la ejecución, es bastante barato en comparación con el código vinculado de E / S. Lamentablemente, creo que la metáfora se descontrolará por completo si trato de justificar esto con cubos.

Tenga en cuenta que el comportamiento óptimo con el código enlazado de E / S generalmente sigue teniendo como máximo un subproceso por canalización / núcleo / CPU. Sin embargo, debe escribir código de E / S asíncrono o síncrono / sin bloqueo, y la mejora del rendimiento relativamente pequeña no siempre justificará la complejidad adicional.


PD. Mi problema con la metáfora original del corredor es que sugiere fuertemente que debería poder tener 4 colas de personas, con 2 colas cargando basura y 2 regresando para recoger más. A continuación, puede hacer que cada cola casi tan largo como el corredor, y la gente añadiendo hizo acelerar el algoritmo (que, básicamente, se volvió todo el corredor en una cinta transportadora).

De hecho, este escenario es muy similar a la descripción estándar de la relación entre la latencia y el tamaño de la ventana en las redes TCP, por lo que me llamó la atención.

Inútil
fuente
No es una metáfora, es una aproximación diseñada para explicar el sistema a las personas de manera que puedan visualizarlo fácilmente. Como tal, las personas que conocen el siguiente nivel de detalle siempre lo van a 'rozar', pero no se dan cuenta de que su nivel de detalle no es realmente necesario para los principiantes. Nadie aprende física de partículas comenzando en el nivel de doctorado. Todo lo anterior es una aproximación que te lleva gradualmente, refinándolo a medida que avanzas. No está 'mal', simplemente no es la imagen completa.
EightBitTony
Nadie está confundido sobre qué figura de lenguaje usaste, y no es una mala analogía. Cada analogía tiene un límite más allá del cual diverge de lo que se supone que describe y deja de ser útil. Solo mencioné esto porque el original me recordaba fuertemente a un escenario diferente, y porque no creo que esta versión sea más compleja para la (con suerte) mejor predictividad.
Inútil
0

Es bastante sencillo y fácil de entender. Tener más subprocesos de los que admite su CPU realmente está serializando y no paralelizando. Cuantos más subprocesos tenga, más lento será su sistema. Sus resultados son en realidad una prueba de este fenómeno.

Bruno Taboada
fuente