SIMD 命令を使用して atoi 関数を最適化するにはどうすればよいですか?

SIMD を使用して atoi を実装する方法

この記事では、文字列表現を変換する atoi 関数を実装するためのアルゴリズムを検討します。単一命令複数データ (SIMD) 命令を使用して、整数をその数値に変換します。 SIMD を使用すると、複数の要素を並列処理することで大幅なパフォーマンスの向上を達成できる可能性があります。

アルゴリズム

提案されたアルゴリズムは次のステップで構成されます。

1. 長さ N のベクトルを初期化します: 長さ N のベクトルを作成します。 N は、サポートする最大桁数です。降順で 10 の累乗を表す値でベクトルを初期化します (例: [10^N, 10^(N-1), ..., 10^1])。
2. それぞれを変換しますバッファ内の文字を整数に変換します: 入力文字列内の各文字を対応する整数値に変換し、別の文字列に格納しますVector.
3. 有効数字を 10 の累乗で乗算します: 有効数字のベクトルから各要素を取り出し、10 の累乗のベクトルから対応する要素を掛けます。次の結果を合計します。これらの乗算を使用して文字列の数値を取得します。

具体的には、入力の各桁に対してstring:

• 48 から ASCII コードを減算して、数字の値 (0 ～ 9) を抽出します。
• 対応する 10 のべき乗を数字の値に掛けます。
• その結果を以前に計算した合計に加算します。

実装の考慮事項

このアルゴリズムを SIMD コードで実装する場合、SIMD 命令の固有の並列性を利用して複数の桁を同時に処理できます。コードは、使用されている特定の SIMD 命令セット (SSE4.2、AVX2 など) に合わせて最適化する必要があります。

潜在的な最適化:

さらに最適化することが可能です。このアルゴリズムは、有効数字を 10 の累乗で乗算する別のループの必要性を排除することによって実現されます。これは、次の手法を使用することで実現できます。 「融合乗算加算によるベクトルインデックス付け」と呼ばれます。この手法により、インデックス付けと乗算の両方を 1 つの命令で実行できるようになり、パフォーマンスが向上します。

代替案

コメントで Peter Cordes が提案したように、最後の 2 つの add xor 命令の代わりに、imul (整数乗算) 命令を使用することもできます。これにより、コード サイズとパフォーマンスの両方の点で効率が向上する可能性があります。

Intel 構文を使用した GNU アセンブラーでの実装

アルゴリズムのサンプル実装は次のとおりです。 Intel を使用した GNU アセンブラで構文:

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

結論

この最適化された atoi 関数の SIMD 実装により、大量の数値データを処理する際のパフォーマンスが大幅に向上します。 SIMD 命令の並列処理機能を利用することで、実行時間を短縮し、数値計算をより効率的に処理できます。

以上がSIMD 命令を使用して atoi 関数を最適化するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。