4.1 Accélérer le traitement des chaines UTF8 avec les instructions « intrinsics » d’Intel (fr)

Accélérer le traitement des chaines UTF8 avec les instructions « intrinsics » d’Intel

English Version

J’ai découvert le pouvoir des instructions « intrinsics » lors de la lecture d’un blog de Daniel Lemire (https://lemire.me/blog/2018/05/16/validating-utf-8-strings-using-as-little-as-0-7-cycles-per-byte/).

L’idée de base est d’utiliser une fenêtre glissante de 16 octets une la chaine de caractères et de projeter ces blocs de 16 caractères sur un entier de 128 bits (16×8). On peut alors détecter en une seule opération si l’un des octets a une valeur supérieure à 127. Rappelons que tout octet contenant une valeur supérieure à 127 a son bit le plus à gauche à 1. De cette façon, on peut détecter si une chaine contient ou non potentiellement des caractères UTF8.

Premier caractère UTF8

Après expérimentations, j’ai finalement intégré une variation de cette méthode dans Tamgu pour les manipulation de chaines UTF8.

static const __m128i checkutf8byte = _mm_set1_epi8(0x80);

bool checkAscii(unsigned char* src, long len, long& firstbloc) {
    __m128i current_bytes = _mm_setzero_si128();
    
    firstbloc = 0;
    for (; (firstbloc + 15) < len; firstbloc += 16) {
       current_bytes = _mm_loadu_si128((const __m128i *)(src + firstbloc));
        if (!_mm_testz_si128(checkutf8byte, current_bytes))
            return false;
    }

…

La chaine est découpée en bloc de 16 caractères et on vérifie pour chaque bloc la présence d’au moins un bit à l’extrême gauche. Cependant, et c’est là une différence avec l’exemple de Daniel Lemire, nous conservons chaque fois la position du premier caractère du dernier bloc analysé. Cela permet d’isoler rapidement la section en UTF8. Dans la majorité des cas, pour des langues comme l’anglais ou le français, cette détection est souvent fructueuse en terme de temps de conversion ou d’accès à des sous-chaines. Pour les autres langues, la méthode checkAscii échoue dès le premier test ce qui peut ralentir légèrement le fonctionnement normal du système.

Recherche d’une sous-chaine

Nous avons étendu ce principe aussi à la recherche d’une sous-chaine. Ici, l’idée revient à détecter dans la chaine principale l’endroit où se trouve le premier caractère de la sous-chaine à rechercher.

static const __m128i checkifzero = _mm_set1_epi8(0xFF);

long find_intel_byte(unsigned char* src, unsigned char* search, long lensrc, long lensearch, long i) {
   uchar c = search[0];
    __m128i firstchar = _mm_set1_epi8(c);
    __m128i current_bytes = _mm_setzero_si128();
    
    uchar* s=src;
    long j;
    
   for (; (i + 15) < lensrc; i += 16) {
        s=src+i;
        current_bytes = _mm_loadu_si128((const __m128i *)s);

       current_bytes = _mm_cmpeq_epi8(firstchar, current_bytes);
       q = _mm256_movemask_epi8(current_bytes);
       if (q) {
	  q = _bit_scan_forward(q);
          return (i+q);
       }

…

Le principe est proche de celui de « checkAscii ». On construit un masque « firstchar » comprenant 16 fois le premier caractère de la sous-chaine « search » et on vérifie si l’on a une intersection non nulle avec une fenêtre glissante de 16 caractères sur la chaine principale. Il suffit dès lors de retrouver la position dans le bloc de ce premier caractère et de comparer avec la sous-chaine. Il faut noter que ce caractère peut être présent plus d’une fois dans le bloc, d’où la boucle.

Des test empiriques montrent que cette méthode est souvent deux à trois fois plus rapides qu’un « std::string::find » dont il faut avouer qu’il n’est pas un modèle d’efficacité. En particulier, la détection qu’une chaine n’est pas présente est remarquablement efficace.