Java 8 transmite desempenho serial vs paralelo

Question

Na minha máquina, o programa abaixo imprime:

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

Não está claro por que executar o programa em série é mais rápido do que executá-lo em paralelo.Eu dei os dois programas -Xms2g -Xmx2g em um 8gb caixa que é relativamente silenciosa.Alguém pode esclarecer o que está acontecendo?

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

Embora Brian Goetz esteja certo sobre sua configuração, por ex.que você deve usar .range(1, 1000000) em vez de .iterate(1, n -> n + 1).limit(1000000) e que seu método de benchmark é muito simplista, quero enfatizar um ponto importante:

mesmo depois de corrigir esses problemas, mesmo usando um relógio de parede e o TaskManager você pode ver que há algo errado.Na minha máquina a operação leva cerca de meio minuto e você pode ver que o paralelismo cai para núcleo único após cerca de dois segundos.Mesmo que uma ferramenta de benchmark especializada pudesse produzir resultados diferentes, isso não faria diferença, a menos que você queira executar seu aplicativo final dentro de uma ferramenta de benchmark o tempo todo…

Agora poderíamos tentar zombar mais sobre sua configuração ou dizer que você deve aprender coisas especiais sobre a estrutura Fork/Join, como o implementadores fizeram na lista de discussão.

Ou tentamos uma implementação 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);

Na minha máquina, ele faz o que eu esperaria da execução paralela, demorando apenas um pouco mais do que ⟨sequential time⟩/⟨number of cpu cores⟩.Sem mudar nada em seu fourConsecutives implementação.

O resultado final é que, pelo menos quando o processamento de um único item leva um tempo significativo, o atual Stream implementação (ou a estrutura Fork/Join subjacente) tem problemas como já discutido nesta questão relacionada.Se você deseja paralelismo confiável, eu recomendaria usar métodos comprovados e testados ExecutorServiceS.Como você pode ver no meu exemplo, isso não significa abandonar os recursos do Java 8, eles se encaixam bem.Somente o paralelismo automatizado introduzido com Stream.parallel deve ser usado com cuidado (dada a implementação atual).

Answer 2

Podemos facilitar a execução em paralelo, mas não podemos necessariamente facilitar o paralelismo.

O culpado do seu código é a combinação de limite + paralelo.A implementação de limit() é trivial para fluxos sequenciais, mas bastante cara para fluxos paralelos.Isso ocorre porque a definição da operação limite está vinculada à ordem de encontro do fluxo.Streams com limit() costumam ser mais lentos em paralelo do que em sequencial, a menos que o cálculo feito por elemento seja muito alto.

A escolha da fonte do fluxo também limita o paralelismo.Usando iterate(0, n->n+1) fornece os números inteiros positivos, mas iterate é fundamentalmente sequencial;você não pode calcular o enésimo elemento até ter calculado o (n-1)-ésimo elemento.Então, quando tentamos dividir esse fluxo, acabamos dividindo (primeiro, descanse).Tente usar range(0,k) em vez de;isso se divide muito melhor, dividindo-se perfeitamente ao meio com acesso aleatório.