Comment implémenter efficacement atoi à l'aide des instructions SIMD ?

Comment implémenter atoi à l'aide de SIMD ?

Problème :
J'aimerais essayer d'écrire un atoi implémentation à l'aide d'instructions SIMD, à inclure dans RapidJSON. L'algorithme que j'ai proposé est le suivant :

1. Initialisez un vecteur de longueur N de la manière suivante :
   [10^N..10^1]
2. Convertir chaque caractère du tampon en un entier et placez-le dans un autre vecteur.
3. Prenez chaque nombre du vecteur de chiffres significatifs et multipliez-le par le nombre correspondant dans les nombres vectoriels et additionner les résultats.

Mon algorithme est correct ? Existe-t-il une meilleure façon ? Existe-t-il une implémentation de référence pour atoi utilisant un jeu d'instructions SIMD ?

Réponse :
L'algorithme est correct et complet. Il fonctionne pour int et uint, de MIN_INT=-2147483648 à MAX_INT=2147483647 et de MIN_UINT=0 à MAX_UINT=4294967295.

Une implémentation de référence est fournie, écrite en GNU Assembler avec la syntaxe Intel.

Les propriétés de ce code sont les suivantes suit :

• Un caractère '-' en tête indique un nombre négatif (comme raisonnable), un caractère ' ' en tête est ignoré
• Les zéros en tête (avec ou sans caractère de signe) sont ignorés
• Le débordement est ignoré - les nombres plus grands sont juste enroulés
• Les chaînes de longueur nulle donnent la valeur 0 = -0
• Les caractères invalides sont reconnus et la conversion se termine au premier caractère invalide
• Au moins 16 octets après le dernier zéro non significatif doivent être accessibles et les éventuelles implications de sécurité de la lecture après EOS sont laissées à l'appelant
• Seul SSE4.2 est nécessaire

L'approche de l'algorithme est la suivante suit :

• Un pointeur vers une chaîne numérique est attendu dans ESI
• Vérifiez si le premier caractère est '-', puis indiquez si un nombre négatif dans EDX (A)
• Vérifiez les zéros non significatifs et EOS (B)
• Vérifiez la chaîne pour les chiffres valides et obtenir strlen() de caractères valides (C)
• Chaîne inversée pour que la puissance de
  10^0 soit toujours à BYTE 15
  10^1 soit toujours à BYTE 14
  10^2 est toujours à BYTE 13
  10^3 est toujours à BYTE 12
  10^4 est toujours à BYTE 11
  ...
  et masquez tous les caractères suivants (D)
• Soustrayez le « 0 » saturé de chacun des les 16 caractères possibles (1)
• Prendre 16 consécutifs valeurs d'octets et les diviser en MOTS
  dans deux registres XMM (2)
  P O N M L K J I | H G F E D C B A ->
  H G F E | D C B A (XMM0)
  P O N M | L K J I (XMM1)
• Multipliez chaque MOT par sa valeur de position modulo 10000 (1,10,100,1000)
  (facteurs plus petits que MAX_WORD, 4 facteurs par QWORD/halfXMM)
  ( 2) pour pouvoir combiner horizontalement deux fois avant l'autre multiplier.
  L'instruction PMADDWD peut faire cela et l'étape suivante :
• Ajouter horizontalement des MOTS adjacents aux DWORDs (3)
  H1000 G100 F10 E1 | D1000 C100 B10 A1 (XMM0)
  P1000 O100 N10 M1 | L1000 K100 J10 I1 (XMM1)
• Ajouter horizontalement des DWORDs adjacents de XMM0 et XMM1 à XMM0 (4)
  xmmDst[31-0] = xmm0[63-32] xmm0[31-0]
  xmmDst[63-32] = xmm0[127-96] xmm0[95-64]
  xmmDst[95-64] = xmm1[63-32] xmm1[31-0]
  xmmDst[127-96] = xmm1[127-96] xmm1[95-64]
• Les valeurs dans XMM0 sont multipliées par les facteurs (5)
  P1000 O100 N10 M1 (facteur DWORD 1000000000000 = trop grand pour DWORD, mais peut-être utile pour les chaînes numériques QWORD)
  L1000 K100 J10 I1 (facteur DWORD 100000000)
  H 1000 G100 F10 E1 (facteur DWORD 10000)
  D1000 C100 B10 A1 (facteur DWORD 1)

• La dernière étape consiste à ajouter ces quatre DWORD avec 2PHADDD émulé par 2(PSHUFD PADDD)

  • xmm0[31-0] = xmm0[63-32] xmm0[31-0] (6 )
    xmm0[63-32] = xmm0[127-96] xmm0[95-64]
    (le QWORD supérieur contient le même et est ignoré)
  • xmm0[31-0] = xmm0[63-32] xmm0[31-0 ] (7)
• Si le le nombre est négatif (indiqué dans EDX par 000...0=pos ou 111...1=neg), annulez-le (8)

Le résultat de l'analyse du débit Intel-IACA pour Haswell 32 bits :

Analyse du débit Rapport

Débit de blocs : goulot d'étranglement du débit de cycles 16.10 : interitération

Liaison de port en cycles par itération :

| Port | 0 - VD | 1 | 2-D | 3-D | 4 | 5 | 6 | 7 |

| Cycles | 9,5 0,0 | 10,0 | 4,5 4,5 | 4,5 4,5 | 0,0 | 11.1 | 11.4 | 0.0 |

N - numéro de port ou nombre de cycles de conflits de ressources provoqués par un retard, DV - Tuyau de séparation (sur le port 0)
D - Tuyau de récupération de données (sur les ports 2 et 3), CP - sur un chemin critique
F - Macro Fusion avec l'instruction précédente s'est produite

• • instruction micro-ops non liés à un port
    ^ - Micro Fusion s'est produite

    - L'uop de synchronisation de suivi ESP a été émis

    @ - L'instruction SSE a suivi une instruction AVX256, une pénalité de dizaines de cycles est attendue
    ! - instruction non prise en charge, n'a pas été comptabilisée dans Analyse

| Nombre de | Pression des ports en cycles | |

| Oups | 0 - VD | 1 | 2-D | 3-D | 4 | 5 | 6 | 7 | |

| 0* | | | | | | | | | | xor eax, eax
| 0* | | | | | | | | | | xor ecx, ecx
| 0* | | | | | | | | | | xor edx, edx
| 1 | | 0,1 | | | | | 0,9 |

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!