Wie kann Atoi mithilfe von SIMD-Anweisungen effizient implementiert werden?

Wie implementiert man Atoi mit SIMD?

Problem:
Ich würde gerne versuchen, ein Atoi zu schreiben Implementierung mithilfe von SIMD-Anweisungen, die in RapidJSON enthalten sein sollen. Der Algorithmus, den ich mir ausgedacht habe, lautet wie folgt:

1. Initialisieren Sie einen Vektor der Länge N auf folgende Weise:
   [10^N..10^1]
2. Konvertieren Wandeln Sie jedes Zeichen im Puffer in eine Ganzzahl um und platzieren Sie sie in einem anderen Vektor.
3. Nehmen Sie jede Zahl im Vektor mit signifikanten Ziffern und multiplizieren Sie sie mit der passenden Zahl im Zahlenvektor und Summierung der Ergebnisse.

Mein Algorithmus ist korrekt? Gibt es einen besseren Weg? Gibt es eine Referenzimplementierung für Atoi, die einen SIMD-Befehlssatz verwendet?

Antwort:
Der Algorithmus ist korrekt und vollständig. Es funktioniert für int und uint, von MIN_INT=-2147483648 bis MAX_INT=2147483647 und von MIN_UINT=0 bis MAX_UINT=4294967295.

Eine Referenzimplementierung wird bereitgestellt, geschrieben in GNU Assembler mit Intel-Syntax.

Die Eigenschaften dieses Codes sind wie folgt folgt:

• Ein führendes '-'-Zeichen gibt eine negative Zahl an (sofern sinnvoll), ein führendes ' '-Zeichen wird ignoriert
• Führende Nullen (mit oder ohne Vorzeichenzeichen) werden ignoriert
• Überlauf wird ignoriert – größere Zahlen werden einfach umbrochen
• Strings mit der Länge Null führen zum Wert 0 = -0
• Ungültige Zeichen werden erkannt und die Konvertierung endet beim ersten ungültigen Zeichen
• Mindestens 16 Bytes nach der letzten führenden Null müssen zugänglich sein und mögliche Sicherheitsauswirkungen des Lesens nach EOS bleiben bestehen der Aufrufer
• Es wird nur SSE4.2 benötigt

Der Ansatz des Algorithmus ist wie folgt folgt:

• Zeiger auf Zahlenzeichenfolge wird in ESI erwartet
• Überprüfen Sie, ob das erste Zeichen „-“ ist, und geben Sie dann an, ob eine negative Zahl in EDX vorliegt (A)
• Überprüfen Sie, ob führende Nullen und EOS (B) vorhanden sind.
• Überprüfen Sie die Zeichenfolge auf gültige Ziffern und Holen Sie sich strlen() gültiger Zeichen (C)
• Kehren Sie die Zeichenfolge um, sodass die Potenz von
  10^0 immer bei BYTE 15 liegt.
  10^1 ist immer bei BYTE 14
  10^2 ist immer bei BYTE 13
  10^3 ist immer bei BYTE 12
  10^4 ist immer bei BYTE 11
  ...
  und maskiert alle folgenden Zeichen (D)
• Subtrahieren Sie jeweils die gesättigte „0“. die 16 möglichen Zeichen (1)
• Nehmen Sie 16 aufeinanderfolgende Byte-Werte und teilen sie in WORDs
  in zwei XMM-Registern auf (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)
• Multiplizieren Sie jedes WORD mit seinem Stellenwert Modulo 10000 (1,10,100,1000)
  (Faktoren kleiner als MAX_WORD, 4 Faktoren pro QWORD/halbXMM)
  ( 2), sodass wir zweimal voreinander horizontal kombinieren können multiplizieren.
  Die PMADDWD-Anweisung kann dies und den nächsten Schritt tun:
• Horizontal benachbarte WORDs zu DWORDs hinzufügen (3)
  H1000 G100 F10 E1 | D1000 C100 B10 A1 (XMM0)
  P1000 O100 N10 M1 | L1000 K100 J10 I1 (XMM1)
• Horizontal benachbarte DWORDs von XMM0 und XMM1 zu XMM0 hinzufügen (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]
• Werte in XMM0 werden mit den Faktoren (5)
  P1000 O100 N10 M1 (DWORD-Faktor 1000000000000 = zu groß für DWORD, aber möglicherweise nützlich für QWORD-Zahlenzeichenfolgen)L
  1000 K100 J10 I1 (DWORD-Faktor 100000000)H
  1000 G100 F10 E1 (DWORD-Faktor 10000)D
  1000 C100 B10 A1 (DWORD-Faktor 1)
• Der letzte Schritt ist das Hinzufügen dieser vier DWORDs zusammen mit 2

  PHADDD emuliert durch 2(PSHUFD PADDD)

  xmm0[31-0] = xmm0[63-32] xmm0[31-0] (
  • 6 )xmm0[63-32] = xmm0[127-96] xmm0[95-64]
    (das obere QWORD enthält dasselbe und wird ignoriert)
    
  xmm0[31-0] = xmm0[63-32] xmm0[31-0 ] (
  • 7)
Wenn die Zahl negativ ist (in EDX angezeigt durch 000...0=pos oder 111...1=neg), negiere sie (
• 8)

Die Ergebnis der Intel-IACA-Durchsatzanalyse für Haswell 32-Bit:

Durchsatzanalyse Bericht

Blockdurchsatz: 16,10 Zyklen Durchsatzengpass: InterIteration

Portbindung in Zyklen pro Iteration:

| Hafen | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |

| Zyklen | 9,5 0,0 | 10,0 | 4,5 4,5 | 4,5 4,5 | 0,0 | 11.1 | 11,4 | 0,0 |

N – Portnummer oder Anzahl der Zyklen, die durch einen Ressourcenkonflikt verursacht wurden, DV – Divider Pipe (auf Port 0)
D – Datenabrufpipe (auf Port 2 und 3), CP – auf a Kritischer Pfad
F – Makrofusion mit der vorherigen Anweisung ist aufgetreten

• • Anweisung Micro-Ops sind nicht an einen Port gebunden
    ^ - Micro Fusion ist aufgetreten

    - ESP Tracking sync uop wurde ausgegeben

    @ - SSE-Anweisung folgte einer AVX256-Anweisung, Dutzende Zyklen Strafe werden erwartet
    ! - Anleitung nicht unterstützt, wurde in der Analyse nicht berücksichtigt

| Anzahl | Anschlussdruck in Zyklen | |

| Ups | 0 - DV | 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 |

Das obige ist der detaillierte Inhalt vonWie kann Atoi mithilfe von SIMD-Anweisungen effizient implementiert werden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!