Por que usar mais encadeamentos torna mais lento do que usar menos encadeamentos

Question

Tentou executar o programa X usando 8 threads e acabou em n minutos .
Tentei executar o mesmo programa usando 50 threads e terminou em n * 10 minutos .

Por que isso acontece e como posso obter o número ideal de threads que posso usar?

    

Answer 1

Esta é uma pergunta complicada que você está fazendo. Sem saber mais sobre a natureza dos seus tópicos, é difícil dizer. Algumas coisas a considerar ao diagnosticar o desempenho do sistema:

É o processo / thread

• CPU ligado (precisa de muitos recursos da CPU)
• Limite de memória (precisa de muitos recursos de RAM)
• Limite de E / S (recursos de rede e / ou disco rígido)

Todos esses três recursos são finitos e qualquer um pode limitar o desempenho de um sistema. Você precisa analisar quais (talvez 2 ou 3 juntas) sua situação específica está consumindo.

Você pode usar ntop e iostat e vmstat para diagnosticar o que está acontecendo.

    

Answer 2

"Por que isso acontece?" é fácil de responder. Imagine que você tem um corredor para acomodar quatro pessoas, lado a lado. Você quer mover todo o lixo de um lado para o outro. O número mais eficiente de pessoas é 4.

Se você tem 1-3 pessoas, então você está perdendo algum espaço no corredor. Se você tem 5 ou mais pessoas, pelo menos uma dessas pessoas está basicamente presa atrás de outra pessoa o tempo todo. Adicionando mais e mais pessoas simplesmente entope o corredor, isso não acelera a atividade.

Assim, você quer ter o maior número de pessoas possível sem causar filas. Por que você tem filas (ou gargalos) depende das perguntas na resposta do slm.

    

Answer 3

Uma recomendação comum é n + 1 threads, sendo n o número de núcleos de CPU disponíveis. Dessa forma, n encadeamentos podem trabalhar a CPU enquanto 1 encadeamento aguarda a E / S de disco. Ter menos encadeamentos não utilizaria totalmente o recurso da CPU (em algum momento sempre haveria E / S para aguardar), ter mais encadeamentos faria com que as encadeamentos disputassem o recurso da CPU.

Threads não são gratuitos, mas com overhead como switches de contexto, e - se os dados precisam ser trocados entre threads, o que geralmente é o caso - vários mecanismos de bloqueio. Isso só vale o custo quando você realmente tem mais núcleos de CPU dedicados para executar o código. Em uma CPU de núcleo único, um único processo (sem encadeamentos separados) é geralmente mais rápido do que qualquer encadeamento feito. Threads não fazem sua CPU magicamente ir mais rápido, apenas significa trabalho extra.

    

Answer 4

Como outros apontaram ( resposta slm , Resposta do EightBitTony ) esta é uma pergunta complicada e mais ainda, já que você não descreve o que você fez e como eles fazem isso.

Mas jogar definitivamente mais tópicos pode piorar as coisas.

No campo da computação paralela, há a lei de Amdahl que pode ser aplicável (ou não, mas você não não descreva os detalhes do seu problema, então ...) e pode dar uma visão geral sobre essa classe de problemas.

O ponto da lei de Amdahl é que em qualquer programa (em qualquer algoritmo) há sempre uma porcentagem que não pode ser executada em paralelo (a porção sequencial ) e há outra porcentagem que pode ser executada em paralelo (a porção paralela ) [Obviamente estas duas partes se somam para 100%].

Essas partes podem ser expressas como uma porcentagem do tempo de execução. Por exemplo, pode haver 25% do tempo gasto em operações estritamente seqüenciais, e os 75% restantes do tempo são gastos em operações que podem ser executadas em paralelo.

(Imagemde Wikipedia )

A lei de Amdahl prevê que para cada porção paralela (por exemplo, 75%) de um programa você só pode acelerar a execução até o momento (por exemplo, no máximo 4 vezes) mesmo se usar mais e mais processadores para fazer o trabalho. / p>

Como regra geral, quanto mais programas você não puder transformar em execução paralela, menos poderá obter usando mais unidades de execução (processadores).

Dado que você está usando threads (e não processadores físicos), a situação pode ser ainda pior do que isso. Lembre-se que os threads podem ser processados (dependendo da implementação e do hardware disponível, por exemplo, CPUs / Cores) compartilhando o mesmo processador / núcleo físico (é uma forma de multitarefa, como apontado em outra resposta).

Esta predição teorética (sobre tempos de CPU) não considera outros gargalos práticos como

1. Velocidade limitada de E / S (disco rígido e velocidade de rede)
2. Limites de tamanho da memória
3. Outros

que pode ser facilmente o fator limitante em aplicações práticas.

    

Answer 5

O culpado aqui deve ser o "CONTEXTO SWITCHING". É o processo de salvar o estado do thread atual para iniciar a execução de outro thread. Se um número de threads receber a mesma prioridade, eles precisarão ser alternados até concluir a execução.

No seu caso, quando há 50 threads, ocorre muita troca de contexto quando comparado a apenas 10 threads.

Esta sobrecarga de tempo introduzida por causa da troca de contexto é o que faz com que seu programa seja executado com lentidão

    

Answer 6

Para corrigir a metáfora do EightBitTony:

"Why does this happen?" is kind of easy to answer. Imagine you have two swimming pools, one full and one empty. You want to move all the water from one to the other, and have 4 buckets. The most efficient number of people is 4.

If you have 1-3 people then you're missing out on using some buckets. If you have 5 or more people, then at least one of those people is stuck waiting for a bucket. Adding more and more people ... doesn't speed up the activity.

So you want to have as many people as can do some work (use a bucket) simultaneously.

Uma pessoa aqui é um thread e um bucket representa qualquer recurso de execução que seja o gargalo. Adicionando mais tópicos não ajuda se eles não podem fazer nada. Além disso, devemos enfatizar que passar um balde de uma pessoa para outra é normalmente mais lento do que uma única pessoa carregando apenas o balde na mesma distância. Ou seja, dois segmentos que se revezam em um núcleo normalmente realizam menos trabalho do que um único segmento executando o dobro do tempo: isso é devido ao trabalho extra feito para alternar entre os dois segmentos.

Se o recurso de execução limitante (bucket) é uma CPU, ou um núcleo, ou um pipeline de instrução hyper-threaded para seus propósitos depende de qual parte da arquitetura é o seu fator limitante. Note também que estamos assumindo que os threads são inteiramente independentes. Este é apenas o caso se eles compartilham dados não (e evitam colisões de cache).

Como algumas pessoas sugeriram, para E / S, o recurso de limitação pode ser o número de operações de E / S que podem ser executadas em fila: isso pode depender de vários fatores de hardware e kernel, mas pode ser muito maior que o número de núcleos. Aqui, a troca de contexto, que é tão cara quando comparada ao código de execução, é bem barata se comparada ao código de entrada / saída. Infelizmente eu acho que a metáfora vai ficar completamente fora de controle se eu tentar justificar isso com baldes.

Note que o comportamento óptimo com código I / O é normalmente ainda para ter no máximo um thread por pipeline / core / CPU. No entanto, você precisa escrever um código de E / S assíncrono ou síncrono / não-bloqueador, e o aprimoramento de desempenho relativamente pequeno nem sempre justificará a complexidade extra.

PS. Meu problema com a metáfora original do corredor é que ela sugere strongmente que você deve ter 4 filas de pessoas, com 2 filas carregando lixo e 2 retornando para coletar mais. Então você pode tornar cada fila quase tão longa quanto o corredor, e adicionar pessoas fez acelerar o algoritmo (você basicamente transformou todo o corredor em uma esteira).

Na verdade, esse cenário é muito semelhante à descrição padrão da relação entre a latência e o tamanho da janela na rede TCP, e é por isso que ela se sobressaltou em mim.

    

Answer 7

É bastante simples e simples de entender. Tendo mais threads suportados pela sua CPU, você está realmente serializando e não fazendo paralelismo. Quanto mais threads você tiver, mais lento será o seu sistema. Seus resultados são, na verdade, uma prova desse fenômeno.