compilation - transparencia - ¿Los lenguajes funcionales son inherentemente lentos?
programacion logica (11)
Nada es intrínsecamente nada. Aquí hay un ejemplo donde OCaml interpretado se ejecuta más rápido que el código C equivalente , porque el optimizador OCaml tiene información diferente disponible, debido a las diferencias en el idioma. Por supuesto, sería una tontería hacer una afirmación general de que OCaml es categóricamente más rápido que C. El punto es que depende de lo que esté haciendo y de cómo lo haga.
Dicho esto, OCaml es un ejemplo de un lenguaje (principalmente) funcional que está diseñado para el rendimiento , en contraste con la pureza.
¿Por qué los lenguajes funcionales siempre van detrás de C en los puntos de referencia? Si tiene un lenguaje funcional estáticamente estátizado, me parece que podría compilarse con el mismo código que C, o con un código aún más optimizado, ya que hay más semántica disponible para el compilador. ¿Por qué parece que todos los lenguajes funcionales son más lentos que C y por qué siempre necesitan recolección de basura y uso excesivo del montón?
¿Alguien sabe de un lenguaje funcional apropiado para aplicaciones integradas / en tiempo real, donde la asignación de memoria se mantiene al mínimo y el código de la máquina producida es ligero y rápido?
C es rápido porque básicamente es un conjunto de macros para el ensamblador :) No hay "detrás de la escena" cuando está escribiendo un programa en C. Usted asigna memoria cuando decide que es hora de hacerlo y la libera de la misma manera. Esta es una gran ventaja cuando estás escribiendo una aplicación en tiempo real, donde la predicción es importante (más que cualquier otra cosa, en realidad).
Además, los compiladores de C son generalmente extremadamente rápidos porque el lenguaje en sí mismo es simple. Incluso no realiza ninguna verificación de tipo :) Esto también significa que es más fácil hacer que los errores sean difíciles de encontrar. La ventaja de los anuncios con la falta de comprobación de tipos es que el nombre de una función solo se puede exportar con su nombre, por ejemplo, y esto hace que el código C sea fácil de vincular con el código de otro idioma.
El flujo de control de los lenguajes procedurales se adapta mucho mejor a los patrones de procesamiento actuales de las computadoras modernas.
C se aproxima mucho al código ensamblador que produce su compilación, de ahí el apodo de "ensamblaje multiplataforma". Los fabricantes de computadoras han pasado algunas décadas haciendo que el código de ensamblaje se ejecute lo más rápido posible, por lo que C hereda toda esta velocidad bruta.
En comparación, el paralelismo inherente a los efectos colaterales de los lenguajes funcionales no se correlaciona bien con ningún procesador en particular. El orden arbitrario en el que se pueden invocar las funciones debe ser serializado hasta el cuello de botella de la CPU: sin una compilación extremadamente inteligente, vas a estar cambiando de contexto todo el tiempo, ninguna de las pre-búsquedas funcionará porque estás constantemente saltando en todas partes, ... Básicamente, todo el trabajo de optimización que los fabricantes de computadoras han hecho por lenguajes procedimentales agradables y predecibles es bastante inútil.
¡Sin embargo! Con el movimiento hacia muchos núcleos menos poderosos (en lugar de uno o dos núcleos turboalimentados), los lenguajes funcionales deberían comenzar a cerrar la brecha, ya que naturalmente se escalan horizontalmente.
La respuesta corta: porque C es rápido. Como en, increíblemente loco, rápido . Un lenguaje simplemente no tiene que ser "lento" para que C. le dé la espalda.
La razón por la cual C es rápido es que fue creado por codificadores realmente geniales, y gcc se ha optimizado en el transcurso de un par de décadas más y por docenas de codificadores más brillantes que el 99% de los idiomas que existen.
En resumen, no vas a vencer a C, excepto para tareas especializadas que requieren construcciones de programación funcional muy específicas.
Los lenguajes funcionales requieren la eliminación del estado mutable que es visible en el nivel de la abstracción del lenguaje. Por lo tanto, los datos que serían mutados en su lugar por un lenguaje imperativo deben ser copiados en su lugar, con la mutación teniendo lugar en la copia. Para un ejemplo simple, vea una clasificación rápida en Haskell vs. C.
Además, se requiere recolección de basura porque free() no es una función pura, ya que tiene efectos secundarios. Por lo tanto, la única manera de liberar memoria que no implica efectos secundarios en el nivel de la abstracción del lenguaje es con la recolección de basura.
Por supuesto, en principio, un compilador suficientemente inteligente podría optimizar gran parte de esta copia. Esto ya se ha hecho hasta cierto punto, pero hacer el compilador lo suficientemente inteligente como para entender la semántica de su código en ese nivel es simplemente difícil.
No estoy de acuerdo con tuinstoel. La pregunta importante es si el lenguaje funcional proporciona un tiempo de desarrollo más rápido y da como resultado un código más rápido cuando se usa para los lenguajes funcionales que se pretende usar. Vea la sección de problemas de eficiencia en Wikipedia para tener una idea de lo que quiero decir.
Por ahora, los lenguajes funcionales no se usan en gran medida para proyectos de la industria, por lo que no hay suficiente trabajo serio para los optimizadores. Además, la optimización del código imperativo para un objetivo imperativo es probablemente mucho más fácil.
Los lenguajes funcionales tienen una proeza que les permitirá superar los lenguajes imperativos muy pronto: la paralelización trivial.
Trivial no en el sentido de que es fácil, sino que puede integrarse en el entorno del lenguaje, sin que el desarrollador tenga que pensar en ello.
El costo de un multihilo robusto en un lenguaje agnóstico como C es prohibitivo para muchos proyectos.
Una razón más para un tamaño ejecutable más grande podría ser la evaluación perezosa y el no rigor. El compilador no puede determinar en tiempo de compilación cuándo se evalúan ciertas expresiones, de modo que parte del tiempo de ejecución se rellena en el ejecutable para manejar esto (para solicitar la evaluación de los denominados " thunks" ). En cuanto al rendimiento, la pereza puede ser buena y mala. Por un lado, permite una optimización potencial adicional, por otro lado, el tamaño del código puede ser mayor y los programadores tienen más probabilidades de tomar malas decisiones, por ejemplo, ver el foldl de Haskell vs. foldr vs. foldl '' contra foldr'' .
Well Haskell es solo 1.8 veces más lento que C ++ de GCC, que es más rápido que la implementación C de GCC para tareas típicas de referencia. Eso hace que Haskell sea muy rápido, incluso más rápido que C # (Mono que es).
Velocidad relativa del lenguaje
- 1.0 C ++ GNU g ++
- 1.1 C GNU gcc
- 1.2 ATS
- 1.5 Java 6 -server
- 1.5 Limpio
- 1.6 Pascal Free Pascal
- 1.6 Fortran Intel
- 1.8 Haskell GHC
- 2.0 C # Mono
- 2.1 Scala
- 2.2 Ada 2005 GNAT
- 2.4 Lisp SBCL
- 3.9 Lua LuaJIT
Para el registro utilizo Lua para juegos en el iPhone, por lo que podría usar fácilmente Haskell o Lisp si lo prefiere, ya que son más rápidos.
Un lenguaje funcional es fácil de ejecutar en paralelo, ejemplo erlang, es más lento que C, sí, no es compilar a código nativo, pero es más fácil de ejecutar paralelo y en modo paralelo es más rápido que eso en secuencia. El buen lenguaje es diferente en un caso u otro.
¿Los lenguajes funcionales son inherentemente lentos?
En cierto sentido, sí. Requieren una infraestructura que inevitablemente agrega gastos generales a lo que teóricamente puede lograrse utilizando ensamblador a mano. En particular, los cierres léxicos de primera clase solo funcionan bien con la recolección de basura porque permiten que los valores se lleven a cabo fuera del alcance.
¿Por qué los lenguajes funcionales siempre van detrás de C en los puntos de referencia?
En primer lugar, tenga cuidado con el sesgo de selección. C actúa como el mínimo común denominador en las suites de referencia, lo que limita lo que se puede lograr. Si tiene un punto de referencia que compara C con un lenguaje funcional, es casi seguro que es un programa extremadamente simple. Podría decirse que es tan simple que hoy tiene poca relevancia práctica. No es factible en la práctica resolver problemas más complicados usando C para una mera referencia.
El ejemplo más obvio de esto es el paralelismo. Hoy, todos tenemos multinúcleos. Incluso mi teléfono es multinúcleo. El paralelismo multinúcleo es notoriamente difícil en C pero puede ser fácil en los lenguajes funcionales (me gusta F #). Otros ejemplos incluyen todo lo que se beneficia de las estructuras de datos persistentes, por ejemplo, los búferes de deshacer son triviales con estructuras de datos puramente funcionales, pero pueden ser una gran cantidad de trabajo en lenguajes imperativos como C.
¿Por qué parece que todos los lenguajes funcionales son más lentos que C y por qué siempre necesitan recolección de basura y uso excesivo del montón?
Los lenguajes funcionales parecerán más lentos porque solo verá puntos de referencia que comparen el código que sea lo suficientemente fácil para escribir bien en C y nunca verá puntos de referencia que comparen tareas más exigentes donde los lenguajes funcionales comiencen a sobresalir.
Sin embargo, ha identificado correctamente cuál es probablemente el mayor cuello de botella en los lenguajes funcionales actuales: sus tasas de asignación excesiva. ¡Buen trabajo!
Las razones por las que los lenguajes funcionales se asignan tan fuertemente se pueden dividir en razones históricas e inherentes.
Históricamente, las implementaciones de Lisp han estado haciendo mucho boxeo durante 50 años. Esta característica se extiende a muchos otros lenguajes que usan representaciones intermedias tipo Lisp. Con los años, los implementadores de lenguaje han recurrido continuamente al boxeo como una solución rápida para las complicaciones en la implementación del lenguaje. En los lenguajes orientados a objetos, el valor predeterminado ha sido asignar siempre de forma aleatoria todos los objetos, incluso cuando obviamente se pueden asignar apilados. La carga de la eficiencia se colocó en el recolector de basura y se invirtió una gran cantidad de esfuerzo en la construcción de recolectores de basura que pueden lograr un rendimiento cercano al de la asignación de la pila, por lo general mediante el uso de una generación de guardería que asigna los topes. Creo que se debe dedicar mucho más esfuerzo a la investigación de diseños de lenguaje funcional que minimicen los diseños de boxeo y recolector de basura que están optimizados para diferentes requisitos.
Los recolectores de basura generacionales son excelentes para los lenguajes que el montón asigna mucho porque pueden ser casi tan rápidos como la asignación de la pila. Pero agregan gastos generales sustanciales en otros lugares. Los programas actuales utilizan cada vez más estructuras de datos como colas (por ejemplo, para la programación concurrente) y dan un comportamiento patológico a los recolectores de basura generacionales. Si los artículos en la cola sobreviven a la primera generación, todos son marcados, luego todos son copiados ("evacuados"), luego todas las referencias a sus ubicaciones anteriores se actualizan y luego son elegibles para la recolección. Esto es aproximadamente 3 veces más lento de lo necesario (p. Ej., En comparación con C). Los recolectores de Mark Mark como Beltway (2002) e Immix (2008) tienen el potencial para resolver este problema porque el vivero se reemplaza por una región que puede ser recolectada como si fuera un vivero o, si contiene valores alcanzables, puede se sustituirá por otra región y se dejará envejecer hasta que contenga valores prácticamente inalcanzables.
A pesar de la preexistencia de C ++, los creadores de Java cometieron el error de adoptar el borrado de tipos de genéricos, lo que condujo a un boxeo innecesario. Por ejemplo, comparé una tabla de hash simple que funciona 17 veces más rápido en .NET que en la JVM, en parte porque .NET no cometió este error (utiliza genéricos reificados) y también porque .NET tiene tipos de valores. En realidad culpo a Lisp por hacer que Java sea lento.
Todas las implementaciones modernas de lenguaje funcional continúan encajonando excesivamente. Los lenguajes basados en JVM como Clojure y Scala tienen pocas opciones porque la máquina virtual a la que se dirigen no puede expresar tipos de valores. OCaml arroja información tipo al principio de su proceso de compilación y recurre a enteros etiquetados y al boxeo en tiempo de ejecución para manejar el polimorfismo. En consecuencia, OCaml a menudo encajona números de coma flotante individuales y siempre coloca tuplas. Por ejemplo, un triple de bytes en OCaml está representado por un puntero (con una etiqueta implícita de 1 bit incrustada en él que se comprueba repetidamente en tiempo de ejecución) a un bloque asignado al montón con un encabezado de 64 bits y un cuerpo de 192 bits que contiene tres enteros de 63 bits etiquetados (donde las 3 etiquetas son, de nuevo, examinadas repetidamente en tiempo de ejecución). Esto es claramente loco.
Se ha hecho algo de trabajo sobre optimizaciones de unboxing en lenguajes funcionales, pero nunca ganó realmente tracción. Por ejemplo, el compilador de MLton para Standard ML era un compilador de optimización de todo el programa que realizaba optimizaciones sofisticadas de unboxing. Lamentablemente, fue antes de tiempo y los tiempos de compilación "largos" (¡probablemente por debajo de 1 en una máquina moderna!) Impidieron que la gente lo usara.
La única plataforma importante que ha roto esta tendencia es .NET pero, sorprendentemente, parece haber sido un accidente. A pesar de tener una implementación de Dictionary muy optimizada para claves y valores que son de tipos de valor (porque están unboxed), los empleados de Microsoft como Eric Lippert siguen afirmando que lo importante sobre los tipos de valor es su semántica de valor por paso y no el rendimiento características que se derivan de su representación interna sin caja. Parece que Eric ha demostrado estar equivocado: a más desarrolladores .NET parece importarles más el desempaquetado que el valor pasante. De hecho, la mayoría de las estructuras son inmutables y, por lo tanto, son referencialmente transparentes, por lo que no existe una diferencia semántica entre pasar por valor y pasar por referencia. El rendimiento es visible y las estructuras pueden ofrecer mejoras de rendimiento masivas. El rendimiento de las estructuras, incluso el y las estructuras guardadas se utilizan para evitar la latencia de GC en software comercial como Rapid Addition''s .
La otra razón para una gran asignación por idiomas funcionales es inherente. Las estructuras de datos imperativas, como las tablas hash, usan enormes matrices monolíticas internamente. Si estos fueran persistentes, entonces los enormes arreglos internos tendrían que copiarse cada vez que se realizara una actualización. Por lo tanto, las estructuras de datos puramente funcionales como los árboles binarios equilibrados se fragmentan en muchos pequeños bloques asignados en el montón para facilitar la reutilización de una versión de la colección a la siguiente.
Clojure utiliza un buen truco para solucionar este problema cuando colecciones como diccionarios solo se escriben durante la inicialización y luego se leen mucho. En este caso, la inicialización puede usar una mutación para construir la estructura "detrás de escena". Sin embargo, esto no ayuda con las actualizaciones incrementales y las colecciones resultantes son todavía mucho más lentas de leer que sus equivalentes imperativos. En el lado positivo, las estructuras de datos puramente funcionales ofrecen persistencia, mientras que las imperativas no. Sin embargo, pocas aplicaciones prácticas se benefician de la persistencia en la práctica, por lo que a menudo esto no es ventajoso. De ahí el deseo de lenguajes funcionales impuros en los que pueda apegarse al estilo imperativo sin esfuerzo y cosechar los beneficios.
¿Alguien sabe de un lenguaje funcional apropiado para aplicaciones integradas / en tiempo real, donde la asignación de memoria se mantiene al mínimo y el código de la máquina producida es ligero y rápido?
Eche un vistazo a Erlang y OCaml si aún no lo ha hecho. Ambos son razonables para sistemas con memoria limitada, pero ninguno genera un código de máquina especialmente bueno.