Ajouter à une liste de lecture
Continuons cette série sur les codes fantastiques avec la découverte d’une implémentation audacieuse de strlen.
Au XXIe siècle, quand on parle de code vectorisé, on veut souvent dire « code qui utilise un jeu d’instructions vectorielles », comme SSE ou AVX, afin d’exécuter plusieurs opérations en une seule instruction. Par exemple, en C, on peut charger dans des registres vectoriels les données issues de tableaux de flottants, puis en faire le produit, en utilisant l’intrinsèque :
Chaque registre vectoriel contenant 4 nombres flottants en format simple précision, on aura alors fait 4 opérations en 1 seule instruction. Et il existe une multitude de ces fonctions. Il y a néanmoins un inconvénient : il faut commencer par charger des données depuis la mémoire vers des registres vectoriels, et cela a un coût qu’il faut ensuite amortir en faisant plusieurs opérations vectorielles sur ces registres.
Dans le cas qui nous intéresse, strlen, on veut rechercher un zéro le plus rapidement possible. On pourrait utiliser une instruction SSE pour cela (p. ex. _mm_cmpeq_epi8 disponible depuis SSE2, ou la bien plus évoluée _mm_cmpistri depuis SSE4.2), mais cette fois, on ne va pas utiliser de registre vectoriel : on va plutôt considérer qu’un uint32_t, ou un mot, est une sorte de registre vectoriel contenant 4 octets. L’idée étant alors de parcourir les octets 4 par 4, c’est-à-dire un mot à la fois, ce qu’un processeur sait faire de manière efficace. La boucle principale de notre implémentation serait alors :
qui s’exécute 4 fois plus vite que la boucle naïve sur des octets, à condition d’avoir un test rapide pour has_zero. Et pour cela, on peut consulter la magnifique page de Sean Eron Anderson, Bit Twiddling Hacks, https://graphics.stanford.edu/~seander/bithacks.html, qui nous propose :
soit tout juste 4 opérations arithmétiques pour tester chaque octet du mot considéré. Notons au passage que cela s’étend facilement à des mots de 8 octets.
Une fois sorti de la boucle, il faudra tout de même trouver quel est l’octet positionné à zéro, il se trouve qu’un appel à __builtin_ctz (ctz = Count Trailing Zero) sur la sortie de haszero suffit.
Cette implémentation est plus difficile à maintenir que la version naïve, et on peut se demander si cela vaut vraiment la peine. Sur une fonction aussi usitée que strlen, les développeurs de la glibc ont tranché pour vous, la réponse est oui, c’est une de leurs implémentations qui a inspiré cet article, vous pouvez la retrouver sur https://sourceware.org/git/?p=glibc.git;a=blob;f=string/strlen.c. Et de manière plus générale, l’astuce consistant à utiliser des registres scalaires comme des registres vectoriels est amusante, et offre une belle occasion de se plonger dans les bit twiddling hacks !
