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

• Sujet consacré à un algorithme de recherche de sous-chaînes compatible SIMD
• Présentation d’une approche technique pour une recherche de chaînes rapide
• Orientation vers une amélioration de l’efficacité par rapport aux méthodes existantes grâce au traitement parallèle
• Mis en avant comme un conseil de performance utile pour les développeurs et les professionnels de l’IT
• Cet algorithme est lié à l’optimisation pour le matériel moderne

---

Aperçu

• Ce document présente un algorithme de recherche de sous-chaînes optimisé pour le jeu d’instructions SIMD (Single Instruction, Multiple Data)
• Dans l’environnement IT actuel, où la vitesse de traitement des chaînes est devenue cruciale, il traite d’une méthode de traitement parallèle visant à compenser les limites des approches de recherche séquentielle traditionnelles
• En exploitant le SIMD, il devient possible de comparer plusieurs données simultanément en une seule opération, ce qui permet d’attendre des gains de performance significatifs pour la recherche dans de grands volumes de chaînes

Points clés

• L’algorithme SIMD divise la chaîne d’entrée en plusieurs parties, puis compare plusieurs octets à la fois avec la même instruction
• Cette méthode permet une recherche plus rapide et plus efficace que les comparaisons classiques basées sur des boucles
• Elle est particulièrement efficace dans des domaines exigeant un traitement rapide de grands volumes de données, comme la recherche textuelle, l’analyse de logs ou le séquençage ADN

Avantages pour les développeurs et les ingénieurs

• L’application d’un algorithme compatible SIMD permet, avec des modifications minimales du code, de maximiser le potentiel des CPU modernes
• Elle offre des avantages en termes de vitesse et d’efficacité par rapport aux logiques de recherche existantes
• Elle présente également une excellente scalabilité des performances dans les environnements multicœurs

Conclusion

• Dans les domaines où les performances de recherche de sous-chaînes sont cruciales, comme les services IT, l’analyse de données et les moteurs de recherche en temps réel, l’adoption d’un algorithme basé sur le SIMD peut se traduire par une amélioration concrète des performances
• Il s’agit d’une stratégie d’optimisation essentielle pour tirer parti des environnements matériels les plus récents

[GN⁺]

Commentaires Hacker News

• Explication selon laquelle l’accélération de ripgrep repose sur une approche AVX2 (générique) utilisant la crate Rust regex. L’accent est mis sur le fait que, même pour une expression régulière comme \w+\s+Sherlock\s+\w+, il est possible d’extraire Sherlock séparément pour effectuer une recherche rapide. L’implémentation réelle peut être consultée ici. Il est aussi mentionné que la principale différence avec l’algorithme de l’article est l’utilisation d’une heuristique qui optimise la recherche à l’aide de 2 octets moins fréquents dans la distribution de fond, plutôt que du premier/dernier octet de l’aiguille. Des benchmarks montrent des performances bien supérieures à une simple approche Two-Way ou au memmem de GNU libc. Il est également souligné que, dans le benchmark prebuilt, les routines de type memmem sont pénalisées par une limite d’API : elles doivent reconstruire leur état à chaque fois que l’aiguille fixe change

  • Remarque demandant comment connaître la distribution de fond des octets, en faisant valoir que scanner toute la haystack pour l’obtenir risquerait au contraire de nuire aux performances

• Partage d’une expérience d’implémentation de ce type d’algorithme de recherche de chaînes lors d’une tentative d’optimisation SIMD de la libc Wasm/WASI. Avis selon lequel, lorsque la longueur de la haystack est connue et que l’aiguille est suffisamment grande, il est utile de la combiner avec Quick Search, avec un code associé et un lien expliquant l’algorithme

• Mention qu’en C# aussi, SIMD est appliqué à IndexOf, avec plus de détails ici

• Présentation d’une expérience personnelle consistant à avoir soi-même implémenté divers algorithmes pour la recherche et le split de chaînes en utilisant une approche SMID. Le source conversion.cxx de tamgu est partagé. Il est précisé qu’un algorithme différent de celui mentionné dans l’article a été utilisé

  • Demande d’un bref résumé de cet algorithme personnel. En exemple, il est ajouté que le premier algorithme du texte original compare le premier et le dernier caractère, tandis que le second compare simultanément les 4 premiers caractères pour vérifier plusieurs positions candidates

  • Partage d’une expérience datant de quelques années, où une version modifiée pour la recherche de fenêtre LZ77 avait été envisagée à l’aide du SIMD générique de Zig. Plus de contexte ici

• Avis disant que cela fait penser au projet hparse, qui utilise des algorithmes SIMD pour un parsing HTTP rapide

• Mention que l’algorithme swar caste des données alignées sur 1 octet en blocs de 8 octets, ce qui provoque de l’UB (comportement indéfini). Il est également signalé que les chargements non alignés peuvent poser des problèmes de performance

  • Réponse indiquant que ce type de code a souvent été perçu comme un algorithme idéal ou du pseudocode écrit pour la lisibilité. Il est souligné que mempcy n’est pas utilisé et que les vérifications de limites sont inexactes. En supposant par exemple que la longueur de la haystack soit un multiple de 8, ou si l’aiguille est vide, un overflow d’entier non signé peut entraîner un accès out-of-bounds ; il y a donc au total trois cas d’UB. Expérience partagée selon laquelle, dans les démos SIMD, on montre souvent surtout des usages intéressants des vecteurs en omettant les conditions aux limites

• Le fait que strstr de libc soit lent est déjà connu, mais il est souligné que musl est rapide et repose sur un algorithme moderne. Il ne resterait plus qu’à lui donner un nom pour l’ajouter à smart shootout. Curiosité exprimée quant à sa comparaison avec les meilleurs algorithmes SIMD

  • Présentation, comme benchmark de référence, d’un comparatif entre le Two-Way de musl et un algorithme libc optimisé SIMD partagé par l’intervenant. La méthode de benchmark repose sur ce code. Les améliorations liées à l’usage de SIMD peuvent être consultées dans ce tableau. L’auteur estime honnêtement qu’il ne s’agit pas de quelque chose d’exceptionnel, mais d’une amélioration tout à fait correcte. Il mentionne que musl est spécialisé pour les chaînes à longueur fixe (memmem), tandis que, dans un environnement Wasm, il a pu tenter librement diverses optimisations pour les chaînes de longueur inconnue (strstr). Les chaînes terminées par NUL compliquent l’emploi de nombreux bons algorithmes

  • Souhait que smart inclue davantage d’algorithmes SIMD, avec l’envie personnelle de faire des tests si le temps le permet

• Question demandant si la version 2018 ne manque pas dans la comparaison SIMD des recherches de chaînes

• Question sur la taille de chaîne à partir de laquelle l’approche SIMD devient réellement efficace. Il est rappelé que, pour les petites chaînes, le surcoût d’initialisation de SIMD (alignement, calcul de longueur, etc.) peut au contraire la rendre plus lente qu’une simple recherche au niveau des octets. Il est aussi précisé que cela peut varier fortement selon l’architecture matérielle

  • Réponse indiquant que, d’après l’expérience de l’intervenant, c’est plutôt l’inverse. Ces algorithmes fonctionnent presque en brute force, avec très peu de configuration superflue, mais leur complexité temporelle se dégrade pour des aiguilles longues et répétitives. À l’inverse, les algorithmes avancés de recherche de chaînes qui évitent les problèmes quadratiques ou permettent une exécution sublinéaire exigent une phase d’initialisation coûteuse, car ils doivent analyser plus profondément la structure de l’aiguille

• Souhait de pouvoir utiliser SIMD directement depuis Python, sans appeler un autre langage

  • Mention du blog d’Austin et d’un recueil de billets (story on vowels detection lien), puis question plus précise sur ce que signifie exactement « utiliser SIMD directement sans appeler un autre langage ». Il est ajouté sur le ton de la plaisanterie que l’assembleur est lui aussi, d’une certaine manière, « un autre langage ». Il est ensuite expliqué que l’écosystème Python autour de SIMD couvre un spectre très large : PeachPy (écriture d’assembleur x86 en Python), Mojo (nouveau langage de style Python), ou encore des bibliothèques SIMD à couche de binding CPython très fine. Il est demandé quel type d’approche est recherché exactement et, si la cible est l’ASCII, la fonction find_first_of de StringZilla (code) est également recommandée

  • Questionnement sur l’intérêt de vouloir absolument le faire directement en Python. Si le problème vient d’une limite de performance, il est conseillé que changer simplement de langage peut déjà apporter un gain de 20 à 50× ou davantage