Hispanopedia Wiki
Articulo de referencia

Seguimiento de la compilación justo a tiempo

La compilación justo a tiempo con seguimiento 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 logr...

Hispanopedia WikiContenido en espanolLectura gratuita

La compilación justo a tiempo con seguimiento 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 logra registrando una secuencia lineal de operaciones que se ejecutan con frecuencia, compilándolas a código máquina nativo y ejecutándolas. En cambio, la compilación justo a tiempo (JIT) tradicional compila cada método de forma secuencial, sin optimizar el proceso entre ellos.

Descripción general

La compilación justo a tiempo (JIT) es una técnica para aumentar la velocidad de ejecución de los programas mediante la compilación de partes de un programa a código máquina en tiempo de ejecución. Una forma de clasificar los diferentes compiladores JIT es según su ámbito de compilación. Mientras que los compiladores JIT basados ​​en métodos traducen un método a la vez a código máquina, los JIT de rastreo utilizan bucles de ejecución frecuente como unidad de compilación. Los JIT de rastreo se basan en el hecho de que muchos programas pasan la mayor parte del tiempo en ciertos bucles , denominados bucles calientes , y las iteraciones posteriores de los bucles suelen seguir rutas similares. Las máquinas virtuales que tienen un JIT de rastreo suelen ser entornos de ejecución de modo mixto, lo que significa que tienen un intérprete o un compilador de métodos, junto con el JIT de rastreo.

Detalles técnicos

Un compilador JIT con rastreo atraviesa varias fases durante la ejecución. Primero, se recopila información de perfilado para los bucles. Una vez identificado un bucle crítico, se inicia una fase de rastreo especial que registra todas las operaciones ejecutadas en dicho bucle. Esta secuencia de operaciones se denomina rastreo. A continuación, el rastreo se optimiza y se compila a código máquina. Cuando se ejecuta de nuevo este bucle, se llama al rastreo compilado en lugar del código del programa.

Estos pasos se explican detalladamente a continuación:

Fase de elaboración de perfiles

El objetivo del análisis de rendimiento es identificar bucles críticos. Esto se suele hacer contando el número de iteraciones de cada bucle. Cuando el número de iteraciones de un bucle supera un umbral determinado, se considera que el bucle está crítico y se inicia la fase de rastreo.

Fase de seguimiento

En la fase de rastreo, la ejecución del bucle continúa con normalidad, pero además, cada operación ejecutada se registra en un rastro. Estas operaciones registradas se almacenan normalmente en un árbol de rastreo , a menudo en una representación intermedia (IR). El rastreo sigue las llamadas a funciones, lo que provoca que se inserten en el rastro. El rastreo continúa hasta que el bucle finaliza y vuelve al inicio.

Dado que el rastro se registra siguiendo una ruta de ejecución concreta del bucle, las ejecuciones posteriores de dicho rastro pueden desviarse de esa ruta. Para identificar los puntos donde esto puede ocurrir, se insertan instrucciones de protección especiales en el rastro. Un ejemplo de ello son las sentencias condicionales (if). La protección consiste en una comprobación rápida para determinar si la condición original sigue siendo verdadera. Si la protección falla, la ejecución del rastro se interrumpe.

Dado que el rastreo se realiza durante la ejecución, este puede incluir información de tiempo de ejecución (por ejemplo, información de tipos ). Esta información puede utilizarse 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 una única ruta de ejecución, lo que significa que no existe flujo de control y no requiere 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 de constantes y el análisis de escape . [ 1 ]

Tras la optimización, el rastro se convierte en código máquina. Al igual que la optimización, esto resulta sencillo debido a la naturaleza lineal de los rastros.

Ejecución

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

Historia

Si bien la idea de los JIT se remonta a la década de 1960, el rastreo de JIT se ha vuelto más frecuente solo recientemente. La primera mención de una idea similar a la actual de rastreo de JIT data de 1970. [ 2 ] Se observó que el código compilado podía derivarse de un intérprete en tiempo de ejecución simplemente almacenando las acciones realizadas durante la interpretación.

La primera implementación de rastreo es Dynamo, "un sistema de optimización dinámica de software capaz de mejorar de forma transparente el rendimiento de un flujo de instrucciones nativo mientras se ejecuta en el procesador". [ 3 ] Para ello, el flujo de instrucciones nativo se interpreta hasta encontrar una secuencia de instrucciones "caliente". Para esta secuencia, se genera, almacena en caché y ejecuta una versión optimizada.

Dynamo se extendió posteriormente a DynamoRIO . Un proyecto basado en DynamoRIO fue un marco para la construcción de intérpretes que combina el rastreo y la evaluación parcial. Se utilizó para "eliminar dinámicamente la sobrecarga del intérprete de las implementaciones de lenguajes". [ 4 ]

En 2006, se desarrolló HotpathVM, el primer compilador JIT de rastreo para un lenguaje de alto nivel . [ 5 ] Esta máquina virtual era capaz de identificar dinámicamente las instrucciones de bytecode ejecutadas con frecuencia, las cuales se rastreaban y luego se compilaban a código máquina mediante la construcción estática de forma de asignación única (SSA). La motivación para HotpathVM era contar con una JVM eficiente para dispositivos móviles con recursos limitados.

Otro ejemplo de un JIT de rastreo es TraceMonkey , una de las implementaciones de JavaScript de Mozilla para Firefox (2009). [ 6 ] TraceMonkey compila rastreos 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 compiladores JIT de rastreo es PyPy . Permite el uso de compiladores JIT de rastreo para implementaciones de lenguaje escritas con la cadena de herramientas de traducción de PyPy, mejorando así el rendimiento de cualquier programa ejecutado con dicho intérprete. Esto es posible rastreando el intérprete en sí, en lugar del programa ejecutado por este. [ 7 ]

Microsoft también ha explorado el rastreo de JITs en el proyecto SPUR para su Lenguaje Intermedio Común (CIL). SPUR es un rastreador genérico para CIL, que también puede usarse para rastrear una implementación de JavaScript. [ 8 ]

Ejemplo de traza

Considere el siguiente programa en Python que calcula la suma de los cuadrados de números enteros sucesivos hasta que dicha suma supere los 100000:

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

Un registro de seguimiento para 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 a la función squarese inserta en línea en el rastreo y cómo la instrucció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 asignación mediante evaluación parcial en un JIT de rastreo" (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. Recuperado 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 (Tesis doctoral). Universidad Carnegie Mellon . ISBN 978-0-8240-4414-5LCCN 79050563 . OCLC 633313022 . S2CID 36249021 . Expediente AAI7104538 . Consultado el 13-12-2020 .   
  3. ↑ 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-12-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-12-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 . Wikidata Q56580114 . 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 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-12-2020 . 
  7. ↑ Bolz, Carl Friedrich; Cuni, Antonio; Fijalkowski, Maciej; Rigo, Armin (julio de 2009). "Rastreando el metanivel: el compilador JIT de rastreo de PyPy" (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. págs. 18–25 . doi : 10.1145/1565824.1565827 . ISBN  978-1-60558-541-3. S2CID 7478596 . Consultado el 13-12-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 de la ACM sobre sistemas, lenguajes y aplicaciones de programación orientada a objetos . OOPSLA '10. págs. 708–725 . doi : 10.1145/1869459.1869517 . ISBN  978-1-4503-0203-6. S2CID 3395746 . Consultado el 13-12-2020 . 
  • Sitio web oficial , LuaJIT