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

246

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.

PyRulez
fuente
27
"ya que GHC compila Haskell a C", no lo hace. GHC tiene múltiples backends. El más antiguo (pero no el predeterminado) es un generador de C. Genera código Cmm para IR, pero eso no es "compilar a C" que normalmente esperarías. ( downloads.haskell.org/~ghc/latest/docs/html/users_guide/… )
viraptor
19
Le recomiendo leer Implementación de lenguajes de programación funcional por Simon Payton Jones (el implementador principal de GHC) que responderá muchas de sus preguntas.
Joe Hillenbrand
94
¿Por qué? 25 años de duro trabajo.
augustss
31
"Aunque pueda haber una respuesta objetiva, no hará nada más que solicitar opiniones". - Esta es la peor razón posible para cerrar una pregunta. Porque puede tener una buena respuesta, pero potencialmente también atraerá a los de baja calidad. ¡Qué asco! Resulta que tengo una buena respuesta histórica y objetiva sobre la investigación académica y cuándo ocurrieron ciertos desarrollos. Pero no puedo publicarlo porque a la gente le preocupa que esta pregunta también pueda atraer respuestas de baja calidad. De nuevo, qué asco.
sclv
77
@cimmanon Necesitaría un mes o varias publicaciones de blog para recorrer los conceptos básicos de los detalles de cómo funciona un compilador funcional. Solo necesito una respuesta SO para esbozar a grandes rasgos cómo se puede implementar una máquina de gráficos limpiamente en el hardware de stock y señalar las fuentes relevantes para una lectura adicional ...
sclv

Respuestas:

264

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

Orquídea matemática
fuente
13
@cimmanon No creo que esté puramente basado en opiniones. Es una pregunta interesante a la que otras personas probablemente hayan querido una respuesta. Pero creo que veremos lo que piensan otros votantes.
MathematicalOrchid
8
@cimmanon: esa búsqueda solo da un hilo y medio, y todos tienen que ver con auditorías de revisión. y la respuesta votada al hilo dice "por favor, deja de moderar cosas que no entiendes". Sugeriría que si alguien piensa que la respuesta a esto es necesariamente demasiado amplia, entonces se sorprendería y disfrutaría la respuesta, ya que la respuesta no es demasiado amplia.
sclv
34
"En, digamos, Java, la JVM debe verificar si hay punteros nulos y lanzar una excepción si hace referencia a uno". La comprobación nula implícita de Java es (en su mayoría) sin costo. Las implementaciones de Java pueden y aprovechan la memoria virtual para asignar la dirección nula a una página faltante, por lo que la desreferenciación de un puntero nulo desencadena un error de página en el nivel de CPU, que Java atrapa y arroja como una excepción de alto nivel. Entonces, la unidad de mapeo de memoria en la CPU realiza la mayoría de las verificaciones nulas de forma gratuita.
Boann
44
@cimmanon: Quizás eso se deba a que los usuarios de Haskell parecen ser la única comunidad que en realidad es un grupo amistoso de personas de mente abierta ... lo que consideras "una broma" ..., en lugar de una comunidad de nazis de perros-come-perros. rasgarse uno nuevo cada vez que tengan la oportunidad ... lo que parece ser lo que ustedes consideran "normal".
Evi1M4chine
14
@MathematicalOrchid: ¿tiene una copia de su programa original que tardó 20 minutos en ejecutarse? Creo que sería bastante instructivo estudiar por qué es tan lento.
George
79

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 .

sclv
fuente
2
¡Ese enlace del analizador de demanda vale su peso en oro! Finalmente, algo sobre el tema que no actúa como si fuera básicamente magia negra inexplicable. ¿Cómo nunca he oído hablar de esto? ¡Debe estar vinculado desde cualquier lugar donde cualquiera pregunte cómo abordar los problemas con la pereza!
Evi1M4chine
@ Evi1M4chine No veo un enlace relacionado con un analizador de demanda, quizás se haya perdido de alguna manera. ¿Alguien puede restaurar el enlace o aclarar la referencia? Suena bastante interesante
Cris P
1
@CrisP Creo que el último enlace es al que se hace referencia. Va a una página en el Wiki de GHC sobre el analizador de demanda en GHC.
Serp C
@Serpentine Cougar, Chris P: Sí, es lo que quise decir.
Evi1M4chine
19

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.


fuente
3

¿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:

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?

Jon Harrop
fuente
66
¿Alguien volvió a decir el nombre de Harrop frente al espejo tres veces?
Chuck Adams el
2
no 10 veces, pero aún así, toda esta entrada es publicidad y tripas de marketing. De hecho, GHC es bastante capaz de acercarse a C o incluso superarlo, en términos de velocidad, pero eso generalmente requiere un estilo de programación bastante complejo y de bajo nivel, no muy diferente de la programación en C en sí. Desafortunadamente. cuanto más alto es el código, más lento suele ser. fugas de espacio, tipos ADT convenientes pero de bajo rendimiento ( algebraicos , no abstractos , como era la promesa), etc., etc.
Will Ness
1
Solo estoy publicando esto porque lo vi hoy chrispenner.ca/posts/wc . Es una implementación de la utilidad wc escrita en Haskell que supuestamente supera a la versión c.
Guarnición
3
@Garrison gracias por el enlace . 80 líneas es lo que llamé "estilo de programación de bajo nivel no muy diferente de la programación en C". . "el código de nivel superior", ese sería el "estúpido" fmap (length &&& length . words &&& length . lines) readFile. Si eso fuera más rápido (o incluso comparable a) C, la exageración aquí estaría totalmente justificada entonces . Todavía tenemos que trabajar duro para la velocidad en Haskell como en C, ese es el punto.
Will Ness
2
A juzgar por esta discusión en Reddit reddit.com/r/programming/comments/dj4if3/…, el código de Haskell es realmente defectuoso (por ejemplo, los saltos en las líneas comienzan o terminan con espacios en blanco, los espacios en à) y otros no pueden reproducir los resultados de rendimiento reclamados.
Jon Harrop