Présentation

GitHub a développé une méthode pour accélérer la mise en forme de code, en particulier la mise en minuscule, qui est essentielle pour les recherches de code et les comparaisons de chaînes de caractères. Cette optimisation a été réalisée en supprimant une optimisation existante, plutôt qu'en en ajoutant une nouvelle.

Contexte technique

La mise en forme de code est une opération de base, mais qui est exécutée à grande échelle par GitHub, qui indexe plus de 180 millions de référentiels, représentant plus de 480 To de code source. Chaque octet est mis en minuscule avant d'être indexé, et pour chaque résultat de recherche potentiel, une autre opération de mise en minuscule est nécessaire pour localiser les correspondances.

Fonctionnement de la mise en forme

La mise en forme de code n'est pas la même chose que la minuscule. La minuscule est utilisée pour l'affichage et est sensible au contexte et à la localisation, tandis que la mise en forme de code est utilisée pour la comparaison et est indépendante du contexte et de la localisation. La mise en forme de code est réalisée en utilisant la table de correspondance de cas fournie par la base de données de caractères Unicode.

let mut high_bit_acc: u8 = 0; 
   for b in &mut bytes { 
       high_bit_acc |= *b; // détecter tout octet non-ASCII 
       let is_upper = b.wrapping_sub(b'A') < 26; // test sans branchement pour A..=Z 
       *b |= u8::from(is_upper) << 5; // mettre à jour le bit 5 pour mettre en minuscule 
   } 
   if high_bit_acc & 0x80 == 0 { 
       return bytes; // pur ASCII : déjà mis en forme sur place, pas de deuxième tampon 
   }

Performances et optimisation

Les performances de la mise en forme de code ont été améliorées en supprimant les branches dans le code, ce qui permet une vectorisation plus efficace. Les résultats montrent que la suppression des branches permet d'atteindre une vitesse de traitement de plus de 45 Go/s, soit environ 15 fois plus rapide que la version originale. Les tests ont également montré que la fusion des deux passes de traitement, bien que tentante, est en réalité moins efficace que la méthode en deux passes.