¿Puede un lenguaje dinámico como Ruby / Python alcanzar un rendimiento similar a C / C ++?

64

Me pregunto si es posible construir compiladores para lenguajes dinámicos como Ruby para tener un rendimiento similar y comparable a C / C ++. Por lo que entiendo sobre los compiladores, tomemos Ruby, por ejemplo, compilar el código Ruby nunca puede ser eficiente porque la forma en que Ruby maneja el reflejo, características como la conversión automática de tipo de entero a gran número y la falta de tipeo estático hacen que la construcción de un compilador eficiente para Ruby extremadamente difícil.

¿Es posible construir un compilador que pueda compilar Ruby o cualquier otro lenguaje dinámico en un binario que funcione muy de cerca con C / C ++? ¿Existe una razón fundamental por la cual los compiladores JIT, como PyPy / Rubinius, eventualmente o nunca coincidirán con C / C ++ en rendimiento?

Nota: Entiendo que el "rendimiento" puede ser vago, así que para aclarar eso, quiero decir, si puedes hacer X en C / C ++ con rendimiento Y, ¿puedes hacer X en Ruby / Python con un rendimiento cercano a Y? Donde X es todo, desde los controladores de dispositivos y el código del sistema operativo, hasta las aplicaciones web.

Ichiro
fuente
1
¿Puede reformular la pregunta para que fomente respuestas respaldadas por evidencia adecuada sobre los demás?
Rafael
@Raphael He seguido adelante y editado. Creo que mi edición no cambia fundamentalmente el significado de la pregunta, sino que la hace menos atractiva para los artículos de opinión.
Gilles 'SO- deja de ser malvado'
1
En particular, creo que debe corregir una (o algunas) medidas concretas de rendimiento. Tiempo de ejecución? Uso del espacio? ¿Uso de energía? Tiempo de desarrollador? ¿Retorno de la inversión? Tenga en cuenta también esta pregunta en nuestro meta que se refiere a esta pregunta (o más bien sus respuestas).
Raphael
Esta pregunta es un iniciador típico de guerras religiosas. Y como podemos ver en las respuestas, tenemos una, aunque muy civilizada.
Andrej Bauer
Hay lenguajes dinámicos que permiten anotaciones de tipo opcionales (por ejemplo: Clojure). Por lo que sé, el rendimiento asociado con las funciones de tipo anotado es equivalente a cuando un idioma se escribiría estáticamente.
Pedro Morte Rolo

Respuestas:

68

A todos aquellos que dijeron "sí", ofreceré un contrapunto de que la respuesta es "no", por diseño . Esos idiomas nunca podrán igualar el rendimiento de los idiomas compilados estáticamente.

Kos ofreció el punto (muy válido) de que los lenguajes dinámicos tienen más información sobre el sistema en tiempo de ejecución que se puede utilizar para optimizar el código.

Sin embargo, hay otra cara de la moneda: esta información adicional debe mantenerse al tanto. En arquitecturas modernas, esto es un asesino de rendimiento.

William Edwards ofrece una buena visión general del argumento .

En particular, las optimizaciones mencionadas por Kos no se pueden aplicar más allá de un alcance muy limitado a menos que limite drásticamente el poder expresivo de sus idiomas, como lo menciona Devin. Por supuesto, esto es una compensación viable, pero por el bien de la discusión, terminas con un lenguaje estático , no dinámico. Esos lenguajes difieren fundamentalmente de Python o Ruby como la mayoría de la gente los entendería.

William cita algunas diapositivas interesantes de IBM :

  • Cada variable se puede escribir dinámicamente: se necesitan verificaciones de tipo
  • Cada declaración puede generar excepciones debido a la falta de coincidencia de tipos, etc.: se necesitan verificaciones de excepción
  • Todos los campos y símbolos se pueden agregar, eliminar y cambiar en tiempo de ejecución: se necesitan verificaciones de acceso
  • El tipo de cada objeto y su jerarquía de clases se pueden cambiar en tiempo de ejecución: se necesitan verificaciones de jerarquía de clases

Algunos de esos controles pueden eliminarse después del análisis (NB: este análisis también lleva tiempo, en tiempo de ejecución).

Además, Kos argumenta que los lenguajes dinámicos podrían incluso superar el rendimiento de C ++. El JIT puede analizar el comportamiento del programa y aplicar optimizaciones adecuadas.

¡Pero los compiladores de C ++ pueden hacer lo mismo! Los compiladores modernos ofrecen la denominada optimización guiada por perfil que, si se les proporciona una entrada adecuada, puede modelar el comportamiento del tiempo de ejecución del programa y aplicar las mismas optimizaciones que aplicaría un JIT.

Por supuesto, todo esto depende de la existencia de datos de entrenamiento realistas y, además, el programa no puede adaptar sus características de tiempo de ejecución si el patrón de uso cambia a mitad de carrera. Los JIT teóricamente pueden manejar esto. Me interesaría ver cómo funciona esto en la práctica, ya que, para cambiar las optimizaciones, el JIT continuamente tendría que recopilar datos de uso, lo que una vez más ralentiza la ejecución.

En resumen, no estoy convencido de que las optimizaciones de los puntos calientes de tiempo de ejecución superen la sobrecarga de la información de tiempo de seguimiento a largo plazo , en comparación con el análisis estático y la optimización.

Konrad Rudolph
fuente
2
@Raphael Esa es una "deficiencia" del compilador entonces. En particular, ¿ javacalguna vez la optimización guiada por perfil? No hasta donde yo sé. En general, no tiene sentido hacer que el compilador de un lenguaje JITted sea bueno para la optimización, ya que el JIT puede manejarlo (y al menos, de esta manera, más idiomas se benefician del esfuerzo). Entonces (comprensiblemente) nunca se puso mucho esfuerzo en el javacoptimizador, que yo sepa (para los lenguajes .NET esto es definitivamente cierto).
Konrad Rudolph
1
@Raphael La palabra clave es: tal vez. No lo muestra de ninguna manera. Eso es todo lo que quería decir. He dado razones (pero no pruebas) de mi suposición en los párrafos anteriores.
Konrad Rudolph
1
@Ben, no niego que sea complicado. Esto es simplemente una intuición. El seguimiento de toda esa información en tiempo de ejecución tiene un costo, después de todo. No estoy convencido por su punto sobre IO. Si esto es predecible (= caso de uso típico), entonces PGO puede predecirlo. Si es espurio, tampoco estoy convencido de que el JIT pueda optimizarlo. Tal vez de vez en cuando, por pura suerte. Pero confiablemente? ...
Konrad Rudolph
2
@ Konrad: Tu intuición es falsa. No se trata de variar en tiempo de ejecución, se trata de imprevisibilidad en tiempo de compilación . El punto óptimo para los JIT frente a la optimización estática no es cuando el comportamiento del programa cambia en tiempo de ejecución "demasiado rápido" para la creación de perfiles, es cuando el comportamiento del programa es fácil de optimizar en cada ejecución individual del programa, sino que varía enormemente entre carreras. Un optimizador estático generalmente tendrá que optimizar solo para un conjunto de condiciones, mientras que un JIT optimiza cada ejecución por separado, para las condiciones que ocurren en esa ejecución.
Ben
3
Aviso: este hilo de comentarios se está convirtiendo en una mini sala de chat. Si desea continuar esta discusión, tráigala al chat. Los comentarios deben usarse para mejorar la publicación original. Por favor, interrumpa esta conversación aquí. Gracias.
Robert Cartaino
20

si puede hacer X en C / C ++ con rendimiento Y, ¿puede hacer X en Ruby / Python con un rendimiento cercano a Y?

Si. Tomemos, como ejemplo, PyPy. Es una colección de código Python que se realiza cerca de C al interpretar (no tan cerca, pero tampoco tan lejos). Para ello, realiza un análisis completo del programa en el código fuente para asignar a cada variable un tipo estático (consulte los documentos Annotator y Rtyper para más detalles), y luego, una vez armado con la misma información de tipo que le da a C, puede realizar lo mismo tipos de optimizaciones. Al menos en teoría.

La compensación, por supuesto, es que solo RPython acepta un subconjunto de código Python y, en general, incluso si se elimina esa restricción, solo un subconjunto de código Python puede funcionar bien: el subconjunto que puede analizarse y recibir tipos estáticos.

Si restringe Python lo suficiente, se pueden construir optimizadores que pueden aprovechar el subconjunto restringido y compilarlo en un código eficiente. Esto no es realmente un beneficio interesante, de hecho, es bien conocido. Pero el objetivo principal de usar Python (o Ruby) en primer lugar fue que queríamos usar características interesantes que tal vez no se analicen bien y resulten en un buen rendimiento. Entonces la pregunta interesante es en realidad ...

Además, ¿los compiladores JIT, como PyPy / Rubinius, igualarán alguna vez el rendimiento de C / C ++?

Nah

Por lo que quiero decir: claro, tal vez a medida que se acumula el código se puede obtener suficiente información de escritura y puntos de acceso suficientes para compilar todo el código hasta el código de la máquina. Y tal vez podamos lograr que esto funcione mejor que C para algún código. No creo que sea muy controvertido. Pero todavía tiene que "calentarse", y el rendimiento sigue siendo un poco menos predecible, y no será tan bueno como C o C ++ para ciertas tareas que requieren un rendimiento alto constante y previsible.

Los datos de rendimiento existentes para Java, que tienen más información de tipo que Python o Ruby, y un compilador JIT mejor desarrollado que Python o Ruby, aún no coinciden con C / C ++. Sin embargo, está en el mismo estadio.

Devin Jeanpierre
fuente
1
"La compensación, por supuesto, es que solo se acepta un subconjunto de código Python, o mejor dicho, solo un subconjunto de código Python puede funcionar bien: el subconjunto que puede analizarse y recibir tipos estáticos". Esto no es del todo exacto. Solo el subconjunto puede ser aceptado por el compilador RPython. Compilar en RPython a C razonablemente eficiente solo funciona precisamente porque las partes difíciles de compilar de Python nunca se producirán en los programas de RPython; no se trata simplemente de que si se producen no se optimizarán. Es el intérprete compilado que maneja todo Python.
Ben
1
Acerca de JIT: He visto más de un punto de referencia donde Java superó varios sabores de C (++). Solo C ++ con impulso parece mantenerse a la vanguardia de manera confiable. En ese caso, me pregunto sobre el rendimiento por tiempo de desarrollador, pero ese es otro tema.
Raphael
@Ben: una vez que tenga RPython, es trivial crear un compilador / intérprete que recurra al uso del intérprete CPython cuando falla el compilador RPython, por lo tanto, "solo un subconjunto de código Python puede funcionar bien: ..." es totalmente preciso.
Lie Ryan
99
@Raphael Se ha demostrado muchas veces que el código C ++ bien escrito supera a Java. Sin embargo, es la parte "bien escrita" que es bastante difícil de obtener en C ++, por lo que en muchos bancos se ven los resultados de que Java supera a C ++. C ++ es, por lo tanto, más costoso, pero cuando se necesita el control estricto de la memoria y la arena metálica, C / C ++ es a lo que recurre. C en particular es solo ensamblador ac / p.
TC1
77
Comparar el rendimiento máximo de otros idiomas con lenguajes como C / C ++ es una especie de ejercicio inútil, ya que puede incorporar el ensamblaje directamente como parte de la especificación del lenguaje. Cualquier cosa que la máquina pueda hacer ejecutando un programa escrito en cualquier idioma, en el peor de los casos, puede duplicar escribiendo ensamblado a partir de un rastro de instrucciones ejecutadas. Una métrica mucho más interesante sería, como sugiere @Raphael en un comentario anterior, rendimiento por esfuerzo de desarrollo (horas hombre, líneas de código, etc.).
Patrick87
18

La respuesta corta es: no sabemos , vuelva a preguntar en 100 años. (Es posible que aún no lo sepamos; posiblemente nunca lo sabremos).

En teoría, esto es posible. Tome todos los programas que se han escrito, traduzca manualmente al código de máquina más eficiente posible y escriba un intérprete que asigne los códigos fuente a los códigos de máquina. Esto es posible ya que solo se ha escrito un número finito de programas (y a medida que se escriben más programas, mantenga las traducciones manuales). Esto también es, por supuesto, completamente idiota en términos prácticos.

Por otra parte, en teoría, los lenguajes de alto nivel podrían alcanzar el rendimiento del código de máquina, pero no lo superarán. Esto sigue siendo muy teórico, porque en términos prácticos, rara vez recurrimos a escribir código de máquina. Este argumento no se aplica a la comparación de lenguajes de nivel superior: no implica que C deba ser más eficiente que Python, solo que el código de máquina no puede ser peor que Python.

Viniendo del otro lado, en términos puramente experimentales, podemos ver que la mayoría de las veces , los lenguajes interpretados de alto nivel tienen un rendimiento peor que los lenguajes compilados de bajo nivel. Tendemos a escribir código no sensible al tiempo en lenguajes de muy alto nivel y bucles internos críticos en el ensamblaje, con lenguajes como C y Python en el medio. Si bien no tengo ninguna estadística para respaldar esto, creo que esta es la mejor decisión en la mayoría de los casos.

Sin embargo, hay instancias indiscutibles donde los lenguajes de alto nivel superan el código que uno escribiría de manera realista: entornos de programación de propósito especial. Programas como Matlab y Mathematica a menudo son mucho mejores para resolver ciertos tipos de problemas matemáticos que lo que los simples mortales pueden escribir. Las funciones de la biblioteca pueden haber sido escritas en C o C ++ (lo cual es combustible para el campamento “los lenguajes de bajo nivel son más eficientes”), pero eso no es asunto mío si estoy escribiendo código de Mathematica, la biblioteca es un recuadro negro.

¿Es teóricamente posible que Python esté tan cerca, o tal vez incluso más cerca, de un rendimiento óptimo que C? Como se vio anteriormente, sí, pero hoy estamos muy lejos de eso. Por otra parte, los compiladores han progresado mucho en las últimas décadas, y ese progreso no se está desacelerando.

Los lenguajes de alto nivel tienden a hacer más cosas automáticas, por lo que tienen más trabajo que realizar y, por lo tanto, tienden a ser menos eficientes. Por otro lado, tienden a tener más información semántica, por lo que puede ser más fácil detectar optimizaciones (si está escribiendo un compilador Haskell, no tiene que preocuparse de que otro hilo modifique una variable debajo de su nariz). Uno de los varios esfuerzos para comparar diferentes lenguajes de programación de manzanas y naranjas es el Computer Language Benchmark Game (anteriormente conocido como el tiroteo). Fortran tiende a brillar en las tareas numéricas; pero cuando se trata de manipular datos estructurados o conmutación de hilos de alta velocidad, F # y Scala lo hacen bien. No tome estos resultados como evangelio: mucho de lo que están midiendo es lo bueno que fue el autor del programa de prueba en cada idioma.

Un argumento a favor de los lenguajes de alto nivel es que el rendimiento en los sistemas modernos no está tan fuertemente correlacionado con el número de instrucciones que se ejecutan, y menos con el tiempo. Los lenguajes de bajo nivel son una buena combinación para máquinas secuenciales simples. Si un lenguaje de alto nivel ejecuta el doble de instrucciones, pero logra usar el caché de manera más inteligente, por lo que hace la mitad de las fallas de caché, puede terminar siendo el ganador.

En las plataformas de servidor y de escritorio, las CPU casi han alcanzado una meseta en la que no llegan más rápido (las plataformas móviles también están llegando allí); Esto favorece los lenguajes donde el paralelismo es fácil de explotar. Muchos procesadores pasan la mayor parte de su tiempo esperando una respuesta de E / S; El tiempo dedicado a la computación importa poco en comparación con la cantidad de E / S, y un lenguaje que permite al programador minimizar las comunicaciones es una ventaja.

En general, si bien los idiomas de alto nivel comienzan con una penalización, tienen más margen de mejora. ¿Qué tan cerca pueden llegar? Pregunte nuevamente en 100 años.

Nota final: a menudo, la comparación no es entre el programa más eficiente que se puede escribir en el idioma A y el mismo en el idioma B, ni entre el programa más eficiente jamás escrito en cada idioma, sino entre el programa más eficiente que se puede escribir por un humano en una cierta cantidad de tiempo en cada idioma. Esto introduce un elemento que no puede analizarse matemáticamente, ni siquiera en principio. En términos prácticos, esto a menudo significa que el mejor rendimiento es un compromiso entre la cantidad de código de bajo nivel que necesita escribir para cumplir con los objetivos de rendimiento y la cantidad de código de bajo nivel que tiene tiempo de escribir para cumplir con las fechas de lanzamiento.

Gilles 'SO- deja de ser malvado'
fuente
Creo que la distinción entre alto nivel y bajo nivel es incorrecta. C ++ puede ser (muy) de alto nivel. Sin embargo, el C ++ moderno de alto nivel no (necesariamente) funciona peor que un equivalente de bajo nivel, todo lo contrario. C ++ y sus bibliotecas fueron cuidadosamente diseñadas para ofrecer abstracciones de alto nivel sin penalización de rendimiento. Lo mismo ocurre con su ejemplo de Haskell: sus abstracciones de alto nivel a menudo permiten en lugar de evitar optimizaciones. La distinción original entre lenguajes dinámicos y lenguajes estáticos tiene más sentido a este respecto.
Konrad Rudolph
@KonradRudolph Tienes razón, en ese nivel bajo / alto es una distinción algo arbitraria. Pero los lenguajes dinámico vs estático tampoco capturan todo; un JIT puede eliminar gran parte de la diferencia. Esencialmente, las respuestas teóricas conocidas a esta pregunta son triviales e inútiles, y la respuesta práctica es "depende".
Gilles 'SO- deja de ser malvado'
Bueno, entonces, creo que la pregunta se convierte en "qué tan buenos pueden ser los JIT, y si superan la compilación estática, ¿pueden los lenguajes compilados estáticamente también beneficiarse de ellos?" Al menos así es como entiendo la pregunta una vez que tenemos en cuenta los JIT. Y sí, estoy de acuerdo con su evaluación, pero seguramente podemos obtener algunas conjeturas informadas que van más allá de "depende". ;-)
Konrad Rudolph
@KonradRudolph Si quisiera adivinar, preguntaría sobre Ingeniería de Software .
Gilles 'SO- deja de ser malvado'
1
Desafortunadamente, el tiroteo del idioma es una fuente cuestionable de puntos de referencia cuantitativos: no aceptan todos los programas, solo aquellos que se consideran típicos del idioma. Este es un requisito complicado y muy subjetivo; significa que no se puede suponer que una implementación de tiroteo es realmente buena (y en la práctica, algunas implementaciones obviamente tienen alternativas superiores rechazadas). Por otro lado; Estos son microbenchmarks y algunas implementaciones usan técnicas inusuales que nunca considerarías en un escenario más normal solo para ganar rendimiento. Entonces: es un juego, no una fuente de datos muy confiable.
Eamon Nerbonne
10

La diferencia básica entre la declaración C ++ x = a + by la declaración de Python x = a + bes que un compilador C / C ++ se puede decir de esta declaración (y un poco de información extra que tiene fácilmente disponible sobre los tipos de x, ay b) precisamente lo que el código máquina tiene que ser ejecutado . Mientras que para saber qué operaciones va a hacer la declaración de Python, debe resolver el problema de detención.

En C, esa declaración básicamente se compilará en uno de los pocos tipos de adición de máquinas (y el compilador de C sabe cuál). En C ++ podría compilarse de esa manera, o podría compilarse para llamar a una función conocida estáticamente, o (en el peor de los casos) podría tener que compilar a una búsqueda y llamada de método virtual, pero incluso esto tiene una sobrecarga de código de máquina bastante pequeña. Sin embargo, lo más importante es que el compilador de C ++ puede distinguir entre los tipos estáticamente conocidos involucrados si puede emitir una sola operación de adición rápida o si necesita usar una de las opciones más lentas.

En Python, un compilador en teoría podría hacer casi tan bueno si se sabía que ay bfueron ambos ints. Hay algunos gastos adicionales de boxeo, pero si los tipos se conocieran estáticamente, probablemente también podría deshacerse de eso (mientras presenta la interfaz de que los enteros son objetos con métodos, jerarquía de superclases, etc.). El problema es que un compilador para Python no puedesepa esto, porque las clases se definen en tiempo de ejecución, se pueden modificar en tiempo de ejecución e incluso los módulos que realizan la definición y la importación se resuelven en tiempo de ejecución (e incluso qué instrucciones de importación se ejecutan depende de cosas que solo se pueden conocer en tiempo de ejecución). Por lo tanto, el compilador de Python tendría que saber qué código se ha ejecutado (es decir, resolver el problema de detención) para saber qué hará la declaración que está compilando.

Entonces, incluso con los análisis más sofisticados que son teóricamente posibles , simplemente no se puede decir mucho sobre lo que una declaración Python dada va a hacer con anticipación. Esto significa que incluso si se implementara un compilador Python sofisticado, en la mayoría de los casos aún tendría que emitir código de máquina que siga el protocolo de búsqueda del diccionario Python para determinar la clase de un objeto y encontrar métodos (atravesando el MRO de la jerarquía de clases, que también puede cambiar dinámicamente en tiempo de ejecución y, por lo tanto, es difícil de compilar en una tabla de método virtual simple, y básicamente hacer lo que hacen los intérpretes (lentos). Es por eso que no hay realmente ningún compilador de optimización sofisticado para lenguajes dinámicos. No es simplemente difícil crear uno, el beneficio máximo posible no es

Tenga en cuenta que esto no se basa en lo que está haciendo el código , se basa en lo que el código podría estar haciendo. Incluso el código Python que es una serie simple de operaciones aritméticas de enteros debe compilarse como si pudiera invocar operaciones de clase arbitrarias. Los lenguajes estáticos tienen mayores restricciones sobre las posibilidades de lo que el código podría estar haciendo y, en consecuencia, sus compiladores pueden hacer más suposiciones.

Los compiladores JIT ganan en esto al esperar hasta el tiempo de ejecución para compilar / optimizar. Esto les permite emitir código que funciona para lo que está haciendo el código en lugar de lo que podría estar haciendo. Y debido a esto, los compiladores JIT tienen un beneficio potencial mucho mayor para los lenguajes dinámicos que para los estáticos; para más lenguajes estáticos, mucho de lo que un optimizador desearía saber puede conocerse con anticipación, por lo que también podría optimizarlo, dejando menos para que lo haga un compilador JIT.

Existen varios compiladores JIT para lenguajes dinámicos que afirman alcanzar velocidades de ejecución comparables a las de C / C ++ compilado y optimizado. Incluso hay optimizaciones que puede hacer un compilador JIT que no puede hacer un compilador anticipado para ningún idioma, por lo que teóricamente, la compilación JIT (para algunos programas) algún día podría superar el mejor compilador estático posible. Pero como Devin señaló correctamente, las propiedades de la compilación JIT (solo los "puntos calientes" son rápidos, y solo después de un período de calentamiento) significa que es poco probable que los lenguajes dinámicos compilados JIT sean adecuados para todas las aplicaciones posibles, incluso si se vuelven tan rápido o más rápido que los lenguajes compilados estáticamente en general.

Ben
fuente
1
Eso es ahora dos votos negativos sin comentarios. ¡Me gustaría recibir sugerencias sobre cómo mejorar esta respuesta!
Ben
No voté en contra, pero está equivocado acerca de "la necesidad de resolver el problema de detención". Se ha demostrado en muchas circunstancias que el código en lenguajes dinámicos se puede compilar para obtener un código objetivo óptimo, mientras que, hasta donde sé, ninguna de estas demostraciones ha incluido una solución al problema de detención :-)
mikera
@mikera Lo siento, pero no, eres incorrecto. Nadie ha implementado un compilador (en el sentido de que comprendamos que GCC es un compilador) para Python totalmente general u otros lenguajes dinámicos. Cada uno de estos sistemas solo funciona para un subconjunto del lenguaje, o solo para ciertos programas, o a veces emite código que es básicamente un intérprete que contiene un programa codificado. Si lo desea, le escribiré un programa de Python que contiene la línea foo = x + ydonde predecir el comportamiento del operador de suma en tiempo de compilación depende de la resolución del problema de detención.
Ben
Estoy en lo cierto y creo que te estás perdiendo el punto. Dije "en muchas circunstancias". No dije "en todas las circunstancias posibles". Si puede o no construir un ejemplo artificial relacionado con el problema de detención es irrelevante en el mundo real. FWIW, también podrías construir un ejemplo similar para C ++ para que no pruebes nada de todos modos. De todos modos, no vine aquí para discutir, solo para sugerir mejoras a su respuesta. Tómelo o déjelo.
mikera
@mikea Creo que podrías estar perdiendo el punto. Para compilar x + yen operaciones de adición de máquina eficientes, debe saber en el momento de la compilación si es o no. Todo el tiempo , no solo algunas veces. Para los lenguajes dinámicos esto casi nunca es posible con programas realistas, a pesar de que heurísticas razonables acertarían la mayor parte del tiempo. La compilación requiere garantías en tiempo de compilación . Entonces, al hablar de "en muchas circunstancias", en realidad no está abordando mi respuesta.
Ben
9

Solo un puntero rápido que describe el peor de los casos para lenguajes dinámicos:

El análisis de Perl no es computable

Como consecuencia, Perl (completo) nunca puede compilarse estáticamente.


En general, como siempre, depende. Estoy seguro de que si intenta emular características dinámicas en un lenguaje compilado estáticamente, intérpretes bien concebidos o variantes (parcialmente) compiladas pueden acercarse o socavar el rendimiento de los lenguajes compilados estáticamente.

Otro punto a tener en cuenta es que los lenguajes dinámicos resuelven otro problema que C. C es apenas más que una buena sintaxis para ensamblador, mientras que los lenguajes dinámicos ofrecen ricas abstracciones. El rendimiento en tiempo de ejecución a menudo no es la principal preocupación: el tiempo de comercialización, por ejemplo, depende de que sus desarrolladores puedan escribir sistemas complejos y de alta calidad en plazos cortos. La extensibilidad sin recompilación, por ejemplo con complementos, es otra característica popular. ¿Qué idioma prefieres en estos casos?

Rafael
fuente
5

En un intento de ofrecer una respuesta más objetivamente científica a esta pregunta, argumento lo siguiente. Un lenguaje dinámico requiere un intérprete, o tiempo de ejecución, para tomar decisiones en tiempo de ejecución. Este intérprete, o tiempo de ejecución, es un programa de computadora y, como tal, fue escrito en algún lenguaje de programación, ya sea estático o dinámico.

Si el intérprete / tiempo de ejecución se escribió en un lenguaje estático, entonces se podría escribir un programa en ese lenguaje estático que (a) realiza la misma función que el programa dinámico que interpreta y (b) realiza al menos también. Con suerte, esto es evidente, ya que proporcionar una prueba rigurosa de estas afirmaciones requeriría un esfuerzo adicional (posiblemente considerable).

Suponiendo que estas afirmaciones sean ciertas, la única salida es exigir que el intérprete / tiempo de ejecución también se escriba en un lenguaje dinámico. Sin embargo, nos encontramos con el mismo problema que antes: si el intérprete es dinámico, requiere un intérprete / tiempo de ejecución, que también debe haber sido escrito en un lenguaje de programación, dinámico o estático.

A menos que asuma que una instancia de un intérprete es capaz de interpretarse a sí misma en tiempo de ejecución (espero que esto sea evidentemente absurdo), la única forma de vencer a los lenguajes estáticos es que cada instancia de intérprete sea interpretada por una instancia de intérprete separada; esto lleva a una regresión infinita (espero que esto sea evidentemente absurdo) o un ciclo cerrado de intérpretes (espero que esto también sea evidentemente absurdo).

Parece, entonces, que incluso en teoría, los lenguajes dinámicos no pueden funcionar mejor que los lenguajes estáticos, en general. Cuando se usan modelos de computadoras realistas, parece aún más plausible; después de todo, una máquina solo puede ejecutar secuencias de instrucciones de máquina, y todas las secuencias de instrucciones de máquina pueden compilarse estáticamente.

En la práctica, hacer coincidir el rendimiento de un lenguaje dinámico con un lenguaje estático podría requerir volver a implementar el intérprete / tiempo de ejecución en un lenguaje estático; sin embargo, que puede hacer eso es el punto crucial de este argumento. Es una pregunta de huevo y gallina y, siempre que esté de acuerdo con los supuestos no comprobados (aunque, en mi opinión, en su mayoría evidentes) hechos anteriormente, podemos responderlo; Tenemos que dar el visto bueno a los lenguajes estáticos, no dinámicos.

Otra forma de responder a la pregunta, a la luz de esta discusión, es esta: en el programa almacenado, control = modelo de datos de computación que se encuentra en el corazón de la computación moderna, la distinción entre compilación estática y dinámica es una falsa dicotomía; Los lenguajes compilados estáticamente deben tener un medio para generar y ejecutar código arbitrario en tiempo de ejecución. Está fundamentalmente relacionado con la computación universal.

Patrick87
fuente
Al releer esto, no creo que sea verdad. La compilación JIT rompe tu argumento. Incluso el código más simple, por ejemplo, main(args) { for ( i=0; i<1000000; i++ ) { if ( args[0] == "1" ) {...} else {...} }puede acelerarse significativamente una vez que argsse conoce el valor de (suponiendo que nunca cambie, lo que podemos afirmar). Un compilador estático no puede crear código que elimine la comparación. (Por supuesto, en ese ejemplo, simplemente ifsaca el lazo. Pero la cosa puede ser más complicada.)
Raphael
@Raphael Creo que JIT probablemente hace mi argumento. Los programas que compilan JIT (por ejemplo, JVM) suelen ser programas compilados estáticamente. Si un programa JIT compilado estáticamente podría ejecutar un script más rápido que otro programa estático podría hacer el mismo trabajo, simplemente "agrupe" el script con el compilador JIT y llame al paquete un programa compilado estáticamente. Esto debe funcionar al menos tan bien como el JIT que opera en un programa dinámico separado, contradiciendo cualquier argumento de que JIT debe hacerlo mejor.
Patrick87
Hm, eso es como decir que agrupar un script Ruby con su intérprete te da un programa compilado estáticamente. No estoy de acuerdo (ya que elimina todas las distinciones de idiomas a este respecto), pero ese es un problema de semántica, no de conceptos. Conceptualmente, adaptar el programa en tiempo de ejecución (JIT) puede hacer optimizaciones que no puedes hacer en tiempo de compilación (compilador estático), y ese es mi punto.
Raphael
@Raphael Que no haya una distinción significativa es el punto de la respuesta: cualquier intento de clasificar rígidamente algunos idiomas como estáticos y, por lo tanto, sufriendo limitaciones de rendimiento, falla exactamente por esta razón: no hay una diferencia convincente entre un preempaquetado (Ruby , script) paquete y un programa C. Si (Ruby, script) puede hacer que la máquina ejecute la secuencia correcta de instrucciones para resolver eficientemente un problema dado, entonces podría hacerlo un programa C ingeniosamente diseñado.
Patrick87
Pero se puede definir la diferencia. Una variante envía el código disponible al procesador sin cambios (C), la otra compila en tiempo de ejecución (Ruby, Java, ...). El primero es lo que entendemos por "compilación estática", mientras que el segundo sería "compilación justo a tiempo" (que permite optimizaciones dependientes de los datos).
Raphael
4

¿Puedes construir compiladores para lenguajes dinámicos como Ruby para que tengan un rendimiento similar y comparable a C / C ++?

Creo que la respuesta es "sí" . También creo que incluso pueden superar la arquitectura C / C ++ actual en términos de eficiencia (aunque sea un poco).

La razón es simple: hay más información en tiempo de ejecución que en tiempo de compilación.

Los tipos dinámicos son solo un pequeño obstáculo: si una función se ejecuta siempre o casi siempre con los mismos tipos de argumentos, entonces un optimizador JIT puede generar una rama y un código de máquina para ese caso específico. Y hay mucho más que se puede hacer.

Vea Dynamic Languages ​​Strike Back , un discurso de Steve Yegge de Google (también hay una versión de video en algún lugar, creo). Menciona algunas técnicas concretas de optimización JIT de V8. Inspirador!

¡Espero con ansias lo que vamos a tener en los próximos 5 años!

Kos
fuente
2
Amo el optimismo.
Dave Clarke
Creo que hubo algunas críticas muy específicas de imprecisiones en la charla de Steve. Los publicaré cuando los encuentre.
Konrad Rudolph
1
@DaveClarke eso es lo que me mantiene corriendo :)
Kos
2

Las personas que aparentemente piensan que esto es teóricamente posible, o en un futuro lejano, están completamente equivocadas en mi opinión. El punto radica en el hecho de que los lenguajes dinámicos proporcionan e imponen un estilo de programación totalmente diferente. En realidad, la diferencia es doble, incluso si ambos aspectos están interrelacionados:

  • Los símbolos (vars, o más bien enlaces de referencia <-> datum de todo tipo) no están tipificados.
  • Las estructuras (los datos, todo lo que vive en tiempo de ejecución) tampoco están tipificadas por los tipos de sus elementos.

El segundo punto proporciona genérico de forma gratuita. Tenga en cuenta que las estructuras aquí son elementos compuestos, colecciones, pero también tipos propios, e incluso (!) Rutinas de todo tipo (funciones, acciones, operaciones) ... Podríamos escribir estructuras por sus tipos de elementos, pero debido al primer punto, la verificación sucedería en tiempo de ejecución de todos modos. Podríamos haber tecleado símbolos y todavía tener estructurados sin tipo según sus tipos de elementos (una matriz asimplemente se escribiría como una matriz, no como una matriz de entradas), pero incluso estas pocas no son ciertas en un lenguaje dinámico (también apodría contener una cuerda).

L

  • ElementLL
  • ElementL
  • todas las estructuras (nuevamente, incluidas las rutinas de modelos) reciben solo elementos

Para mí está claro que esto solo es una gran penalización; y ni siquiera toco todas las consecuencias (la miríada de comprobaciones de tiempo de ejecución de todo tipo necesarias para garantizar la sensibilidad del programa) bien descritas en otras publicaciones.

espiritu
fuente
+1 Muy interesante. ¿Has leído mi respuesta? Tu y mi pensamiento parecen similares, aunque tu respuesta proporciona más detalles y una perspectiva interesante.
Patrick87
Los lenguajes dinámicos no tienen que estar sin tipo. La implementación de un modelo de lenguaje dinámico en C restringe severamente las posibilidades de optimización; hace que sea muy difícil para el compilador reconocer optimizaciones de alto nivel (por ejemplo, datos inmutables), y obliga a algunas operaciones fundamentales (por ejemplo, llamadas a funciones) a pasar por C. Lo que usted describe no está lejos de ser un intérprete de bytecode, con la decodificación de bytecode preevaluado Los compiladores nativos tienden a funcionar significativamente mejor, dudo que la decodificación de bytecode pueda justificar la diferencia.
Gilles 'SO- deja de ser malvado'
@ Patrick87: tienes razón, nuestras líneas de pensamiento parecen muy similares (no lo había leído antes, lo siento, mi reflejo proviene de implementar actualmente un dyn lang en C).
spir
@Gilles: Prefiero estar de acuerdo con "... no tiene que estar sin tipo", si quiere decir que no está estáticamente escrito. Pero esto no es lo que la gente piensa de dyn langs en general, supongo. Personalmente considero que el carácter genérico (en el sentido general dado en la respuesta anterior) es una característica mucho más poderosa y mucho más difícil de vivir. Podemos encontrar fácilmente formas de hacer con los tipos estáticos ampliando nuestro pensamiento sobre cómo se puede definir un tipo dado (aparentemente polimórfico), o dando más flexibilidad a las instancias directamente.
spir
1

No tuve tiempo de leer todas las respuestas en detalle ... pero me divirtió.

Hubo una controversia similar en los años sesenta y principios de los setenta (la historia de la informática a menudo se repite): se pueden compilar lenguajes de alto nivel para producir un código tan eficiente como el código de máquina, bueno, digamos código de ensamblaje, producido manualmente por un programador. Todos saben que un programador es mucho más inteligente que cualquier programa y puede llegar a una optimización muy inteligente (pensando en realidad en lo que ahora se llama optimización de mirilla). Esto es, por supuesto, ironía de mi parte.

Incluso existía un concepto de expansión de código: la relación entre el tamaño del código producido por un compilador y el tamaño del código para el mismo programa producido por un buen programador (como si hubiera habido demasiados de estos :-). Por supuesto, la idea era que esta proporción siempre era mayor que 1. Los idiomas de la época eran Cobol y Fortran 4, o Algol 60 para los intelectuales. Creo que Lisp no fue considerado.

Bueno, hubo algunos rumores de que alguien había producido un compilador que a veces podía obtener una relación de expansión de 1 ... hasta que simplemente se convirtió en la regla de que el código compilado era mucho mejor que el código escrito a mano (y también más confiable). La gente estaba preocupada por el tamaño del código en esos momentos (pequeños recuerdos), pero lo mismo ocurre con la velocidad o el consumo de energía. No voy a entrar en las razones.

Las características extrañas, las características dinámicas de un idioma no importan. Lo que importa es cómo se usan, si se usan. El rendimiento, en cualquier unidad (tamaño del código, velocidad, energía, ...) a menudo depende de partes muy pequeñas de los programas. Por lo tanto, existe una buena posibilidad de que las instalaciones que otorgan poder expresivo realmente no se interpongan en el camino. Con una buena práctica de programación, las instalaciones avanzadas se usan solo de manera disciplinada, para imaginar nuevas estructuras (esa fue la lección de lisp).

El hecho de que un idioma no tenga escritura estática nunca ha significado que los programas escritos en ese idioma no estén estáticamente escritos. Por otro lado, podría ser que el sistema de tipos que utiliza un programa aún no esté suficientemente formalizado para que exista un verificador de tipos ahora.

Ha habido, en la discusión, varias referencias al análisis del peor de los casos ("problema de detención", análisis PERL). Pero el análisis del peor de los casos es irrelevante. Lo que importa es lo que sucede en la mayoría de los casos o en casos útiles ... independientemente de cómo se defina, comprenda o experimente. Aquí viene otra historia, directamente relacionada con la optimización del programa. Tuvo lugar hace mucho tiempo en una importante universidad de Texas, entre un estudiante de doctorado y su asesor (que luego fue elegido en una de las academias nacionales). Según recuerdo, el estudiante insistió en estudiar un problema de análisis / optimización que el asesor había demostrado que no se podía tratar. Pronto dejaron de hablar. Pero el estudiante tenía razón: el problema era lo suficientemente manejable en la mayoría de los casos prácticos, de modo que la disertación que produjo se convirtió en un trabajo de referencia.

Y para comentar más sobre la afirmación de que Perl parsing is not computable, sea lo que sea ​​que signifique esa oración, existe un problema similar con ML, que es un lenguaje notablemente bien formalizado. Type checking complexity in ML is a double exponential in the lenght of the program.Ese es un resultado muy preciso y formal en la peor complejidad del caso ... que no importa en absoluto. Afaik, los usuarios de ML todavía están esperando un programa práctico que explote el verificador de tipos.

En muchos casos, como lo era antes, el tiempo humano y la competencia son más escasos que la potencia informática.

El verdadero problema del futuro será evolucionar nuestros lenguajes para integrar nuevos conocimientos, nuevas formas de programación, sin tener que reescribir todo el software heredado que todavía se utiliza.

Si nos fijamos en las matemáticas, es un conjunto de conocimientos muy amplio. Los lenguajes utilizados para expresarlo, las anotaciones y los conceptos han evolucionado a lo largo de los siglos. Es fácil escribir viejos teoremas con los nuevos conceptos. Adaptamos las pruebas principales, pero no nos molestamos en obtener muchos resultados.

Pero en el caso de la programación, podríamos tener que reescribir todas las pruebas desde cero (los programas son pruebas). Puede ser que lo que realmente necesitamos sean lenguajes de programación evolutivos y de muy alto nivel. Los diseñadores optimizadores estarán encantados de seguirlo.

babou
fuente
0

Un par de notas:

  • No todos los lenguajes de alto nivel son dinámicos. Haskell tiene un nivel muy alto, pero está completamente tipado estáticamente. Incluso los lenguajes de programación de sistemas como Rust, Nim y D pueden expresar abstracciones de alto nivel de manera sucinta y eficiente. De hecho, pueden ser tan concisos como los lenguajes dinámicos.

  • Existen compiladores anticipados altamente optimizadores para lenguajes dinámicos. Las buenas implementaciones de Lisp alcanzan la mitad de la velocidad del equivalente C.

  • La compilación JIT puede ser una gran victoria aquí. El firewall de aplicaciones web de CloudFlare genera código Lua que es ejecutado por LuaJIT. LuaJIT optimiza en gran medida las rutas de ejecución realmente tomadas (generalmente, las rutas sin ataque), con el resultado de que el código se ejecuta mucho más rápido que el código producido por un compilador estático en la carga de trabajo real. A diferencia de un compilador estático con optimización guiada por perfil, LuaJIT se adapta a los cambios en las rutas de ejecución en tiempo de ejecución.

  • La desoptimización también es crucial. En lugar de que el código compilado por JIT necesite verificar si una clase está parcheada, el acto de parchear mono desencadena un gancho en el sistema de tiempo de ejecución que descarta el código de máquina que dependía de la definición anterior.

Demi
fuente
¿Cómo es esta una respuesta? Bueno, la bala tres quizás, si agregaste referencias.
Raphael
Soy muy escéptico ante la afirmación de que PGO no puede igualar el rendimiento de LuaJIT para el código de la aplicación web bajo la carga de trabajo típica.
Konrad Rudolph
@KonradRudolph La ventaja clave de un JIT es que el JIT adapta el código a medida que las diferentes rutas se calientan.
Demi
@Demetri lo sé. Pero es muy difícil cuantificar si esto es una ventaja: vea mi respuesta y la discusión de comentarios allí. En pocas palabras: si bien el JIT puede adaptarse a los cambios en el uso, también necesita realizar un seguimiento de las cosas en tiempo de ejecución, lo que conlleva una sobrecarga. El punto de equilibrio para esto es intuitivamente solo cuando ocurren cambios frecuentes en el comportamiento. Para las aplicaciones web, probablemente solo haya un patrón de uso único (o muy pocos) para el que la optimización valga la pena, por lo que el aumento de rendimiento mínimo debido a la adaptabilidad no compensa la sobrecarga de la creación de perfiles continua.
Konrad Rudolph