¿Hay alguna razón para no usar el paraleloSort de Java 8?

sorting parallel-processing

Question

Estaba leyendo esta pregunta sobre las diferencias entre Arrays.sort de Java y Arrays.parallelSort , que ya tiene algunos años. Lo que me sorprendió es que solo había una pregunta que mencionaba alguna desventaja con el uso de parallelSort ; es decir, que la aceleración disminuye si está utilizando una gran cantidad de su CPU.

Suponiendo que no se encuentre en algún tipo de entorno especializado de un solo subproceso, ¿debería uno elegir siempre el orden parallelSort ? ¿Hay alguna razón para no hacerlo? Tenga en cuenta que una de las respuestas a la pregunta anterior menciona que si hay menos de 4096 elementos, parallelSort simplemente llama a sort todos modos.

Answer 1

Además de razones como el uso de un grupo común y el tamaño mínimo que es optimizable, es posible que no tenga que paralelizar una sola ordenación si, por lo general, tiene muchas transacciones que requieren clasificaciones en paralelo.

En ese escenario, podría evitar la sobrecarga al dividir los paquetes de trabajo. (Sin embargo, tener un ejecutor controlable con un trabajo paralelo configurable también funciona para el envío de múltiples subprocesos, solo se aumenta el número de subprocesos estacionados e interruptores de contexto)

Answer 2

Esto no es muy diferente a la pregunta de cuándo usar stream() vs parallelStream() , depende de la cantidad de datos que tenga. Por supuesto, la mayoría de las veces, al ordenar 10 elementos en paralelo, será consumida por el marco de subprocesos que está debajo del capó (que no está especificado en la documentación), no por la clasificación en sí.

Pero también hay que preguntarse por qué se introducen tales métodos en la OMI. El hardware se está moviendo (¿ya se ha movido?) Hacia muchas CPU, no más GHz , por lo que hacer cosas en paralelo es solo un curso normal para cualquier idioma que quiera seguir vivo en los próximos 20 años.

En cuanto a la cantidad de datos que necesita para tener un MIN_ARRAY_SORT_GRAN + 1 rendimiento para parallelSort en lugar de sort , además de saber que necesitamos al menos MIN_ARRAY_SORT_GRAN + 1 para obtener cualquier beneficio potencial; escribir una prueba adecuada para demostrar que para esta configuración y ejecución en particular , necesitaría al menos X números, no es tan complicado. También debe tener en cuenta que algunas matrices pueden estar ya ordenadas (explicadas más adelante), mientras que otras pueden estar totalmente 5,4,3,2,1 ( 5,4,3,2,1 por ejemplo), esto conlleva algunas penalizaciones para la segunda.

Tomando algunos datos al azar y haciendo una prueba:

@Warmup(iterations = 10)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Measurement(iterations = 2, time = 2, timeUnit = TimeUnit.SECONDS)
public class ParallelSort {
public static void main(String[] args) throws Exception {
Options opt = new OptionsBuilder()
.include(ParallelSort.class.getName())
.build();
new Runner(opt).run();
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@Fork(1)
public int[] parallel(ParallelSortExecutionPlan plan) {
Arrays.parallelSort(plan.ints());
return plan.ints();
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@Fork(1)
public int[] nonParallel(ParallelSortExecutionPlan plan) {
Arrays.sort(plan.ints());
return plan.ints();
}
}
@State(Scope.Benchmark)
public class ParallelSortExecutionPlan {
@Param(value = {"10", "100", "1000", "10000", "100000", "1000000"})
private int howMany;
private int[] ints;
public static void main(String[] args) {
}
@Setup(Level.Invocation)
public void setUp() {
ints = new int[howMany];
for (int i = 0; i < howMany; ++i) {
ints[i] = ThreadLocalRandom.current().nextInt();
}
}
int[] ints() {
return ints;
}
}

Simplemente note que la segunda clase está usando @Setup(Level.Invocation) (si conoce un poco de JMH ) - esta es una herramienta muy precisa aquí; pero lo uso porque quiero una matriz sin clasificar para cada Invocation del método. Como de otro modo, si se hubiera usado la @Benhcmark Trial , por ejemplo, solo la primera llamada sería una matriz no ordenada, todas las demás llamadas del método @Benhcmark ya estarían ordenadas. Por el gusto de hacerlo, podría cambiar esa línea única a @Setup(Level.Trial) por ejemplo y ver los resultados, tendrán muy poco sentido.

Ejecutando esto revela:

Benchmark (howMany) Mode Cnt Score Error Units
ParallelSort.nonParallel 10 avgt 2 128.847 ns/op
ParallelSort.parallel 10 avgt 2 116.656 ns/op
ParallelSort.nonParallel 100 avgt 2 1956.746 ns/op
ParallelSort.parallel 100 avgt 2 1963.335 ns/op
ParallelSort.nonParallel 1000 avgt 2 32162.611 ns/op
ParallelSort.parallel 1000 avgt 2 31716.915 ns/op
ParallelSort.nonParallel 10000 avgt 2 423531.663 ns/op
ParallelSort.parallel 10000 avgt 2 201802.609 ns/op
ParallelSort.nonParallel 100000 avgt 2 6503511.987 ns/op
ParallelSort.parallel 100000 avgt 2 1363169.661 ns/op
ParallelSort.nonParallel 1000000 avgt 2 69058738.586 ns/op
ParallelSort.parallel 1000000 avgt 2 13469112.930 ns/op

Bastante una salida muy esperada para mí.

Answer 3

Hay algunas desventajas de usar Arrays.parallelSort

• utiliza ForkJoinPool.commonPool() y luchará con otras funciones que lo usan de forma predeterminada (por ejemplo, parallel() en una secuencia)
• el Arrays.parallelSort subprocesos que Arrays.parallelSort utiliza no es configurable (solo a nivel global mediante el aumento de la cantidad de subprocesos de pools comunes)
• se desempeña peor en pequeños conjuntos de datos (la mayoría de las veces los arreglos contienen pocos elementos, el JDK incluso reconoce que, por ejemplo, la mayoría de los ArrayList permanecen vacíos durante toda su vida útil, lo que ahorra un poco de memoria y tiempo de CPU para no crear instancias de arreglos que nunca se llenarán )

Y otro escenario anecdótico: diga si implementa un juego de cartas que necesita ordenación. Es vergonzosamente fácil paralelizar varias ejecuciones de juegos uno al lado del otro en lugar de paralelizar el mecanismo de clasificación de una carrera que puede tomar solo una fracción de todo el ciclo del juego. Perdió una forma fácil de paralelizar ahora (por ejemplo, al ejecutar el juego en el contexto de algoritmos genéticos).

Pero sí, si tiene matrices de gran tamaño y la clasificación es una parte sustancial del tiempo de ejecución de sus aplicaciones, use Arrays.parallelSort .

EDITAR: e incluso si Arrays.parallelSort cambia a una ordenación normal si la matriz dada tiene menos de 4096 elementos: todo se trata de mostrar intenciones: si es posible, se desea una ordenación paralela que tenga un significado diferente a la sort simple. Y para ser nítido: de hecho, su desempeño es peor en los arreglos pequeños, ya que tiene que hacer la verificación adicional si el arreglo contiene menos de 4096 elementos y algunos otros controles sobre el recuento de subprocesos de grupos comunes (lo que por supuesto es despreciable) :) .

Answer 4

No, diría que no para arreglos lo suficientemente pequeños. La sobrecarga de configurar los hilos no dará lugar a una velocidad observable.

La clave es "lo suficientemente pequeña". No será la misma respuesta para todos los problemas.

El dogma nunca debe aplicarse, excepto en el caso de esta regla de dogma. Al igual que lo único que nunca debemos tolerar es la intolerancia. Hay una paradoja de Popper en alguna parte.