🇪🇸 Mejorar soporte a los grandes números de Haskell

:es: Traducción al español de “Improving Haskell’s big numbers support”

Publicado por Sylvain Henry en el blog de IOHK el 27 de Julio de 2020


El trabajo de los ingenieros de IOHK es parte de la última versión del compilador Glasgow

Haskell es vital para el trabajo IOHK para asegurar que Cardano sea una blockchain segura para el futuro de las finanzas descentralizadas. Como parte de esto, usamos el lenguaje para desarrollar la plataforma de contratos inteligentes Plutus, y puede que haya leído sobre los cursos de formación dirigidos por nuestros ingenieros, incluyendo un curso de Haskell en Mongolia este mes. Las aplicaciones de contratos inteligentes son una forma poderosa de generar valor en una red distribuida, permitiendo a los individuos y a las empresas acordar condiciones y ejecutar automáticamente intercambios de información y riqueza, sin depender de terceros. Los contratos Plutus contienen una cantidad sustancial de código que se ejecuta fuera de la cadena, en las computadoras de los usuarios. Para facilitar la creación de ejecutables portátiles para estos, queremos compilar el código fuera de la cadena de Haskell en JavaScript o WebAssembly. Para alcanzar ese objetivo, participamos en el desarrollo del Glasgow Haskell Compiler (GHC), GHCJS (compilador de Haskell a JavaScript) y Asterius (compilador de Haskell a WebAssembly).

Recientemente hemos estado trabajando en mejorar el soporte del GHC para números grandes, es decir, números mayores de 64 bits (tanto los tipos Enteros como los Naturales en Haskell). Hemos desarrollado una implementación de operaciones de grandes números en Haskell que es más rápida que la anterior (entero-simple). También hemos mejorado la forma en que el GHC trata las diferentes implementaciones para hacerlo más robusto y evolutivo. Estas contribuciones forman parte de la última versión del GHC, la 9.0.

Antecedentes

Cada compilador de Haskell tiene que apoyar los números enteros de precisión arbitraria (ver informes Haskell 98 y Haskell 2010, sección 6.4). GHC no es una excepción y como tal proporciona los omnipresentes tipos Enteros y Naturales (‘números grandes’ para el resto de este post).

Hasta ahora, GHC podría usar uno de los dos paquetes para este soporte:

  • integer-gmp: usa la biblioteca GNU MP (GMP) (a través de FFI), LGPL. Buen rendimiento.

  • integer-simple: Implementación de Haskell, BSD3. Mal rendimiento.

La elección de uno u otro dependía de consideraciones de licencia, rendimiento y compilación cruzada. En algunos casos, la licencia LGPL de GMP puede ser problemática, especialmente si se utiliza la vinculación estática, que se requiere en algunas plataformas, incluyendo Windows. En lo que respecta al rendimiento: entero-simple es a veces varios órdenes de magnitud más lento que el entero-gmp, como se explica a continuación. Y con la compilación cruzada, algunas plataformas de destino pueden no soportar GMP, como JavaScript.

La situación ya era desafortunada, pero había problemas adicionales:

  1. Cada implementación tenía su propia manera de representar los grandes números (matriz de palabras sin recuadro o lista de palabras con recuadro). El GHC estaba al tanto de la implementación seleccionada y produjo un código diferente para cada una. Esto podría conducir a errores - ¡incluso a la “locura”! - cuando se intercambiaban grandes números entre procesos compilados con diferentes implementaciones. Además, complicaba el código del compilador porque tenía que lidiar con esta discrepancia (por ejemplo, al inspeccionar objetos montón en tiempo de ejecución en GHCi).
  2. De manera similar, debido a las diferentes representaciones internas, hay por lo menos 71 paquetes en Hackage (entre ellos algunos ampliamente utilizados como bytestring y texto) que dependen explícitamente del paquete integer-gmp o que proporcionan un indicador para depender ya sea de integer-gmp o de integer-simple. Es una carga de mantenimiento porque cada ruta de código podría tener errores específicos y debería ser probada en CI.

Todo esto significaba que cada nueva implementación de un gran número era una tarea desalentadora. En primer lugar, la interfaz a implementar era muy grande (los tipos Integer y Natural y todas sus operaciones). Luego, necesitábamos asegurarnos de que las reglas de reescritura de GHC (plegado constante) seguían funcionando para la implementación, los paquetes mencionados anteriormente necesitaban ser arreglados, y se agregaron nuevas banderas de Cabal (por cierto, las banderas de Cabal son booleanas, por lo que no pueden ser fácilmente extendidas para soportar más de dos opciones). Finalmente, el sistema de construcción de GHC necesitaba ser modificado. No es de extrañar que nunca ocurriera.

Afortunadamente, la mayoría de estos problemas ya están solucionados en la última versión, GHC 9.0.

El paquete ghc-bignum

A partir de GHC 9.0, el soporte de grandes números es proporcionado por un solo paquete: ghc-bignum. Esto proporciona una implementación de Haskell de números grandes (backend nativo) que es más rápida que la de integer-simple (las cifras de rendimiento se dan más abajo), también tiene licencia BSD3, y utiliza la misma representación de números grandes que integer-gmp.

Ahora las diferentes implementaciones de números grandes se consideran como backends internos de la biblioteca ghc-bignum y no debería haber ninguna diferencia observable entre los backends, excepto en el rendimiento. Para reforzar esto, incluso tenemos un meta-backend utilizado durante las pruebas que realiza cada operación con dos backends (el backend nativo y otro seleccionado) y comprueba que sus resultados son los mismos.

Una implementación pura de Haskell no puede esperar realmente superar el rendimiento de librerías altamente optimizadas como GMP, por lo que se ha integrado integer-gmp en ghc-bignum como backend (gmp-backend).

Añadir un backend de grandes números es ahora mucho más fácil. La interfaz a implementar es mínima y está documentada. Un nuevo backend no tiene que proporcionar toda la implementación por adelantado: las operaciones proporcionadas por el **backend nativo **pueden ser utilizadas para llenar los huecos mientras se desarrolla otro backend. El marco de pruebas no tiene que ser reescrito para cada backend y los resultados pueden ser comprobados automáticamente contra el backend nativo con el meta-backend mencionado anteriormente. Esperamos que en un futuro próximo se desarrollen backends que utilicen otras librerías, como OpenSSL libcrypto integers o BSDNT.

El paquete ghc-bignum también tiene un tercer ffi-backend que no proporciona una implementación en sí mismo pero realiza llamadas FFI para cada operación. Así que ghc-bignum debe estar enlazado con un objeto que provea la implementación o el compilador debe reemplazar estas llamadas con operaciones específicas de la plataforma (por ejemplo, operaciones de JavaScript/CLR/JVM big numbers) cuando este backend sea seleccionado. Es similar a lo que el compilador de Asterius estaba haciendo - reemplazando las llamadas GMP FFI con las llamadas JavaScript BigInt - pero de una manera más limpia porque GMP ya no está involucrado.

Una gran ventaja de ghc-bignum es que todos los backends usan la misma representación para los números grandes: un conjunto de palabras almacenadas en orden little-endian. Esta representación también es utilizada por la mayoría de las bibliotecas de grandes números. Anteriormente, el integer-simple era una excepción notoria porque usaba una lista Haskell para almacenar las palabras, lo que explicaba en parte su pobre rendimiento. Ahora, cualquier paquete que quiera acceder a la representación de los grandes números sólo tiene que depender de ghc-bignum. Las banderas Cabal y el código CPP ya no son necesarios para tratar con las diferentes implementaciones. Sin embargo, el código condicional puede ser necesario durante la transición de los paquetes integer * a ghc-bignum.

Para facilitar la transición, se sigue proporcionando el paquete integer-gmp-1.1, pero se ha reescrito para que dependa de ghc-bignum y proporcione algunas funciones y sinónimos de patrones compatibles con las versiones anteriores. No obstante, cabe señalar que algunas funciones que sólo estaban disponibles en integer-gmp-1.0.* (por ejemplo, la prueba del número primo, GCD ampliado) se han eliminado en integer-gmp-1.1. Esperamos que estas funciones muy específicas sean exportadas por paquetes como hgmp en su lugar. Alternativamente, alguien podría implementar las versiones de Haskell de estas funciones en un backend nativo.

El código GHC se ha simplificado y se ha hecho más rápido. Los tipos y constructores de grandes números son ahora conocidos por el compilador (‘wired-in’), de la misma manera que otros literales, por lo que GHC no tiene que leer los archivos de interfaz cada vez que quiere generar código con ellos. La representación unificada evita la necesidad de dos rutas de código, lo que hace que el código sea más robusto y más fácil de probar.

Rendimiento

Hemos comparado el rendimiento de los backends nativos con las últimas implementaciones integer-simple e integer-gmp (Figura 1). Hemos medido el tiempo necesario para calcular las operaciones básicas:

La plataforma era Linux 5.5.4 en un CPU Intel Core i7-9700K corriendo a 3.60GHz. Los tres bindist GHC han sido construidos con Hadrian usando el sabor ‘perf’. integer-gmp e integer-simple bindist están construidos a partir de la commit 84dd96105. native-backend bindist está construido a partir de la rama ghc-bignum rebasada en la commit 9d094111.

Los cálculos se han realizado con números enteros positivos de los siguientes tamaños: pequeño - 1 palabra (64 bits); mediano - 8 palabras (512 bits); grande - 76 palabras (4.848 bits).

Figura 1. El retroceso nativo y el entero-gmp son más rápidos que el entero-sencillo en casi todos los casos (nótese la escala logarítmica)

La figura 1 muestra que el backend nativo y el integer-gmp son siempre más rápidos que el integer-simple. Las únicas excepciones son cuando añadimos o restamos un número pequeño (1 palabra) a uno grande, ya que estas operaciones son particularmente adecuadas para la representación del bignum de los números integer-simple (una lista) porque la cola de la lista permanece inalterada y se comparte entre los números grandes antes y después de la operación. Con la otra representación, la cola tiene que ser duplicada en la memoria.

La división con integer-simple funciona tan mal que el backend nativo es 40 veces más rápido en todos los casos probados.

A veces, el backend nativo es más rápido que el integer-gmp (por ejemplo, la suma/resta con un número pequeño/medio). La biblioteca GMP es probablemente al menos tan buena como el backend nativo, pero este último evita las llamadas FFI, lo que puede explicar el mejor rendimiento. Por lo demás, el backend nativo sigue siendo más lento que el integer-gmp pero estos resultados son esperados porque sólo implementa algoritmos básicos y no utiliza instrucciones vectorizadas u optimizadas del procesador.

En lo que respecta a las pruebas de rendimiento del GHC, tomamos nuestra línea de base como GHC HEAD compilado con integer-gmp. Comparamos los resultados con el gmp-backend de ghc-bignum. No hay regresiones. En la tabla 1 se observan mejoras notables en el uso de la memoria.

A continuación, comparamos las métricas obtenidas con el backend nativo con las obtenidas con el GHC HEAD construido con integer-simple. La nueva implementación de Haskell resulta en cambios notables (Tabla 2). Nótese que las primeras cuatro pruebas fueron desactivadas con integer-simple porque tardaron demasiado o no se completaron (desbordamiento de la pila) pero todas pasaron con el backend nativo. Además, T10678, la prueba final de la tabla, realiza muchas adiciones de un número pequeño a un número grande. Como vimos anteriormente, este es el único caso en el que la representación de números integer-simples es mejor: en la mayoría de las iteraciones sólo se modifica la cabeza de la lista sin duplicar la cola. Se refleja de nuevo en este resultado.

Finalmente, comparamos el backend nativo con el gmp-backend: nos dice lo lejos que está nuestra implementación de Haskell de nuestro mejor backend. Los cambios notables se reportan en la Tabla 3.

Conclusión

Estamos muy orgullosos de haber hecho esta contribución a GHC. IOHK y toda la comunidad se benefician ahora de la mejora del rendimiento y la robustez del compilador. Los programas que utilizan la nueva implementación de Haskell de números grandes (backend nativo) deben obtener un aumento de rendimiento cuando cambian de integer-simple.

También estamos ansiosos por ver lo que la comunidad hará con este trabajo. En particular, ahora debería ser más fácil crear backends basados en otras bibliotecas. También hay mucho espacio para la optimización en el backend nativo. También animamos a todo el mundo a probar esta nueva implementación y a informar de cualquier problema en el rastreador de errores de GHC.