-
Notifications
You must be signed in to change notification settings - Fork 13
4.4 Remplacement rapide dans une chaine(fr)
Lorsque l'on cherche un morceau de code pour remplacer toutes les sous-chaînes d'une chaîne de caractères, on trouve souvent l'algorithme suivant :
//Le "sub" dans "s" est remplacé par "rep".
string s_replacestring(string& s, string& sub, string& rep) {
long subsz = sub.size() ;
long strsz = s.size() ;
long from = 0 ;
long foundHere ;
while ((foundHere = s.find(sub, from)) != string::npos) {
if (foundHere != from)
neo += s.substr(from, foundHere - from) ;
neo += rep ;
from = foundHere + subsz ;
}
if (from < rsz)
neo += s.substr(from, strsz - from) ;
return neo ;
}
Grosso modo, il s'agit de détecter dans une chaîne toutes les occurrences de "sub" afin de construire une nouvelle chaîne où "sub" est remplacé par "rep".
Cela fonctionne très bien mais ce n'est pas très rapide. Le "find", surtout du type "std::string", est loin d'être optimal.
Il existe un autre moyen d'accélérer ce morceau de code... Les instructions AVX. Rappelons que ces instructions permettent de manipuler des registres de 128 bits en un seul cycle. Il existe des versions plus récentes comme AVX2, qui permet de manipuler des registres de 256 bits. AVX512, la dernière version, permet même d'utiliser des registres de 512 bits.....
Un caractère est codé sur 8 bits, ce qui fait : 32 caractères par bloc de 256 bits (8x32= 256).
L'idée ici est de parcourir notre chaîne de caractères par blocs de 32 caractères à la fois pour déterminer si notre "sub" est présent en une seule opération.
Bien sûr, ce n'est pas nécessairement le cas le plus fréquent (quoique), mais il servira de base pour le reste de nos améliorations...
L'algorithme est en fait très simple. Nous lisons notre chaîne par bloc de 32 caractères que nous transformons à chaque fois en un nombre de 256 bits. Ensuite, nous vérifions en un seul cycle si le caractère que nous recherchons est présent dans ce bloc de 32 caractères. S'il n'est pas présent, 32 autres caractères sont lus. S'il est présent, le remplacement est effectué.
// " c " est le caractère que nous recherchons dans " src ".
char c = src[0] ;
//Un nombre de 256 bits est construit, chaque octet est égal à "c".
__m256i firstchar = _mm256_set1_epi8(c) ;
//Nous balayons ensuite notre chaîne par bloc de 32 caractères
for ( ; (i + 31) < lensrc ; i += 32) {
//"s" pointe vers le bloc actuel
s=USTR(src)+i ;
//Nous transformons ensuite ces 32 octets en un nombre de 256 bits
__m256i octets_courants = _mm256_loadu_si256((const __m256i *)s) ;
//Nous vérifions si "octets_courants" contient un "c" quelque part.
octets_courants = _mm256_cmpeq_epi8(firstchar, octets_courants) ;
//Si l'octet courant est différent de 0, cela signifie que le "c" est présent quelque part.
if (_mm256_movemask_epi8(octets_courants)) {
q = _mm256_movemask_epi8(octets_courants) ;
if (q) {
//Le dernier bit de droite renvoie la position où se produit cette première correspondance
j = _bit_scan_forward(q) ;
for ( ; j < 32 ; j++) {
si (*s == c) {
foundHere = i + j ;
si (from != foundHere)
neo += src.substr(from,foundHere-from) ;
neo += replace ;
from = foundHere+lensearch ;
}
++s ;
}
}
}
Comme on peut le voir sur ce bout de code, l'algorithme n'est pas très compliqué et est finalement très similaire à celui que nous avons présenté plus haut. En revanche, le système élimine très rapidement des sections entières de la chaîne dont il sait à l'avance qu'elles ne contiendront pas le caractère souhaité.
En fait, il est possible d'étendre cette méthode à deux ou même quatre caractères. Dans ce cas, la contrainte sera beaucoup plus forte pour détecter les endroits où la sous-chaîne est potentiellement présente, ce qui nous permettra d'éliminer encore plus rapidement les candidats au changement.
Pour deux caractères, nous les combinons simplement en un entier de 16 bits....
int16_t cc = search[1] ;
cc <<== 8 ;
cc |= search[0] ;
// LE TRUC, nous créons notre FILTRE sur un bloc de 16 bits....
__m256i firstchar = _mm256_set1_epi16(cc) ;
...Ensuite, pour la comparaison, nous utilisons "_mm256_cmpeq_epi16" au lieu de "_mm256_cmpeq_epi8", afin d'effectuer une comparaison bloc 16 bits au lieu de 8.
Il est encore possible d'imposer d'autres contraintes. Trouver une séquence de 4 caractères est encore plus spécifique qu'une séquence de deux. Nous utilisons alors un entier de 32 bits....
int32_t cc = search[3] ;
for (shift = 2 ; shift >= 0 ; shift--) {
cc <<== 8 ;
cc |= search[shift] ;
}
// LE TRUC, nous créons notre FILTRE sur un bloc 32 bits....
__m256i firstchar = _mm256_set1_epi32(cc) ;
...
La comparaison est alors effectuée avec "_mm256_cmpeq_epi32" au lieu de "_mm256_cmpeq_epi16".
Sauf que si vous essayez de faire une comparaison bit à bit, les séquences doivent être parfaitement alignées pour que cela fonctionne.
Par conséquent, un simple test n'est plus suffisant. Pour 2 caractères, 2 tests sont nécessaires et pour 4 caractères, 4 tests sont nécessaires, avec à chaque fois un "décalage d'un caractère à droite".....
for ( ; (i + 31) < lensrc ; i += 32) {
shift = 0 ;
//On va tester 4 fois, avec à chaque fois un décalage de 1 vers la gauche
for (shift = 0 ; shift < 4 ; shift ++) {
//Notre décalage
s=USTR(src) + i + shift ;
// Lecture de 32 caractères à la fois
current_bytes = _mm256_loadu_si256((const __m256i *)s) ;
// Nous vérifions si notre séquence de 4 caractères apparaît dans ce segment.
octets_courants = _mm256_cmpeq_epi32(firstchar, octets_courants) ;
//Si oui, nous nous arrêtons
q = _mm256_movemask_epi8(octets_courants) ;
si (q)
pause ;
}
if (shift != 4) {
//Et nous faisons notre boucle, jusqu'à 28... (28+4 == 32)
//Pour deux caractères, nous bouclons jusqu'à 30...
j = _bit_scan_forward(q) ; //Nous cherchons le premier emplacement de correspondance
for ( ; j < 29 ; j++) {
if (*s == c) {
if (charcomp(s,USTR(search),lensearch)) {
//Nous prenons en compte le "shift" (décalage)
foundHere = i + j + shift ;
if (from != foundHere)
neo += src.substr(from,foundHere-from) ;
neo += replace ;
from = foundHere+lensearch ;
}
}
++s ;
}
}
}
Notez que ce code n'est efficace que si la chaîne dans laquelle les remplacements sont effectués est grande. Mais dans ce cas, cette méthode peut être deux à trois fois plus rapide qu'une méthode classique.
Ce code fait partie de Tamgu et est implémenté dans "https://github.com/naver/tamgu/blob/master/src/conversion.cxx".