Les caractères doivent être codés en bits d'une manière ou d'une autre. La plupart des chaînes sur Internet, y compris ce post sur Habré, sont encodées en UTF-8. Le format UTF-8 représente des «caractères» sur un, deux, trois ou quatre octets. Il s'agit d'une généralisation au standard ASCII, qui n'utilise qu'un octet par caractère. Autrement dit, la chaîne ASCII est également une chaîne UTF-8.
C'est en fait un peu plus compliqué, car techniquement, UTF-8 décrit les points de code. Un caractère visible comme un emoji peut être constitué de plusieurs points de code ... mais la plupart des programmeurs n'ont pas besoin de ces mots pédants.
Il existe également d'autres normes. Certains langages de programmation plus anciens comme C # et Java reposent sur UTF-16. Il utilise deux ou quatre octets par caractère. Cela semblait être une bonne idée à l'époque, mais maintenant, le consensus s'oriente vers l'utilisation de l'UTF-8 à tout moment, n'importe où.
La plupart des encodages ont des restrictions applicables. En d'autres termes, aucune séquence aléatoire de bits ne peut entrer dans UTF-8. Ainsi, vous devez valider les chaînes - vérifiez qu'il s'agit bien de UTF-8.
Qu'importe? Génial. Par exemple, le serveur Web de Microsoft présente une telle vulnérabilité: il accepte un URI qui semble valide et sûr, mais lorsqu'il est interprété par le serveur, il donne à l'attaquant un accès distant au disque. Même les problèmes de sécurité mis à part, vous ne voulez certainement pas stocker de lignes invalides dans votre base de données.
Ainsi, les langages de programmation, les serveurs Web, les navigateurs et les moteurs de bases de données valident en permanence l'UTF-8.
Si vos chaînes sont pour la plupart simplement ASCII, les vérifications sont assez rapides et la vérification UTF-8 n'est pas un problème. Il est révolu le temps où la plupart des chaînes étaient encodées en ASCII. Nous vivons dans un monde d'émojis et de nombreux alphabets nationaux.
En 2018, je me suis demandé:À quelle vitesse les chaînes UTF-8 peuvent-elles être validées ? A cette époque, j'ai trouvé une option de validation avec plusieurs cycles CPU par symbole. On pouvait se calmer là-dessus, mais cette réponse ne m'a pas satisfait.
Le travail a pris des années, mais il semble que nous ayons maintenant une version proche de l'idéal. Le nouvel algorithme est un ordre de grandeur plus rapide que les autres options de recherche rapide. Nous avons préparé un livre blanc: «UTF-8 Validation in Less than One Instruction Per Byte» (à paraître dans Software: Practice and Experience ) et également publié un utilitaire d'analyse comparative .
Tous les détails sont expliqués dans un article scientifique, nous n'entrerons donc pas dans les détails ici, mais ne considérerons que brièvement l'essence. La partie principale de la validation UTF-8 se fait en recherchant des paires d'octets consécutifs. Après avoir vérifié toutes les paires d'octets et identifié toutes les violations possibles qui peuvent être trouvées à partir de ces informations, il reste relativement peu à faire.
Tous les processeurs ont des instructions SIMD rapides. Ils fonctionnent avec des registres larges (128 bits, 256 bits, etc.). La plupart des ensembles ont une instruction de "recherche vectorisée" qui prend, par exemple, des valeurs de 16 octets (allant de 0 à 16) et les recherche dans une table de 16 octets. Dans les processeurs Intel et AMD, cette description correspond à l'instruction
pshufb... Une valeur comprise entre 0 et 16 est parfois appelée quartet et s'étend sur 4 bits. L'octet est composé de deux quartets (bas et haut).
Dans notre algorithme de recherche, l'instruction de recherche vectorisée est appelée trois fois: une fois pour le quartet faible, une fois pour le quartet élevé et une fois pour le quartet élevé pour l'octet suivant. Nous avons trois tables de recherche de 16 octets correspondantes. Si vous les choisissez correctement, le ET au niveau du bit des trois recherches détecte une erreur.
Voir l'article scientifique pour plus de détails , mais finalement, la validation UTF-8 presque complète se fait avec seulement cinq lignes de code C ++ rapide sans aucune branche ... et ces cinq lignes vérifient des blocs jusqu'à 32 octets à la fois ...
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}Bien que ce ne soit pas immédiatement évident, cette validation est suffisante et sûre à 100%. Ça l'est vraiment . Il ne reste que quelques étapes techniques supplémentaires peu coûteuses.
En conséquence, sur les processeurs Intel / AMD récents, il faut un peu moins d'une instruction par octet pour valider même l'entrée aléatoire la plus indésirable. Le code étant extrêmement optimisé, vous pouvez aller jusqu'à trois instructions par cycle, et même plus. Autrement dit, nous utilisons une petite partie du cycle (moins d'un tiers) par octet d'entrée sur un processeur moderne. Ainsi, la vitesse de traitement est maintenue de manière fiable à plus de 12 Go / s.
La leçon est que les tables de recherche régulières sont utiles, mais les tables vectorisées sont les blocs de construction fondamentaux pour les algorithmes à grande vitesse.
Si vous devez utiliser la fonction de validation UTF-8 rapide en production, nous vous recommandons la bibliothèque simdjson (version 0.5 ou supérieure). Il est bien testé et possède des fonctionnalités intégrées utiles telles que la distribution d'exécution. Bien que la bibliothèque soit conçue pour analyser JSON, vous pouvez l'utiliser uniquement pour la validation UTF-8, même s'il n'y a pas du tout de JSON. Il prend en charge les processeurs ARM 64 bits et x64, et dispose également d'un traitement de secours pour les autres processeurs. Nous l'avons emballé dans un fichier d'en-tête avec un fichier source; vous pouvez donc simplement le mettre dans votre projet C ++.
Précédent travail... Le principal mérite de vulgariser la méthode de classification vectorisée, qui est la clé de l'algorithme de recherche, appartient à Mula. Autant que je sache, Keizer a été le premier à proposer notre stratégie de triple recherche. Le premier algorithme de validation UTF-8 basé sur SIMD a été créé par K. Willets. Plusieurs personnes, dont Z. Wegner, y ont apporté des améliorations. Travis Downs a proposé des idées intelligentes sur la façon d'accélérer les algorithmes conventionnels.
Lectures complémentaires . Si vous aimez ce travail, vous aimerez peut-être d'autres articles sur des sujets connexes: «Encodage et décodage en base64 à une vitesse de copie presque en mémoire» (Software: Practice and Experience, 50 (2), 2020) et «Parsing JSON Gigabytes Per Second» ( Journal VLDB, 28 (6), 2019).