Comment les instructions SIMD peuvent-elles être utilisées pour optimiser la fonction atoi ?

Comment implémenter atoi à l'aide de SIMD

Dans cet article, nous explorerons un algorithme pour implémenter la fonction atoi, qui convertit une représentation sous forme de chaîne d'un entier dans sa valeur numérique, à l'aide d'instructions SIMD (Single Instruction Multiple Data). En utilisant SIMD, nous pouvons potentiellement obtenir des améliorations significatives des performances en traitant plusieurs éléments en parallèle.

L'algorithme

L'algorithme proposé comprend les étapes suivantes :

1. Initialiser un vecteur de longueur N : Créer un vecteur de longueur N, où N est le nombre maximum de chiffres que vous souhaitez prendre en charge. Initialisez le vecteur avec des valeurs représentant les puissances de 10 par ordre décroissant (par exemple, [10^N, 10^(N-1), ..., 10^1]).
2. Convertissez chaque caractère dans le tampon en un entier : Convertissez chaque caractère de la chaîne d'entrée en sa valeur entière correspondante et stockez-la dans un autre vecteur.
3. Multipliez les chiffres significatifs par des puissances de 10 : Prenez chaque élément du vecteur de chiffres significatifs et multipliez-le par l'élément correspondant du vecteur des puissances de 10. Additionnez les résultats de ces multiplications pour obtenir la valeur numérique de la chaîne.

Plus précisément, pour chaque chiffre de l'entrée string :

• Extraire la valeur numérique (0 à 9) en soustrayant son code ASCII de 48.
• Multipliez la valeur numérique par la puissance correspondante de 10.
• Ajoutez le résultat à la somme des valeurs précédemment calculées.

Mise en œuvre Considérations

Lors de la mise en œuvre de cet algorithme dans le code SIMD, nous pouvons profiter du parallélisme inhérent aux instructions SIMD pour traiter plusieurs chiffres simultanément. Le code doit être optimisé pour le jeu d'instructions SIMD spécifique utilisé (par exemple, SSE4.2, AVX2).

Optimisation potentielle :

Il est possible d'optimiser davantage cet algorithme en éliminant le besoin d'une boucle séparée pour multiplier les chiffres significatifs par les puissances de 10. Ceci peut être réalisé en utilisant une technique appelée « indexation vectorielle avec fusion multiplier-ajouter." Cette technique nous permet d'effectuer à la fois l'indexation et la multiplication en une seule instruction, améliorant ainsi les performances.

Une suggestion alternative

Comme suggéré par Peter Cordes dans les commentaires, une alternative aux deux dernières instructions add xor consiste à utiliser une instruction imul (multiplication d'entiers). Cela a le potentiel d'être plus efficace en termes de taille de code et de performances.

Implémentation dans GNU Assembler avec Intel Syntax

Voici un exemple d'implémentation de l'algorithme dans GNU Assembler avec la syntaxe Intel :

.intel_syntax noprefix
.data
  .align 64
    ddqDigitRange: .byte  '0','9',0,0,0,0,0,0,0,0,0,0,0,0,0,0
    ddqShuffleMask:.byte  15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 
    ddqFactor1:    .word  1,10,100,1000, 1,10,100,1000  
    ddqFactor2:    .long  1,10000,100000000,0
.text    
_start:
   mov   esi, lpInputNumberString
   /* (**A**) indicate negative number in EDX */
   mov   eax, -1
   xor   ecx, ecx
   xor   edx, edx
   mov   bl,  byte ptr [esi]
   cmp   bl,  '-'
   cmove edx, eax
   cmp   bl,  '+'
   cmove ecx, eax
   sub   esi, edx
   sub   esi, ecx
   /* (**B**)remove leading zeros */
   xor   eax,eax               /* return value ZERO */
  remove_leading_zeros:
   inc   esi
   cmp   byte ptr [esi-1], '0'  /* skip leading zeros */
  je remove_leading_zeros
   cmp   byte ptr [esi-1], 0    /* catch empty string/number */
  je FINISH
   dec   esi
   /* check for valid digit-chars and invert from front to back */
   pxor      xmm2, xmm2         
   movdqa    xmm0, xmmword ptr [ddqDigitRange]
   movdqu    xmm1, xmmword ptr [esi]
   pcmpistri xmm0, xmm1, 0b00010100 /* (**C**) iim8=Unsigned bytes, Ranges, Negative Polarity(-), returns strlen() in ECX */
  jo FINISH             /* if first char is invalid return 0 - prevent processing empty string - 0 is still in EAX */
   mov al , '0'         /* value to subtract from chars */
   sub ecx, 16          /* len-16=negative to zero for shuffle mask */
   movd      xmm0, ecx
   pshufb    xmm0, xmm2 /* broadcast CL to all 16 BYTEs */
   paddb     xmm0, xmmword ptr [ddqShuffleMask] /* Generate permute mask for PSHUFB - all bytes < 0 have highest bit set means place gets zeroed */
   pshufb    xmm1, xmm0 /* (**D**) permute - now from highest to lowest BYTE are factors 10^0, 10^1, 10^2, ... */
   movd      xmm0, eax                         /* AL='0' from above */
   pshufb    xmm0, xmm2                        /* broadcast AL to XMM0 */
   psubusb   xmm1, xmm0                        /* (**1**) */
   movdqa    xmm0, xmm1
   punpcklbw xmm0, xmm2                        /* (**2**) */
   punpckhbw xmm1, xmm2
   pmaddwd   xmm0, xmmword ptr [ddqFactor1]    /* (**3**) */
   pmaddwd   xmm1, xmmword ptr [ddqFactor1]
   phaddd    xmm0, xmm1                        /* (**4**) */
   pmulld    xmm0, xmmword ptr [ddqFactor2]    /* (**5**) */
   pshufd    xmm1, xmm0, 0b11101110            /* (**6**) */
   paddd     xmm0, xmm1
   pshufd    xmm1, xmm0, 0b01010101            /* (**7**) */
   paddd     xmm0, xmm1
   movd      eax, xmm0
   /* negate if negative number */              
   add       eax, edx                          /* (**8**) */
   xor       eax, edx
  FINISH:
   /* EAX is return (u)int value */

Conclusion

Cette implémentation SIMD optimisée de la fonction atoi peut améliorer considérablement les performances lors du traitement de grandes quantités de données numériques. En utilisant les capacités de traitement parallèle des instructions SIMD, nous pouvons obtenir des temps d'exécution plus rapides et gérer les calculs numériques plus efficacement.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!