Estrategias para implementar un lexer extremadamente rápido

• Comparte la estrategia y datos de rendimiento medidos al diseñar e implementar directamente un lexer ultrarrápido para el lenguaje purple-garden
• Aplica varias técnicas de optimización como threaded lexing (basado en tabla de saltos), copia cero con cadenas por ventana, interning y bump allocator
• Maximiza la velocidad de parsing mediante hashing de tokens y comparación de hashes precomputados del diccionario de palabras clave; una tabla de saltos supera a un simple switch en eficiencia de caché de CPU
• Al usar mmap para mapear el archivo completo y minimizar la asignación dinámica, reduce drásticamente el costo de IO y de gestión de memoria en entradas grandes
• Demuestra una velocidad de procesamiento de más de 10 veces frente a lexers conocidos (por ejemplo, flex y handcoded), y presenta microbenchmarks por etapa de parsing y ejecución

---

Resumen de lexing y del pipeline de compilación

• El lexer (tokenizador) transforma la cadena de entrada en una lista de tokens con significado, que luego el parser usa para construir un AST (árbol de sintaxis abstracta)
• En el lenguaje purple-garden, el diseño de tokens mantiene una estructura mínima con el enum TokenType y solo información de cadena y tipo

Diseño mínimo del lexer y ejemplo de código

• La estructura del lexer solo guarda la cadena de entrada y la posición actual
• Genera tokens según cada carácter mediante una sentencia switch
• Para depuración, usa un arreglo de mapeo tipo-cadena e inicialización por tipo

Threaded Lexing (basado en tabla de saltos)

• En lugar de una sentencia switch, usa una tabla de saltos (jump table) para distinguir tokens (computed goto)
  • En un arreglo de 256 bytes, asigna a cada valor de carácter una etiqueta de procesamiento usando el carácter como índice
  • En la rama real del código, el macro JUMP_TARGET ejecuta el salto de inmediato
• Ventajas:
  • Menos fallos de caché y mejor predicción de ramas, entre otros, para una ejecución más rápida
• Desventajas:
  • No es compatible con MSVC (solo Clang y GCC) y dificulta la depuración

Gestión de memoria y abstracción del allocator

• Define una interfaz (estructura Allocator) para varias estrategias de asignación de memoria, como bump allocator
• El macro CALL simplifica los logs verbosos y el paso de contexto
• Muestra ejemplos de código y estructuras para asignación, liberación y estadísticas reales

Copia cero y manejo de cadenas basado en ventanas

• Introduce la estructura Str (puntero, longitud, hash) para un procesamiento eficiente en C
• Implementa directamente operaciones como slice, concat, eq, hashing y conversión numérica
• Los slices de cadena se crean al instante moviendo solo el puntero, sin asignación de memoria
• La conversión numérica también usa un algoritmo propio de conversión de caracteres a enteros

Hashing de tokens y comparación de palabras clave con hash precomputado

• Calcula el hash al crear el token (FNV-1a) para optimizar comparaciones repetidas e interning
• Las palabras clave constantes como true/false se comparan de inmediato por hash para ramificar más rápido
• is_alphanum (detección de letras/números/caracteres especiales) también se optimiza con operaciones bit a bit y lookup

Eficiencia en el parsing numérico y traslado a la etapa de compilación

• El lexer solo guarda la ventana y el hash de los tokens numéricos, y la conversión real a entero/flotante se hace una sola vez en la etapa de compilación
• Se confirma una mejora de más del 64% en throughput total cuando hay parsing repetido de valores numéricos

Aceleración de IO para archivos grandes

• En lugar del enfoque tradicional con fread, usa mmap para mapear directamente todo el archivo en memoria
• La función IO_read_file_to_string aplica mmap a toda la entrada y logra mejoras de 6 a 35 veces en archivos grandes

Benchmarks reales y comparación de rendimiento

• En laptop: 44 ms (solo tokenización) con entradas de más de 1,000,000 de líneas y 25 MB
• En desktop: 30 ms con la misma entrada (hasta 848 MB/s)
• Frente a otros lexers, logra más de 10 veces de mejora (0.3 s vs 2~13 s)
• Los microbenchmarks cuantifican el efecto de cada optimización (por ejemplo, 1.58x con bump allocator, 1.4~1.5x con cadenas sin alloc, 2.8x al mover el parsing numérico a compilación, etc.)

Resumen de la estrategia de implementación

• Ramificación directa basada en tabla de saltos (threaded lexing)
• Estructura de tokens por ventana con copia cero
• Interning de tokens constantes
• Gestión de memoria con bump allocator
• Hashing de tokens y comparación con hash precomputado
• Parsing diferido e interning de tokens numéricos y de cadena
• Procesamiento de archivos grandes con mmap
• Como trabajo futuro, propone uso de SIMD, algoritmos de hashing más rápidos, alineación de memoria y prefetch, y optimización de tablas de saltos según la entrada