SIMD 命令を使用して atoi を効率的に実装するにはどうすればよいですか?

SIMD を使用して atoi を実装するには?

問題:
atoi を書いてみたいSIMD 命令を使用した実装。RapidJSON に含まれます。私が思いついたアルゴリズムは次のとおりです。

1. 次の方法で長さ N のベクトルを初期化します。
   [10^N..10^1]
2. 変換バッファー内の各文字を整数に変換し、別のベクトルに配置します。
3. 有効数字ベクトル内の各数値を取得し、それに一致する値を乗算します。数値ベクトルの数値を入力し、その結果を合計します。

私のアルゴリズムは正しいですか?もっと良い方法はありますか? SIMD 命令セットを使用した atoi のリファレンス実装はありますか?

答え:
アルゴリズムは正しく、完全です。これは、MIN_INT=-2147483648 から MAX_INT=2147483647 まで、および MIN_UINT=0 から MAX_UINT=4294967295 までの int と uint に対して機能します。

Intel 構文を使用して GNU Assembler で書かれたリファレンス実装が提供されています。

これのプロパティコードは次のとおりです。

• 先頭の '-' 文字は負の数を示します (意味のあるものとして)。先頭の ' ' 文字は無視されます
• 先頭のゼロ (符号付きまたはなし) ) は無視されます
• オーバーフローは無視されます - より大きな数値はラップアラウンドするだけです
• 長さゼロ文字列の結果は値 0 = -0 になります
• 無効な文字が認識され、変換は最初の無効な文字で終了します
• 最後の先頭の 0 から少なくとも 16 バイトにアクセスできる必要があり、セキュリティへの影響の可能性があります。 EOS 後の読み取りは呼び出し元に任せられます
• SSE4.2 のみです必要です

アルゴリズムのアプローチは次のとおりです:

• ESI では数値文字列へのポインタが必要です
• 最初の文字が '-' であるかどうかを確認し、EDX で負の数値かどうかを示します (A)
• 先頭のゼロと EOS をチェックします (B)
• 文字列をチェックします有効な数字を取得し、有効な文字 (C) の strlen() を取得します。
• 文字列を反転して、
  10^0 のべき乗が常に BYTE 15
  10^1 になるようにします。常に BYTE 14
  10^2 は常に BYTE 13
  10^3 は常にBYTE 12
  10^4 は常に BYTE 11
  ...
  にあり、後続のすべての文字 (D)
• から飽和 '0' を減算します。 16 個の可能な文字のそれぞれ(1)
• 16 個の連続したバイト値を取得し、それらを 2 つの XMM レジスター内の WORD
  に分割します (2)
  P O N M L K J I | H G F E D C B A ->
  H G F E | DC B A (XMM0)
  P O N M | L K J I (XMM1)
• 各 WORD に 10000 を法とする位の値を乗算します (1,10,100,1000)
  (MAX_WORD より小さい因数、QWORD/halfXMM ごとに 4 因数)
  ( 2) なので、水平方向に 2 回結合してから次の結合を行うことができます。
  PMADDWD 命令はこれと次のステップを実行できます:
• 隣接する WORD を DWORD に水平方向に追加 (3)
  H1000 G100 F10 E1 | D1000 C100 B10 A1 (XMM0)
  P1000 O100 N10 M1 | L1000 K100 J10 I1 (XMM1)
• XMM0 と XMM1 から XMM0 に隣接する DWORD を水平方向に追加します (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]
• XMM0 の値に係数 (5)
  P1000 O100 N10 M1 (DWORD 係数 1000000000000 = 大きすぎますDWORD、ただし QWORD 数値文字列に役立つ可能性があります)L
  1000 K100 J10 I1 (DWORD 係数 100000000)H
  1000 G 100F10 E1 (DWORD 係数 10000)D
  1000 C100 B10 A1 (DWORD 係数 1)
• 最後のステップこれら 4 つの DWORD と、エミュレートされた 2

  PHADDD を追加しています。 2(PSHUFD PADDD)

  xmm0[31-0] = xmm0[63-32] xmm0[31-0] (
  • 6)xmm0[ 63-32] = xmm0[127-96] xmm0[95-64]
    (上位 QWORD には同じものが含まれているため無視されます)
    
  xmm0[31-0] = xmm0[63-32] xmm0[31-0] (
  • 7 )
数値が負の場合 (表示EDX では 000...0=pos または 111...1=neg)、それを否定します (
• 8)

Intel-IACA スループットの結果Haswell 32 ビットの分析:

スループット分析レポート

ブロック スループット: 16.10 サイクル スループットのボトルネック: 反復間

反復ごとのサイクルでのポート バインディング:

| ポート | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |

|サイクル | 9.5 0.0 | 10.0 | 4.5 4.5 | 4.5 4.5 | 0.0 | 11.1 | 11.4 | 0.0 |

N - リソースの競合によって遅延が発生したポート番号またはサイクル数、DV - ディバイダー パイプ (ポート 0 上)
D - データ フェッチ パイプ (ポート 2 および 3 上)、CP -クリティカル パス
F - 前の命令とのマクロ融合発生しました

• • 命令 micro-ops がポートにバインドされていません
    ^ - Micro Fusion が発生しました

    - ESP Tracking sync uop が発行されました

    @ - SSE 命令が AVX256 命令に続いた場合、数十サイクルのペナルティが発生します期待
    ！ - 命令はサポートされていません。分析では考慮されていません

|の数 | サイクル内のポート圧力 | |

| うおっ | 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 |

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