Algorithme de recherche de sous-chaîne adapté au SIMD (2018)

• Des API comme strstr ou std::string::find partent du principe d’une recherche ponctuelle de sous-chaîne, mais sur les CPU modernes le coût des comparaisons de chaînes courtes et de vecteurs est faible, ce qui peut rendre une approche SIMD plus avantageuse
• L’idée centrale consiste à remplacer la condition de hachage faible de Karp-Rabin par un prédicat vectoriel, puis à n’effectuer une comparaison exacte de sous-chaîne qu’aux positions candidates
• L’algorithme SIMD générique réduit les candidats en comparant en parallèle le premier caractère et le dernier caractère du motif, puis ne vérifie avec memcmp que les positions susceptibles de correspondre
• Les approches SSE4.1 MPSADBW et SSE4.2 PCMPESTRM sont aussi comparées, mais les mesures montrent que le SIMD générique est plus rapidement performant et stable, et que PCMPESTRM tend même à être plus lent que MPSADBW
• Le SIMD générique était plus rapide que le strstr en C sur toutes les plateformes, mais il n’est pas sûr, car il peut lire au-delà de la chaîne d’entrée, et les conditions de comparaison ne sont pas totalement identiques puisqu’il reçoit aussi les longueurs en entrée

---

Hypothèses de coût désormais dépassées pour la recherche de chaînes

• Des API comme strstr en C, std::string::find en C++, ou pos et index sur les chaînes Python sont conçues pour une recherche unique d’une sous-chaîne dans une chaîne donnée
• Les algorithmes classiques se répartissent grosso modo en deux familles
  • les approches basées sur des automates finis déterministes, comme Knuth-Morris-Pratt ou Boyer-Moore
  • les approches à comparaison simple, comme Karp-Rabin
• Les algorithmes standard supposent qu’une comparaison d’une paire de caractères, une consultation de table auxiliaire et un branchement conditionnel coûtent peu, alors qu’une comparaison entre deux sous-chaînes est coûteuse
• Sur les CPU de bureau modernes, cette hypothèse peut ne plus tenir
  • sur un CPU 64 bits, comparer 1, 2, 4 ou 8 octets coûte le même prix
  • avec des instructions SIMD, comparer des vecteurs de 16, 32 ou 64 octets peut coûter aussi peu qu’une comparaison d’un seul octet
  • une consultation de table implique un accès mémoire du niveau d’un aller-retour au cache L1, et la lecture caractère par caractère a un coût comparable
  • une mauvaise prédiction de branchement peut entraîner une pénalité d’environ 10 à 20 cycles
  • une courte chaîne de dépendances lecture de caractère → comparaison → branchement conditionnel rend plus difficile l’exploitation de l’exécution out-of-order par le CPU

Approche : utiliser un prédicat vectoriel au lieu d’un hachage faible

• Karp-Rabin n’effectue une comparaison exacte que lorsque le hachage faible de la sous-chaîne recherchée est égal à celui de la fenêtre courante
• L’approche SIMD remplace cette condition de hachage par un prédicat vectoriel
  • le prédicat est calculé en parallèle
  • une comparaison exacte de la sous-chaîne n’est effectuée qu’aux positions où le vecteur de prédicat est vrai
• La spécialisation par longueur sert aussi à améliorer les performances
  • une implémentation générale appelle une fonction comme memcmp pour la comparaison de sous-chaînes
  • si la longueur du motif à rechercher est connue, cet appel peut être remplacé par quelques instructions CPU spécifiques à cette longueur, voire parfois une seule instruction
  • cela réduit le coût de l’appel de fonction et le coût interne de memcmp

Algorithme 1 : SIMD générique

• L’algorithme SIMD générique s’applique à la plupart des jeux d’instructions SIMD ainsi qu’à l’approche SWAR
• Le prédicat de base consiste à vérifier si le premier caractère et le dernier caractère du motif correspondent tous deux
  • on remplit le registre F avec le premier caractère
  • on remplit le registre L avec le dernier caractère
  • à chaque itération, on lit le bloc A du haystack à l’offset courant i, puis le bloc B à i + k - 1
  • on calcule F == A et B == L, puis on combine les deux résultats pour produire un masque de positions candidates
  • une comparaison exacte de la sous-chaîne n’est effectuée qu’aux positions où ce masque est vrai
• Dans l’exemple de recherche de "cat" dans "a_cat_tries", l’indice 2 est la seule position où le premier caractère c et le dernier t correspondent, donc une seule comparaison exacte est nécessaire
• Choisir systématiquement le premier et le dernier caractère n’est pas toujours optimal
  • si l’entrée est surtout composée de 'A' et que le motif est "AjohndoeA", cela peut produire beaucoup de candidats
  • l’implémentation peut choisir, au lieu du dernier caractère, le caractère le plus éloigné qui diffère du premier
  • si tous les caractères du motif sont identiques, une procédure spéciale peut être utilisée pour des motifs comme "AAAAA"

Différences selon les implémentations

• Les implémentations SSE et AVX2 ont presque la même structure et utilisent le nombre minimal d’instructions
  • comme on sait déjà que le premier et le dernier caractère correspondent, memcmp n’a pas besoin de les comparer de nouveau
• L’approche SWAR exploite le fait qu’un résultat XOR nul signifie que les octets sont égaux
  • au lieu d’un AND des résultats partiels comme en SSE/AVX2, elle utilise un OR
  • la détection des positions contenant un octet nul demande davantage de travail
  • l’implémentation C++ pour vecteurs 64 bits calcule un masque d’octets exact
• AVX512F ne dispose pas d’opérations sur octets et son plus petit élément vectoriel est le mot 32 bits, d’où le recours à une technique SWAR
  • deux XOR et un OR sont calculés avec des instructions AVX512F
  • on repère les éléments 32 bits qui contiennent un octet nul
  • pour chaque élément 32 bits correspondant, on vérifie 4 sous-chaînes candidates
• L’implémentation ARM Neon 32 bits utilise des registres SIMD 128 bits
  • le long aller-retour entre l’unité Neon et le CPU constitue un goulot d’étranglement
  • les résultats de comparaison sont écrits en mémoire sous forme de mots 64 bits pour être traités
  • dérouler les 2 boucles internes donne un gain d’environ 1,2×
• L’implémentation AArch64 est presque identique à la procédure ARM Neon, mais la lecture directe des lanes des registres SIMD y est rapide

Algorithme 2 : SSE4.1 MPSADBW

• En SSE4.1 et AVX2, MPSADBW calcule la distance de Manhattan entre un sous-vecteur de 4 octets d’un registre et 8 sous-vecteurs consécutifs de 4 octets d’un autre registre
• Si deux sous-vecteurs sont identiques, leur distance L1 est nulle, ce qui permet de s’en servir pour repérer des positions candidates
  • cette approche utilise comme prédicat l’égalité des 4 premiers caractères
• Comparer les 4 premiers caractères semble plus fort qu’une comparaison premier/dernier caractère, mais cela n’évite pas la complexité quadratique dans le pire cas
  • si le haystack est rempli de "a" et que le motif est "aaaabcde", le prédicat sera vrai pour tous les caractères de l’entrée
• L’approche MPSADBW a plusieurs contraintes
  • elle ne convient pas naturellement aux sous-chaînes de longueur inférieure à 4
  • un traitement pour la longueur 3 est possible, mais demande du code supplémentaire
  • en SSE, MPSADBW ne traite que 8 octets à la fois
  • en AVX2, MPSADBW fonctionne par lanes 128 bits et non sur tout le vecteur 256 bits, ce qui impose du code de chargement supplémentaire
  • la latence de l’instruction est élevée, de 5 à 7 cycles selon le CPU, mais son throughput est de 1 à 2 cycles, ce qui permet de masquer la latence en déroulant la boucle
• AVX512F n’inclut pas MPSADBW, mais comme il gère nativement les éléments 32 bits, il est possible d’émuler un prédicat d’égalité sur un préfixe de 4 octets
  • à chaque itération, on construit 4 vecteurs AVX512 contenant les préfixes possibles de 4 octets
  • chaque construction de vecteur nécessite 2 décalages et 1 OR
  • la boucle de comparaison devient plus complexe, et il faut lire 4 octets au-delà du vecteur pour remplir le dernier élément

Algorithme 3 : SSE4.2 PCMPESTRM

• SSE4.2 a introduit l’ensemble d’instructions STNI avec l’objectif de fournir des briques de base pour les opérations sur chaînes
• Intel a ensuite pratiquement abandonné STNI dans les processeurs ultérieurs, n’en a pas proposé de version AVX2, et ces instructions sont très lentes
  • une latence de 11 cycles est jugée difficilement acceptable
• Les instructions PCMPxSTRx existent en quatre variantes selon le mode de détermination de la longueur et le format du résultat
  • la longueur peut être fournie explicitement, ou bien la première valeur nulle peut être traitée comme fin de chaîne à la manière des chaînes C traditionnelles
  • le résultat peut être stocké sous forme de masque de bits ou d’octets, ou comme numéro du premier/dernier bit activé du masque
• Ici, le mode de comparaison utilisé est range ordered
  • malgré son nom, il recherche le préfixe même si la sous-chaîne dépasse la largeur du registre ou dépasse la fin
  • dans l’exemple où l’on cherche "ABCD" dans "ABCD_ABC_ABCD_AB", le suffixe "AB" peut lui aussi être considéré comme une correspondance
  • on ne peut donc supposer en toute sécurité que l’égalité du premier caractère, et il faut vérifier le reste avec memcmp

Environnement de mesure des performances

• Les performances de plusieurs implémentations SIMD ont été mesurées, y compris avec spécialisation à l’exécution pour les sous-chaînes courtes
• Le strstr en C est inclus comme point de comparaison, mais il est absent du tableau x64 à cause d’un bug de performance de std::string::find dans GNU libc
• Chaque programme de test est exécuté trois fois
• Environnement de test x64
  • Westmere i5 M540, GCC 6.2.0
  • Bulldozer FX-8150, GCC 4.8.4
  • Haswell i7 4470, GCC 5.4.1
  • Skylake i7 6700, GCC 5.4.1
  • Knights Landing 7210, GCC 5.3.0
• Environnement de test ARM
  • ARMv7 Raspberry Pi 3, code 32 bits, GCC 4.9.2
  • ARMv8 ARM Cortex A57 / AMD Opteron A1100, code 64 bits, Clang 3.8.0

Résultats x64

• L’implémentation SIMD générique montre les gains les plus importants face à strstr sur x64
  • sur Westmere, SSE2 generic atteint 0,74589 s, contre 0,82246 s pour strstr
  • sur Haswell, AVX2 generic atteint 0,38653 s, contre 0,52786 s pour strstr
  • sur Skylake, AVX2 generic atteint 0,36309 s, contre 0,66148 s pour strstr
  • sur KNL, AVX512F generic atteint 1,14057 s, contre 4,94606 s pour strstr
• Le gain maximal atteint 1,10× sur Westmere, 1,37× sur Haswell, 1,82× sur Skylake et 4,33× sur KNL
• Les performances de strstr sur Bulldozer, à 9,37792 s, sont trop mauvaises pour en faire une référence crédible
• L’approche MPSADBW donne globalement de mauvais résultats, sauf sur Skylake, et elle est particulièrement mauvaise sur KNL
• L’approche PCMPESTRM est encore plus lente que MPSADBW

Résultats ARM

• Sur ARMv7, std::strstr prend 7,30405 s et std::string::find 4,17131 s
• Sur ARMv7, ARM Neon 32 bits generic atteint 1,29861 s, soit jusqu’à 3,1× plus rapide que std::string::find
• Sur ARMv8, std::strstr prend 3,37546 s et std::string::find 1,81368 s
• Sur ARMv8, AArch64 64 bits generic atteint 0,27897 s, soit jusqu’à 6,5× plus rapide que std::string::find
• Sur ARMv8, SWAR 64 bits generic atteint 0,46269 s, avec des performances proches de la procédure SIMD 32 bits

Conclusion et limites

• L’algorithme SIMD générique est plus rapide que strstr en C sur toutes les plateformes
• Il est préférable que l’implémentation sélectionne la version SIMD la plus élevée disponible sur le CPU visé
• MPSADBW, à l’exception du cas Skylake, offre de mauvaises performances, et est très mauvais sur Knights Landing
• PCMPESTRM est moins performant que MPSADBW
• Les performances d’ARM Neon sont bonnes, y compris avec l’implémentation SWAR
  • la version SWAR est 1,7× plus rapide que string::find
  • la version SIMD est 3,1× plus rapide que string::find
• La comparaison avec strstr n’est pas totalement équitable
  • strstr traite des chaînes dont la longueur n’est pas connue
  • ces implémentations reçoivent la longueur en argument et l’exploitent
• L’implémentation n’est pas sûre
  • elle peut lire des données au-delà de la chaîne d’entrée
  • si la chaîne se trouve juste avant une zone mémoire non mappée, cela peut provoquer une violation d’accès
  • AddressSanitizer peut aussi signaler le problème
  • il serait possible de rendre cela sûr, mais ce n’était pas l’objectif
• Toutes les implémentations et tous les programmes de test sont disponibles sur GitHub