¿Cómo puede un lenguaje cuyo compilador está escrito en C ser más rápido que C?

Echando un vistazo a la página web de Julia , puede ver algunos puntos de referencia de varios idiomas en varios algoritmos (los tiempos se muestran a continuación). ¿Cómo puede un lenguaje con un compilador originalmente escrito en C, superar el código C?

Figura: tiempos de referencia relativos a C (cuanto menor es mejor, rendimiento de C = 1.0).

No existe una relación necesaria entre la implementación del compilador y la salida del compilador. Podría escribir un compilador en un lenguaje como Python o Ruby, cuyas implementaciones más comunes son muy lentas, y ese compilador podría generar un código de máquina altamente optimizado capaz de superar a C. El compilador mismo tardaría mucho tiempo en ejecutarse, porque suEl código está escrito en un lenguaje lento. (Para ser más precisos, escrito en un idioma con una implementación lenta. Los idiomas no son realmente inherentemente rápidos o lentos, como lo señala Raphael en un comentario. Amplío esta idea a continuación). El programa compilado sería tan rápido como implementación propia permitida: podríamos escribir un compilador en Python que genere el mismo código de máquina que un compilador Fortran, y nuestros programas compilados serían tan rápidos como Fortran, aunque tomarían mucho tiempo compilarlos.

Es una historia diferente si estamos hablando de un intérprete. Los intérpretes deben estar ejecutándose mientras se ejecuta el programa que están interpretando, por lo que existe una conexión entre el idioma en el que se implementa el intérprete y el rendimiento del código interpretado. Se necesita una optimización inteligente del tiempo de ejecución para hacer un lenguaje interpretado que se ejecute más rápido que el idioma en el que se implementa el intérprete, y el rendimiento final puede depender de qué tan adecuado sea un fragmento de código para este tipo de optimización. Muchos lenguajes, como Java y C #, usan tiempos de ejecución con un modelo híbrido que combina algunos de los beneficios de los intérpretes con algunos de los beneficios de los compiladores.

Como ejemplo concreto, echemos un vistazo más de cerca a Python. Python tiene varias implementaciones. El más común es CPython, un intérprete de código de bytes escrito en C. También está PyPy, que está escrito en un dialecto especializado de Python llamado RPython, y que utiliza un modelo de compilación híbrido algo así como la JVM. PyPy es mucho más rápido que CPython en la mayoría de los puntos de referencia; Utiliza todo tipo de trucos increíbles para optimizar el código en tiempo de ejecución. Sin embargo, el lenguaje Python que ejecuta PyPy es exactamente el mismo lenguaje Python que ejecuta CPython, salvo algunas diferencias que no afectan el rendimiento.

Supongamos que escribimos un compilador en lenguaje Python para Fortran. Nuestro compilador produce el mismo código de máquina que GFortran. Ahora compilamos un programa Fortran. Podemos ejecutar nuestro compilador sobre CPython, o podemos ejecutarlo en PyPy, ya que está escrito en Python y ambas implementaciones ejecutan el mismo lenguaje Python. Lo que encontraremos es que si ejecutamos nuestro compilador en CPython, luego lo ejecutamos en PyPy, luego compilamos la misma fuente Fortran con GFortran, obtendremos exactamente el mismo código de máquina las tres veces, por lo que el programa compilado siempre se ejecutará aproximadamente a la misma velocidad. Sin embargo, el tiempo que lleva producir ese programa compilado será diferente. CPython probablemente tomará más tiempo que PyPy, y PyPy probablemente tomará más tiempo que GFortran, a pesar de que todos ellos generarán el mismo código de máquina al final.

Al escanear la tabla de referencia del sitio web de Julia, parece que ninguno de los lenguajes que se ejecutan en los intérpretes (Python, R, Matlab / Octave, Javascript) tiene puntos de referencia donde superan a C. Esto generalmente es consistente con lo que esperaría ver, aunque podría imaginar que el código escrito con la biblioteca Numpy altamente optimizada de Python (escrita en C y Fortran) supera algunas implementaciones posibles de código similar en C Los lenguajes que son iguales o mejores que C se están compilando (Fortran, Julia ) o utilizando un modelo híbrido con compilación parcial (Java y probablemente LuaJIT). PyPy también usa un modelo híbrido, por lo que es muy posible que si ejecutamos el mismo código Python en PyPy en lugar de CPython, realmente lo veamos vencer a C en algunos puntos de referencia.

¿Cómo puede una máquina construida por un hombre ser más fuerte que un hombre? Esta es exactamente la misma pregunta.

La respuesta es que la salida del compilador depende de los algoritmos implementados por ese compilador, no del lenguaje utilizado para implementarlo. Podría escribir un compilador realmente lento e ineficiente que produce un código muy eficiente. No hay nada especial en un compilador: es solo un programa que toma algo de entrada y produce algo de salida.

Quiero señalar un punto en contra de una suposición común que, en mi opinión, es falaz hasta el punto de ser perjudicial al elegir herramientas para un trabajo.

No existe un lenguaje lento o rápido. ¹

En nuestro camino hacia la CPU que realmente está haciendo algo, hay muchos pasos².

1. Al menos un programador con ciertas habilidades.
2. El lenguaje (formal) en el que programan ("código fuente").
3. Las bibliotecas que usan.
4. Algo que traduce el código fuente en código máquina (compiladores, intérpretes).
5. La arquitectura general del hardware, por ejemplo, número de unidades de procesamiento y diseño de la jerarquía de memoria.
6. El sistema operativo que gestiona el hardware.
7. Optimizaciones en CPU.

Cada elemento contribuye al tiempo de ejecución real que puede medir, a veces en gran medida. Diferentes "idiomas" se centran en diferentes cosas³.

Solo para dar algunos ejemplos.

• 1 vs 2-4 : es probable que un programador C promedio produzca un código mucho peor que un programador Java promedio, tanto en términos de corrección como de eficiencia. Eso es porque el programador tiene más responsabilidades en C.

• 1/4 vs 7 : en lenguaje de bajo nivel como C, puede explotar ciertas funciones de la CPU como programador . En lenguajes de nivel superior, solo el compilador / intérprete puede hacerlo, y solo si conocen la CPU de destino.

• 1/4 vs 5 : ¿desea o tiene que controlar el diseño de la memoria para utilizar mejor la arquitectura de memoria en cuestión? Algunos idiomas te dan control sobre eso, otros no.

• 2/4 vs 3 : Python interpretado en sí mismo es terriblemente lento, pero hay enlaces populares a bibliotecas altamente optimizadas y compiladas de forma nativa para la informática científica. Entonces, hacer ciertas cosas en Python es rápido al final, si la mayoría del trabajo es realizado por estas bibliotecas.

• 2 vs 4 : el intérprete estándar de Ruby es bastante lento. JRuby, por otro lado, puede ser muy rápido. Es el mismo lenguaje que es rápido usando otro compilador / intérprete.

• 1/2 vs 4 : utilizando optimizaciones del compilador, el código simple puede traducirse en un código de máquina muy eficiente.

La conclusión es que el punto de referencia que encontró no tiene mucho sentido, al menos no cuando se reduce a la tabla que incluye. Incluso si todo lo que le interesa es el tiempo de ejecución, debe especificar toda la cadena desde el programador hasta la CPU; intercambiar cualquiera de los elementos puede cambiar los resultados dramáticamente.

Para ser claros, esto responde a la pregunta porque muestra que el lenguaje en el que está escrito el compilador (paso 4) no es más que una pieza del rompecabezas, y probablemente no sea relevante en absoluto (ver otras respuestas).

1. Ciertamente, hay características de lenguaje que son más costosas de implementar que otras. Pero la existencia de características no significa que tenga que usarlas, y una característica costosa puede ahorrar el uso de muchas más baratas y, por lo tanto, pagar al final. (De tener otras ventajas no medibles en tiempo de ejecución).
2. Salto el nivel algorítmico porque no siempre se aplica y es principalmente independiente del lenguaje de programación utilizado. Tenga en cuenta que diferentes algoritmos se prestan mejor a diferentes hardware, por ejemplo.

3. Deliberadamente, no entro en diferentes métricas de éxito aquí: eficiencia del tiempo de ejecución, eficiencia de la memoria, tiempo del desarrollador, seguridad, seguridad, (¿demostrable?) Corrección, soporte de herramientas, independencia de la plataforma, ...

   Comparar lenguajes con una métrica aunque haya sido diseñado para objetivos completamente diferentes es una gran falacia.

Aquí hay una cosa olvidada sobre la optimización.

Hubo un debate prolongado sobre el rendimiento de Fortran C. Separando el debate mal formado: el mismo código fue escrito en C y Fortran (como pensaban los evaluadores) y el rendimiento se probó en base a los mismos datos. El problema es que estos lenguajes difieren, C permite el alias de punteros, mientras que fortran no.

Por lo tanto, los códigos no eran los mismos, no había restricción __ en los archivos probados en C, lo que daba diferencias, después de reescribir los archivos para decirle al compilador que puede optimizar los punteros, los tiempos de ejecución se vuelven similares.

El punto aquí es que algunas técnicas de optimización son más fáciles (o comienzan a ser legales) en un lenguaje recién creado.

También es posible a largo plazo que VM con JIT supere el rendimiento C. Hay dos posibilidades: el
código JIT puede aprovechar la máquina que lo aloja (por ejemplo, algunos SSE u otros exclusivos para algunas instrucciones vectorizadas de CPU) que no se implementaron en programa comparado$X$

En segundo lugar, VM puede realizar una prueba de presión mientras se ejecuta, por lo que puede tomar código presionado y optimizarlo o incluso precalcularlo durante el tiempo de ejecución. Por adelantado, el programa C compilado no espera dónde está la presión o (la mayoría de las veces) hay versiones genéricas de ejecutables para la familia general de máquinas.

En esta prueba también hay JS, bueno, hay máquinas virtuales más rápidas que V8, y también funciona más rápido que C en algunas pruebas.

Lo he comprobado y había técnicas de optimización únicas que aún no están disponibles en los compiladores de C.

El compilador de C tendría que hacer un análisis estático de todo el código de una vez, marchar sobre una plataforma determinada y solucionar problemas de alineación de memoria.

VM simplemente transcribió parte del código al ensamblaje optimizado y lo ejecutó.

Acerca de Julia: como verifiqué, funciona con AST de código, por ejemplo, GCC omitió este paso y recientemente comenzó a tomar información de allí. Esto más otras restricciones y técnicas de VM podrían explicar un poco.

Ejemplo: tomemos un ciclo simple, que toma el punto final inicial y final de las variables y carga parte de las variables en los cálculos que se conocen en el tiempo de ejecución.

El compilador de C genera variables de carga a partir de registros.
Pero en el tiempo de ejecución, estas variables se conocen y se tratan como constantes a través de la ejecución.
Entonces, en lugar de cargar variables de los registros (y no realizar el almacenamiento en caché porque puede cambiar, y del análisis estático no está claro), se tratan completamente como constantes y se pliegan, se propagan.

Las respuestas anteriores dan más o menos la explicación, aunque principalmente desde un ángulo pragmático, por mucho que la pregunta tenga sentido , como lo explica excelentemente la respuesta de Raphael .

Además de esta respuesta, debemos tener en cuenta que, hoy en día, los compiladores de C están escritos en C. Por supuesto, como señaló Raphael, su salida y su rendimiento pueden depender, entre otras cosas, de la CPU en la que se está ejecutando. Pero también depende de la cantidad de optimización realizada por el compilador. Si escribe en C un mejor compilador de optimización para C (que luego compila con el anterior para poder ejecutarlo), obtendrá un nuevo compilador que hace que C sea un lenguaje más rápido que antes. Entonces, ¿cuál es la velocidad de C? Tenga en cuenta que incluso puede compilar el nuevo compilador consigo mismo, como un segundo paso, de modo que se compila de manera más eficiente, aunque sigue dando el mismo código de objeto. Y el teorema del pleno empleo muestra que no hay fin a tales mejoras (gracias a Rafael por el puntero).

Pero creo que puede valer la pena tratar de formalizar el problema, ya que ilustra muy bien algunos conceptos fundamentales, y particularmente la visión denotacional versus operativa de las cosas.

¿Qué es un compilador?

Un compilador , abreviado a si no hay ambigüedad, es la realización de una función computable que traducirá un texto de programa computando una función , escrito en un lenguaje fuente en el texto del programa escrito en un idioma de destino , que se supone que para calcular la misma función .$C_{S\to T}$$C$$\mathcal C_{S\to T}$$P_{:S}$$\mathcal P$ $S$$P_{:T}$ $T$$\mathcal P$

Desde un punto de vista semántico, es decir, denotacionalmente , no importa cómo se calcula esta función de compilación , es decir, qué realización se elige . Incluso podría hacerse por un oráculo mágico. Matemáticamente, la función es simplemente un conjunto de pares .$\mathcal C_{S\to T}$$C_{S\to T}$$\{(P_{:S},P_{:T})\mid P_S\in S \wedge P_T\in T\}$

La función de recopilación semántica es correcta si ambos y calculan la misma función . Pero esta formalización se aplica también a un compilador incorrecto. El único punto es que todo lo que se implementa logra el mismo resultado independientemente de los medios de implementación. Lo que importa semánticamente es lo que hace el compilador, no cómo (y qué tan rápido) se hace.$\mathcal C_{S\to T}$$P_S$$P_T$$\mathcal P$

En realidad, obtener de es un problema operativo que debe resolverse. Esta es la razón por la cual la función de compilación debe ser una función computable. Entonces, cualquier idioma con el poder de Turing, sin importar cuán lento sea, seguramente podrá producir código tan eficiente como cualquier otro idioma, incluso si lo hace de manera menos eficiente.$P_{:T}$$P_{:S}$$\mathcal C_{S\to T}$

Refinando el argumento, probablemente queremos que el compilador tenga una buena eficiencia, de modo que la traducción se pueda realizar en un tiempo razonable. Por lo tanto, el rendimiento del programa compilador es importante para los usuarios, pero no tiene ningún impacto en la semántica. Estoy diciendo rendimiento, porque la complejidad teórica de algunos compiladores puede ser mucho mayor de lo que cabría esperar.

Sobre bootstrapping

Esto ilustrará la distinción y mostrará una aplicación práctica.

Ahora es un lugar común implementar primero un lenguaje con un intérprete , y luego escribir un compilador en el lenguaje mismo. Este compilador se puede ejecutar con el intérprete para traducir cualquier programa en un programa . Así que tenemos un compilador en ejecución desde el lenguaje al lenguaje (¿máquina?) , pero es muy lento, aunque solo sea porque se ejecuta sobre un intérprete.I S C S → $S$$I_S$ S C S → $C_{S\to T\,:S}$$S$ I S P : S P : T S$C_{S\to T\,:S}$$I_S$$P_{:S}$$P_{:T}$$S$$T$

Pero puede usar esta función de compilación para compilar el compilador , ya que está escrito en el lenguaje , y así obtiene un compilador escrito en el idioma de destino . Si se supone, como suele ser el caso, de que es un lenguaje que se interpreta de manera más eficiente (nativo de la máquina, por ejemplo), entonces se obtiene una versión más rápida de su compilador se ejecuta directamente en el lenguaje . Realiza exactamente el mismo trabajo (es decir, produce los mismos programas de destino), pero lo hace de manera más eficiente. S C S → $C_{S\to T\,:S}$$S$ TT$C_{S\to T\,:T}$$T$$T$$T$

Según el teorema de aceleración de Blum, hay programas que se escriben y se ejecutan en la combinación más rápida de computadora / compilador que se ejecutarán más lentamente que un programa para el mismo en su primera PC que ejecuta BASIC interpretado. Simplemente no hay un "lenguaje más rápido". Todo lo que puede decir es que si escribe el mismo algoritmo en varios lenguajes (implementaciones; como se señaló, hay muchos compiladores de C diferentes, e incluso me encontré con un intérprete de C bastante capaz), se ejecutará más rápido o más lento en cada uno .

No puede haber una jerarquía "siempre más lenta". Este es un fenómeno que todos conocen con fluidez en varios idiomas: cada lenguaje de programación fue diseñado para un tipo específico de aplicaciones, y las implementaciones más utilizadas se han optimizado para ese tipo de programas. Estoy bastante seguro de que, por ejemplo, un programa para perder el tiempo con cadenas escritas en Perl probablemente superará el mismo algoritmo escrito en C, mientras que un programa masticando grandes matrices de enteros en C será más rápido que Perl.

Volvamos a la línea original: "¿Cómo puede un lenguaje cuyo compilador está escrito en C ser más rápido que C?" Creo que esto realmente quería decir: ¿cómo puede un programa escrito en Julia, cuyo núcleo está escrito en C, ser más rápido que un programa escrito en C? Específicamente, ¿cómo podría ejecutarse el programa "mandel" tal como está escrito en Julia en el 87% del tiempo de ejecución del programa "mandel" equivalente escrito en C?

El tratado de Babou es la única respuesta correcta a esta pregunta hasta ahora. Todas las otras respuestas hasta ahora son más o menos respuestas a otras preguntas. El problema con el texto de babou es que la descripción teórica de muchos párrafos de "Qué es un compilador" está escrita en términos de que el póster original probablemente tendrá problemas para comprender. Cualquiera que comprenda los conceptos a los que se refieren las palabras "semántico", "denotacionalmente", "realización", "computable", etc., ya sabrá la respuesta a la pregunta.

La respuesta más simple es que ni el código C ni el código Julia son directamente ejecutables por la máquina. Ambos tienen que ser traducidos, y ese proceso de traducción introduce muchas formas en que el código máquina ejecutable puede ser más lento o más rápido, pero aún así producir el mismo resultado final. Tanto C como Julia compilan, lo que significa una serie de traducciones a otra forma. Comúnmente, un archivo de texto legible para humanos se traduce en alguna representación interna y luego se escribe como una secuencia de instrucciones que la computadora puede entender directamente. Con algunos idiomas, hay más que eso, y Julia es uno de estos: tiene un compilador "JIT", lo que significa que todo el proceso de traducción no tiene que ocurrir de una vez para todo el programa. Pero el resultado final para cualquier idioma es el código de máquina que no necesita traducción adicional, código que se puede enviar directamente a la CPU para que haga algo. Al final, ESTE es el "cálculo", y hay más de una forma de decirle a una CPU cómo obtener la respuesta que desea.

Uno podría imaginar un lenguaje de programación que tenga tanto un operador "más" como un "multiplicador", y otro lenguaje que solo tenga "más". Si su cálculo requiere multiplicación, un idioma será "más lento" porque, por supuesto, la CPU puede hacer ambas cosas directamente, pero si no tiene ninguna forma de expresar la necesidad de multiplicar 5 * 5, tiene que escribir "5 + 5 + 5 + 5 + 5 ". A este último le tomará más tiempo llegar a la misma respuesta. Presumiblemente, hay algo de esto pasando con Julia; quizás el lenguaje permita al programador establecer el objetivo deseado de calcular un conjunto de Mandelbrot de una manera que no sea posible expresar directamente en C.

El procesador utilizado para el punto de referencia figuraba como una CPU Xeon E7-8850 de 2.00GHz. El benchmark C usó el compilador gcc 4.8.2 para producir instrucciones para esa CPU, mientras que Julia usa el marco del compilador LLVM. Es posible que el backend de gcc (la parte que produce el código de máquina para una arquitectura de CPU en particular) no sea tan avanzado de alguna manera como el backend LLVM. Eso podría marcar una diferencia en el rendimiento. También están sucediendo muchas otras cosas: el compilador puede "optimizar" tal vez emitiendo instrucciones en un orden diferente al especificado por el programador, o incluso no haciendo algunas cosas si puede analizar el código y determinar que no requerido para obtener la respuesta correcta. Y el programador podría haber escrito parte del programa C de una manera que lo haga lento, pero no lo hizo

Todas estas son formas de decir: hay muchas maneras de escribir código de máquina para calcular un conjunto de Mandelbrot, y el lenguaje que usa tiene un efecto importante en cómo se escribe ese código de máquina. Cuanto más comprenda sobre compilación, conjuntos de instrucciones, cachés, etc., estará mejor equipado para obtener los resultados que desea. La conclusión principal de los resultados de referencia citados para Julia es que ningún idioma o herramienta es el mejor en todo. De hecho, ¡el mejor factor de velocidad en todo el gráfico fue para Java!

La velocidad de un programa compilado depende de dos cosas:

1. Las características de rendimiento de la máquina que lo ejecuta.
2. El contenido del archivo ejecutable

El lenguaje en el que está escrito un compilador es irrelevante para (1). Por ejemplo, un compilador de Java puede escribirse en C o Java o Python, pero en todos los casos la "máquina" que ejecuta el programa es la JVM.

El lenguaje en el que está escrito un compilador es irrelevante para (2). Por ejemplo, no hay ninguna razón por la cual un compilador de C escrito en Python no pueda generar exactamente el mismo archivo ejecutable que un compilador de C escrito en C o Java.

Trataré de ofrecer una respuesta más corta.

El núcleo de la pregunta radica en la definición de "velocidad" de un idioma .

La mayoría de las pruebas de comparación de velocidad, si no todas, no prueban cuál es la velocidad máxima posible. En cambio, escriben un pequeño programa en un idioma que desean probar, para resolver un problema. Al escribir el programa, el programador usa lo que ellos asumen * como las mejores prácticas y convenciones del lenguaje, en el momento de la prueba. Luego miden la velocidad a la que se ejecutó el programa.

* Las suposiciones son ocasionalmente incorrectas.

El código escrito en un lenguaje X cuyo compilador está escrito en C, puede superar el rendimiento de un código escrito en C, siempre que el compilador C tenga una optimización deficiente en comparación con el lenguaje X. Si mantenemos la optimización fuera de discusión, entonces si el compilador de X pudiera generar mejor código de objeto que el generado por el compilador de C, entonces también el código escrito en X puede ganar la carrera.

Pero si el lenguaje X es un lenguaje interpretado, y el intérprete está escrito en C, y si asumimos que el intérprete del lenguaje X y el código escrito en C es compilado por el mismo compilador de C, entonces el código escrito en X no superará en absoluto el código escrito en C, siempre que la implementación siga el mismo algoritmo y use estructuras de datos equivalentes.