Comment les instructions SIMD peuvent-elles être utilisées pour implémenter une fonction atoi hautes performances ?

Implémentation SIMD de la fonction atoi

Introduction :

atoi est une fonction qui convertit une représentation sous forme de chaîne d'un entier par rapport à sa valeur numérique. Cet article explore comment implémenter atoi à l'aide des instructions SIMD.

Algorithme :

1. Initialiser un vecteur V avec les valeurs 10^0, 10^1, .. ., 10^N.
2. Convertissez chaque caractère de la chaîne d'entrée en un entier et stockez-le dans un vecteur S.
3. Multipliez chaque élément de S par l'élément correspondant de V et stockez les résultats dans un nouveau vecteur P.
4. Effectuez une série d'additions et de multiplications horizontales sur P pour obtenir le résultat final .

Implémentation dans GNU Assembleur :

.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             /* if first char is invalid return 0 - prevent processing empty string - 0 is still in EAX */
   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 */

Avantages de la mise en œuvre de SIMD :

• Performances accrues pour le traitement de grandes chaînes de nombres.
• Réalisable pour les architectures x86 et x86-64.
• Prend en charge plusieurs opérations atoi simultanées.

Limitations :

• Nécessite des instructions SSE4.2 spécifiques.
• Peut ne pas convenir aux petites chaînes ou des cordes avec des mélanges caractères.

Conclusion :

L'implémentation SIMD d'atoi offre une accélération significative pour le traitement des grandes chaînes entières par rapport aux méthodes traditionnelles. L'algorithme est optimisé pour les architectures x86 et x86-64 et peut effectuer plusieurs opérations atoi en parallèle. Bien qu'elle présente des limites dans la gestion des chaînes de caractères petites et mixtes, elle reste une technique précieuse pour les calculs numériques.

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!