GitHub est parvenue à exécuter le pliage de la casse, ou Case Folding, à une vitesse supérieure à 45 gigaoctets par seconde sur un seul cœur en repensant la boucle logicielle afin qu’elle ne s’arrête pas au premier octet non-ASCII, mais balaie l’intégralité du tampon sans branches de contrôle dépendant des données. L’entreprise utilise cette opération dans son moteur de recherche de code Blackbird, qui indexe plus de 180 millions de dépôts et plus de 480 téraoctets de code source.
Alexander Neubeck et Greg Orzell ont présenté les détails de cette conception dans un billet publié sur le blog de GitHub le 31 juillet 2026. Le billet annonçait également la mise à disposition du résultat dans une bibliothèque Rust open source appelée casefold.
Le pliage de la casse ne consiste pas simplement à convertir en minuscules
Les moteurs de recherche et les outils de correspondance de texte ont besoin d’une représentation standard qui rende égales lors de la comparaison les chaînes qui diffèrent par la casse. Cela intervient dans la recherche, les expressions régulières insensibles à la casse, ainsi que les noms d’utilisateur et les noms d’hôte.
Mais la conversion en minuscules ne produit pas le même résultat. La conversion en minuscules peut dépendre de la langue et du contexte, comme la différence de forme de la lettre sigma grecque en fin de mot et à l’intérieur d’un mot, ou les règles différentes applicables à la lettre I en turc. Le pliage de la casse est, lui, conçu pour la comparaison et est donc indépendant de la langue et du contexte. Le résultat diffère également dans des cas tels que la lettre allemande ß, la lettre turque İ et le sigma grec final.
La bibliothèque effectue un pliage simple, un-à-un, conformément aux conditions C et S du fichier CaseFolding.txt de la base de données des caractères Unicode. Elle n’effectue pas les opérations de pliage multicaractères, comme la conversion de ß en ss, ni les opérations de pliage propres au turc.
Supprimer l’optimisation qui ralentissait la boucle
Comme le code source se compose majoritairement de caractères ASCII, le chemin le plus rapide se concentre sur la conversion des lettres latines majuscules de A à Z en minuscules. La conception intuitive s’arrêtait dès qu’elle trouvait un octet non-ASCII, puis transférait le reste du texte vers un chemin Unicode. Mais les tests réalisés sur un processeur Apple M4 ont montré que cette approche ne dépassait pas environ 3 gigaoctets par seconde.
La principale raison réside dans les branches de contrôle à l’intérieur de la boucle. Au lieu de tester chaque octet et de s’arrêter rapidement, l’algorithme rassemble le bit de poids fort de tous les octets dans une seule variable, puis teste le résultat une fois le balayage terminé. Le test visant à déterminer si l’octet appartient à l’intervalle des lettres majuscules est, quant à lui, effectué arithmétiquement en soustrayant le caractère A avec bouclage, puis en comparant le résultat au nombre 26. Un masque arithmétique est ensuite utilisé pour fixer le cinquième bit de l’octet, ce qui convertit la lettre majuscule en minuscule sans branche ni écriture conditionnelle.
Cette structure permet au compilateur LLVM de générer des instructions vectorielles traitant 16 octets à la fois à l’aide de NEON sur l’Apple M4. Le résultat dépasse 45 gigaoctets par seconde, ce qui s’approche de la limite de la bande passante mémoire. Les mesures de GitHub indiquent que la suppression de la sortie anticipée est le facteur ayant permis la vectorisation ; conserver une sortie dépendant des données empêche la génération d’instructions vectorielles, même si le reste de la boucle devient dépourvu de branches.
Pourquoi un balayage combiné n’est-il pas toujours plus rapide ?
GitHub a testé un compromis fondé sur l’examen de l’ASCII par blocs, puis la conversion du préfixe ASCII. Cette méthode lit les données deux fois, mais a atteint environ 23 gigaoctets par seconde, soit bien plus que la boucle naïve, tout en conservant la possibilité de s’arrêter au premier bloc non-ASCII.
En revanche, combiner l’examen et la conversion dans une seule boucle opérant sur des blocs de 16 octets s’est révélé plus lent, avec environ 8,7 gigaoctets par seconde contre 23 gigaoctets par seconde pour la solution à deux passages. Selon le billet, une branche de sortie anticipée après chaque bloc empêche le compilateur de dérouler la boucle ou de masquer le temps d’attente entre la lecture, le test, la conversion et l’écriture. Deux boucles propres et facilement vectorisables ont donc dépassé une seule boucle qui touche moins souvent aux données, mais contient une branche dépendant du contenu.
Réduire les allocations mémoire
La fonction simple_fold prend une chaîne String par propriété, ce qui lui permet de modifier son tampon et de le renvoyer directement. Si le texte est entièrement ASCII, la même mémoire est renvoyée après la conversion des caractères sur place, sans second tampon ni copie supplémentaire.
En présence de caractères non-ASCII, l’algorithme ne crée un nouveau tampon que lorsqu’il atteint un caractère dont la longueur ou le contenu change. Le billet précise que la plupart des opérations de pliage conservent la longueur UTF-8 ou la réduisent, mais que les caractères U+023A et U+023E peuvent chacun passer de deux à trois octets. L’algorithme réserve donc en une seule fois une capacité maximale équivalant approximativement à 1,5 fois la longueur de l’entrée, au lieu d’agrandir progressivement le tampon et de recopier les données.
Il déplace également les groupes d’octets inchangés à l’aide de copy_nonoverlapping, au lieu de les copier octet par octet. Certains textes non latins, comme le CJK, le Hangul, le Kana, l’arabe, l’hébreu et les symboles, conservent leur allocation d’origine lorsqu’ils ne contiennent pas de caractères nécessitant un pliage.
Traiter Unicode dans l’espace des octets
Unicode 16.0 contient 1484 opérations de pliage simples, mais GitHub a compressé sa table à 1776 octets en exploitant le regroupement des caractères pliables en pages de 64 points de code. Pour déterminer si un caractère nécessite un pliage, l’algorithme utilise une carte de bits ; si le bit correspondant n’est pas activé, le caractère est rejeté immédiatement sans décoder l’UTF-8 ni effectuer de recherche dans une table de hachage.
À l’intérieur des pages contenant des opérations de pliage, l’algorithme stocke des plages contiguës plutôt qu’une entrée distincte pour chaque point de code. Les plages sont décrites par un début, une fin, un pas et un écart, ce qui réduit environ 1484 opérations à 238 plages réparties sur 59 pages. Il utilise également une comparaison parallèle sur huit clés à la fois pour déterminer la plage appropriée.
Une fois la plage trouvée, les caractères pliés sont calculés en additionnant des octets au niveau de l’UTF-8 avec une constante propre à la plage, au lieu de décoder le caractère en point de code puis de l’encoder à nouveau. Cela permet de gérer les changements de longueur, comme la conversion de U+212A, le symbole du kelvin, de trois octets en la lettre k d’un seul octet, ou la conversion de U+023A en un caractère de trois octets.
Cette approche suppose que l’entrée est un UTF-8 valide et minimal, hypothèse garantie par les types String et str de Rust. Les données brutes provenant d’autres sources doivent, quant à elles, être validées ou normalisées avant l’utilisation de ces calculs.
Résultats et limites des mesures
Dans le cas courant de l’ASCII, la vitesse de la bibliothèque dépasse 45 gigaoctets par seconde, soit plus de 50 % de mieux que la fonction pas tout à fait équivalente str::to_lowercase, selon les mesures présentées dans le billet. Dans les pires cas d’entrée, où la plupart des caractères nécessitent un pliage, les solutions fondées sur des calculs dans l’espace des octets étaient environ deux fois plus rapides qu’un chemin optimisé de décodage et de réencodage de l’UTF-8.
GitHub souligne que les chiffres et les pourcentages de comparaison sont indicatifs et ne peuvent pas être transposés littéralement d’un processeur à l’autre, car ils dépendent de la vectorisation automatique, du SWAR, des calculs sur les octets en ordre little-endian, ainsi que de la bande passante mémoire et de l’architecture du processeur. Le billet résume l’idée en deux principes : balayer entièrement le chemin courant sans branches, et exécuter le chemin rare propre à Unicode dans l’espace des octets plutôt que de décoder les caractères et de les réencoder.