Articles

Ver el análisis de Escape Funcionando

Posted on

Es posible que haya oído hablar de una fase de análisis del compilador llamada análisis de escape. Informa una optimización llamada reemplazo escalar de agregados que elimina la asignación innecesaria de objetos Java. Encuentro que la gente a menudo tiene un malentendido de lo que realmente hace esta optimización y una subestimación de lo que es capaz de hacer. Podemos conocerla mejor viéndola funcionar en la práctica.

Context

Mostraré cómo el compilador GraalVM, como parte de GraalVM y configurado para la compilación justo a tiempo en la configuración alojada, aplica el análisis de escape y el reemplazo escalar de agregados. El compilador GraalVM es más potente en este sentido que el compilador just-in-time más común al que probablemente esté acostumbrado, C2 en HotSpot.

Tenga en cuenta que cada vez que digo compilador en este artículo, me refiero a compilación justo a tiempo, el tipo de compilación que ocurre en tiempo de ejecución en la JVM. No me refiero al compilador javac.

Mostraré cómo entiende el compilador nuestros programas de ejemplo observando una de las estructuras de datos que utiliza durante la compilación, su representación intermedia superior. Este es un gráfico que captura el significado de un programa Java a medida que se optimiza y transforma antes de que comience la conversión a código máquina. Eso probablemente suene muy avanzado, pero creo que para la mayoría de las personas con algo de experiencia en Java, en realidad es una forma bastante accesible de entender lo que está haciendo el compilador.

Esta representación intermedia es diferente a un árbol de sintaxis abstracta, o AST, que es una representación sintáctica del texto en su programa. También es diferente a un gráfico de llamadas, que solo te dice qué métodos llaman a qué otros métodos.

Usaré una herramienta llamada Seafoam, del equipo de implementación de lenguaje de Shopify, para crear diagramas de las estructuras de datos descargadas de Graal. También puede usar una herramienta llamada Visualizador de gráficos Ideal de Oracle Labs.

Terminología

El análisis de escape es un proceso de análisis. Detecta si un objeto es visible fuera de una unidad de compilación (una unidad de compilación suele ser un método más cualquier otro método insertado en él.) Un objeto puede ser visible fuera de una unidad de compilación al ser devuelto, o pasado como argumento a otro método, o escrito en un campo, o similar.

El reemplazo escalar de agregados utiliza el resultado del análisis de escape y funciona en objetos que no escapan de la unidad de compilación, o que solo escapan en algunas ramas. Reemplaza objetos (agregados) con valores simples (escalares) de efecto similar a las variables locales. Veremos esto más concretamente más adelante.

Asignación de objetos

Trabajaremos con una clase simple Vector que contiene campos double x y y. Tiene un constructor, getters y un método add que devuelve un nuevo objeto que es este Vector agregado a otro.

Tengo un método main que ejecuta un bucle y llama a un método

sum

que usa

add

para sumar dos vectores generados aleatoriamente. El bucle está ahí para obtener el código lo suficientemente caliente como para activar la compilación justo a tiempo, la aleatorización está ahí para que los valores no se perfilen para que sean efectivamente constantes, y el método sum separado está ahí para crear un bloque de código ordenado para observar cuando se observa cómo se compila el código.

Compilaré y ejecutaré esto usando GraalVM CE en Java 8 20.3.0 en macOS en AMD64. Desactivo una optimización llamada reemplazo en la pila porque esta optimización hace que la compilación sea un poco más complicada y difícil de entender. Luego utilizo la opción

dump

de Graal para pedirle que descargue sus estructuras de datos de representación intermedia.

Ahora podemos usar Seafoam para ver cómo el compilador entiende el método sum, justo antes de ejecutar el análisis de escape. El archivo sum.bgv contiene la estructura de datos que el compilador descargó para nosotros.

% seafoam sum.bgv:14 render

Lo que estamos viendo aquí? Este gráfico es la forma en que Graal entiende el método sum mientras lo compila. Es código Java, pero libre de las restricciones de una representación textual. Las operaciones se representan como nodos (las cajas, los diamantes y los óvalos) y las relaciones entre las operaciones se representan como bordes (las flechas). La flecha roja gruesa significa que una operación debe ocurrir antes que otra. La flecha más delgada significa que la salida de la operación se utiliza como entrada para otra operación.

Dijimos que el programa se liberó de las restricciones de una representación textual. Mire la operación agregar en el nodo 14, por ejemplo. Sabemos que debe suceder después de cargar los dos valores de los dos campos x, y antes de almacenar el valor en el campo x en el nodo 19, pero no nos importa si sucede antes o después de cargar los dos campos y. En el código fuente textual de Java, todo está escrito en un orden lineal. El gráfico relaja esta restricción y codifica solo las restricciones que la Especificación del lenguaje Java realmente requiere. El compilador es libre de elegir el orden final en el que se ejecuta todo.

Leyendo este gráfico, podemos ver que creamos un nuevo Vector, luego cargamos los dos campos x y y de los objetos de entrada, los sumamos y luego los almacenamos en el nuevo Vector que creamos antes de devolverlo. Hay algunos detalles adicionales en el gráfico, como la verificación null, la barrera de campo final, y más porque este es un gráfico de compilador real, pero ignoraremos los de este artículo para mantenerlo corto.

La clave para ver aquí ahora es que hay un punto definido donde se crea el nuevo objeto Vector.

Reemplazo escalar básico

Veamos el mismo método justo después de que se haya ejecutado el análisis de escape y el reemplazo escalar de agregados.

% seafoam sum.bgv:15 render

Ahora el gráfico se ha relajado aún más de la forma en que aparece en el texto. En lugar de una operación New Vector, ahora la hemos descompuesto en una operación genérica para asignar un objeto, tomando el valor de los campos de ese objeto. Ya no hay StoreField aquí.

En este método en particular, esto no ha logrado nada útil: el gráfico se ha relajado, pero no reveló ninguna optimización realmente útil. Eso es porque el único objeto que asignamos realmente necesita ser asignado porque deja el método. El análisis de escape se ha ejecutado, pero el objeto escapó, por lo que no hubo reemplazo escalar de agregados.

Para llevar esto más lejos, veamos un método que suma tres objetos Vector.

private static Vector sum(Vector a, Vector b, Vector c) {return a.add(b).add(c);}

El gráfico antes del análisis de escape y el reemplazo escalar de agregados tiene la misma estructura que el método anterior. Tenemos dos operaciones New Vector. El resultado de a.add(b) se escribe en el primer objeto nuevo, y luego se lee de nuevo para el siguiente .add(c). Podemos ver cómo esto es un desperdicio, el objeto intermedio nunca es visible fuera de la unidad de compilación porque no se almacena ni se pasa en ningún lugar, así que ¿por qué asignarlo y por qué almacenar campos en él que acabamos de leer de nuevo de inmediato?

Si miramos el gráfico después del análisis de escape y el reemplazo escalar de agregados, vemos que el intermedio Vector se ha eliminado por completo. Solo hay uno Alloc, no dos. El agregado de los campos del objeto intermedio se ha reemplazado con los valores escalares de bordes que conectan directamente al productor y al consumidor, sin hacer un intermedio StoreField y luego LoadField.

La efectividad del reemplazo escalar

Algunos ejemplos más mostrarán cómo esta optimización es un poco más poderosa de lo que la gente suele suponer.

Si sumamos un array de objetos Vector estaremos creando lógicamente uno Vector por iteración.

private static Vector sum(Vector first, Vector... rest) {Vector sum = first;for (Vector vector : rest) {sum = sum.add(vector);}return sum;}

Este gráfico ahora es bastante complicado, pero el punto clave es que puedes ver una operación New Vector dentro del bucle (dentro del círculo formado por flechas rojas gruesas.)

Después del análisis de escape parcial y el reemplazo escalar de agregados, ahora no hay New Vector dentro del bucle. Hay una única asignación al final para el Vector final que se devuelve, y los valores para x y y se acumulan acumulando valores (los pequeños bucles alrededor de los nodos 33 y 92, y los nodos 36 y 93.) Esto significa que ya no se asigna memoria en el bucle interno de este método.

A veces la gente habla de objetos que no escapan de una unidad de compilación que se asigna en la pila. He aquí por qué es un malentendido. Este método suma dos objetos Vector pero solo devuelve el componente x.

private static double sumX(Vector a, Vector b) {return a.add(b).getX();}

Antes de que se ejecute el análisis de escape, este método se ve exactamente como el sum original, excepto que el campo x se carga y devuelve. El campo y se almacena pero nunca se usa, y el intermedio Vector no escapa de la unidad de compilación.

Después del análisis de escape y el reemplazo escalar de agregados, podemos ver un punto importante a tener en cuenta: después de que el objeto fue reemplazado por escalares, no hubo consumidor del valor y, por lo que el código para generarlo no tenía nada para conectarlo al gráfico y por lo tanto se eliminó.

Si estuviéramos literalmente asignando el objeto en la pila, almacenando el objeto en el mismo formato solo en la memoria de pila en lugar de en la memoria de pila, aún tendríamos que generar el valor intermedio y. No asignamos el objeto a ninguna parte, lo reemplazamos con bordes de flujo de datos.

Tenga en cuenta que la asignación de pila de objetos es realmente una cosa, y se propone para HotSpot estándar y C2, pero es para un propósito ligeramente diferente al que no vamos a entrar aquí por simplicidad.

En comparación con la optimización manual

¿Reescribiría algunos de estos métodos para acumular x y y en variables locales y no crear objetos intermedios Vector? Por ejemplo, podría reescribir sum sobre un array de objetos Vector como este:

Este gráfico es de hecho más eficiente que el gráfico de nuestra suma con objetos intermedios Vector antes del análisis de escape. No hay asignación dentro del bucle.

Pero si miramos hacia atrás a nuestro bucle de suma anterior con objetos intermedios Vector después del análisis de escape y el reemplazo escalar de agregados, se ven básicamente iguales. No hubo beneficio en reescribir este método de la versión de alto nivel con objetos intermedios simples Vector a la versión optimizada manualmente.

(Bueno, en realidad tal vez lo haya – la versión optimizada manualmente es más rápida de compilar y se ejecuta más rápidamente mientras se interpreta hasta que se compila.)

Análisis de escape parcial

Algo que Graal puede hacer que C2 no puede, y una ventaja clave de GraalVM, es el análisis de escape parcial. En lugar de determinar un valor binario de si un objeto escapa de la unidad de compilación o no, esto puede determinar en qué ramas se escapa un objeto, y mover la asignación del objeto solo a aquellas ramas donde se escapa.

Este método artificial suma dos objetos Vector, y luego, basado en una condición s, lo pasa como parámetro a otro método llamado blackhole, lo que hace que escape, o agrega un tercer vector y luego lo devuelve.

El intermedio Vector almacenado en x se escapa en la primera rama, pero no en la segunda.

Evitamos que blackhole esté en línea especificando -XX:CompileCommand=dontinline,Vector.blackhole.

Antes de ejecutar el análisis de escape parcial, podemos ver que New Vector para x se ejecuta para ambas ramas.

Después del análisis de escape parcial y el reemplazo escalar de agregados, el intermedio New Vector ha desaparecido. En cambio, en la rama donde se escapa tenemos el objeto Alloc, que hace referencia a los valores que debería tener de x y y, y en la otra rama donde el objeto no se escapa, los valores de x y y se usan directamente.

La asignación se ha movido solo a la rama donde realmente se necesita.

Esperamos que todo esto le ayude a comprender qué es el análisis de escape y el reemplazo escalar de agregados al verlo funcionar en la práctica. También espero que te muestre que no es realmente una asignación de pila y que en realidad es algo más poderoso que eso, y que te muestre lo que el compilador GraalVM puede hacer por ti.

Más información

El algoritmo de análisis de escape parcial de Graal se describe en Análisis de Escape Parcial y Reemplazo Escalar para Java.

He escrito más sobre estos gráficos de compiladores y cómo leerlos en Understanding Basic Graal Graphs.

Autor: Chris Seaton

Chris es Investigador (Ingeniero de Personal Senior) en Shopify, donde trabaja en el lenguaje de programación Ruby, y Visitante en la Universidad de Manchester.

Anteriormente fue Gerente de Investigación en el Grupo de Investigación de Máquinas Virtuales de Oracle Labs, donde dirigió la implementación de Ruby en TruffleRuby y trabajó en otros proyectos de lenguaje y máquinas virtuales. Antes de esto, completó un doctorado en Manchester, donde investigó lenguajes de programación y paralelismo irregular, y un MEng en la Universidad de Bristol sobre lenguajes con sintaxis y semántica mutables.

En su tiempo libre es Líder de escuadrón del escuadrón de Yeomanry de Cheshire del Propio Yeomanry de la Reina, el escuadrón de caballería ligera de reserva histórica de Cheshire.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.