El seguimiento de la compilación justo a tiempo es una técnica que utilizan las máquinas virtuales para optimizar la ejecución de un programa en tiempo de ejecución . Esto se hace registrando una secuencia lineal de operaciones ejecutadas con frecuencia, compilándolas en código de máquina nativo y ejecutándolas. Esto se opone a los compiladores tradicionales just-in-time (JIT) que funcionan por método.
Descripción general
La compilación justo a tiempo es una técnica para aumentar la velocidad de ejecución de programas compilando partes de un programa en código de máquina en tiempo de ejecución. Una forma de categorizar diferentes compiladores JIT es por su alcance de compilación. Mientras que los compiladores JIT basados en métodos traducen un método a la vez al código de máquina, los JIT de seguimiento utilizan bucles ejecutados con frecuencia como su unidad de compilación. Los JIT de rastreo se basan en la suposición de que los programas pasan la mayor parte de su tiempo en algunos bucles del programa ("bucles en caliente") y las iteraciones de bucle subsiguientes a menudo toman caminos similares. Las máquinas virtuales que tienen un JIT de seguimiento suelen ser entornos de ejecución de modo mixto, lo que significa que tienen un intérprete o un compilador de métodos además del JIT de seguimiento.
Detalles técnicos
Un compilador JIT de seguimiento pasa por varias fases en tiempo de ejecución. En primer lugar, se recopila la información de creación de perfiles de los bucles. Una vez que se ha identificado un bucle activo, se ingresa a una fase de seguimiento especial , que registra todas las operaciones ejecutadas de ese bucle. Esta secuencia de operaciones se llama rastreo. Luego, el rastreo se optimiza y se compila en código de máquina (rastreo). Cuando este bucle se vuelve a ejecutar, se llama a la traza compilada en lugar de a la contraparte del programa.
Estos pasos se explican en detalle a continuación:
Fase de elaboración de perfiles
El objetivo de la creación de perfiles es identificar los bucles en caliente. Esto se hace a menudo contando el número de iteraciones de cada ciclo. Una vez que el recuento de un bucle supera un cierto umbral, se considera que el bucle está activo y se ingresa a la fase de seguimiento.
Fase de seguimiento
En la fase de seguimiento, la ejecución del bucle procede normalmente, pero además cada operación ejecutada se registra en un seguimiento. Las operaciones registradas normalmente se almacenan en un árbol de seguimiento , a menudo en una representación intermedia (IR). El seguimiento sigue a las llamadas a funciones, lo que hace que se incluyan en el seguimiento. El rastreo continúa hasta que el bucle llega a su final y vuelve al inicio.
Dado que la traza se registra siguiendo una ruta de ejecución concreta del bucle, las ejecuciones posteriores de esa traza pueden divergir de esa ruta. Para identificar los lugares donde eso puede suceder, se insertan instrucciones especiales de guardia en la traza. Un ejemplo de un lugar así son las declaraciones if. La protección es una verificación rápida para determinar si la condición original sigue siendo cierta. Si falla una guardia, se aborta la ejecución de la traza.
Dado que el rastreo se realiza durante la ejecución, se puede hacer que el rastreo contenga información de tiempo de ejecución (por ejemplo, información de tipo ). Esta información se puede utilizar posteriormente en la fase de optimización para aumentar la eficiencia del código.
Fase de optimización y generación de código
Las trazas son fáciles de optimizar, ya que representan solo una ruta de ejecución, lo que significa que no existe un flujo de control y no necesita manejo. Optimizaciones típicos incluyen eliminación constante subexpresión , eliminación de código muerto , regístrese asignación , movimiento invariante de código , plegado constante , y análisis de escape . [1]
Después de la optimización, la traza se convierte en código de máquina. De manera similar a la optimización, esto es fácil debido a la naturaleza lineal de las trazas.
Ejecución
Una vez que la traza se ha compilado en código de máquina, se puede ejecutar en iteraciones posteriores del bucle. La ejecución de la traza continúa hasta que falla un guardia.
Historia
Mientras que la idea de los JIT se remonta a la década de 1960, los JIT de rastreo se han utilizado con más frecuencia solo recientemente. La primera mención de una idea que es similar a la idea actual de rastrear JIT fue en 1970. [2] Se observó que el código compilado podría derivarse de un intérprete en tiempo de ejecución simplemente almacenando las acciones realizadas durante la interpretación.
La primera implementación del rastreo es Dynamo, "un sistema de optimización dinámica de software que es capaz de mejorar de forma transparente el rendimiento de un flujo de instrucciones nativo a medida que se ejecuta en el procesador". [3] Para hacer esto, el flujo de instrucciones nativo se interpreta hasta que se encuentra una secuencia de instrucciones "activa". Para esta secuencia, se genera, almacena en caché y ejecuta una versión optimizada.
Más tarde, Dynamo se extendió a DynamoRIO . Un proyecto basado en DynamoRIO fue un marco para la construcción de intérpretes que combina el seguimiento y la evaluación parcial. Se utilizó para "eliminar dinámicamente la sobrecarga del intérprete de las implementaciones del lenguaje". [4]
En 2006, se desarrolló HotpathVM, el primer compilador JIT de rastreo para un lenguaje de alto nivel [ cita requerida ] . [5] Esta máquina virtual era capaz de identificar dinámicamente instrucciones de código de bytes ejecutadas con frecuencia, que se rastrean y luego se compilan en código de máquina mediante la construcción de asignación única estática (SSA). La motivación de HotpathVM era tener una JVM eficiente para dispositivos móviles con recursos limitados.
Otro ejemplo de seguimiento JIT es TraceMonkey , una de las implementaciones de JavaScript de Mozilla para Firefox (2009). [6] TraceMonkey compila seguimientos de bucle ejecutados con frecuencia en el lenguaje dinámico JavaScript en tiempo de ejecución y especializa el código generado para los tipos dinámicos reales que ocurren en cada ruta.
Otro proyecto que utiliza JIT de rastreo es PyPy . Permite el uso de JIT de rastreo para implementaciones de lenguaje que fueron escritas con la cadena de herramientas de traducción de PyPy, mejorando así el rendimiento de cualquier programa que se ejecute usando ese intérprete. Esto es posible rastreando al propio intérprete, en lugar del programa que ejecuta el intérprete. [7]
Trazando los ECI también han sido exploradas por Microsoft en el proyecto para su SPUR Common Intermediate Language (CIL). SPUR es un rastreador genérico para CIL, que también se puede utilizar para rastrear a través de una implementación de JavaScript. [8]
Ejemplo de traza
Considere el siguiente programa de Python que calcula una suma de cuadrados de números enteros sucesivos hasta que esa suma excede 100000:
def cuadrado ( x ): return x * xi = 0 y = 0 mientras que Verdadero : y + = cuadrado ( i ) si y > 100000 : romper i = i + 1
Un rastro de este programa podría verse así:
loopstart ( i1 , y1 ) i2 = int_mul ( i1 , i1 ) # x * x y2 = int_add ( y1 , i2 ) # y + = i * i b1 = int_gt ( y2 , 100000 ) guard_false ( b1 ) i3 = int_add ( i1 , 1 ) # i = i + 1 salto ( i3 , y2 )
Observe cómo la llamada a la función a square
está insertada en el seguimiento y cómo la instrucción if se convierte en un guard_false
.
Ver también
Referencias
- ^ Bolz, Carl Friedrich; Cuni, Antonio; FijaBkowski, Maciej; Leuschel, Michael; Pedroni, Samuele; Rigo, Armin (enero de 2011). "Eliminación de asignaciones por evaluación parcial en un JIT de seguimiento" (PDF) . Actas del vigésimo taller ACM SIGPLAN sobre evaluación parcial y manipulación de programas . PEPM '11. págs. 43–52. doi : 10.1145 / 1929501.1929508 . S2CID 15871223 . Consultado el 13 de diciembre de 2020 .
- ^ Mitchell, James G. (29 de junio de 1970). El Diseño y Construcción de Sistemas de Programación Interactiva (PhD) flexibles y eficientes . Universidad Carnegie Mellon . ISBN 978-0-8240-4414-5. LCCN 79050563 . OCLC 633313022 . S2CID 36249021 . Expediente AAI7104538 . Consultado el 13 de diciembre de 2020 .
- ^ Bala, Vasanth; Duesterwald, Evelyn; Banerjia, Sanjeev (mayo de 2000). "Dynamo: un sistema de optimización dinámica transparente" (PDF) . Actas de la conferencia ACM SIGPLAN 2000 sobre diseño e implementación de lenguajes de programación . PLDI '00. págs. 1-12. doi : 10.1145 / 349299.349303 . ISBN 978-1-58113-199-4. S2CID 53223267 . Consultado el 13 de diciembre de 2020 .
- ^ Sullivan, Gregory T .; Bruening, Derek L .; Barón, Iris; Garnett, Timothy; Amarasinghe, Saman (junio de 2003). "Optimización dinámica nativa de intérpretes" (PDF) . Actas del taller de 2003 sobre intérpretes, máquinas virtuales y emuladores . IVME '03. págs. 50–57. doi : 10.1145 / 858570.858576 . ISBN 978-1-58113-655-5. S2CID 509405 . Consultado el 13 de diciembre de 2020 .
- ^ Gal, Andreas ; Probst, Christian W .; Franz, Michael (junio de 2006). "HotpathVM: un compilador JIT eficaz para dispositivos con recursos limitados" (PDF) . Actas de la 2ª conferencia internacional sobre entornos de ejecución virtual . VEE '06. págs. 144-153. doi : 10.1145 / 1134760.1134780 . ISBN 978-1-59593-332-4. S2CID 17846788 . QID 56580114 . Consultado el 13 de diciembre de 2020 .
- ^ Gal, Andreas; Orendorff, Jason; Ruderman, Jesse; Smith, Edwin W .; Reitmaier, Rick; Bebenita, Michael; Chang, Mason; Franz, Michael; Eich, Brendan; Shaver, Mike; Anderson, David; Mandelin, David; Haghighat, Mohammad R .; Kaplan, Blake; Hoare, Graydon; Zbarsky, Boris (junio de 2009). "Especialización de tipo Just-in-Time basada en trazas para lenguajes dinámicos" (PDF) . Actas de la 30ª Conferencia ACM SIGPLAN sobre diseño e implementación de lenguajes de programación . PLDI '09. págs. 465–478. doi : 10.1145 / 1542476.1542528 . ISBN 978-1-60558-392-1. S2CID 207172806 . Consultado el 13 de diciembre de 2020 .
- ^ Bolz, Carl Friedrich; Cuni, Antonio; Fijalkowski, Maciej; Rigo, Armin (julio de 2009). "Seguimiento del metanivel: compilador JIT de seguimiento de PyPy" (PDF) . Actas del 4º taller sobre Implementación, Compilación, Optimización de Lenguajes Orientados a Objetos y Sistemas de Programación . ICOOOLPS '09. págs. 18-25. doi : 10.1145 / 1565824.1565827 . ISBN 978-1-60558-541-3. S2CID 7478596 . Consultado el 13 de diciembre de 2020 .
- ^ Bebenita, Michael; Brandner, Florian; Fahndrich, Manuel; Logozzo, Francesco; Schulte, Wolfram; Tillmann, Nikolai; Venter, Herman (octubre de 2010). "SPUR: un compilador JIT basado en seguimiento para CIL" (PDF) . Actas de la conferencia internacional ACM sobre lenguajes y aplicaciones de sistemas de programación orientados a objetos . OOPSLA '10. págs. 708–725. doi : 10.1145 / 1869459.1869517 . ISBN 978-1-4503-0203-6. S2CID 3395746 . Consultado el 13 de diciembre de 2020 .
enlaces externos
- Sitio web oficial de LuaJIT