SIMDに適した部分文字列探索アルゴリズム（2018）

 (0x80.pl)
1 ポイント 投稿者 GN⁺ 2025-06-15 | まだコメントはありません。 | WhatsAppで共有
  • strstr、std::string::find のような API は 1回限りの部分文字列探索を前提としているが、現代の CPU では短い文字列・ベクトル比較のコストが低く、SIMD 方式が有利になり得る
  • 核心となるアイデアは、Karp-Rabin の弱いハッシュ条件を ベクトル述語に置き換え、候補位置でだけ正確な部分文字列比較を行うこと
  • 汎用 SIMD アルゴリズムは needle の 先頭文字と末尾文字を並列比較して候補を絞り、一致する可能性のある位置だけを memcmp で検証する
  • SSE4.1 MPSADBW、SSE4.2 PCMPESTRM 方式も比較しているが、測定結果では汎用 SIMD の方がより安定して高速で、PCMPESTRM は MPSADBW よりも遅い傾向がある
  • 汎用 SIMD はすべてのプラットフォームで C の strstr より高速だったが、入力文字列の外側を読み得るため 安全ではなく、長さ情報を事前に受け取る点でも比較条件は完全には同じではない

文字列探索で変わったコスト前提

  • C の strstr、C++ の std::string::find、Python 文字列の pos、index のような API は、与えられた文字列から部分文字列を探す 1回限りの探索に合わせて設計されている
  • 既存のアルゴリズムは大きく2種類に分けられる
    • Knuth-Morris-Pratt、Boyer Moore のような 決定性有限オートマトンベースの方式
    • Karp-Rabin のような単純比較ベースの方式
  • 標準的なアルゴリズムは、1組の文字比較、補助テーブル参照、条件分岐は安く、2つの部分文字列比較は高いという前提を置いている
  • 現代のデスクトップ CPU では、この前提があまり当てはまらない場合がある
    • 64ビット CPU では 1、2、4、8バイト比較のコストに差がない
    • SIMD 命令をサポートしていれば、16、32、64バイトのベクトル比較も単一バイト比較と同じくらい安くなり得る
    • テーブル参照は L1 キャッシュ往復程度のメモリアクセスコストがかかり、文字単位の読み取りも同程度のコストを持つ
    • 誤予測された分岐は約 10〜20サイクルのペナルティを生む可能性がある
    • 文字読み取り、比較、条件分岐へと続く短い依存関係の連鎖は、CPU のアウトオブオーダー実行の活用を難しくする

アプローチ：弱いハッシュの代わりにベクトル述語を使う

  • Karp-Rabin は、検索対象の部分文字列の 弱いハッシュと現在の文字列区間のハッシュが等しい場合にだけ、正確な比較を実行する
  • SIMD 方式は、このハッシュ条件を ベクトル述語で置き換える
    • 述語は並列に計算される
    • 述語ベクトルで真になった各位置についてのみ、正確な部分文字列比較を行う
  • 長さごとの特殊化も性能改善に使われる
    • 一般的な実装は、部分文字列比較に memcmp のような関数を呼び出す
    • 検索する部分文字列の長さが分かっていれば、特定の長さに合わせて関数呼び出しをいくつかの CPU 命令、場合によっては1命令で置き換えられる
    • この方式は関数呼び出しのコストと memcmp 内部のコストを削減する

アルゴリズム 1：汎用 SIMD

  • 汎用 SIMD アルゴリズムは、SIMD 命令セット全般と SWAR 方式に適用できる
  • 基本となる述語は、needle の 先頭文字と 末尾文字がどちらも一致するかを確認するもの
    • 先頭文字をレジスタ F に詰める
    • 末尾文字をレジスタ L に詰める
    • 各反復で haystack の現在オフセット i からチャンク A を読み、i + k - 1 からチャンク B を読む
    • F == A と B == L を計算した後、2つの結果を結合して候補位置のマスクを作る
    • マスクが真の位置でのみ、正確な部分文字列比較を行う
  • "cat" を "a_cat_tries" から探す例では、先頭文字 c と末尾文字 t がどちらも一致する位置はインデックス 2 の1か所だけなので、正確な比較も1回だけ行われる
  • 先頭文字と末尾文字を選ぶ方法が常に良いとは限らない
    • 入力文字列の大半が 'A' で needle が "AjohndoeA" の場合、候補が大量に発生し得る
    • 実装では、末尾文字の代わりに先頭文字と異なる最も遠い文字を選択できる
    • needle のすべての文字が同じなら、"AAAAA" のようなパターン向けの特殊手順を使える

実装ごとの差異

  • SSE と AVX2 の実装は構造がほぼ同じで、最小限の命令数を使う
    • すでに先頭文字と末尾文字が一致していることが分かっているため、memcmp でこれらの文字を再度比較する必要はない
  • SWAR 方式は、XOR 結果が 0 ならバイトが等しいという点を利用する
    • SSE/AVX2 のように部分結果を AND する代わりに OR を使う
    • 0 バイト位置を見つける過程にはより多くの作業が必要になる
    • 64ビットベクトル用の C++ 実装では、正確なバイトマスクを計算する
  • AVX512F はバイト演算がなく、最小のベクトル要素が 32ビットワードなので SWAR 技法が必要になる
    • 2つの XOR と OR を AVX512F 命令で計算する
    • 32ビット要素のうち 0 バイトを含む要素を見つける
    • 該当する 32ビット要素ごとに4つの候補部分文字列を確認する
  • ARM Neon 32ビット実装は 128ビット SIMD レジスタを使う
    • Neon ユニットから CPU へ戻る長い往復がボトルネックになる
    • 比較結果を 64ビットワードとしてメモリに保存して処理する
    • 内側ループ2つをアンロールすると約 1.2倍速くなる
  • AArch64 実装は ARM Neon 手順とほぼ同じだが、SIMD レジスタ lane を直接読む動作が速い

アルゴリズム 2：SSE4.1 MPSADBW

  • SSE4.1 と AVX2 の MPSADBW は、あるレジスタの4バイト下位ベクトルと、別のレジスタ内の連続する4バイト下位ベクトル8個との間の Manhattan distance を計算する
  • 2つの下位ベクトルが同じなら L1 距離は 0 になるため、これを候補位置探索に使う
    • この方式は 先頭4文字の同一性を述語として使う
  • 先頭4文字を比較するため、先頭・末尾文字比較より強力に見えるが、最悪の場合は2次の計算量を避けられない
    • haystack が "a" で埋まっていて needle が "aaaabcde" の場合、述語はすべての入力文字で真になる
  • MPSADBW 方式にはいくつかの制約がある
    • 長さ4未満の部分文字列には基本的に適さない
    • 長さ3の処理は可能だが追加コードが必要
    • SSE MPSADBW は一度に8バイトしか処理しない
    • AVX2 MPSADBW は 256ビット全体ではなく 128ビット lane 単位で動作するため、追加のロードコードが必要になる
    • 命令 latency は CPU によって 5〜7サイクルと高いが、throughput は 1〜2サイクルなので、ループアンローリングで latency を隠せる
  • AVX512F には MPSADBW がないが、32ビット要素がネイティブにサポートされているため、4バイト prefix 同一性の述語を模倣できる
    • 各反復で、可能な4バイト prefix を入れた AVX512 ベクトルを4つ作る
    • 各ベクトルの構築には shift 2つと OR 1つが必要
    • 比較ループが複雑になり、最後の要素を埋めるにはベクトルの先に4バイトが必要になる

アルゴリズム 3：SSE4.2 PCMPESTRM

  • SSE4.2 は、文字列演算のビルディングブロックを目的として STNI 命令セットを導入した
  • Intel はその後のプロセッサで STNI を事実上中断し、AVX2 版も導入しておらず、これらの命令は非常に遅い
    • latency 11サイクルは受け入れがたいと評価されている
  • PCMPxSTRx 命令には、文字列長の決定方法と結果の保存方法に応じて4つの変種がある
    • 長さは明示的に与えることも、従来の C 文字列のように最初の 0 バイトを終端と見なすこともできる
    • 結果はビット/バイトマスク、またはマスク内の最初/最後にセットされたビット番号として保存できる
  • ここでは range ordered 比較方式を使う
    • 名前に反して、部分文字列またはレジスタ幅を超える場合はその prefix を探す
    • 例で "ABCD" を "ABCD_ABC_ABCD_AB" から探すと、suffix "AB" も一致として扱われる可能性がある
    • したがって安全に仮定できるのは 先頭文字の一致だけで、残りは memcmp で確認する必要がある

性能測定環境

  • 複数の SIMD 実装の性能を測定し、短い部分文字列に対するランタイム特殊化も含めた
  • C の strstr を比較対象に含めたが、GNU libc の std::string::find の性能バグのため x64 表からは除外した
  • テストは各プログラムを3回実行した
  • x64 テスト環境
    • Westmere i5 M540、GCC 6.2.0
    • Bulldozer FX-8150、GCC 4.8.4
    • Haswell i7 4470、GCC 5.4.1
    • Skylake i7 6700、GCC 5.4.1
    • Knights Landing 7210、GCC 5.3.0
  • ARM テスト環境
    • ARMv7 Raspberry Pi 3、32ビットコード、GCC 4.9.2
    • ARMv8 ARM Cortex A57 / AMD Opteron A1100、64ビットコード、Clang 3.8.0

x64 の結果

  • 一般的な SIMD 実装は、x64 で strstr に対して最も大きな速度向上を示した
    • Westmere では SSE2 generic が 0.74589秒、strstr は 0.82246秒
    • Haswell では AVX2 generic が 0.38653秒、strstr は 0.52786秒
    • Skylake では AVX2 generic が 0.36309秒、strstr は 0.66148秒
    • KNL では AVX512F generic が 1.14057秒、strstr は 4.94606秒
  • 最大の速度向上は Westmere 1.10倍、Haswell 1.37倍、Skylake 1.82倍、KNL 4.33倍
  • Bulldozer の strstr 性能は 9.37792秒と非常に悪く、基準として使いにくい
  • MPSADBW 方式は Skylake を除くと全体的に良くなく、KNL では特に悪かった
  • PCMPESTRM 方式は MPSADBW よりもさらに遅い結果となった

ARM の結果

  • ARMv7 で std::strstr は 7.30405秒、std::string::find は 4.17131秒だった
  • ARMv7 で ARM Neon 32ビット generic は 1.29861秒で、std::string::find に対して最大 3.1倍速い
  • ARMv8 で std::strstr は 3.37546秒、std::string::find は 1.81368秒だった
  • ARMv8 で AArch64 64ビット generic は 0.27897秒で、std::string::find に対して最大 6.5倍速い
  • ARMv8 で SWAR 64ビット generic は 0.46269秒で、32ビット SIMD 手順に近い性能を示した

結論と限界

  • 一般的な SIMD アルゴリズムは、すべてのプラットフォームで C の strstr より高速だった
  • 実装は、特定の CPU で利用できる最上位の SIMD バージョンを選択するのが望ましい
  • MPSADBW は Skylake という例外を除くと性能が良くなく、Knights Landing では非常に悪い
  • PCMPESTRM は MPSADBW より性能が低い
  • ARM Neon の性能は SWAR 実装まで含めて良好だった
    • SWAR バージョンは string::find より 1.7倍速い
    • SIMD バージョンは string::find より 3.1倍速い
  • strstr との比較は完全に公平ではない可能性がある
    • strstr は長さが分からない文字列を処理する
    • これらの実装は長さを引数として受け取り、それを活用する
  • 実装は安全ではない
    • 入力文字列の外側のデータを読み得る
    • 文字列がマップされていないメモリの直前にある場合、アクセス違反が発生する可能性がある
    • address sanitizer も問題を報告する可能性がある
    • 安全にすることは可能だが、目標ではなかった
  • すべての実装とテストプログラムは GitHub にある

関連記事

まだコメントはありません。

まだコメントはありません。