Tecnicamente, por que os processos em Erlang são mais eficientes que os threads do SO?

170

Características de Erlang

Da Programação Erlang (2009):

A simultaneidade de Erlang é rápida e escalável. Seus processos são leves, pois a máquina virtual Erlang não cria um encadeamento do SO para cada processo criado. Eles são criados, agendados e manipulados na VM, independentemente do sistema operacional subjacente. Como resultado, o tempo de criação do processo é da ordem de microssegundos e independente do número de processos existentes simultaneamente. Compare isso com Java e C #, onde para cada processo é criado um encadeamento do SO subjacente: você obterá comparações muito competitivas, com o Erlang superando muito as duas linguagens.

Da programação orientada à concorrência em Erlang (pdf) (slides) (2003):

Observamos que o tempo necessário para criar um processo Erlang é constante de 1µs a 2.500 processos; depois disso, aumenta para cerca de 3 µs para até 30.000 processos. O desempenho do Java e C # é mostrado na parte superior da figura. Para um pequeno número de processos, são necessários cerca de 300 µs para criar um processo. Criar mais de dois mil processos é impossível.

Vemos que, para até 30.000 processos, o tempo para enviar uma mensagem entre dois processos Erlang é de cerca de 0,8µs. Para C #, são necessários cerca de 50 µs por mensagem, até o número máximo de processos (que eram cerca de 1800 processos). O Java foi ainda pior: para até 100 processos, foram necessários cerca de 50µs por mensagem; depois, aumentou rapidamente para 10ms por mensagem, quando havia cerca de 1000 processos Java.

Meus pensamentos

Não entendo tecnicamente completamente por que os processos Erlang são muito mais eficientes na geração de novos processos e têm pegadas de memória muito menores por processo. O SO e a Erlang VM precisam fazer agendamento, alternar o contexto e acompanhar os valores nos registros e assim por diante ...

Simplesmente por que os threads do SO não são implementados da mesma maneira que os processos em Erlang? Eles têm que apoiar algo mais? E por que eles precisam de uma maior pegada de memória? E por que eles têm reprodução e comunicação mais lentas?

Tecnicamente, por que os processos em Erlang são mais eficientes do que os threads do SO quando se trata de geração e comunicação? E por que os threads no sistema operacional não podem ser implementados e gerenciados da mesma maneira eficiente? E por que os threads do sistema operacional têm uma maior área de armazenamento de memória, além de geração e comunicação mais lentas?

Mais leitura

multithreading erlang green-threads lightweight-processes Jonas
fonte
1
Antes de tentar entender o motivo pelo qual uma hipótese é verdadeira, você precisa estabelecer se a hipótese é verdadeira - por exemplo, apoiada na evidência. Você tem referências para comparações semelhantes para demonstrar que um processo Erlang é realmente mais eficiente do que (digamos) um encadeamento Java em uma JVM atualizada? Ou um aplicativo C usando o processo do SO e o suporte a threads diretamente? (O último parece muito, muito improvável para mim. O primeiro apenas um pouco provável.) Quero dizer, com um ambiente bastante limitado (ponto de Francisco), pode ser verdade, mas eu gostaria de ver os números.
TJ Crowder
1
@Donal: Como é o caso de tantas outras declarações absolutas. :-)
TJ Crowder
1
@ Jonas: Obrigado, mas cheguei até a data (02/11/1998) e a versão da JVM (1.1.6) e parei. A JVM da Sun melhorou bastante nos últimos 11,5 anos (e presumivelmente o intérprete de Erlang também), principalmente na área de segmentação. (Só para esclarecer, não estou dizendo que a hipótese não seja verdadeira [e Francisco e Donal apontaram por que Erland pode ser capaz de fazer alguma coisa lá]); estou dizendo que não deve ser tomada pelo valor de face sem ser verificado.)
TJ Crowder
1
@Jonas: "... mas eu acho que você pode fazer isso em Erlang ..." É essa parte do "palpite", cara. :-) Você está adivinhando que o processo de Erlang muda além dos milhares. Você está supondo que o desempenho seja melhor do que os encadeamentos Java ou OS. Adivinhar e desenvolvedor de software não são uma ótima combinação. :-) Mas acho que fiz o meu ponto.
TJ Crowder
17
@TJ Crowder: instale erlang e execute erl +P 1000100 +hms 100e digite {_, PIDs} = timer:tc(lists,map,[fun(_)->spawn(fun()->receive stop -> ok end end) end, lists:seq(1,1000000)]).e espere cerca de três minutos para obter o resultado. Isso é tão simples. São necessários 140us por processo e 1 GB de RAM inteira no meu laptop. Mas é diretamente do shell, deve ser melhor do código compilado.
Hynek -Pichi- Vychodil

Respostas:

113

Existem vários fatores contribuintes:

  1. Os processos Erlang não são processos do SO. Eles são implementados pela Erlang VM usando um modelo de threading cooperativo leve (preventivo no nível Erlang, mas sob o controle de um tempo de execução agendado cooperativamente). Isso significa que é muito mais barato alternar o contexto, porque eles alternam apenas em pontos conhecidos e controlados e, portanto, não precisam salvar todo o estado da CPU (normal, registradores SSE e FPU, mapeamento do espaço de endereço etc.).
  2. Os processos Erlang usam pilhas alocadas dinamicamente, que começam muito pequenas e crescem conforme necessário. Isso permite a geração de muitos milhares - até milhões - de processos Erlang sem consumir toda a RAM disponível.
  3. Erlang costumava ser de rosca única, o que significa que não havia requisitos para garantir a segurança da rosca entre os processos. Agora ele suporta SMP, mas a interação entre os processos Erlang no mesmo planejador / núcleo ainda é muito leve (existem filas de execução separadas por núcleo).
Marcelo Cantos
fonte
6
Para o seu segundo ponto: e se o processo ainda não foi executado, não há razão para ter uma pilha alocada para ele. Além disso: vários truques podem ser executados brincando com o GC de um processo para que ele nunca colete memória. Mas isso é avançado e um tanto perigoso :) #
DU RESPOSTAS DE EXCREMENTO
3
Para seu terceiro ponto: Erlang impõe dados imutáveis, portanto, a introdução do SMP não deve afetar a segurança do encadeamento.
Nskp 14/03/12
@ nilskp, isso mesmo, erlang também é uma linguagem de programação funcional. Portanto, não há dados "variáveis". isso leva à segurança do thread.
Liuyang1
6
@nilskp: (RE: você comenta o ponto 3…) Embora a própria linguagem possua um sistema de tipos imutável, a implementação subjacente - passagem de mensagens, agendador etc. - é uma história completamente diferente. O suporte SMP correto e eficiente não aconteceu apenas com o apertar de um botão.
Marcelo Cantos
@rvirding: Obrigado pelo adendo esclarecedor. Tomei a liberdade de integrar seus pontos no corpo da minha resposta.
Marcelo Cantos
73

Depois de mais algumas pesquisas, encontrei uma apresentação de Joe Armstrong.

De Erlang - software para um mundo simultâneo (apresentação) (aos 13 min):

[Erlang] é uma linguagem simultânea - com isso quero dizer que os threads fazem parte da linguagem de programação, eles não pertencem ao sistema operacional. Isso é realmente o que há de errado com linguagens de programação como Java e C ++. Seus threads não estão na linguagem de programação, os threads são algo no sistema operacional - e eles herdam todos os problemas que eles têm no sistema operacional. Um dos problemas é a granularidade do sistema de gerenciamento de memória. O gerenciamento de memória no sistema operacional protege páginas inteiras de memória; portanto, o menor tamanho que um encadeamento pode ter é o menor tamanho de uma página. Isso é realmente muito grande.

Se você adicionar mais memória à sua máquina - você tem o mesmo número de bits que protege a memória e, portanto, aumenta a granularidade das tabelas de páginas - você acaba usando, digamos, 64kB para um processo que você sabe executando em algumas centenas de bytes.

Eu acho que responde, se não todas, pelo menos algumas das minhas perguntas

Jonas
fonte
2
Veja também: stackoverflow.com/questions/2267545/…
Jonas
2
A proteção de memória nas pilhas existe por um motivo. Erlang simplesmente não protege as pilhas de diferentes contextos de execução através da MMU do processador? (E apenas espero o melhor?) E se um thread usar mais do que sua pequena pilha? (São todas as alocações de pilha verificados para ver se uma pilha maior é necessário é a móvel pilha?)
Thanatos
2
@Thanatos: Erlang não permite que programas acessem memória ou mexam com a pilha. Todas as alocações devem passar pelo tempo de execução gerenciado, heap e stack. Em outras palavras: a proteção de hardware é inútil porque protege contra coisas que não podem acontecer de qualquer maneira. O idioma é seguro para ponteiro, pilha, memória e tipo. Um processo não pode usar mais do que sua "pequena pilha" porque a pilha cresce conforme necessário. Você pode pensar nisso como o oposto de minúsculo: infinitamente grande. (Mas preguiçosamente alocado.)
Jörg W Mittag
4
Você deve dar uma olhada no sistema operacional Singularity da Microsoft Research. No Singularity, todos os códigos, kernel, drivers de dispositivo, bibliotecas e programas do usuário são executados no anel 0 com privilégios completos do kernel. Todo o código, kernel, drivers de dispositivo, bibliotecas e programas do usuário são executados em um único espaço de endereço físico plano, sem proteção de memória. A equipe descobriu que as garantias oferecidas pelo idioma são muito mais fortes do que as garantias que a MMU pode oferecer e, ao mesmo tempo, o uso da MMU lhes custa até 30% (!!!) em desempenho. Então, por que usar o MMU se o seu idioma já faz assim mesmo?
Jörg W Mittag
1
O sistema operacional OS / 400 funciona da mesma maneira. Existe apenas um espaço de endereço simples para todos os programas. Atualmente, a maioria das linguagens atualmente em uso tem as mesmas propriedades de segurança (ECMAScript, Java, C♯, VB.NET, PHP, Perl, Python, Ruby, Clojure, Scala, Kotlin, Groovy, Ceilão, F♯, OCaml, o Parte "Objective" de "Objective-C", a parte "++" de "C ++"). Se não fosse o código C legado e os recursos herdados de C ++ e Objective-C, não precisaríamos mais de memória virtual.
Jörg W Mittag
47

Eu implementei corotinas no assembler e medi o desempenho.

A alternância entre corotinas, também conhecidas como processos Erlang, leva cerca de 16 instruções e 20 nanossegundos em um processador moderno. Além disso, você costuma conhecer o processo para o qual está mudando (exemplo: um processo que recebe uma mensagem em sua fila pode ser implementado como transferência direta do processo de chamada para o processo de recebimento) para que o planejador não entre em ação, tornando é uma operação O (1).

Para alternar os threads do sistema operacional, leva de 500 a 1000 nanossegundos, porque você está ligando para o kernel. O planejador de encadeamentos do SO pode ser executado no tempo O (log (n)) ou O (log (log (n))), que começará a ser perceptível se você tiver dezenas de milhares ou até milhões de encadeamentos.

Portanto, os processos Erlang são mais rápidos e escalam melhor porque a operação fundamental da troca é mais rápida e o agendador é executado com menos frequência.

Surfista Jeff
fonte
33

Os processos Erlang correspondem (aproximadamente) a linhas verdes em outros idiomas; não há separação imposta pelo sistema operacional entre os processos. (Pode haver uma separação imposta pelo idioma, mas essa é uma proteção menor, apesar de Erlang fazer um trabalho melhor do que a maioria.) Por serem muito mais leves, podem ser usados ​​com muito mais intensidade.

Os threads do sistema operacional, por outro lado, podem ser simplesmente agendados em diferentes núcleos da CPU e (principalmente) são capazes de oferecer suporte ao processamento independente da CPU. Os processos do SO são como threads do SO, mas com uma separação imposta pelo SO muito mais forte. O preço desses recursos é que os threads do sistema operacional e (ainda mais) os processos são mais caros.

Outra maneira de entender a diferença é essa. Supondo que você fosse escrever uma implementação do Erlang no topo da JVM (não uma sugestão particularmente louca), faria com que cada processo do Erlang fosse um objeto com algum estado. Você teria um conjunto de instâncias do Thread (normalmente dimensionadas de acordo com o número de núcleos no sistema host; esse é um parâmetro ajustável nos tempos de execução reais do Erlang, entre outros), que executa os processos do Erlang. Por sua vez, isso distribuirá o trabalho a ser realizado pelos recursos reais do sistema disponíveis. É uma maneira bem legal de fazer as coisas, mas depende totalmenteno fato de que cada processo Erlang individual não faz muito. Tudo bem, é claro; Erlang está estruturado para não exigir que esses processos individuais sejam pesados, pois é o conjunto geral deles que executa o programa.

De muitas maneiras, o problema real é o da terminologia. As coisas que Erlang chama de processos (e que correspondem fortemente ao mesmo conceito no CSP, CCS e, particularmente, no cálculo π) simplesmente não são as mesmas que as linguagens com herança C (incluindo C ++, Java, C # e muitos outros) chamam um processo ou um encadeamento. Existem algumas semelhanças (todas envolvem alguma noção de execução simultânea), mas definitivamente não há equivalência. Portanto, tenha cuidado quando alguém lhe disser "processo"; eles podem entender que isso significa algo totalmente diferente ...

Donal Fellows
fonte
3
Erlang não chega nem perto do Pi Calculus. O cálculo do pi assume eventos síncronos sobre canais que podem ser vinculados a variáveis. Esse tipo de conceito não se encaixa no modelo de Erlang. Tente Join Calculus, Erlang está mais próximo disso, embora ainda precise ser capaz de juntar-se nativamente a algumas mensagens e outros enfeites. Havia um trabalho de tese (e projeto) chamado JErlang dedicado que o implementou.
DUO CONSELHO TERRÍVEL
Tudo depende do que exatamente você visualiza o cálculo pi (e você pode modelar canais assíncronos com canais síncronos e processos de buffer).
Donal Fellows
Você está apenas dizendo que os processos Erlang são leves, mas não estão explicando por que eles têm um espaço menor (são leves) e por que eles têm melhor desempenho do que os threads do SO.
Jonas
1
@ Jonas: Para alguns tipos de tarefas (principalmente tarefas pesadas em computação), os threads do SO se saem melhor. Lembre-se, normalmente não são tarefas para as quais Erlang é usado; Erlang está focado em ter um grande número de tarefas simples de comunicação. Um dos ganhos disso é que, no caso de um grupo de tarefas que entrega uma parte do trabalho e aguarda o resultado, tudo isso pode ser feito em um único encadeamento do SO em um único processador, o que é mais eficiente do que tendo opções de contexto.
Donal Fellows
Teoricamente, você também pode fazer com que um encadeamento do SO seja muito barato usando uma pilha muito pequena e controlando cuidadosamente o número de outros recursos específicos do encadeamento alocados, mas isso é bastante problemático na prática. (Prever requisitos de pilha é um pouco de arte negra.) Portanto, os encadeamentos do SO são especialmente projetados para serem ideais no caso em que há menos deles (da ordem do número de núcleos da CPU) e em que eles são mais significativos quantidades de processamento cada.
Donal Fellows
3

Acho que o Jonas queria alguns números na comparação de threads do sistema operacional com os processos Erlang. O autor da programação de Erlang, Joe Armstrong, testou há um tempo a escalabilidade da geração dos processos Erlang nos threads do sistema operacional. Ele escreveu um servidor Web simples em Erlang e o testou contra o Apache com vários threads (já que o Apache usa threads do SO). Há um site antigo com dados que remontam a 1998. Eu consegui encontrar esse site exatamente uma vez. Portanto, não posso fornecer um link. Mas a informação está lá fora. O ponto principal do estudo mostrou que o Apache atingiu o máximo de menos de 8 mil processos, enquanto o servidor Erlang escrito manualmente lidava com 10 mil + processos.

Jurnell
fonte
5
Acho que você está falando sobre isso: sics.se/~joe/apachevsyaws.html Mas perguntei como o erlang torna os threads tão eficientes em comparação aos threads do kerlenl.
Jonas
O link @Jonas está morto. O último instantâneo está aqui
alvaro g
1
O artigo dizia: "O Apache morre em cerca de 4.000 sessões paralelas. O Yaws ainda está funcionando em mais de 80.000 conexões paralelas".
Nathan Long
veja o artigo completo em citeseerx.ist.psu.edu/viewdoc/… De fato, foi impossível interromper o servidor Erlang usando 16 máquinas atacantes - embora fosse fácil parar o servidor Apache.
Bernhard
1

Como o intérprete Erlang precisa se preocupar apenas com ele, o sistema operacional tem muitas outras coisas com que se preocupar.

Francisco Soto
fonte
0

um dos motivos é que o processo erlang é criado não no sistema operacional, mas na evm (máquina virtual erlang), portanto, o custo é menor.

ratzily
fonte