Optimización de registros en RyuJIT usando algoritmos genéticos

## Optimización de la asignación de registros en RyuJIT mediante algoritmos genéticos

Los algoritmos genéticos destacan por encontrar soluciones contraintuitivas en problemas con espacios de búsqueda masivos —por ejemplo, optimizando el orden de las heurísticas para la asignación de registros en el compilador RyuJIT. En lugar de una secuencia rígida para seleccionar registros libres y ocupados, los investigadores del equipo de .NET encontraron experimentalmente un orden más eficiente que reduce los derrames en bucles "hot" y mejora el PerfScore.

El problema con el orden fijo de heurísticas

El algoritmo de asignación de registros por escaneo lineal (LSRA) en RyuJIT utiliza 17 heurísticas para seleccionar registros durante la compilación del método. Las primeras 13 se aplican a registros libres, las últimas 4 a los ocupados. Por defecto, el orden es estrictamente fijo: ABCDEFGHIJKLMNOPQ. Este enfoque puede ser subóptimo: si se agotan los registros libres en variables fuera de bucles, dentro de los bucles terminas derramando repetidamente valores de registros ocupados, lo que infla el tamaño del código y perjudica el rendimiento.

Ejemplo del mundo real: en un benchmark, todas las variables dentro de un bucle usaban el mismo registro, causando operaciones constantes de derrame/recarga. Esto no se debía a una falta de registros, sino porque la heurística siempre priorizaba los registros libres, incluso cuando no eran la mejor elección a largo plazo.

Refactorización de LSRA para orden dinámico

Para probar secuencias alternativas, los desarrolladores realizaron estos cambios:

• Movieron cada heurística a su propio método con el atributo __forceinline para evitar sobrecargas.
• Crearon una tabla hash que mapea símbolos (A–Q) a punteros de los métodos correspondientes.
• Introdujeron la variable de entorno COMPlus_JitLsraOrdering, que acepta una cadena de 17 símbolos únicos que definen el orden de las heurísticas.

Ahora puedes ejecutar el JIT con cualquier combinación, por ejemplo:

set COMPlus_JitLsraOrdering=PEHDCGAIJNLKOBFMQ

Esto te permite aplicar primero heurísticas para registros ocupados (p. ej., P para PREV_REG_OPT), y luego las de libres, lo que potencialmente ahorra registros libres para secciones críticas del código.

Medición de la efectividad con PerfScore

PerfScore se usa para evaluar la calidad de la asignación de registros —es una puntuación ponderada del costo de ejecución del código generado, que tiene en cuenta las latencias de instrucciones y el rendimiento. Es especialmente sensible a las operaciones de derrame/llenado (mov [rsp], reg / mov reg, [rsp]), particularmente en bucles.

La herramienta superpmi compara dos versiones de clrjit.dll en estas métricas:

• CodeSize — tamaño total del código máquina
• InstructionCount — número de instrucciones
• PerfScore — la métrica principal objetivo

El objetivo de la optimización es minimizar PerfScore. Pero el espacio de búsqueda es enorme: 17! ≈ 3.56 × 10¹⁴ permutaciones posibles. Una búsqueda exhaustiva es imposible, incluso en un clúster.

Aplicación de un algoritmo genético

Un algoritmo genético (GA) es perfecto para esto:

• Cromosoma: una cadena de 17 símbolos únicos (A–Q) que define el orden de las heurísticas.
• Función de aptitud: negativo del promedio de PerfScore en un conjunto de compilaciones de prueba (PerfScore más bajo = mayor aptitud).
• Operador de cruce: cruce basado en orden (p. ej., PMX) que preserva la unicidad de los símbolos.
• Mutación: intercambio aleatorio de dos posiciones.

El algoritmo itera de la siguiente manera:

• Inicializa una población aleatoria (p. ej., 100 cromosomas).
• Calcula la aptitud de cada individuo usando superpmi.
• Selecciona los mejores padres (torneo o ruleta).
• Genera descendencia mediante cruce y mutación.
• Actualiza la población; repite hasta la convergencia.

Resultados y limitaciones

Los experimentos mostraron que algunas permutaciones reducen el PerfScore general en un 0.5–1.2 % respecto al valor predeterminado. Las mayores ganancias se observaron en métodos con bucles anidados y muchas temporales.

Sin embargo, ten en cuenta:

• Las mejoras no son universales: un orden puede ayudar a algunos métodos y perjudicar a otros.
• El GA en sí tiene una alta sobrecarga: requiere miles de ejecuciones de superpmi.
• El orden óptimo depende de la arquitectura (x64 frente a Arm64) y del perfil de carga de trabajo.

Lecciones clave

• El orden fijo de heurísticas de LSRA puede ser subóptimo para escenarios del mundo real.
• COMPlus_JitLsraOrdering te permite ajustar órdenes sin cambiar el código fuente.
• Los algoritmos genéticos brillan en espacios de búsqueda de complejidad factorial.
• PerfScore es una métrica fiable para la calidad de la asignación de registros.
• Incluso reducciones de PerfScore inferiores al 1 % importan en sistemas de alto rendimiento.

— Editorial Team