Por que Haskell (GHC) é tão rápido?

246

Haskell (com o GHCcompilador) é muito mais rápido do que você esperaria . Quando usado corretamente, ele pode aproximar-se dos idiomas de baixo nível. (O que os Haskellers preferem fazer é tentar chegar a 5% de C (ou até superá-lo, mas isso significa que você está usando um programa C ineficiente, já que o GHC compila Haskell para C).) Minha pergunta é: por quê?

Haskell é declarativo e baseado no cálculo lambda. Arquiteturas de máquinas são claramente imperativas, baseando-se em máquinas de turing, aproximadamente. De fato, Haskell nem sequer tem uma ordem de avaliação específica. Além disso, em vez de lidar com tipos de dados de máquina, você cria tipos de dados algébricos o tempo todo.

O mais estranho de tudo é que as funções de ordem superior. Você pensaria que criar funções dinamicamente e jogá-las ao redor tornaria um programa mais lento. Mas o uso de funções de ordem superior realmente torna o Haskell mais rápido. De fato, parece que, para otimizar o código Haskell, você precisa torná-lo mais elegante e abstrato, em vez de mais parecido com uma máquina. Nenhum dos recursos mais avançados de Haskell parece afetar seu desempenho, se não o melhorar.

Desculpe se isso está soando seguro, mas eis a minha pergunta: por que o Haskell (compilado com o GHC) é tão rápido, considerando sua natureza abstrata e suas diferenças em relação às máquinas físicas?

Nota: O motivo pelo qual digo C e outras linguagens imperativas são um pouco semelhantes às Máquinas de Turing (mas não na medida em que Haskell é semelhante ao Cálculo Lambda) é que, em uma linguagem imperativa, você tem um número finito de estados (também conhecido como número de linha) , junto com uma fita (a ram), de modo que o estado e a fita atual determinem o que fazer com a fita. Veja a entrada da Wikipedia, equivalentes de máquinas de Turing , para a transição de máquinas de Turing para computadores.

PyRulez
fonte
27
"desde que o GHC compila Haskell para C" - isso não acontece. O GHC possui vários back-ends. O mais antigo (mas não o padrão) é um gerador C. Ele gera código Cmm para IR, mas isso não é "compilar para C" que você normalmente esperaria. ( downloads.haskell.org/~ghc/latest/docs/html/users_guide/… )
viraptor
19
Eu recomendo a leitura de Implementation of Functional Programming Languages, de Simon Payton Jones (o principal implementador do GHC), que responderá a muitas de suas perguntas.
precisa saber é o seguinte
94
Por quê? 25 anos de trabalho duro.
Aug
31
"Embora possa haver uma resposta factual, ela não fará nada além de solicitar opiniões". - Esse é o pior motivo possível para encerrar uma pergunta. Porque pode ter uma boa resposta, mas potencialmente também atrairá respostas de baixa qualidade. Que nojo! Por acaso, tenho uma boa resposta histórica, factual, alinhada sobre a pesquisa acadêmica e quando certos desenvolvimentos aconteceram. Mas não posso publicá-lo porque as pessoas estão preocupadas com essa pergunta também pode atrair respostas de baixa qualidade. Mais uma vez, eca.
SCLV
7
@cimmanon Eu precisaria de um mês ou várias postagens no blog para ver os detalhes básicos de como um compilador funcional funciona. Eu só preciso de uma resposta SO a esboçar em linhas gerais como uma máquina de gráfico pode ser implementado de forma limpa em hardware estoque e apontam para as fontes relevantes para leitura ...
SCLV

Respostas:

264

Eu concordo com Dietrich Epp: é uma combinação de várias coisas que tornam o GHC rápido.

Em primeiro lugar, Haskell é de alto nível. Isso permite que o compilador execute otimizações agressivas sem quebrar seu código.

Pense em SQL. Agora, quando escrevo uma SELECTdeclaração, pode parecer um loop imperativo, mas não é . Pode parecer que ele faz loop em todas as linhas da tabela tentando encontrar a que corresponde às condições especificadas, mas, na verdade, o "compilador" (o mecanismo do DB) poderia estar fazendo uma pesquisa de índice - que possui características de desempenho completamente diferentes. Mas como o SQL é de alto nível, o "compilador" pode substituir algoritmos totalmente diferentes, aplicar múltiplos processadores ou canais de E / S ou servidores inteiros de forma transparente e muito mais.

Penso em Haskell como sendo o mesmo. Você pode pensar que acabou de pedir ao Haskell para mapear a lista de entrada para uma segunda lista, filtrar a segunda para uma terceira e depois contar quantos itens resultaram. Mas você não viu o GHC aplicar regras de reescrita de fusão por fluxo nos bastidores, transformando tudo em um único loop de código de máquina que faz todo o trabalho em uma única passagem pelos dados sem alocação - o tipo de coisa que seria ser entediante, propenso a erros e insustentável para escrever à mão. Isso só é realmente possível devido à falta de detalhes de baixo nível no código.

Outra maneira de ver isso pode ser ... por que Haskell não deveria ser rápido? O que faz isso deve torná-lo lento?

Não é uma linguagem interpretada como Perl ou JavaScript. Nem sequer é um sistema de máquina virtual como Java ou C #. Ele compila todo o caminho até o código de máquina nativo, portanto não há sobrecarga lá.

Diferente das linguagens OO [Java, C #, JavaScript…], o Haskell possui apagamento total do tipo [como C, C ++, Pascal…]. Toda a verificação de tipo ocorre apenas em tempo de compilação. Portanto, não há verificação de tipo em tempo de execução para atrasar você. (Nenhuma verificação de ponteiro nulo, nesse caso. Em Java, por exemplo, a JVM deve verificar ponteiros nulos e lançar uma exceção se você deferir um. Haskell não precisa se preocupar com essa verificação.)

Você diz que parece lento "criar funções dinamicamente em tempo de execução", mas se você observar com muito cuidado, na verdade não fará isso. Pode parecer que você faz, mas você não. Se você diz (+5), bem, isso está codificado no seu código-fonte. Não pode ser alterado no tempo de execução. Portanto, não é realmente uma função dinâmica. Até funções com curry estão realmente apenas salvando parâmetros em um bloco de dados. Todo o código executável realmente existe em tempo de compilação; não há interpretação em tempo de execução. (Diferente de outros idiomas que possuem uma "função eval").

Pense em Pascal. É velho e ninguém mais o usa, mas ninguém iria reclamar que Pascal é lento . Há muitas coisas para não gostar, mas a lentidão não é realmente uma delas. Haskell não está realmente fazendo tanto que é diferente de Pascal, além de ter coleta de lixo em vez de gerenciamento manual de memória. E dados imutáveis ​​permitem várias otimizações para o mecanismo de GC [que avaliação preguiçosa complica um pouco].

Acho que o fato é que Haskell parece avançado, sofisticado e de alto nível, e todo mundo pensa: "uau, isso é realmente poderoso, deve ser incrivelmente lento! " Mas não é. Ou pelo menos, não é da maneira que você esperaria. Sim, ele tem um sistema de tipos incrível. Mas você sabe o que? Tudo isso acontece em tempo de compilação. No tempo de execução, ele se foi. Sim, permite que você construa ADTs complicados com uma linha de código. Mas você sabe o que? Um ADT é apenas um simples C comum unionde structs. Nada mais.

O verdadeiro assassino é uma avaliação preguiçosa. Quando você acertar a rigidez / preguiça do seu código, poderá escrever um código estupidamente rápido que ainda seja elegante e bonito. Mas se você errar, seu programa fica milhares de vezes mais lento , e não é realmente óbvio porque isso está acontecendo.

Por exemplo, escrevi um pequeno programa trivial para contar quantas vezes cada byte aparece em um arquivo. Para um arquivo de entrada de 25 KB, o programa levou 20 minutos para ser executado e engoliu 6 gigabytes de RAM! Isso é um absurdo !! Mas então percebi qual era o problema, adicionei um único padrão de batida e o tempo de execução caiu para 0,02 segundos .

Este é o lugar onde Haskell vai inesperadamente lentamente. E com certeza leva um tempo para se acostumar. Mas com o tempo, fica mais fácil escrever um código muito rápido.

O que torna o Haskell tão rápido? Pureza. Tipos estáticos. Preguiça. Mas, acima de tudo, sendo suficientemente alto para que o compilador possa alterar radicalmente a implementação sem quebrar as expectativas do seu código.

Mas acho que essa é apenas a minha opinião ...

MathematicsOrchid
fonte
13
@ cimmanon Eu não acho que seja puramente baseado em opiniões. É uma pergunta interessante para a qual outras pessoas provavelmente queriam uma resposta. Mas acho que veremos o que os outros eleitores pensam.
MatemáticoOrchid
8
@ cimmanon - essa pesquisa fornece apenas um tópico e meio e todos eles têm a ver com auditorias de revisão. e a resposta votada para o tópico diz "por favor, pare de moderar coisas que você não entende". Eu sugeriria que, se alguém acha que a resposta é necessariamente muito ampla, ficaria surpreso e apreciaria a resposta, já que a resposta não é muito ampla.
Sclv
34
"Em Java, digamos, a JVM deve verificar se há indicadores nulos e lançar uma exceção se você deferir um." A verificação nula implícita do Java é (principalmente) gratuita. As implementações de Java podem tirar proveito da memória virtual para mapear o endereço nulo para uma página ausente, portanto, a exclusão de um ponteiro nulo aciona uma falha de página no nível da CPU, que Java captura e lança como uma exceção de alto nível. Portanto, a maioria das verificações nulas é realizada gratuitamente pela unidade de mapeamento de memória na CPU.
Boann
4
@cimmanon: Talvez seja porque os usuários de Haskell parecem ser a única comunidade que é na verdade um grupo amigável de pessoas de mente aberta ... que você considera uma "piada" ..., em vez de uma comunidade de nazistas que governam cachorros e cachorros rasgue um ao outro a cada chance que tiverem ... o que parece ser o que você considera "normal".
Evi1M4chine
14
@ MathematicsOrchid: você tem uma cópia do seu programa original que levou 20 minutos para ser executada? Eu acho que seria bastante instrutivo estudar por que é tão lento.
George
79

Durante muito tempo, pensou-se que as linguagens funcionais não pudessem ser rápidas - e, principalmente, as linguagens funcionais preguiçosas. Mas isso ocorreu porque suas primeiras implementações foram, em essência, interpretadas e não genuinamente compiladas.

Uma segunda onda de projetos surgiu com base na redução de gráficos e abriu a possibilidade de uma compilação muito mais eficiente. Simon Peyton Jones escreveu sobre essa pesquisa em seus dois livros A Implementação de Linguagens de Programação Funcional e Implementando Linguagens Funcionais: um tutorial (o primeiro com seções de Wadler e Hancock e o último escrito com David Lester). (Lennart Augustsson também me informou que uma das principais motivações do livro anterior era descrever a maneira como seu compilador LML, que não foi amplamente comentado, realizou sua compilação).

A noção-chave por trás das abordagens de redução de gráfico, como descrito nesses trabalhos, é que não pensamos em um programa como uma sequência de instruções, mas em um gráfico de dependência que é avaliado através de uma série de reduções locais. O segundo insight principal é que a avaliação de um gráfico desse tipo não precisa ser interpretada, mas o próprio gráfico pode ser construído com código . Em particular, podemos representar um nó de um gráfico não como "um valor ou um 'código de operação' e os valores para operar", mas como uma função que, quando chamada, retorna o valor desejado. Na primeira vez em que é invocado, ele solicita os subnós por seus valores e, em seguida, opera sobre eles, e então se sobrescreve com uma nova instrução que apenas diz "retornar o resultado".

Isso é descrito em um artigo posterior, que descreve o básico de como o GHC ainda funciona hoje (embora module vários ajustes): "Implementando idiomas funcionais preguiçosos no hardware de estoque: a G-Machine Spineless Tagless". . O atual modelo de execução do GHC está documentado em mais detalhes no Wiki do GHC .

Portanto, o insight é que a distinção estrita de "dados" e "código", que consideramos "fundamentais" para o funcionamento das máquinas, não é como elas devem funcionar, mas é imposta pelos nossos compiladores. Portanto, podemos jogar isso fora e ter um código (um compilador) que gera código auto-modificável (o executável) e tudo pode funcionar muito bem.

Portanto, embora as arquiteturas de máquinas sejam imperativas em certo sentido, as linguagens podem mapear para elas de maneiras muito surpreendentes que não se parecem com o controle de fluxo convencional no estilo C, e se pensarmos em nível baixo o suficiente, isso também pode ser eficiente.

Além disso, existem muitas outras otimizações abertas pela pureza em particular, pois permitem uma maior variedade de transformações "seguras". Quando e como aplicar essas transformações, de modo que elas melhorem e não piorem, é obviamente uma questão empírica e, sobre esta e muitas outras pequenas escolhas, anos de trabalho foram colocados em trabalhos teóricos e em benchmarking prático. Portanto, é claro que isso também desempenha um papel. Um artigo que fornece um bom exemplo desse tipo de pesquisa é " Criando um curry rápido: pressione / entre versus avalie / solicite idiomas de ordem superior".

Por fim, deve-se notar que esse modelo ainda apresenta uma sobrecarga devido a indireções. Isso pode ser evitado nos casos em que sabemos que é "seguro" fazer as coisas de maneira estrita e, assim, evitar indiretas gráficas. Os mecanismos que inferem rigor / demanda são novamente documentados com alguns detalhes no Wiki do GHC .

sclv
fonte
2
Esse link do analisador de demanda vale seu peso em ouro! Finalmente, algo sobre o tópico que não está agindo como se fosse basicamente magia negra inexplicável. Como eu nunca ouvi falar disso ?? Deve estar ligado de qualquer lugar onde alguém pergunte como lidar com os problemas com preguiça!
Evi1M4chine
@ Evi1M4chine Não vejo um link relacionado a um analisador de demanda, talvez tenha sido perdido de alguma forma. Alguém pode restaurar o link ou esclarecer a referência? Parece bastante interessante.
Cris P
1
@ CrisP Eu acredito que o último link é o que está sendo referido. Ele vai para uma página no Wiki do GHC sobre o analisador de demanda no GHC.
Serp C
@ Cougar Serpentine, Chris P: Sim, é o que eu quis dizer.
Evi1M4chine 14/11
19

Bem, há muito o que comentar aqui. Vou tentar responder o máximo que puder.

Quando usado corretamente, ele pode aproximar-se dos idiomas de baixo nível.

Na minha experiência, geralmente é possível obter 2x o desempenho do Rust em muitos casos. Mas também existem alguns casos de uso (amplos) em que o desempenho é baixo em comparação com os idiomas de baixo nível.

ou até superá-lo, mas isso significa que você está usando um programa C ineficiente, pois o GHC compila Haskell para C)

Isso não está totalmente correto. Haskell compila para C-- (um subconjunto de C), que é então compilado através do gerador de código nativo para montagem. O gerador de código nativo geralmente gera código mais rápido que o compilador C, porque pode aplicar algumas otimizações que um compilador C comum não pode.

Arquiteturas de máquinas são claramente imperativas, baseando-se em máquinas de turing, aproximadamente.

Essa não é uma boa maneira de pensar sobre o assunto, principalmente porque os processadores modernos avaliarão as instruções fora de ordem e possivelmente ao mesmo tempo.

De fato, Haskell nem sequer tem uma ordem de avaliação específica.

Na verdade, Haskell não definem implicitamente um pedido de avaliação.

Além disso, em vez de lidar com tipos de dados de máquina, você cria tipos de dados algébricos o tempo todo.

Eles correspondem em muitos casos, desde que você tenha um compilador suficientemente avançado.

Você pensaria que criar funções dinamicamente e jogá-las ao redor tornaria um programa mais lento.

Haskell é compilado e, portanto, funções de ordem superior não são realmente criadas em tempo real.

parece otimizar o código Haskell, você precisa torná-lo mais elegante e abstrato, em vez de mais semelhante a uma máquina.

Em geral, tornar o código mais "parecido com a máquina" é uma maneira improdutiva de obter melhor desempenho no Haskell. Mas torná-lo mais abstrato nem sempre é uma boa ideia. O que é uma boa idéia é usar estruturas de dados comuns e funções que têm sido altamente otimizado (como listas ligadas).

f x = [x]e f = puresão exatamente a mesma coisa em Haskell, por exemplo. Um bom compilador não produziria melhor desempenho no caso anterior.

Por que Haskell (compilado com o GHC) é tão rápido, considerando sua natureza abstrata e diferenças em relação às máquinas físicas?

A resposta curta é "porque foi projetada para fazer exatamente isso". O GHC usa a g-machine rotativa sem marca (STG). Você pode ler um artigo sobre isso aqui (é bastante complexo). O GHC também faz muitas outras coisas, como análise de rigor e avaliação otimista .

O motivo pelo qual digo C e outras linguagens imperativas são um pouco semelhantes às Máquinas de Turing (mas não na medida em que Haskell é semelhante ao Lambda Calculus) é que, em uma linguagem imperativa, você tem um número finito de estados (também conhecido como número de linha), além com uma fita (a ram), de modo que o estado e a fita atual determinem o que fazer com a fita.

O ponto de confusão é que a mutabilidade deve levar a um código mais lento? A preguiça de Haskell na verdade significa que a mutabilidade não importa tanto quanto você pensa que seria, além de ser de alto nível, para que haja muitas otimizações que o compilador possa aplicar. Assim, modificar um registro no local raramente será mais lento do que em um idioma como C.


fonte
3

Por que Haskell (GHC) é tão rápido?

Algo deve ter mudado dramaticamente desde a última vez que medi o desempenho de Haskell. Por exemplo:

Então o que mudou? Percebo que nem a pergunta nem nenhuma de suas respostas atuais se referem a benchmarks verificáveis ​​ou mesmo código.

Uma coisa favorita dos Haskellers a fazer é tentar chegar a 5% de C

Você tem alguma referência a resultados verificáveis ​​onde alguém chegou perto disso?

Jon Harrop
fonte
6
Alguém disse o nome de Harrop na frente do espelho três vezes novamente?
Chuck Adams
2
não 10x, mas ainda assim, toda essa entrada é propaganda e truque de marketing. O GHC é realmente capaz de se aproximar de C ou mesmo de superá-lo às vezes, em termos de velocidade, mas isso geralmente requer um estilo de programação de baixo nível bastante envolvido, não muito diferente da programação em C. infelizmente. quanto mais alto o código, mais lento é, geralmente. vazamentos espaço, tipos ADT convenientes ainda underperformant ( algébrica , não abstrato , como era a promessa), etc., etc.
Will Ness
1
Estou postando isso porque o vi hoje chrispenner.ca/posts/wc . É uma implementação do utilitário wc escrita em Haskell que supostamente supera a versão c.
Garrison
3
@ Guarnição obrigado pelo link . 80 linhas é o que chamei de "estilo de programação de baixo nível, não muito diferente da programação em C." . "o código de nível superior", isso seria o "estúpido" fmap (length &&& length . words &&& length . lines) readFile. Se que foi mais rápido do que (ou mesmo comparável a) C, o hype aqui seria totalmente justificado em seguida . Ainda precisamos trabalhar duro pela velocidade em Haskell, como em C, é o ponto.
Will Ness
2
A julgar por esta discussão no Reddit reddit.com/r/programming/comments/dj4if3/…, o código Haskell é realmente incorreto (por exemplo, quebras nas linhas começam ou terminam com espaços em branco, quebras em à) e outras não podem reproduzir os resultados de desempenho reivindicados.
91319 Jon Harrop