O trabalho dos engenheiros da IOHK faz parte da versão mais recente do compilador de Glasgow
(Postado originalmente por Sylvain Henry em 28/07/2020, traduzido por Joselmo Cabral)
Haskell é vital para o trabalho da IOHK para garantir que Cardano seja um blockchain seguro para o futuro das finanças descentralizadas. Como parte disso, usamos o idioma para desenvolver a plataforma de contratos inteligentes Plutus, e você pode ter lido sobre os cursos de treinamento realizados por nossos engenheiros, incluindo um curso de Haskell na Mongólia este mês. Os aplicativos inteligentes de contrato são uma maneira poderosa de uma rede distribuída gerar valor, permitindo que indivíduos e empresas concordem com as condições e executem automaticamente trocas de informações e riquezas, sem depender de terceiros. Os contratos de plutus contêm uma quantidade substancial de código que é executado fora da cadeia nos computadores dos usuários. Para facilitar a criação de executáveis portáteis para eles, queremos compilar o código Haskell fora da cadeia em JavaScript ou WebAssembly. Para atingir esse objetivo, participamos do desenvolvimento do compilador Glasgow Haskell (GHC), do GHCJS (compilador Haskell para JavaScript) e do Asterius (compilador Haskell para WebAssembly).
Recentemente, estivemos trabalhando para melhorar o suporte do GHC a grandes números, ou seja, números maiores que 64 bits (tipos inteiro e natural em Haskell). Desenvolvemos uma implementação de operações de grande número no Haskell que é mais rápida que a anterior (número inteiro simples). Também melhoramos a maneira como o GHC lida com as diferentes implementações para torná-lo mais robusto e evolutivo. Essas contribuições fazem parte da versão mais recente do GHC, versão 9.0.
Background
Todo compilador Haskell precisa oferecer suporte a números inteiros de precisão arbitrária (consulte os relatórios Haskell 98 e Haskell 2010, seção 6.4). O GHC não é exceção e, como tal, fornece os tipos inteiro e natural onipresentes (“grandes números” para o restante deste post).
Até agora, o GHC poderia usar um dos dois pacotes para esse suporte:
integer-gmp : usa a biblioteca GNU MP (GMP) (via FFI), LGPL. Boa performance.
Integer-simple : implementação de Haskell, BSD3. Mau desempenho.
A escolha de um ou de outro dependia das considerações sobre licença, desempenho e compilação cruzada. Em alguns casos, a licença LGPL do GMP pode ser problemática, especialmente se você usar links estáticos, o que é necessário em algumas plataformas, incluindo o Windows. Quando se trata de desempenho: integer-simple às vezes é várias ordens de magnitude mais lento que integer-gmp, conforme discutido abaixo. E com a compilação cruzada, algumas plataformas de destino podem não suportar GMP, como JavaScript.
A situação já era lamentável, mas havia outros problemas:
- Cada implementação tinha sua própria maneira de representar grandes números (array de palavras não encaixadas ou lista de palavras em caixa). O GHC estava ciente da implementação selecionada e produziu um código diferente para cada um. Isso pode levar a erros – até a ‘insanidade’! – quando grandes números foram trocados entre processos compilados com diferentes implementações. Além disso, tornou o código do compilador mais complicado porque ele teve que lidar com essa discrepância (por exemplo, ao inspecionar objetos heap em tempo de execução no GHCi).
- Da mesma forma, devido às diferentes representações internas, há pelo menos 71 pacotes no Hackage (entre eles alguns amplamente utilizados, como bytestring e texto) que explicitamente dependem do pacote integer-gmp ou que fornecem um sinalizador para depender do integer-gmp ou inteiro simples. É uma carga de manutenção, porque cada caminho de código pode ter erros específicos e deve ser testado no IC.
Tudo isso significava que toda nova implementação de grande número era uma tarefa assustadora. Primeiro, a interface a implementar era muito grande (tipos Inteiro e Natural e todas as suas operações). Então, precisávamos garantir que as regras de reescrita do GHC (dobragem constante) ainda funcionassem para a implementação, os pacotes mencionados acima precisavam ser corrigidos e novos sinalizadores Cabal adicionados (a propósito, os sinalizadores Cabal são booleanos, portanto, não podem ser facilmente estendido para suportar mais de duas opções). Por fim, o sistema de criação do GHC precisava ser modificado. Não é à toa que nunca aconteceu.
Felizmente, a maioria desses problemas foi corrigida na versão mais recente, o GHC 9.0.
O pacote ghc-bignum
A partir do GHC 9.0, o suporte a grandes números é fornecido por um único pacote: ghc-bignum. Isso fornece uma implementação Haskell de grandes números (native-backend) que é mais rápido que o integer-simple (os números de desempenho são fornecidos abaixo), também é licenciado em BSD3 e usa a mesma representação de grandes números que o integer-gmp.
Agora, as diferentes implementações de grandes números são consideradas como backends internos da biblioteca ghc-bignum e não deve haver diferença observável entre os backends, exceto o desempenho. Para impor isso, temos até um meta-backend usado durante testes que executam todas as operações com dois backends (native-backend e outro selecionado) e verificam se seus resultados são os mesmos.
Uma implementação pura de Haskell não pode realmente esperar superar o desempenho de bibliotecas altamente otimizadas, como o GMP, portanto o integer-gmp foi integrado ao ghc-bignum como um backend (gmp-backend).
Adicionar um grande número de back-end agora é muito mais fácil. A interface a implementar é mínima e está documentada. Um novo back-end não precisa fornecer toda a implementação antecipadamente: as operações fornecidas pelo native-backend podem ser usadas para preencher os buracos enquanto outro backend está sendo desenvolvido. A estrutura de teste não precisa ser reescrita para cada backend e os resultados podem ser verificados automaticamente no native-backend com o meta-backend mencionado acima. Esperamos que o backend usando outras bibliotecas, como números inteiros OpenSSL libcrypto ou BSDNT, seja desenvolvido em um futuro próximo.
O pacote ghc-bignum também possui um terceiro backend do ffi que não fornece uma implementação em si, mas realiza chamadas FFI para cada operação. Portanto, o ghc-bignum deve estar vinculado a um objeto que forneça a implementação ou o compilador deve substituir essas chamadas por operações específicas da plataforma (por exemplo, operações de grandes números JavaScript / CLR / JVM) quando esse backend for selecionado. É semelhante ao que o compilador Asterius estava fazendo – substituindo as chamadas GMP FFI pelas chamadas JavaScript BigInt – mas de uma maneira mais limpa, porque o GMP não está mais envolvido.
Uma grande vantagem do ghc-bignum é que todos os backend usam a mesma representação para grandes números: uma matriz de palavras armazenadas em ordem little-endian. Essa representação também é usada pela maioria das bibliotecas de grandes números. Antigamente, número inteiro-simples era uma exceção notória porque usava uma lista de Haskell para armazenar as palavras, explicando parcialmente o seu baixo desempenho. Agora, qualquer pacote que queira acessar a representação dos grandes números só precisa depender do ghc-bignum. Os sinalizadores de cabala e o código CPP não são mais necessários para lidar com as diferentes implementações. No entanto, pode ser necessário código condicional durante a transição de pacotes integer- * para ghc-bignum.
Para facilitar a transição, o pacote integer-gmp-1.1 ainda é fornecido, mas foi reescrito para depender do ghc-bignum e fornecer algumas funções compatíveis com versões anteriores e sinônimos de padrão. Observe, no entanto, que algumas funções que estavam disponíveis apenas no integer-gmp-1.0. * (Por exemplo, teste do número principal, GCD estendido) foram removidas no integer-gmp-1.1. Esperamos que essas funções muito específicas sejam exportadas por pacotes como o hgmp. Como alternativa, alguém poderia implementar versões Haskell dessas funções no native-backend.
O código GHC foi simplificado e acelerado. Agora, grandes tipos e construtores de números são conhecidos pelo compilador (‘engatados’), da mesma maneira que outros literais, portanto, o GHC não precisa ler os arquivos de interface sempre que quiser gerar código usando-os. A representação unificada evita a necessidade de dois caminhos de código, o que torna o código mais robusto e fácil de testar.
Performance
Comparamos o desempenho do native-backend com as mais recentes implementações de número integer-simple e integer-gmp (Figura 1). Medimos o tempo necessário para calcular as operações básicas:
A plataforma era Linux 5.5.4 na CPU Intel Core i7-9700K, rodando a 3.60GHz. Os três ligantes do GHC foram construídos com Adriano usando o sabor ‘perf’. binders inteiro-gmp e inteiro simples são criados a partir do commit 84dd96105. O bindist de back-end nativo é construído a partir da ramificação ghc-bignum rebased no commit 9d094111
Os cálculos foram realizados com números inteiros positivos dos seguintes tamanhos: pequeno (small) – 1 palavra (64 bits); médio (med) – 8 palavras (512 bits); grande (big) – 76 palavras (4.848 bits).
Figura 1. O native-backend e o integer-gmp são mais rápidos que o número integer-simple em quase todos os casos (observe a escala logarítmica)
A Figura 1 mostra que o native-backend e o integer- gmp são sempre mais rápidos que o integer-simples. As únicas exceções são quando adicionamos ou subtraímos um número pequeno (1 palavra) de um número grande, pois essas operações são particularmente adequadas para a representação bignum de integer-simple (uma lista) porque a cauda da lista permanece inalterada e é compartilhada entre os grandes números antes e depois da operação. Com a outra representação, a cauda deve ser duplicada na memória.
A divisão com número inteiro simples é tão ruim que o native-backend é 40 vezes mais rápido em todos os casos testados.
Às vezes, o native-backend é mais rápido que o integer-gmp (por exemplo, adição / subtração com um número pequeno / médio). A biblioteca GMP provavelmente é pelo menos tão boa quanto a infraestrutura nativa, mas a última evita chamadas FFI, o que pode explicar o melhor desempenho. Caso contrário, o native-backend ainda é mais lento que o integer-gmp, mas esses resultados são esperados porque implementa apenas algoritmos básicos e não usa instruções de processador vetorizadas ou otimizadas.
Quando se trata de testes de desempenho do GHC, adotamos nossa linha de base como GHC HEAD compilado com número inteiro-gmp. Comparamos os resultados com o gmp-backend do ghc-bignum. Não há regressões. Melhorias visíveis no uso da memória são vistas na Tabela 1.
Tabela 1. Performance do GHC para integer-gmp versus o gmp-backend
Em seguida, comparamos as métricas obtidas com native-backend com as obtidas com o GHC HEAD construídas com integer-simple. A nova implementação Haskell resulta em mudanças perceptíveis (Tabela 2). Observe que os quatro primeiros testes foram desabilitados com integer-simples, porque demoraram muito ou não foram concluídos (estouro de heap), mas todos foram aprovados com native-backend. Além disso, o T10678, o teste final da tabela, realiza muitas adições de um número pequeno a um número grande. Como vimos acima, este é o único caso em que a representação integer-simple é melhor: na maioria das iterações, apenas o cabeçalho da lista é modificado sem duplicar a cauda. É refletido novamente neste resultado.
Tabela 2. Performance GHC do integer-simple para o native-backend
Finalmente, comparamos o native-backend com o gmp-backend: ele nos mostra a que distância nossa implementação do Haskell está do nosso melhor backend. Alterações visíveis são relatadas na Tabela 3.
Tabela 3. Performance GHC do gmp-backend para o native-backend.
Conclusão
Estamos muito orgulhosos de ter feito essa contribuição ao GHC. O IOHK e toda a comunidade agora se beneficiam do desempenho e robustez aprimorados do compilador. Os programas que usam a nova implementação de grandes números da Haskell (native-backend) devem obter um aumento de desempenho quando passam do integer-simple.
Também estamos ansiosos para ver o que a comunidade fará com este trabalho. Em particular, agora deve ser mais fácil criar backends com base em outras bibliotecas. Também há muito espaço para otimização no native-backend. Também incentivamos todos a testar esta nova implementação e a relatar qualquer problema no rastreador de erros do GHC.