Stratégies d’implémentation d’un lexer ultra-rapide

• Partage des stratégies de conception et d’implémentation d’un lexer ultra-rapide développé sur mesure pour le langage purple-garden, avec des mesures de performance réelles
• Application de diverses techniques d’optimisation comme le threaded lexing (basé sur une table de saut), les chaînes en fenêtre sans copie, l’interning et le bump allocator
• Accélération maximale du parsing grâce au hachage des tokens et à la comparaison de hachages pré-calculés pour les mots-clés ; les tables de saut se révèlent plus efficaces pour le cache CPU qu’un simple switch
• mmap du fichier entier et réduction des allocations dynamiques pour diminuer fortement les coûts d’E/S et de gestion mémoire sur de gros volumes d’entrée
• Démonstration d’une vitesse de traitement jusqu’à plus de 10 fois supérieure à celle de lexers connus (par ex. flex, handcoded), avec des microbenchmarks détaillés pour chaque étape du parsing et de l’exécution

---

Vue d’ensemble du lexing et du pipeline de compilation

• Le lexer (tokenizer) transforme la chaîne d’entrée en une liste de tokens significatifs, puis le parseur les consomme pour construire un AST (arbre syntaxique abstrait)
• Dans le langage purple-garden, la conception des tokens repose sur l’énumération TokenType et conserve une structure minimale ne stockant que la chaîne et les informations de type

Conception minimale du lexer et exemples de code

• La structure du lexer ne stocke que la chaîne d’entrée et la position courante
• Création des tokens selon chaque caractère via un switch
• Utilisation d’un tableau de correspondance type-chaîne et d’une initialisation par type pour le débogage

Threaded Lexing (basé sur une table de saut)

• Au lieu d’un switch, traitement de la distinction des tokens via une table de saut (jump table, computed goto)
  • Dans un tableau de 256 octets, chaque valeur de caractère sert d’index vers l’étiquette de traitement correspondante
  • Lors des branches réelles du code, exécution immédiate du saut via la macro JUMP_TARGET
• Avantages :
  • Moins de cache misses et meilleure prédiction de branchement, donc exécution plus rapide
• Inconvénients :
  • Non pris en charge par MSVC (Clang et GCC uniquement), débogage plus difficile

Gestion mémoire et abstraction des allocators

• Définition d’une interface (structure Allocator) pour différentes stratégies d’allocation mémoire, dont le bump allocator
• La macro CALL simplifie les logs verbeux et la transmission du contexte
• Présentation d’exemples de code pour l’allocation/libération réelles, les statistiques et les structures associées

Traitement des chaînes sans copie, basé sur des fenêtres

• Introduction de la structure Str (pointeur, longueur, hachage) pour un traitement efficace en C
• Implémentation directe de slice, concat, eq, hashing, conversion numérique, etc.
• Les slices de chaînes sont créées instantanément par simple déplacement de pointeur, sans allocation mémoire
• La conversion numérique repose elle aussi sur un algorithme maison de conversion caractère-entier

Hachage des tokens et comparaison de mots-clés via hachages pré-calculés

• Calcul du hachage (FNV-1a) à la création du token pour optimiser les comparaisons répétées et l’interning
• Pour les mots-clés constants comme true/false, bifurcation immédiate par comparaison de hachage (gain de performance)
• is_alphanum (détection lettres/chiffres/caractères spéciaux) est lui aussi optimisé via des opérations bit à bit et des tables de lookup

Optimisation du parsing numérique et déplacement vers l’étape de compilation

• Le lexer ne stocke pour les tokens numériques que la fenêtre et le hachage ; la conversion effective en entier ou flottant n’est effectuée qu’une seule fois à l’étape de compilation, sans doublon
• En cas de parsing répété de mêmes valeurs numériques, une amélioration de plus de 64 % du débit global a été observée

Accélération des E/S sur de gros fichiers

• Remplacement de l’approche fread par mmap pour mapper directement en mémoire le fichier complet
• La fonction IO_read_file_to_string mappe l’intégralité de l’entrée via mmap, avec des gains de performance de 6 à 35 fois sur de gros fichiers

Benchmarks réels et comparaison des performances

• Sur laptop : 44 ms pour plus de 1 000 000 de lignes et 25 Mo d’entrée (tokenisation seule)
• Sur desktop : 30 ms sur la même entrée (jusqu’à 848 Mo/s)
• Jusqu’à plus de 10 fois plus rapide que d’autres lexers (0,3 s contre 2 à 13 s)
• Les microbenchmarks quantifient l’effet de chaque optimisation (par ex. bump allocator : x1,58 ; chaînes 0 alloc : x1,4 à x1,5 ; déplacement du parsing numérique à l’étape de compilation : x2,8, etc.)

Résumé de la stratégie d’implémentation

• Branchement direct basé sur une table de saut (threaded lexing)
• Structure de tokens en fenêtre sans copie
• Interning des tokens constants
• Gestion mémoire basée sur un bump allocator
• Hachage des tokens et comparaison via hachages pré-calculés
• Parsing différé et interning des tokens numériques et chaînes
• Traitement des gros fichiers via mmap
• Parmi les pistes futures : utilisation du SIMD, algorithmes de hachage plus rapides, alignement mémoire et prefetch, optimisation des tables de saut selon l’entrée, etc.