¿Por qué Haskell (GHC) es tan rápido?

Haskell (con el GHCcompilador) es mucho más rápido de lo que cabría esperar . Utilizado correctamente, puede acercarse a los idiomas de bajo nivel. (Una de las cosas favoritas de Haskellers es intentar alcanzar el 5% de C (o incluso superarlo, pero eso significa que está utilizando un programa de C ineficiente, ya que GHC compila Haskell a C).) Mi pregunta es, ¿por qué?

Haskell es declarativo y se basa en el cálculo lambda. Las arquitecturas de las máquinas son claramente imperativas, y se basan en máquinas de turing, aproximadamente. De hecho, Haskell ni siquiera tiene un orden de evaluación específico. Además, en lugar de tratar con tipos de datos de máquina, crea tipos de datos algebraicos todo el tiempo.

Sin embargo, lo más extraño de todo son las funciones de orden superior. Se podría pensar que crear funciones sobre la marcha y lanzarlas, haría un programa más lento. Pero el uso de funciones de orden superior en realidad hace que Haskell sea más rápido. De hecho, parece que, para optimizar el código Haskell, debe hacerlo más elegante y abstracto en lugar de más parecido a una máquina. Ninguna de las características más avanzadas de Haskell parece afectar su rendimiento, si no lo mejoran.

Lo siento si esto suena desaliñado, pero esta es mi pregunta: ¿por qué Haskell (compilado con GHC) es tan rápido, teniendo en cuenta su naturaleza abstracta y las diferencias con las máquinas físicas?

Nota: La razón por la que digo que C y otros lenguajes imperativos son algo similares a las máquinas de Turing (pero no en la medida en que Haskell es similar al cálculo de Lambda) es que en un lenguaje imperativo, tiene un número finito de estados (también conocido como número de línea) , junto con una cinta (el ram), de modo que el estado y la cinta actual determinen qué hacer con la cinta. Vea la entrada de Wikipedia, Equivalentes de máquinas de Turing , para la transición de Máquinas de Turing a computadoras.

Estoy de acuerdo con Dietrich Epp: es una combinación de varias cosas que hacen que GHC sea rápido.

Ante todo, Haskell es de muy alto nivel. Esto permite que el compilador realice optimizaciones agresivas sin romper su código.

Piensa en SQL. Ahora, cuando escribo una SELECTdeclaración, puede parecer un bucle imperativo, pero no lo es . Puede parecer que recorre todas las filas de esa tabla tratando de encontrar la que coincida con las condiciones especificadas, pero en realidad el "compilador" (el motor DB) podría estar haciendo una búsqueda de índice, que tiene características de rendimiento completamente diferentes. Pero debido a que SQL es de tan alto nivel, el "compilador" puede sustituir algoritmos totalmente diferentes, aplicar múltiples procesadores o canales de E / S o servidores completos de forma transparente y más.

Pienso en Haskell como el mismo. Puede pensar que acaba de pedirle a Haskell que asigne la lista de entrada a una segunda lista, filtre la segunda lista en una tercera lista y luego cuente cuántos elementos se obtuvieron. Pero no vio que GHC aplicaba reglas de reescritura de fusión de flujo detrás de escena, transformando todo en un solo bucle de código de máquina ajustado que hace todo el trabajo en un solo paso sobre los datos sin asignación, el tipo de cosa que ser tedioso, propenso a errores y no mantenible para escribir a mano. Eso solo es realmente posible debido a la falta de detalles de bajo nivel en el código.

Otra forma de verlo podría ser ... ¿por qué Haskell no debería ser rápido? ¿Qué hace que lo haga lento?

No es un lenguaje interpretado como Perl o JavaScript. Ni siquiera es un sistema de máquina virtual como Java o C #. Se compila hasta el código de máquina nativo, por lo que no hay gastos generales allí.

A diferencia de los lenguajes OO [Java, C #, JavaScript ...], Haskell tiene borrado de tipo completo [como C, C ++, Pascal ...]. Toda verificación de tipo ocurre solo en tiempo de compilación. Por lo tanto, tampoco hay una verificación de tipo en tiempo de ejecución para ralentizarlo. (No hay comprobaciones de puntero nulo, para el caso. En, digamos, Java, la JVM debe verificar los punteros nulos y lanzar una excepción si hace una deferencia. Haskell no tiene que molestarse con ese cheque).

Dices que suena lento para "crear funciones sobre la marcha en tiempo de ejecución", pero si miras con mucho cuidado, en realidad no lo haces. Puede parecer que lo haces, pero no lo haces. Si dices (+5), bueno, eso está codificado en tu código fuente. No puede cambiar en tiempo de ejecución. Entonces no es realmente una función dinámica. Incluso las funciones currificadas en realidad solo guardan parámetros en un bloque de datos. Todo el código ejecutable existe realmente en tiempo de compilación; No hay interpretación en tiempo de ejecución. (A diferencia de otros idiomas que tienen una "función de evaluación").

Piensa en Pascal. Es viejo y ya nadie lo usa, pero nadie se quejaría de que Pascal es lento . Hay muchas cosas que no le gustan, pero la lentitud no es realmente una de ellas. Haskell realmente no está haciendo tanto que sea diferente a Pascal, aparte de tener recolección de basura en lugar de administración de memoria manual. Y los datos inmutables permiten varias optimizaciones para el motor GC [cuya evaluación diferida complica un poco].

Creo que la cuestión es que Haskell se ve avanzado, sofisticado y de alto nivel, y todos piensan "¡oh wow, esto es realmente poderoso, debe ser increíblemente lento! " Pero no lo es. O al menos, no está en la forma que esperarías. Sí, tiene un sistema de tipos increíble. ¿Pero sabes que? Todo eso sucede en tiempo de compilación. En tiempo de ejecución, se ha ido. Sí, le permite construir ADT complicados con una línea de código. ¿Pero sabes que? Un ADT es simplemente una C ordinaria unionde structs. Nada mas.

El verdadero asesino es la evaluación perezosa. Cuando obtienes la rigidez / pereza de tu código correctamente, puedes escribir código estúpidamente rápido que todavía es elegante y hermoso. Pero si te equivocas con esto, tu programa va miles de veces más lento , y realmente no es obvio por qué sucede esto.

Por ejemplo, escribí un pequeño programa trivial para contar cuántas veces aparece cada byte en un archivo. Para un archivo de entrada de 25 KB, el programa tardó 20 minutos en ejecutarse y se tragó 6 gigabytes de RAM. ¡¡Eso es absurdo!! Pero luego me di cuenta de cuál era el problema, agregué un solo patrón de explosión y el tiempo de ejecución se redujo a 0.02 segundos .

Aquí es donde Haskell va inesperadamente lento. Y seguro que lleva un tiempo acostumbrarse. Pero con el tiempo, se vuelve más fácil escribir código realmente rápido.

¿Qué hace que Haskell sea tan rápido? Pureza. Tipos estáticos Pereza. Pero, sobre todo, tener un nivel suficientemente alto para que el compilador pueda cambiar radicalmente la implementación sin romper las expectativas de su código.

Pero supongo que esa es solo mi opinión ...

Durante mucho tiempo se pensó que los lenguajes funcionales no podían ser rápidos, y especialmente los lenguajes funcionales perezosos. Pero esto se debió a que sus primeras implementaciones fueron, en esencia, interpretadas y no compiladas genuinamente.

Surgió una segunda ola de diseños basada en la reducción de gráficos, y abrió la posibilidad de una compilación mucho más eficiente. Simon Peyton Jones escribió sobre esta investigación en sus dos libros La implementación de lenguajes de programación funcional y la implementación de lenguajes funcionales: un tutorial (el primero con secciones de Wadler y Hancock, y el segundo escrito con David Lester). (Lennart Augustsson también me informó que una motivación clave para el antiguo libro fue describir la forma en que su compilador LML, que no fue ampliamente comentado, logró su compilación).

La noción clave detrás de los enfoques de reducción de gráficos, como se describe en estos trabajos, es que no pensamos en un programa como una secuencia de instrucciones, sino en un gráfico de dependencia que se evalúa a través de una serie de reducciones locales. La segunda idea clave es que la evaluación de un gráfico de este tipo no necesita ser interpretada, sino que el gráfico en sí mismo puede construirse con código . En particular, podemos representar un nodo de un gráfico no como "un valor o un 'código de operación' y los valores para operar", sino como una función que, cuando se invoca, devuelve el valor deseado. La primera vez que se invoca, pregunta a los subnodos sus valores y luego los opera, y luego se sobrescribe con una nueva instrucción que solo dice "devolver el resultado".

Esto se describe en un artículo posterior que establece los conceptos básicos de cómo GHC todavía funciona hoy (aunque modulo muchos ajustes diferentes): "Implementación de lenguajes funcionales perezosos en hardware de stock: la máquina G sin etiqueta sin espinas". . El modelo de ejecución actual para GHC se documenta con más detalle en el Wiki de GHC .

Entonces, la idea es que la distinción estricta de "datos" y "código" que consideramos "fundamental" para el funcionamiento de las máquinas no es cómo deben funcionar, sino que es impuesta por nuestros compiladores. Por lo tanto, podemos descartarlo y tener un código (un compilador) que genera un código auto modificable (el ejecutable) y todo puede funcionar bastante bien.

Por lo tanto, resulta que si bien las arquitecturas de la máquina son imprescindibles en cierto sentido, los lenguajes pueden mapearse en ellas de maneras muy sorprendentes que no se parecen al control de flujo de estilo C convencional, y si pensamos que es lo suficientemente bajo, esto también puede ser eficiente.

Además de esto, hay muchas otras optimizaciones abiertas por la pureza en particular, ya que permite un mayor rango de transformaciones "seguras". Cuándo y cómo aplicar estas transformaciones para que mejoren las cosas y no empeoren es, por supuesto, una pregunta empírica, y en esta y muchas otras pequeñas opciones, se han dedicado años de trabajo tanto al trabajo teórico como a la evaluación comparativa práctica. Entonces, por supuesto, esto también juega un papel importante. Un artículo que proporciona un buen ejemplo de este tipo de investigación es " Hacer un curry rápido: Push / Enter vs. Eval / Apply para idiomas de orden superior".

Finalmente, debe tenerse en cuenta que este modelo todavía introduce una sobrecarga debido a las indirectas. Esto puede evitarse en los casos en que sabemos que es "seguro" hacer las cosas estrictamente y, por lo tanto, eludir las indirecciones del gráfico. Los mecanismos que infieren rigor / demanda se documentan nuevamente con cierto detalle en el Wiki de GHC .

Bueno, hay mucho que comentar aquí. Trataré de responder tanto como pueda.

Utilizado correctamente, puede acercarse a los idiomas de bajo nivel.

En mi experiencia, generalmente es posible obtener el doble de rendimiento que Rust en muchos casos. Pero también hay algunos casos de uso (amplios) en los que el rendimiento es pobre en comparación con los lenguajes de bajo nivel.

o incluso superarlo, pero eso significa que está utilizando un programa C ineficiente, ya que GHC compila Haskell a C)

Eso no es del todo correcto. Haskell compila a C-- (un subconjunto de C), que luego se compila a través del generador de código nativo para ensamblar. El generador de código nativo generalmente genera código más rápido que el compilador de C, porque puede aplicar algunas optimizaciones que un compilador de C ordinario no puede.

Las arquitecturas de las máquinas son claramente imperativas, y se basan en máquinas de turing, aproximadamente.

Esa no es una buena manera de pensarlo, especialmente porque los procesadores modernos evaluarán las instrucciones fuera de servicio y posiblemente al mismo tiempo.

De hecho, Haskell ni siquiera tiene un orden de evaluación específico.

En realidad, Haskell no definen implícitamente una orden de evaluación.

Además, en lugar de tratar con tipos de datos de máquina, crea tipos de datos algebraicos todo el tiempo.

Corresponden en muchos casos, siempre que tenga un compilador suficientemente avanzado.

Se podría pensar que crear funciones sobre la marcha y lanzarlas, haría que un programa fuera más lento.

Haskell se compila, por lo que las funciones de orden superior no se crean realmente sobre la marcha.

parece optimizar el código de Haskell, debe hacerlo más elegante y abstracto, en lugar de más máquina.

En general, hacer que el código sea más "máquina" es una forma improductiva de obtener un mejor rendimiento en Haskell. Pero hacerlo más abstracto tampoco es siempre una buena idea. Lo que es una buena idea es utilizar estructuras y funciones de datos comunes que se hayan optimizado en gran medida (como las listas vinculadas).

f x = [x]y f = pureson exactamente lo mismo en Haskell, por ejemplo. Un buen compilador no produciría un mejor rendimiento en el primer caso.

¿Por qué Haskell (compilado con GHC) es tan rápido, teniendo en cuenta su naturaleza abstracta y sus diferencias con las máquinas físicas?

La respuesta corta es "porque fue diseñado para hacer exactamente eso". GHC utiliza la máquina g sin etiquetas sin espinas (STG). Puedes leer un artículo al respecto aquí (es bastante complejo). GHC también hace muchas otras cosas, como el análisis de rigor y la evaluación optimista .

La razón por la que digo que C y otros lenguajes imperativos son algo similares a las máquinas de Turing (pero no en la medida en que Haskell es similar al cálculo de Lambda) es que en un lenguaje imperativo, tiene un número finito de estados (también conocido como número de línea) con una cinta (el ram), de modo que el estado y la cinta actual determinen qué hacer con la cinta.

¿Es el punto de confusión entonces que la mutabilidad debería conducir a un código más lento? La pereza de Haskell en realidad significa que la mutabilidad no importa tanto como crees que sería, además es de alto nivel, por lo que hay muchas optimizaciones que el compilador puede aplicar. Por lo tanto, modificar un registro in situ rara vez será más lento de lo que sería en un lenguaje como C.

¿Por qué Haskell (GHC) es tan rápido?

Algo debe haber cambiado drásticamente desde la última vez que medí el rendimiento de Haskell. Por ejemplo:

• Un punto de referencia de procesamiento de archivos RRD donde el autor descubrió que Haskell tardó más en desarrollarse y se ejecuta más lentamente (1,020s) que Go (130s) y OCaml (67s), es decir, 15 veces más lento que OCaml.
• Un punto de referencia del diccionario simple mostró a Haskell corriendo ~ 10 veces más lento que F #.
• La comparación del lenguaje Ray Tracer es otro ejemplo en el que Haskell era más lento que C ++, OCaml e incluso Java y Lisp.
• Una clasificación rápida genérica paralela en Haskell fue un 55% más lenta que F # y requiere mucho más código.

Entonces, ¿qué ha cambiado? Noto que ni la pregunta ni ninguna de sus respuestas actuales se refieren a puntos de referencia verificables o incluso código.

Lo que más les gusta hacer a Haskellers es intentar alcanzar el 5% de C

¿Tiene alguna referencia a resultados verificables donde alguien alguna vez haya llegado a eso?