La representación de valores en memoria es un problema fundamental en la implementación de máquinas virtuales (VMs) para lenguajes de tipado dinámico. Estos lenguajes, como Python o JavaScript, requieren que las variables puedan contener valores de tipos arbitrarios en tiempo de ejecución, lo que a menudo se resuelve con un tipo Value genérico. La eficiencia de esta representación impacta directamente el consumo de memoria y el rendimiento del intérprete, especialmente en operaciones intensivas en datos o en entornos con restricciones de caché. Históricamente, las VMs han empleado diversas estrategias, desde 'boxing' completo hasta esquemas de 'tagging' sofisticados, para equilibrar la flexibilidad con la eficiencia.
El desafío radica en empaquetar la información de tipo y el valor real en el menor número de bits posible, minimizando el 'overhead' de memoria y los accesos a caché. Una representación ineficiente puede llevar a un uso excesivo de memoria, lo que a su vez provoca más fallos de caché (cache misses) y un mayor tráfico de memoria, degradando el rendimiento general. Este artículo aborda cómo una técnica de 'low-bit tagging' puede resolver este problema, permitiendo que los valores se ajusten a un registro de 64 bits y mejorando la 'cache-friendliness' de la VM.
La relevancia actual de esta optimización se acentúa con la creciente demanda de rendimiento en aplicaciones interpretadas, desde gráficos 3D en tiempo real hasta el procesamiento de datos. La capacidad de ejecutar código dinámico con una eficiencia cercana a la de lenguajes compilados es un objetivo constante en el diseño de VMs modernas, y la representación de valores es un pilar crítico para lograrlo.
Arquitectura del Sistema
La arquitectura original de Plush utilizaba un enum etiquetado de Rust para su tipo Value, que ocupaba 16 bytes debido a las restricciones de alineación de memoria, a pesar de que los subtipos individuales y la etiqueta requerían menos bits. Esta representación, aunque conveniente para la lógica de despacho con match en Rust, generaba un desperdicio significativo de memoria, especialmente en estructuras de datos como arrays de valores.
La refactorización introduce un esquema de 'low-bit tagging' donde el tipo Value se encapsula en un u64 (8 bytes). Este esquema utiliza los bits menos significativos de la palabra de 64 bits para codificar el tipo de valor (tag). Se distinguen cinco categorías: 'fixnums' (enteros de 62 bits), 'flonums' (puntos flotantes), 'immediates' (valores como nil, true, false, IDs de funciones/clases, funciones 'host'), y dos tipos de punteros. Los 'fixnums' se almacenan desplazados a la izquierda dos bits (n << 2), permitiendo que los dos bits menos significativos sean 00. Esto es crucial porque las operaciones aritméticas (suma, resta) y comparaciones pueden realizarse directamente sobre los valores etiquetados sin 'untagging' o 'retagging', aprovechando instrucciones de máquina como adds y b.vs (para detección de 'overflow').
Para los 'flonums', se emplea una técnica de 'Float Self-Tagging' basada en un paper de Melançon, Serrano y Feeley. Esta técnica rota los bits superiores del valor flotante y añade un 'bias' para que los dos bits menos significativos sean 10. Esto permite representar 'subnormals', 'infinity' y 'NaNs' sin 'heap boxing', sacrificando solo dos bits del exponente y manteniendo la precisión de la mantisa. Las operaciones con 'flonums' requieren 'untagging' y 'retagging' explícitas, lo que implica más instrucciones bitwise y aritméticas.
Los 'immediates' utilizan un subtag de 5 bits dentro de los bits de etiqueta para identificar subtipos como nil o true. La comparación de igualdad se optimiza mediante un bit en la etiqueta que indica si dos valores pueden compararse directamente con una sola instrucción de máquina (ej. enteros, punteros simples, 'immediates' pequeños). Los valores que exceden el rango de 'fixnums' o 'flonums' se 'boxean' en el 'heap', aunque esto se considera una ruta lenta y poco frecuente. La implementación utiliza un 'bump allocator' para hacer que el 'heap boxing' sea relativamente rápido.
Flujo de Suma de Fixnums
- 1 Pop v1, v0 Cargar v1 y v0 de la pila del intérprete (8 bytes cada uno).
- 2 Test Tags Verificar si v0 y v1 son 'fixnums' (bits bajos '00') con una sola instrucción...
- 3 Fast Path (Fixnum) Si ambos son 'fixnums', realizar suma directa `adds x11, x2, x3`.
- 4 Check Overflow Verificar 'overflow' de 62 bits con `b.vs`.
- 5 Push Result Almacenar el resultado etiquetado (8 bytes) de vuelta en la pila.
- 6 Continue Dispatch Continuar con la siguiente instrucción del intérprete.
- 7 Slow Path (Non-Fixnum) Si no son 'fixnums', desviar a la ruta lenta para 'flonums' o 'boxing'.
Flujo de Suma de Flonums (Fast Path)
- 1 Pop v1, v0 Cargar v1 y v0 de la pila del intérprete.
- 2 Test Tags Verificar si v0 y v1 son 'flonums' (bits bajos '10').
- 3 Undo Rotate & Bias Deshacer la rotación y el 'bias' para obtener el valor IEEE 754 original.
- 4 FPU Add Realizar la suma de punto flotante en la FPU (`fadd d0, d0, d1`).
- 5 Apply Bias & Rotate Aplicar el 'bias' y la rotación para re-etiquetar el resultado.
- 6 Check Result Tag Verificar si el resultado re-etiquetado sigue siendo un 'flonum' válido.
- 7 Push Result Almacenar el resultado etiquetado en la pila.
- 8 Slow Path (Box) Si el resultado no es un 'flonum' válido, 'boxear' en el 'heap'.
| Capa | Tecnología | Justificación |
|---|---|---|
| compute | Rust | Lenguaje de implementación de la VM y el intérprete. Su sistema de tipos (enums) fue el punto de partida para la optimización. |
| storage | Low-Bit Tagging (Custom) | Esquema de representación de valores en memoria para reducir el tamaño de `Value` de 16 a 8 bytes, mejorando la 'cache-friendliness'. vs Rust Tagged Enum (original), NaN Boxing Fixnums (n << 2), Flonums (Float Self-Tagging), Immediates (5-bit subtag) |
| compute | ARM64 / x86-64 | Arquitectura de CPU objetivo. Las optimizaciones aprovechan instrucciones específicas (ej. `adds`, `b.vs`, `ror`, `tst`, `ccmp`) y el tamaño de los registros (64 bits). |
| storage | Bump Allocator | Mecanismo de asignación de memoria para el 'heap' de la VM, utilizado para 'boxear' valores que no caben en la representación etiquetada. Contribuye a la rapidez de las asignaciones. |
Trade-offs
Ganancias
- ▲ Uso de memoria
- ▲ Rendimiento del intérprete
- ▲ Cache-friendliness
Costes
- △ Complejidad del código de la VM
- △ Necesidad de 'heap boxing' para valores fuera de rango
- △ Posible regresión de memoria en casos específicos (ej. sha256_unfixed) si no se optimiza el código fuente
Insn::add => {
let v1 = pop!();
let v0 = pop!();
if v0.is_fixnum() && v1.is_fixnum() {
if let Some(sum) = (v0.raw() as i64).checked_add(v1.raw() as i64) {
push!(Value::from_raw(sum as u64));
continue;
}
}
flonum_op!(v0, v1, +);
let r = slow!("add", self.add_slow(v0, v1));
push!(r);
}Fundamentos Teóricos
El problema de la representación eficiente de valores en lenguajes dinámicos ha sido un tema recurrente en la investigación de lenguajes de programación y diseño de VMs. El esquema de 'low-bit tagging' y 'NaN boxing' (Not a Number boxing) son técnicas bien establecidas en la literatura. 'NaN boxing', popularizado por su uso en motores JavaScript como SpiderMonkey de Firefox, explota las propiedades del formato IEEE 754 de punto flotante de doble precisión, donde ciertos patrones de bits en el campo del exponente indican un NaN, dejando bits de la mantisa disponibles para codificar otros tipos de datos. Este concepto se discute en profundidad en libros como 'Crafting Interpreters' de Robert Nystrom.
La técnica específica de 'Float Self-Tagging' mencionada en el artículo se basa en el trabajo de Olivier Melançon, Manuel Serrano y Marc Feeley, como se describe en su paper 'Float Self-Tagging' (aunque el año específico no se proporciona en el texto, la referencia a autores y título es clave). Este paper propone un método para codificar valores flotantes directamente en una palabra de máquina junto con información de tipo, utilizando rotaciones de bits y un 'bias' para manipular los bits de etiqueta sin necesidad de 'shifting' o 'masking' explícitos para la mayoría de las operaciones. Este enfoque es una evolución de las técnicas de 'tagging' y 'boxing' que buscan minimizar el 'overhead' de rendimiento y memoria en sistemas de tipos dinámicos, conectando directamente con los fundamentos de la arquitectura de computadoras y la teoría de compiladores.