Estoy interesado en la complejidad temporal de un compilador. Claramente esta es una pregunta muy complicada ya que hay muchos compiladores, opciones de compilador y variables a considerar. Específicamente, estoy interesado en LLVM pero estaría interesado en cualquier pensamiento que las personas tuvieran o lugares para comenzar la investigación. Un google bastante parece traer poco a la luz.
Supongo que hay algunos pasos de optimización que son exponenciales, pero que tienen poco impacto en el tiempo real. Por ejemplo, exponencial basado en el número son argumentos de una función.
Desde lo alto de mi cabeza, diría que generar el árbol AST sería lineal. La generación de IR requeriría pasar por el árbol mientras busca valores en tablas cada vez mayores, por lo que u O ( n log n ) . La generación y vinculación de código sería un tipo de operación similar. Por lo tanto, mi suposición sería O ( n 2 ) , si eliminamos las exponenciales de las variables que no crecen de manera realista.
Aunque podría estar completamente equivocado. ¿Alguien tiene alguna idea al respecto?
Respuestas:
El mejor libro para responder a su pregunta probablemente sería: Cooper y Torczon, "Ingeniería de un compilador", 2003. Si tiene acceso a la biblioteca de una universidad, debería poder pedir prestada una copia.
Luego, el árbol de análisis generalmente se "aplana" en un gráfico de flujo de control. Los nodos del gráfico de flujo de control pueden ser instrucciones de 3 direcciones (similar a un lenguaje ensamblador RISC), y el tamaño del gráfico de flujo de control generalmente será lineal en el tamaño del árbol de análisis.
Luego ingresas a la asignación de registros. La asignación de registros puede expresarse como un problema de coloración de gráficos, y se sabe que colorear un gráfico con un número mínimo de colores es NP-Hard. Por lo tanto, la mayoría de los compiladores utilizan algún tipo de heurística codiciosa combinada con derrames de registros con el objetivo de reducir la cantidad de derrames de registros lo mejor posible dentro de límites de tiempo razonables.
Finalmente entras en la generación de código. La generación de código generalmente se realiza en un bloque básico máximo en un momento en que un bloque básico es un conjunto de nodos de diagrama de flujo de control conectados linealmente con una sola entrada y una única salida. Esto puede reformularse como un problema de cobertura de gráfico donde el gráfico que está tratando de cubrir es el gráfico de dependencia del conjunto de instrucciones de 3 direcciones en el bloque básico, y está tratando de cubrir con un conjunto de gráficos que representan la máquina disponible instrucciones. Este problema es exponencial en el tamaño del bloque básico más grande (que podría, en principio, ser del mismo orden que el tamaño de todo el programa), por lo que esto se vuelve a hacer típicamente con heurística donde solo un pequeño subconjunto de las posibles cubiertas examinado.
fuente
En realidad, algunos lenguajes (como C ++, Lisp y D) se completan con Turing en el momento de la compilación, por lo que compilarlos es indecidible en general. Para C ++, esto se debe a la instanciación recursiva de plantillas. Para Lisp y D, puede ejecutar casi cualquier código en tiempo de compilación, por lo que puede lanzar el compilador en un bucle infinito si lo desea.
fuente
Desde mi experiencia real con el compilador de C #, puedo decir que para ciertos programas el tamaño del binario de salida crece exponencialmente con respecto al tamaño de la fuente de entrada (esto es realmente requerido por la especificación de C # y no se puede reducir), por lo que la complejidad del tiempo debe ser al menos exponencial también.
Se sabe que la tarea de resolución de sobrecarga general en C # es NP-hard (y la complejidad de implementación real es al menos exponencial).
Un procesamiento de comentarios de documentación XML en fuentes de C # también requiere evaluar expresiones arbitrarias de XPath 1.0 en tiempo de compilación, que también es exponencial, AFAIK.
fuente
class X<A,B,C,D,E> { class Y : X<Y,Y,Y,Y,Y> { Y.Y.Y.Y.Y.Y.Y.Y.Y y; } }Mídalo con bases de código realistas, como un conjunto de proyectos de código abierto. Si traza los resultados como (codeSize, finishTime), puede trazar esos gráficos. Si sus datos f (x) = y son O (n), entonces graficar g = f (x) / x debería darle una línea recta después de que los datos comiencen a crecer.
Trace f (x) / x, f (x) / lg (x), f (x) / (x * lg (x)), f (x) / (x * x), etc. El gráfico se sumerge apagado a cero, aumentar sin límite, o aplanar. Esta idea es útil para situaciones como la medición de tiempos de inserción a partir de una base de datos vacía (es decir, para buscar una 'pérdida de rendimiento' durante un largo período).
fuente