Compiladores de LISP / Scheme de calidad para competir con C / C ++

Teóricamente hablando, ¿es posible tener un compilador Lisp / Scheme que pueda producir código que pueda competir con C compilado, digamos dentro de un margen de 15-25%?

En mis pruebas, descubrí que la cosecha actual de compiladores (Bigloo, SBCL, Gambit, Chicken, etc.) es 20-50 veces más lenta que el código C equivalente .

El único caso atípico es el compilador de Stalin . Para programas simples, produce binarios que son equivalentes a C. Sin embargo, lo que me parece sospechoso es que ninguno de los otros proyectos (Bigloo, Chicken, Clozure, etc.) ha intentado implementar cualquier truco que utilice Stalin ("optimización de todo el programa", etc)

Soy un gran fanático de LISP desde mediados de los 90 y me encantaría incorporarlo para que mi equipo pueda desarrollar proyectos en la mitad del tiempo que normalmente toma C / C ++ / .NET / etc, pero ... el rendimiento los problemas son un gran obstáculo.

Me pregunto si la falta de compiladores LISP de calidad se debe al hecho de que no se ha invertido mucho tiempo y dinero en el tema O si esto simplemente no es una tarea factible dado el estado actual de la tecnología del compilador.

Como se señaló en los comentarios, no es muy exacto decir "la cosecha actual de compiladores (Bigloo, SBCL, Gambit, Chicken, etc.) es 20-50 veces más lenta que el código C equivalente", sin calificar cómo lo probó y qué lo has probado

Para mi uso, encuentro que para muchas cosas Gambit y Chicken Scheme están bastante cerca del código 'C' equivalente en velocidad, con la versión actual de Gambit (4.7.3) generalmente más rápida que Chicken (4.9.0.1) pero más pre optimizadorel código de salida 'C' (hacer suposiciones sobre el número de registros disponibles, se supone x686) y forzar el uso de memoria de pila para cualquier requisito de memoria adicional, qué decisiones deben dejarse al compilador 'C' como lo hace Chicken, lo que a menudo elimina el requisito de registros adicionales y pasos de procesamiento combinados) para evitar que el compilador 'C' haga sus propias optimizaciones resultando en bucles pequeños muy apretados que sean aproximadamente el doble de lentos que esos mismos pequeños bucles apretados en 'C' (o Chicken ); Chicken simplemente define tantas variables locales para una función dada como mejor le parezca (la mayoría se usa inmutable) y luego depende del compilador para optimizar la mayoría de las que están lejos. Pollo no

EDIT_ADD: He investigado un poco más sobre las versiones del esquema Chicken y Gambit-C y he encontrado lo siguiente:

1. Chicken es más rápido que Gambit para pequeños bucles ajustados por la razón anterior (depende más del compilador 'C' para optimizaciones sin hacer tanto por sí mismo y, por lo tanto, aprovecha mejor los registros adicionales x86-64), pero también porque no incluye una verificación de mantenimiento de la pila "POLL" dentro de los bucles, mientras que Gambit incluye la verificación "POLL" dentro del bucle. Incluso cuando esto no se activa (el caso habitual), tomará varios ciclos de reloj de la CPU para determinar que no se requiere nada (aproximadamente 6 ciclos). Un futuro compilador más inteligente podría ver que no hay necesidad de hacer una verificación de la pila cuando está dentro de un ciclo cerrado y no realizar operaciones de construcción de la pila, hacerlo justo antes o después del ciclo y ahorrar este tiempo.

2. Las macro 'C' de Gambit hacen demasiado trabajo, como se dijo, al definir con precisión cómo deben llevarse a cabo las operaciones, especialmente las operaciones de tamaño de pila fijo, y estas son probablemente más difíciles de optimizar para el compilador 'C'; el uso de registros de manera más efectiva podría reducir el tiempo de ciclo cerrado en quizás 4 ciclos, lo que en combinación con lo anterior lo colocaría en el estadio de Chicken.

3. Ninguna salida optimiza "leer / modificar / escribir" para decir operaciones vectoriales que se modifican en su lugar y no generan código para que el compilador lo haga. Un backend más inteligente como LLVM cuando se usa con Haskell hace este tipo de cosas. Esto reduciría el uso del registro en uno y el tiempo de ejecución al usar una sola instrucción en lugar de una lectura separada, el cálculo de la modificación y una escritura en la misma ubicación; esto se convertiría en un cálculo de la modificación (digamos un bit o), y luego una instrucción de lectura, modificación (| =) escritura. Esto podría hacer que la velocidad sea más rápida en un ciclo más o menos

4. Ambos se escriben dinámicamente y procesan bits de "etiqueta" de datos como parte de sus datos. Tampoco son lo suficientemente inteligentes como para que los bucles ajustados reduzcan las etiquetas, realicen el bucle "sin etiqueta", luego agreguen las etiquetas para obtener resultados del bucle, ni producen código donde el compilador 'C' pueda ver para hacer esto aunque combina estas operaciones para algunos casos. La optimización aquí podría reducir los tiempos de bucle en un par de ciclos de CPU más o menos, dependiendo del bucle.

5. Los bucles 'C' muy ajustados pueden tomar alrededor de 3.5 ciclos de reloj de CPU por bucle en una CPU rápida que no está acelerada la velocidad de acceso a la memoria caché (como AMD Bulldozer, que es aproximadamente el doble de lenta); el mismo ciclo en Chicken actualmente toma alrededor de 6 ciclos y Gambit toma alrededor de 16.9 ciclos. Con todas las optimizaciones según lo anterior, no hay razón para que estas implementaciones de Scheme no puedan hacer eso, sin embargo, se requiere algo de trabajo:

6. En el caso de Gambit, el trabajo más duro podría ser mejorar el análisis de flujo para reconocer cuándo no es necesario insertar pruebas de "ENCUESTA" (es decir, ¿podría esto ser impulsado por interrupción, aunque el compilador permite que se apaguen las interrupciones para algunos usos? ); la mejora más fácil sería simplemente implementar un mejor uso del registro (es decir, reconocer los registros x86-64 mejor en lugar de la arquitectura x686 predeterminada). Para ambos, un mejor análisis de flujo para reconocer que pueden "desetiquetar" los datos, especialmente "Fixnum", "Flonum" y Vector, datos, por lo que estas operaciones no son necesarias dentro de bucles cerrados y combinando instrucciones de lectura / modificación / escritura. Ambos extremos podrían lograrse utilizando un mejor backend como LLVM (no es una cantidad de trabajo trivial, pero ambos ya están en parte).

Conclusión: Chicken actualmente es aproximadamente un 50% más lento que 'C' en las CPU más rápidas (no en mi Bulldozer, donde tiene aproximadamente la misma velocidad debido a la aceleración de caché del código 'C') y Gambit es aproximadamente un 400% más lento (solo aproximadamente 125% más lento en mi Bulldozer lento). Sin embargo, las futuras mejoras en los compiladores podrían reducir esto, de modo que el código no sea más lento que 'C' o dentro del margen que especifica el OP.

Un lenguaje más complejo como Haskell, cuando se usa el backend LLVM, prestando especial atención al uso estricto (no es un problema con el esquema que siempre está ansioso por defecto) y usa estructuras de datos apropiadas (matrices ST sin caja en lugar de listas para bucles estrechos; algo aplicable a Scheme usando vectores), se ejecuta a aproximadamente la misma velocidad que 'C' si el backend LLVM se usa con optimizaciones completas. Si puede hacer esto, también lo puede hacer Scheme con las mejoras del compilador anteriores.

OTRA VEZ, no hay forma de que ninguno de estos sea 20 a 50 veces más lento cuando se usa con indicadores de optimización adecuados. END_EDIT_ADD

Por supuesto, todos los puntos de referencia se invalidan si uno no usa la configuración de optimización adecuada para cada uno como lo haría en un entorno de producción ...

Creo que el compilador comercial de Chez Scheme estaría en el campo de juego en cuanto a la producción de alto rendimiento como lo hacen Gambit y Chicken, ya que al ser comercial seguramente tiene algo de "tiempo y dinero invertidos".

La única forma en que puedo hacer que Gambit o Chicken funcionen tan lento como "20 a 50 veces más lento que 'C'" es no usar ninguna configuración de optimización, en cuyo caso a menudo no funcionan mucho más rápido de lo que se interpreta en sus REPL - 10 veces más lento que con la configuración adecuada.

¿Es posible que el OP no haya probado usando estas configuraciones correctamente?

Si el OP se preocupa por aclarar sus procedimientos de prueba, con mucho gusto editaré esta respuesta para mostrar que al menos Gambit y Chicken no tienen que ser tan lentos.