Wie können SIMD-Anweisungen zur Optimierung der Atoi-Funktion verwendet werden?

So implementieren Sie atoi mit SIMD

In diesem Artikel untersuchen wir einen Algorithmus zur Implementierung der atoi-Funktion, die eine String-Darstellung konvertiert Umwandlung einer Ganzzahl in ihren numerischen Wert mithilfe von SIMD-Anweisungen (Single Instruction Multiple Data). Durch die Verwendung von SIMD können wir möglicherweise erhebliche Leistungsverbesserungen erzielen, indem wir mehrere Elemente parallel verarbeiten.

Der Algorithmus

Der vorgeschlagene Algorithmus besteht aus den folgenden Schritten:

1. Initialisieren Sie einen Vektor der Länge N: Erstellen Sie einen Vektor der Länge N, wobei N die maximale Anzahl von ist Ziffern, die Sie unterstützen möchten. Initialisieren Sie den Vektor mit Werten, die die Potenzen von 10 in absteigender Reihenfolge darstellen (z. B. [10^N, 10^(N-1), ..., 10^1]).
2. Konvertieren Sie jeden Zeichen im Puffer in eine Ganzzahl: Konvertieren Sie jedes Zeichen in der Eingabezeichenfolge in seinen entsprechenden Ganzzahlwert und speichern Sie ihn in einem anderen Vektor.
3. Signifikante Ziffern mit Zehnerpotenzen multiplizieren: Nehmen Sie jedes Element aus dem Vektor der signifikanten Ziffern und multiplizieren Sie es mit dem entsprechenden Element aus dem Vektor der Zehnerpotenzen. Summieren Sie die Ergebnisse von diese Multiplikationen, um den numerischen Wert der Zeichenfolge zu erhalten.

Konkret für jede Ziffer in der Eingabe Zeichenfolge:

• Extrahieren Sie den Ziffernwert (0 bis 9), indem Sie seinen ASCII-Code von 48 subtrahieren.
• Multiplizieren Sie den Ziffernwert mit der entsprechenden Potenz von 10.
• Addieren Sie das Ergebnis zur Summe der zuvor berechneten Werte.

Umsetzung Überlegungen

Bei der Implementierung dieses Algorithmus in SIMD-Code können wir die inhärente Parallelität von SIMD-Anweisungen nutzen, um mehrere Ziffern gleichzeitig zu verarbeiten. Der Code sollte für den spezifischen verwendeten SIMD-Befehlssatz optimiert sein (z. B. SSE4.2, AVX2).

Potenzielle Optimierung:

Eine weitere Optimierung ist möglich Dieser Algorithmus macht eine separate Schleife zum Multiplizieren der signifikanten Ziffern mit Zehnerpotenzen überflüssig. Dies kann durch die Verwendung einer Technik namens „Vektorindizierung mit“ erreicht werden verschmolzenes Multiplizieren-Addieren. Mit dieser Technik können wir sowohl die Indizierung als auch die Multiplikation in einer einzigen Anweisung durchführen und so die Leistung verbessern.

Ein alternativer Vorschlag

Wie von Peter Cordes in den Kommentaren vorgeschlagen, Eine Alternative zu den letzten beiden Add-XOR-Anweisungen ist die Verwendung einer Imul-Anweisung (Integer Multiply). Dies hat das Potenzial, sowohl hinsichtlich der Codegröße als auch der Leistung effizienter zu sein.

Implementierung in GNU Assembler mit Intel-Syntax

Hier ist eine Beispielimplementierung des Algorithmus in GNU Assembler mit Intel Syntax:

.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 */

Fazit

Diese optimierte SIMD-Implementierung der Atoi-Funktion kann die Leistung bei der Verarbeitung großer Mengen numerischer Daten erheblich verbessern. Durch die Nutzung der Parallelverarbeitungsfähigkeiten von SIMD-Anweisungen können wir schnellere Ausführungszeiten erreichen und numerische Berechnungen effizienter durchführen.

Das obige ist der detaillierte Inhalt vonWie können SIMD-Anweisungen zur Optimierung der Atoi-Funktion verwendet werden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!