¿Debería usar siempre un flujo paralelo cuando sea posible?

515

Con Java 8 y lambdas es fácil iterar sobre colecciones como flujos, e igual de fácil usar un flujo paralelo. Dos ejemplos de los documentos , el segundo usando parallelStream:

myShapesCollection.stream()
    .filter(e -> e.getColor() == Color.RED)
    .forEach(e -> System.out.println(e.getName()));

myShapesCollection.parallelStream() // <-- This one uses parallel
    .filter(e -> e.getColor() == Color.RED)
    .forEach(e -> System.out.println(e.getName()));

Mientras no me importe el orden, ¿siempre sería beneficioso usar el paralelo? Uno pensaría que es más rápido dividir el trabajo en más núcleos.

¿Hay otras consideraciones? ¿Cuándo debe usarse la corriente paralela y cuándo debe usarse la no paralela?

(Se le pide a esta pregunta que provoque una discusión sobre cómo y cuándo usar flujos paralelos, no porque piense que usarlos siempre es una buena idea).

Matsemann
fuente

Respuestas:

736

Una corriente paralela tiene una sobrecarga mucho mayor en comparación con una secuencial. La coordinación de los hilos lleva una cantidad de tiempo considerable. Usaría secuencias secuenciales por defecto y solo consideraría las paralelas si

  • Tengo una gran cantidad de elementos para procesar (o el procesamiento de cada elemento lleva tiempo y es paralelo)

  • Tengo un problema de rendimiento en primer lugar

  • Todavía no ejecuto el proceso en un entorno de subprocesos múltiples (por ejemplo: en un contenedor web, si ya tengo muchas solicitudes para procesar en paralelo, agregar una capa adicional de paralelismo dentro de cada solicitud podría tener más efectos negativos que positivos) )

En su ejemplo, el rendimiento estará impulsado de todos modos por el acceso sincronizado System.out.println()y hacer que este proceso sea paralelo no tendrá ningún efecto, o incluso uno negativo.

Además, recuerde que las secuencias paralelas no resuelven mágicamente todos los problemas de sincronización. Si los predicados y las funciones utilizados en el proceso utilizan un recurso compartido, deberá asegurarse de que todo sea seguro para subprocesos. En particular, los efectos secundarios son cosas de las que realmente debe preocuparse si va en paralelo.

En cualquier caso, mida, ¡no adivine! Solo una medición le dirá si el paralelismo lo vale o no.

JB Nizet
fuente
18
Buena respuesta. Agregaría que si tiene una gran cantidad de elementos para procesar, eso solo aumenta los problemas de coordinación del hilo; es solo cuando el procesamiento de cada elemento lleva tiempo y es paralelizable que la paralelización puede ser útil.
Warren Dew
16
@ WarrenDew no estoy de acuerdo. El sistema Fork / Join simplemente dividirá los N elementos en, por ejemplo, 4 partes, y procesará estas 4 partes secuencialmente. Los 4 resultados se reducirán. Si masivo es realmente masivo, incluso para el procesamiento rápido de unidades, la paralelización puede ser efectiva. Pero como siempre, tienes que medir.
JB Nizet
Tengo una colección de objetos que implemento a los Runnableque llamo start()para usarlos Threads, ¿está bien cambiar eso para usar flujos de Java 8 en .forEach()paralelo? Entonces podría quitar el código del hilo de la clase. ¿Pero hay alguna desventaja?
ycomp
1
@JBNizet Si 4 partes se procesan secuencialmente, entonces no hay diferencia de que sea un proceso paralelo o secuencialmente conocido? Por
favor
3
@Harshana, obviamente, significa que los elementos de cada una de las 4 partes se procesarán secuencialmente. Sin embargo, las partes mismas pueden procesarse simultáneamente. En otras palabras, si tiene varios núcleos de CPU disponibles, cada parte puede ejecutarse en su propio núcleo independientemente de las otras partes, mientras procesa sus propios elementos secuencialmente. (NOTA: No sé, si así es como funcionan las secuencias paralelas de Java, solo estoy tratando de aclarar lo que significaba JBNizet).
Mañana
258

La API Stream se diseñó para facilitar la escritura de cálculos de una manera que se abstraía de cómo se ejecutarían, facilitando el cambio entre secuencial y paralelo.

Sin embargo, solo porque sea fácil, no significa que siempre sea una buena idea, y de hecho, es una mala idea simplemente dejar .parallel()todo el lugar simplemente porque puedes.

Primero, tenga en cuenta que el paralelismo no ofrece otros beneficios que la posibilidad de una ejecución más rápida cuando hay más núcleos disponibles. Una ejecución paralela siempre implicará más trabajo que una secuencial, porque además de resolver el problema, también debe realizar el despacho y la coordinación de subtareas. La esperanza es que pueda obtener la respuesta más rápido al dividir el trabajo en múltiples procesadores; si esto realmente sucede depende de muchas cosas, incluido el tamaño de su conjunto de datos, cuánto cálculo está haciendo en cada elemento, la naturaleza del cálculo (específicamente, ¿el procesamiento de un elemento interactúa con el procesamiento de otros?) , la cantidad de procesadores disponibles y la cantidad de otras tareas que compiten por esos procesadores.

Además, tenga en cuenta que el paralelismo a menudo también expone el no determinismo en el cálculo que a menudo está oculto por implementaciones secuenciales; a veces esto no importa, o puede mitigarse limitando las operaciones involucradas (es decir, los operadores de reducción deben ser apátridas y asociativos).

En realidad, a veces el paralelismo acelerará su cálculo, a veces no, y a veces incluso lo ralentizará. Lo mejor es desarrollar primero usando la ejecución secuencial y luego aplicar paralelismo donde

(A) usted sabe que en realidad hay un beneficio para un mayor rendimiento

(B) que realmente ofrecerá un mayor rendimiento.

(A) es un problema comercial, no técnico. Si es un experto en rendimiento, generalmente podrá mirar el código y determinar (B), pero la ruta inteligente es medir. (Y ni siquiera se moleste hasta que esté convencido de (A); si el código es lo suficientemente rápido, mejor aplicar sus ciclos cerebrales en otro lugar)

El modelo de rendimiento más simple para el paralelismo es el modelo "NQ", donde N es el número de elementos y Q es el cálculo por elemento. En general, necesita que el producto NQ supere algún umbral antes de comenzar a obtener un beneficio de rendimiento. Para un problema de baja Q como "sumar números del 1 al N", generalmente verá un punto de equilibrio entre N = 1000 y N = 10000. Con problemas de mayor Q, verá los puntos de equilibrio en los umbrales más bajos.

Pero la realidad es bastante complicada. Por lo tanto, hasta que obtenga experiencia, primero identifique cuándo el procesamiento secuencial realmente le está costando algo y luego mida si el paralelismo ayudará.

Brian Goetz
fuente
18
Esta publicación brinda más detalles sobre el modelo NQ: gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html
Pino
44
@specializt: la conmutación de una corriente de secuencial a paralelo hace cambiar el algoritmo (en la mayoría de los casos). El determinismo mencionado aquí se refiere a las propiedades en las que sus operadores (arbitrarios) pueden confiar (la implementación de Stream no puede saber eso), pero por supuesto no debería confiar. Eso es lo que esa sección de esta respuesta intentó decir. Si te interesan las reglas, puedes tener un resultado determinista, como dices, (de lo contrario, las corrientes paralelas eran bastante inútiles), pero también existe la posibilidad de no determinismo intencionalmente permitido, como cuando se usa en findAnylugar de findFirst...
Holger
44
"Primero, tenga en cuenta que el paralelismo no ofrece más beneficios que la posibilidad de una ejecución más rápida cuando hay más núcleos disponibles", o si está aplicando una acción que involucra IO (por ejemplo myListOfURLs.stream().map((url) -> downloadPage(url))...).
Julio
66
@Pacerier Esa es una buena teoría, pero tristemente ingenua (para empezar, vea la historia de 30 años de intentos de construir compiladores de paralelización automática). Como no es práctico adivinar el tiempo suficiente para no molestar al usuario cuando inevitablemente nos equivocamos, lo más responsable fue dejar que el usuario diga lo que quiere. Para la mayoría de las situaciones, el valor predeterminado (secuencial) es correcto y más predecible.
Brian Goetz
2
@Jules: nunca use flujos paralelos para IO. Están destinados exclusivamente para operaciones intensivas de CPU. Se usan transmisiones paralelas ForkJoinPool.commonPool()y no desea que las tareas de bloqueo vayan allí.
R2C2
68

Vi una de las presentaciones de Brian Goetz (Arquitecto de lenguaje Java y líder de especificaciones para Lambda Expressions) . Explica en detalle los siguientes 4 puntos a considerar antes de ir a la paralelización:

Costos de división / descomposición
: ¡a veces dividir es más costoso que simplemente hacer el trabajo!
Despacho de tareas / costos de administración
: puede hacer mucho trabajo en el tiempo que lleva el trabajo manual a otro hilo.
Costos de combinación de resultados
: a veces, la combinación implica copiar muchos datos. Por ejemplo, agregar números es barato, mientras que fusionar conjuntos es costoso.
Localidad
- El elefante en la habitación. Este es un punto importante que todos pueden pasar por alto. Debería considerar los errores de caché, si una CPU espera datos debido a errores de caché, entonces no ganaría nada por la paralelización. Es por eso que las fuentes basadas en matriz paralelizan mejor a medida que se almacenan en caché los siguientes índices (cerca del índice actual) y hay menos posibilidades de que la CPU experimente una pérdida de caché.

También menciona una fórmula relativamente simple para determinar una posibilidad de aceleración paralela.

Modelo NQ :

N x Q > 10000

donde,
N = número de elementos de datos
Q = cantidad de trabajo por elemento

Ram Patra
fuente
13

JB golpeó el clavo en la cabeza. Lo único que puedo agregar es que Java 8 no hace un procesamiento paralelo puro, lo hace paraquential . Sí, escribí el artículo y he estado haciendo F / J durante treinta años, así que entiendo el problema.

Edharned
fuente
10
Las secuencias no son iterables porque las secuencias hacen iteración interna en lugar de externa. Esa es la razón de las transmisiones de todos modos. Si tienes problemas con el trabajo académico, entonces la programación funcional podría no ser para ti. Programación funcional === matemática === académica. Y no, J8-FJ no está roto, es solo que la mayoría de las personas no leen el manual f ******. Los documentos de Java dicen muy claramente que no es un marco de ejecución paralelo. Esa es toda la razón de todas las cosas de spliterator. Sí, es académico, sí, funciona si sabes cómo usarlo. Sí, debería ser más fácil usar un ejecutor personalizado
Kr0e
1
Stream tiene un método iterator (), por lo que puede iterarlos externos si lo desea. Comprendí que no implementan Iterable porque solo puedes usar ese iterador una vez y nadie podría decidir si eso estaba bien.
Trejkaz
14
para ser honesto: todo su trabajo se lee como una diatriba masiva y elaborada, y eso prácticamente niega su credibilidad ... recomendaría volver a hacerlo con un tono mucho menos agresivo; de lo contrario, no muchas personas se molestarán en leerlo por completo ... im sayan
specializt
Un par de preguntas sobre su artículo ... en primer lugar, ¿por qué aparentemente equipara estructuras de árbol equilibradas con gráficos acíclicos dirigidos? Sí, los árboles equilibrados son DAG, pero también lo son las listas vinculadas y casi todas las estructuras de datos orientadas a objetos que no sean matrices. Además, cuando dice que la descomposición recursiva solo funciona en estructuras de árbol equilibradas y, por lo tanto, no es relevante comercialmente, ¿cómo justifica esa afirmación? Me parece (sin admitir que realmente examiné el problema en profundidad) que debería funcionar igual de bien en estructuras de datos basadas en matrices, por ejemplo ArrayList/ HashMap.
Julio
1
Este hilo es de 2013, mucho ha cambiado desde entonces. Esta sección es para comentarios, no respuestas detalladas.
edharned
3

Otras respuestas ya han cubierto la creación de perfiles para evitar la optimización prematura y los costos generales en el procesamiento paralelo. Esta respuesta explica la elección ideal de las estructuras de datos para la transmisión en paralelo.

Por regla general, las ganancias de rendimiento de paralelismo son mejores en las corrientes más ArrayList, HashMap, HashSet, y ConcurrentHashMapcasos; matrices; intrangos; y longrangos. Lo que estas estructuras de datos tienen en común es que todas pueden dividirse de manera precisa y económica en subrangos de cualquier tamaño deseado, lo que facilita la división del trabajo entre hilos paralelos. La abstracción utilizada por la biblioteca de secuencias para realizar esta tarea es el spliterator, que devuelve el spliteratormétodo on Streamy Iterable.

Otro factor importante que todas estas estructuras de datos tienen en común es que proporcionan una localidad de referencia de buena a excelente cuando se procesan secuencialmente: las referencias de elementos secuenciales se almacenan juntas en la memoria. Los objetos a los que hacen referencia esas referencias pueden no estar cerca uno del otro en la memoria, lo que reduce la localidad de referencia. La localidad de referencia resulta ser de vital importancia para la paralelización de operaciones masivas: sin ella, los subprocesos pasan gran parte de su tiempo inactivos, esperando que los datos se transfieran de la memoria al caché del procesador. Las estructuras de datos con la mejor localidad de referencia son matrices primitivas porque los datos se almacenan contiguamente en la memoria.

Fuente: Artículo # 48 Tenga precaución al hacer flujos paralelos, Java 3e efectivo por Joshua Bloch

ruhong
fuente
2

Nunca paralelice una corriente infinita con un límite. Esto es lo que pasa:

    public static void main(String[] args) {
        // let's count to 1 in parallel
        System.out.println(
            IntStream.iterate(0, i -> i + 1)
                .parallel()
                .skip(1)
                .findFirst()
                .getAsInt());
    }

Resultado

    Exception in thread "main" java.lang.OutOfMemoryError
        at ...
        at java.base/java.util.stream.IntPipeline.findFirst(IntPipeline.java:528)
        at InfiniteTest.main(InfiniteTest.java:24)
    Caused by: java.lang.OutOfMemoryError: Java heap space
        at java.base/java.util.stream.SpinedBuffer$OfInt.newArray(SpinedBuffer.java:750)
        at ...

Lo mismo si usas .limit(...)

Explicación aquí: Java 8, el uso de .parallel en una secuencia provoca un error OOM

Del mismo modo, no use paralelo si la secuencia está ordenada y tiene muchos más elementos de los que desea procesar, p. Ej.

public static void main(String[] args) {
    // let's count to 1 in parallel
    System.out.println(
            IntStream.range(1, 1000_000_000)
                    .parallel()
                    .skip(100)
                    .findFirst()
                    .getAsInt());
}

Esto puede durar mucho más tiempo porque los subprocesos paralelos pueden funcionar en muchos rangos de números en lugar del crucial 0-100, lo que lleva mucho tiempo.

tkruse
fuente