Java 8 transmite rendimiento en serie versus paralelo

Question

En mi máquina, el siguiente programa imprime:

OptionalLong[134043]
 PARALLEL took 127869 ms
OptionalLong[134043]
 SERIAL took 60594 ms

No me queda claro por qué ejecutar el programa en serie es más rápido que ejecutarlo en paralelo.He dado ambos programas. -Xms2g -Xmx2g en una 8gb Caja que es relativamente silenciosa.¿Alguien puede aclarar qué está pasando?

import java.util.stream.LongStream;
import java.util.stream.LongStream.Builder;

public class Problem47 {

    public static void main(String[] args) {

        final long startTime = System.currentTimeMillis();
        System.out.println(LongStream.iterate(1, n -> n + 1).parallel().limit(1000000).filter(n -> fourConsecutives(n)).findFirst());
        final long endTime = System.currentTimeMillis();
        System.out.println(" PARALLEL took " +(endTime - startTime) + " ms");

        final long startTime2 = System.currentTimeMillis();
        System.out.println(LongStream.iterate(1, n -> n + 1).limit(1000000).filter(n -> fourConsecutives(n)).findFirst());
        final long endTime2 = System.currentTimeMillis();
        System.out.println(" SERIAL took " +(endTime2 - startTime2) + " ms");
    }

    static boolean fourConsecutives(final long n) {
        return distinctPrimeFactors(n).count() == 4 &&
                distinctPrimeFactors(n + 1).count() == 4 &&
                distinctPrimeFactors(n + 2).count() == 4 &&
                distinctPrimeFactors(n + 3).count() == 4;
    }

    static LongStream distinctPrimeFactors(long number) {
        final Builder builder = LongStream.builder();
        final long limit = number / 2;
        long n = number;
        for (long i = 2; i <= limit; i++) {
            while (n % i == 0) {
                builder.accept(i);
                n /= i;
            }
        }
        return builder.build().distinct();
    }

}

Answer 1

Si bien Brian Goetz tiene razón acerca de su configuración, p.que deberías usar .range(1, 1000000) en vez de .iterate(1, n -> n + 1).limit(1000000) y que tu método de benchmark es muy simplista, quiero enfatizar el punto importante:

Incluso después de solucionar estos problemas, incluso usando un reloj de pared y el Administrador de tareas puedes ver que algo anda mal.En mi máquina, la operación dura aproximadamente medio minuto y se puede ver que el paralelismo cae a un solo núcleo después de aproximadamente dos segundos.Incluso si una herramienta de evaluación comparativa especializada pudiera producir resultados diferentes, no importaría a menos que desee ejecutar su aplicación final dentro de una herramienta de evaluación comparativa todo el tiempo...

Ahora podríamos intentar burlarnos más de su configuración o decirle que debería aprender cosas especiales sobre el marco Fork/Join como el los implementadores hicieron en la lista de discusión.

O intentamos una implementación alternativa:

ExecutorService es=Executors.newFixedThreadPool(
                       Runtime.getRuntime().availableProcessors());
AtomicLong found=new AtomicLong(Long.MAX_VALUE);
LongStream.range(1, 1000000).filter(n -> found.get()==Long.MAX_VALUE)
    .forEach(n -> es.submit(()->{
        if(found.get()>n && fourConsecutives(n)) for(;;) {
            long x=found.get();
            if(x<n || found.compareAndSet(x, n)) break;
        }
    }));
es.shutdown();
try { es.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS); }
catch (InterruptedException ex) {throw new AssertionError(ex); }
long result=found.get();
System.out.println(result==Long.MAX_VALUE? "not found": result);

En mi máquina hace lo que esperaría de una ejecución paralela, que requiere sólo un poco más de ⟨sequential time⟩/⟨number of cpu cores⟩.Sin cambiar nada en tu fourConsecutives implementación.

La conclusión es que, al menos cuando procesar un solo artículo lleva mucho tiempo, la situación actual Stream implementación (o el marco subyacente Fork/Join) tiene problemas como ya discutido en esta pregunta relacionada.Si desea un paralelismo confiable, le recomendaría utilizar herramientas probadas y probadas. ExecutorServices.Como puede ver en mi ejemplo, esto no significa eliminar las funciones de Java 8, encajan bien.Sólo el paralelismo automatizado introducido con Stream.parallel debe usarse con cuidado (dada la implementación actual).

Answer 2

Podemos facilitar la ejecución en paralelo, pero no necesariamente podemos facilitar el paralelismo.

El culpable en su código es la combinación de límite+paralelo.Implementar limit() es trivial para flujos secuenciales, pero bastante costoso para flujos paralelos.Esto se debe a que la definición de la operación límite está ligada al orden de encuentro de la corriente.Las transmisiones con limit() suelen ser más lentas en paralelo que en secuencial, a menos que el cálculo realizado por elemento sea muy alto.

Su elección de fuente de transmisión también limita el paralelismo.Usando iterate(0, n->n+1) te da los números enteros positivos, pero iterate es fundamentalmente secuencial;no puedes calcular el enésimo elemento hasta que hayas calculado el (n-1)ésimo elemento.Entonces, cuando intentamos dividir esta corriente, terminamos dividiéndola (primero, descansa).Intenta usar range(0,k) en cambio;esto se divide mucho mejor, dividiéndose claramente por la mitad con acceso aleatorio.