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

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.

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

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 .

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.

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:

• Um benchmark de processamento de arquivos RRD em que o autor descobriu que Haskell demorou mais para desenvolver e roda mais lentamente (1.020s) do que Go (130s) e OCaml (67s), ou seja, 15x mais lento que OCaml.
• Um benchmark de dicionário simples mostrou Haskell rodando ~ 10 vezes mais lento que o F #.
• A comparação de linguagem Ray Tracer é outro exemplo em que Haskell foi mais lento que C ++, OCaml e até Java e Lisp.
• Um quicksort genérico paralelo em Haskell era 55% mais lento que o F # e requer substancialmente mais código.

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?