Cuando una máquina virtual basada en bytecode genera un error en tiempo de ejecución, necesita traducir el desplazamiento del bytecode a la línea del código fuente que lo produjo. Este artículo, surgido de los retos del capítulo 14 del libro 'Crafting Interpreters' de Robert Nystrom, analiza de forma didáctica las estrategias para almacenar esa correspondencia y compara su coste en memoria y en tiempo de acceso.
La solución más directa asigna una línea a cada byte del bytecode, con acceso O(1) pero consumo O(n). Para reducir espacio se recurre a la codificación por longitudes de carrera (run-length encoding), que compacta bloques de bytes consecutivos de la misma línea en pares (conteo, línea), reduciendo la tabla a O(r). Sin embargo, si se repite un escaneo lineal por cada byte a desensamblar, el recorrido completo puede llegar a O(n²). Un recorrido en una sola pasada con un cursor lo deja en O(n).
Una alternativa más versátil consiste en registrar los desplazamientos de inicio de cada línea en lugar de la longitud de la carrera. Como los pares quedan ordenados, basta una búsqueda binaria para resolver lookups aleatorios en O(log r), mientras un cursor durante el desensamblado secuencial mantiene el recorrido total en O(n). El artículo incluye código en Rust con la invariantes necesarias.
Finalmente, se compara el enfoque con máquinas virtuales reales: la JVM usa una LineNumberTable con pares (start_pc, line_number) y HotSpot realiza una búsqueda lineal para encontrar el predecesor; Lua almacena deltas de una línea respecto a la anterior con puntos de control absolutos ocasionales para acotar los escaneos.