Sempre devo usar um fluxo paralelo quando possível?

514

Com o Java 8 e lambdas, é fácil iterar sobre coleções como fluxos e tão fácil quanto usar um fluxo paralelo. Dois exemplos dos documentos , o 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()));

Desde que eu não me importe com a ordem, sempre seria benéfico usar o paralelo? Alguém poderia pensar que é mais rápido dividir o trabalho em mais núcleos.

Existem outras considerações? Quando o fluxo paralelo deve ser usado e quando o não paralelo deve ser usado?

(Esta pergunta é solicitada para iniciar uma discussão sobre como e quando usar fluxos paralelos, não porque eu acho que sempre usá-los seja uma boa idéia.)

Matsemann
fonte

Respostas:

736

Um fluxo paralelo tem uma sobrecarga muito maior em comparação com um sequencial. Coordenar os threads leva uma quantidade significativa de tempo. Eu usaria fluxos sequenciais por padrão e consideraria apenas os paralelos se

  • Tenho uma quantidade enorme de itens para processar (ou o processamento de cada item leva tempo e é paralelamente agradável)

  • Eu tenho um problema de desempenho em primeiro lugar

  • Eu ainda não executo o processo em um ambiente com vários threads (por exemplo: em um contêiner da Web, se eu já tiver muitas solicitações para processar em paralelo, adicionar uma camada adicional de paralelismo dentro de cada solicitação pode ter efeitos mais negativos do que positivos )

No seu exemplo, o desempenho será direcionado pelo acesso sincronizado a System.out.println(), e tornar esse processo paralelo não terá efeito, ou até mesmo negativo.

Além disso, lembre-se de que fluxos paralelos não solucionam magicamente todos os problemas de sincronização. Se um recurso compartilhado for usado pelos predicados e funções usados ​​no processo, você precisará garantir que tudo seja seguro para threads. Em particular, efeitos colaterais são coisas com as quais você realmente precisa se preocupar se for paralelo.

De qualquer forma, meça, não adivinhe! Apenas uma medida lhe dirá se o paralelismo vale a pena ou não.

JB Nizet
fonte
18
Boa resposta. Eu acrescentaria que, se você tiver uma quantidade enorme de itens para processar, isso só aumentará os problemas de coordenação de threads; é somente quando o processamento de cada item leva tempo e é paralelamente agradável que a paralelização possa ser útil.
perfil completo de Warren Dew
16
@WarrenDew Eu discordo. O sistema Fork / Join simplesmente dividirá os itens N em, por exemplo, 4 partes e processará essas 4 partes sequencialmente. Os 4 resultados serão reduzidos. Se maciço é realmente maciço, mesmo para o processamento rápido da unidade, a paralelização pode ser eficaz. Mas como sempre, você tem que medir.
JB Nizet
Eu tenho uma coleção de objetos que implementam Runnableque eu chamo start()para usá-los como Threads, está tudo bem mudar isso usando java 8 streams em um .forEach()paralelo? Então eu seria capaz de retirar o código do segmento da classe. Mas existem algumas desvantagens?
ycomp 5/06/16
1
@JBNizet Se 4 partes processam sequencialmente, então não há diferença de ser um processo paralelo ou saber sequencialmente? Pls esclarecer
Harshana
3
@Harshana, ele obviamente significa que os elementos de cada uma das 4 partes serão processados ​​sequencialmente. No entanto, as próprias peças podem ser processadas simultaneamente. Em outras palavras, se você tiver vários núcleos de CPU disponíveis, cada parte poderá executar em seu próprio núcleo, independentemente das outras partes, enquanto processa seus próprios elementos sequencialmente. (NOTA: Eu não sei, se é assim paralela Java córregos trabalho, eu só estou tentando esclarecer o que JBNizet significava.)
amanhã
258

A API Stream foi projetada para facilitar a gravação de cálculos de uma maneira que foi abstraída da maneira como eles seriam executados, facilitando a alternância entre seqüencial e paralelo.

No entanto, só porque é fácil, não significa que é sempre uma boa ideia e, de fato, é uma idéia simplesmente cair .parallel()por todo o lugar simplesmente porque você pode.

Primeiro, observe que o paralelismo não oferece outros benefícios além da possibilidade de execução mais rápida quando houver mais núcleos disponíveis. Uma execução paralela sempre envolverá mais trabalho do que seqüencial, porque além de resolver o problema, ela também deve executar o envio e a coordenação de subtarefas. A esperança é que você consiga chegar à resposta mais rapidamente, dividindo o trabalho em vários processadores; se isso realmente acontece depende de muitas coisas, incluindo o tamanho do seu conjunto de dados, quanta computação você está fazendo em cada elemento, a natureza da computação (especificamente, o processamento de um elemento interage com o processamento de outros?) , o número de processadores disponíveis e o número de outras tarefas que competem por esses processadores.

Além disso, observe que o paralelismo também frequentemente expõe o não determinismo na computação que geralmente é oculta por implementações seqüenciais; às vezes isso não importa ou pode ser mitigado restringindo as operações envolvidas (ou seja, os operadores de redução devem ser apátridas e associativos).

Na realidade, às vezes o paralelismo acelera a computação, às vezes não, e às vezes até diminui a velocidade. É melhor desenvolver primeiro usando a execução sequencial e depois aplicar o paralelismo onde

(A) você sabe que há realmente benefícios em aumentar o desempenho e

(B) que realmente proporcionará um desempenho aprimorado.

(A) é um problema comercial, não técnico. Se você é um especialista em desempenho, geralmente poderá analisar o código e determinar (B), mas o caminho inteligente é medir. (E nem se preocupe até que você esteja convencido de (A); se o código for rápido o suficiente, melhor aplicar seu cérebro a outros lugares.)

O modelo de desempenho mais simples para paralelismo é o modelo "NQ", em que N é o número de elementos e Q é o cálculo por elemento. Em geral, você precisa que o NQ do produto exceda algum limite antes de começar a obter um benefício de desempenho. Para um problema de baixa Q, como "some números de 1 a N", geralmente você verá um ponto de equilíbrio entre N = 1000 e N = 10000. Com problemas com Q mais alto, você verá interrupções em limites mais baixos.

Mas a realidade é bastante complicada. Portanto, até que você atinja a perícia, primeiro identifique quando o processamento seqüencial realmente está lhe custando algo e depois avalie se o paralelismo ajudará.

Brian Goetz
fonte
18
Este post dá mais detalhes sobre o modelo NQ: gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html
Pino
4
@specializt: interrupção de um fluxo a partir sequencial para paralelo faz mudar o algoritmo (na maioria dos casos). O determinismo mencionado aqui é sobre as propriedades nas quais seus operadores (arbitrários) podem confiar (a implementação do Stream não pode saber disso), mas é claro que não devem confiar. É o que a seção desta resposta tentou dizer. Se você se importa com as regras, pode ter um resultado determinístico, como você diz, (caso contrário, fluxos paralelos eram bastante inúteis), mas também há a possibilidade de não-determinismo permitido intencionalmente, como quando usar em findAnyvez de findFirst...
Holger
4
"Primeiro, observe que o paralelismo não oferece outros benefícios além da possibilidade de execução mais rápida quando houver mais núcleos disponíveis" - ou se você estiver aplicando uma ação que envolva IO (por exemplo myListOfURLs.stream().map((url) -> downloadPage(url))...).
Jules
6
@Pacerier Essa é uma teoria legal, mas infelizmente ingênua (veja o histórico de 30 anos de tentativas de criar compiladores com paralelismo automático para começar). Como não é prático adivinhar o tempo suficiente para não incomodar o usuário quando inevitavelmente erramos, a coisa responsável a fazer era apenas permitir que o usuário dissesse o que queria. Para a maioria das situações, o padrão (seqüencial) é correto e mais previsível.
Brian Goetz
2
@ Jules: nunca use fluxos paralelos para E / S. Eles são voltados exclusivamente para operações intensivas da CPU. Fluxos paralelos são usados ForkJoinPool.commonPool()e você não deseja que tarefas de bloqueio sejam executadas lá.
R2C2
68

Eu assisti a uma das apresentações de Brian Goetz (Java Language Architect e líder de especificação para Lambda Expressions) . Ele explica detalhadamente os quatro pontos a serem considerados antes de ir para a paralelização:

Custos de divisão / decomposição
- Às vezes, a divisão é mais cara do que apenas fazer o trabalho!
Custos de despacho / gerenciamento de tarefas
- pode fazer muito trabalho no tempo necessário para entregar o trabalho a outro encadeamento.
Custos da combinação de resultados
- Às vezes, a combinação envolve copiar muitos dados. Por exemplo, adicionar números é barato, enquanto a fusão de conjuntos é cara.
Localidade
- O elefante na sala. Este é um ponto importante que todos podem sentir falta. Você deve considerar falhas de cache, se uma CPU aguardar dados devido a falhas de cache, você não obterá nada por paralelização. É por isso que as fontes baseadas em array são paralelas às melhores, pois os próximos índices (próximos ao índice atual) são armazenados em cache e há menos chances de a CPU sofrer uma falha de cache.

Ele também menciona uma fórmula relativamente simples para determinar uma chance de aceleração paralela.

Modelo NQ :

N x Q > 10000

onde,
N = número de itens de dados
Q = quantidade de trabalho por item

Ram Patra
fonte
13

JB bateu na unha na cabeça. A única coisa que posso acrescentar é que o Java 8 não faz processamento paralelo puro, mas paraquencial . Sim, eu escrevi o artigo e faço F / J há trinta anos, então entendo a questão.

edharned
fonte
10
Os fluxos não são iteráveis ​​porque os fluxos fazem iteração interna em vez de externa. Essa é toda a razão para os fluxos de qualquer maneira. Se você tiver problemas com o trabalho acadêmico, a programação funcional pode não ser para você. Programação funcional === matemática === acadêmica. E não, o J8-FJ não está quebrado, é que a maioria das pessoas não lê o manual do f ******. Os documentos em java dizem muito claramente que não é uma estrutura de execução paralela. Essa é a razão de todas as coisas de spliterator. Sim, é acadêmico, sim, funciona se você souber usá-lo. Sim, deve ser mais fácil de usar um executor costume
Kr0e
1
O Stream possui um método iterator (), para que você possa iterá-los externamente, se desejar. Meu entendimento era que eles não implementam o Iterable porque você só pode usar esse iterador uma vez e ninguém pode decidir se isso está correto.
Trejkaz
14
para ser honesto: todo o seu artigo parece um discurso maciço e elaborado - e isso nega sua credibilidade ... eu recomendo refazê-lo com um tom muito menos agressivo, caso contrário, muitas pessoas não se incomodarão em lê-lo completamente. ... im apenas sayan
specializt
Algumas perguntas sobre o seu artigo ... em primeiro lugar, por que você aparentemente equipara estruturas de árvores balanceadas a gráficos acíclicos direcionados? Sim, árvores balanceadas são DAGs, mas também listas vinculadas e praticamente toda estrutura de dados orientada a objetos que não sejam matrizes. Além disso, quando você diz que a decomposição recursiva só funciona em estruturas de árvores equilibradas e, portanto, não é relevante comercialmente, como você justifica essa afirmação? Parece-me (reconhecidamente, sem realmente examinar o assunto em profundidade) que deveria funcionar tão bem em estruturas de dados baseadas em array, por exemplo, ArrayList/ HashMap.
Jules
1
Esta discussão é de 2013, muita coisa mudou desde então. Esta seção é para comentários, respostas não detalhadas.
Edharned
3

Outras respostas já abordaram a criação de perfil para evitar otimização prematura e custos indiretos no processamento paralelo. Esta resposta explica a escolha ideal de estruturas de dados para streaming paralelo.

Como regra geral, os ganhos de desempenho de paralelismo são melhores em fluxos mais ArrayList, HashMap, HashSet, e ConcurrentHashMapcasos; matrizes; intgamas; e longintervalos. O que essas estruturas de dados têm em comum é que todas podem ser divididas com precisão e baixo custo em subfaixas dos tamanhos desejados, o que facilita a divisão do trabalho entre encadeamentos paralelos. A abstração usada pela biblioteca de fluxos para executar esta tarefa é o spliterator, retornado pelo spliteratormétodo on Streame Iterable.

Outro fator importante que todas essas estruturas de dados têm em comum é que elas fornecem localidade de referência boa a excelente quando processadas sequencialmente: as referências de elementos seqüenciais são armazenadas juntas na memória. Os objetos referidos por essas referências podem não estar próximos um do outro na memória, o que reduz a localidade de referência. A localidade de referência acaba sendo extremamente importante para paralelizar operações em massa: sem ela, os encadeamentos passam grande parte do tempo ociosos, aguardando a transferência de dados da memória para o cache do processador. As estruturas de dados com a melhor localidade de referência são matrizes primitivas porque os próprios dados são armazenados contiguamente na memória.

Fonte: Item # 48 Tenha cuidado ao criar fluxos paralelos e eficazes em Java 3e por Joshua Bloch

ruhong
fonte
2

Nunca paralelize um fluxo infinito com um limite. Aqui está o que acontece:

    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 ...

Mesmo se você usar .limit(...)

Explicação aqui: Java 8, usando .parallel em um fluxo causa erro de OOM

Da mesma forma, não use paralelo se o fluxo for ordenado e tiver muito mais elementos do que você deseja processar, por exemplo

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());
}

Isso pode demorar muito mais, porque os encadeamentos paralelos podem funcionar em vários intervalos de números, em vez do crucial, de 0 a 100, fazendo com que isso demore muito tempo.

tkruse
fonte