Seguimiento de la compilación justo a tiempo
Técnica utilizada para optimizar la ejecución de un programa en tiempo de ejecución.
Ejecución del programa
Conceptos generales
Tipos de código
Estrategias de compilación
Tiempos de ejecución notables
Compiladores y cadenas de herramientas notables

El seguimiento de la compilación Just-in-Time 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 que se ejecutan con frecuencia, compilándolas en código de máquina nativo y ejecutándolas. Esto se opone a los compiladores Just-in-Time (JIT) tradicionales que funcionan por método.

Descripción general

La compilación justo a tiempo es una técnica que permite aumentar la velocidad de ejecución de los programas compilando partes de un programa en código de máquina en tiempo de ejecución. Una forma de clasificar los distintos compiladores JIT es por su ámbito de compilación. Mientras que los compiladores JIT basados ​​en métodos traducen un método a la vez en código de máquina, los JIT de seguimiento utilizan bucles ejecutados con frecuencia como unidad de compilación. Los JIT de seguimiento se basan en la suposición de que los programas pasan la mayor parte de su tiempo en algunos bucles del programa ("bucles activos") y las iteraciones de bucle posteriores suelen seguir rutas 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 información de creación de perfiles para los bucles. Una vez identificado un bucle activo, se pasa a una fase de seguimiento especial , que registra todas las operaciones ejecutadas de ese bucle. Esta secuencia de operaciones se denomina seguimiento. A continuación, el seguimiento se optimiza y se compila en código de máquina. Cuando se vuelve a ejecutar este bucle, se llama al seguimiento compilado en lugar del programa homólogo.

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 activos. Esto se suele hacer contando la cantidad de iteraciones de cada bucle. Una vez que el recuento de un bucle supera un umbral determinado, se considera que el bucle está activo y se inicia la fase de seguimiento.

Fase de rastreo

En la fase de seguimiento, la ejecución del bucle se lleva a cabo de forma normal, pero además, cada operación ejecutada se registra en un seguimiento. Las operaciones registradas se almacenan normalmente en el árbol de seguimiento , a menudo en una representación intermedia (IR). El seguimiento sigue a las llamadas de función, lo que hace que se incorporen en el seguimiento. El seguimiento continúa hasta que el bucle llega a su final y vuelve al inicio.

Dado que el seguimiento se registra siguiendo una ruta de ejecución concreta del bucle, las ejecuciones posteriores de ese seguimiento pueden desviarse de esa ruta. Para identificar los lugares donde esto puede suceder, se insertan instrucciones de protección especiales en el seguimiento. Un ejemplo de un lugar así son las instrucciones if. La protección es una comprobación rápida para determinar si la condición original sigue siendo verdadera. Si una protección falla, se cancela la ejecución del seguimiento.

Dado que el seguimiento se realiza durante la ejecución, se puede hacer que el seguimiento 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

Los rastros 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. Las optimizaciones típicas incluyen la eliminación de subexpresiones comunes , la eliminación de código muerto , la asignación de registros , el movimiento de código invariante , el plegado constante y el análisis de escape . [1]

Después de la optimización, el rastro se convierte en código de máquina. Al igual que la optimización, esto es fácil debido a la naturaleza lineal de los rastros.

Ejecución

Una vez compilado el seguimiento en código de máquina, se puede ejecutar en iteraciones posteriores del bucle. La ejecución del seguimiento continúa hasta que falla una protección.

Historia

Si bien la idea de los JIT se remonta a la década de 1960, los JIT de seguimiento se han utilizado con más frecuencia solo recientemente. La primera mención de una idea similar a la idea actual de los JIT de seguimiento fue en 1970. [2] Se observó que el código compilado se podía derivar 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 ello, se interpreta el flujo de instrucciones nativo hasta que se encuentra una secuencia de instrucciones "caliente". Para esta secuencia se genera una versión optimizada, se almacena en caché y se ejecuta.

Dynamo se amplió posteriormente 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 de los intérpretes de las implementaciones de 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 para HotpathVM era tener una JVM eficiente para dispositivos móviles con recursos limitados.

Otro ejemplo de un JIT de seguimiento es TraceMonkey , una de las implementaciones de JavaScript de Mozilla para Firefox (2009). [6] TraceMonkey compila seguimientos de bucles 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 el rastreo de JIT es PyPy . Permite el uso de JIT de rastreo para implementaciones de lenguaje que se escribieron con la cadena de herramientas de traducción de PyPy, mejorando así el rendimiento de cualquier programa que se ejecute utilizando ese intérprete. Esto es posible al rastrear al intérprete en sí, en lugar del programa que ejecuta el intérprete. [7]

Microsoft también ha explorado el seguimiento de JIT en el proyecto SPUR para su lenguaje intermedio común (CIL). SPUR es un rastreador genérico para CIL, que también se puede utilizar para rastrear una implementación de JavaScript. [8]

Ejemplo de un rastro

Considere el siguiente programa Python que calcula una suma de cuadrados de números enteros sucesivos hasta que esa suma exceda 100000:

def  cuadrado ( x ):  devuelve  x  *  xi  =  0 y  =  0 mientras sea  verdadero :  y  +=  cuadrado ( i )  si  y  >  100000 :  romper  i  =  i  +  1

Un seguimiento de este programa podría verse así:

 loopstart ( i1 ,  y1 )  i2  =  int_mul ( i1 ,  i1 ) # i*i  y2  =  int_add ( y1 ,  i2 ) # y += i*i  b1  =  int_gt ( y2 ,  100000 )  guard_false ( b1 )  i3  =  int_add ( i1 ,  1 ) # i = i+1  jump ( i3 ,  y2 )

Observe cómo la llamada de función squarese incorpora al seguimiento y cómo la declaración if se convierte en un guard_false.

Véase también

Referencias

  1. ^ Bolz, Carl Friedrich; Cuni, Antonio; FijaBkowski, Maciej; Leuschel, Michael; Pedroni, Samuele; Rigo, Armin (enero de 2011). "Eliminación de asignaciones mediante evaluación parcial en un JIT de seguimiento" (PDF) . Actas del 20.º 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 .
  2. ^ Mitchell, James G. (29 de junio de 1970). El diseño y la construcción de sistemas de programación interactiva flexibles y eficientes (PhD). Universidad Carnegie Mellon . ISBN 978-0-8240-4414-5. LCCN  79050563. OCLC  633313022. S2CID  36249021. Expediente AAI7104538 . Consultado el 13 de diciembre de 2020 .
  3. ^ Bala, Vasanth; Duesterwald, Evelyn; Banerjia, Sanjeev (mayo de 2000). "Dynamo: A Transparent Dynamic Optimization System" (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 .
  4. ^ Sullivan, Gregory T.; Bruening, Derek L.; Baron, Iris; Garnett, Timothy; Amarasinghe, Saman (junio de 2003). "Optimización nativa dinámica de intérpretes" (PDF) . Actas del taller de 2003 sobre intérpretes, máquinas virtuales y emuladores . IVME '03. págs. 50–57. CiteSeerX 10.1.1.14.9819 . doi :10.1145/858570.858576. ISBN .  978-1-58113-655-5. S2CID  509405 . Consultado el 13 de diciembre de 2020 .
  5. ^ 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 .
  6. ^ 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 tipos Just-in-Time basada en trazas para lenguajes dinámicos" (PDF) . Actas de la 30.ª Conferencia SIGPLAN de la ACM 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 .
  7. ^ Bolz, Carl Friedrich; Cuni, Antonio; Fijalkowski, Maciej; Rigo, Armin (julio de 2009). "Tracing the Meta-Level: PyPy's Tracing JIT Compiler" (PDF) . Actas del 4º taller sobre la implementación, compilación y optimización de lenguajes y sistemas de programación orientados a objetos . ICOOOLPS '09. pp. 18–25. doi :10.1145/1565824.1565827. ISBN 978-1-60558-541-3. S2CID  7478596 . Consultado el 13 de diciembre de 2020 .
  8. ^ Bebenita, Michael; Brandner, Florian; Fahndrich, Manuel; Logozzo, Francesco; Schulte, Wolfram; Tillmann, Nikolai; Venter, Herman (octubre de 2010). "SPUR: un compilador JIT basado en trazas 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 .
  • Sitio web oficial de LuaJIT
Retrieved from "https://en.wikipedia.org/w/index.php?title=Tracing_just-in-time_compilation&oldid=1244249633"