ハクソク

世界を動かす技術を、日本語で。

部分文字列検索のためのSIMDフレンドリーアルゴリズム (2018)

346日前原文(0x80.pl)

概要

  • 文字列検索アルゴリズムの従来手法の課題と現代CPUとのギャップ
  • SIMD命令を活用した高速な部分文字列検索手法の紹介
  • Karp-RabinアルゴリズムのSIMD最適化と具体的な実装例
  • 各種SIMD命令セット（SSE, AVX2, AVX512F, SWAR, ARM Neon等）への適用方法
  • 実装の工夫点とパフォーマンス向上のポイント

文字列検索アルゴリズムとSIMD最適化の概要

  • 一般的なプログラミング言語には、 部分文字列検索用API （例：Cのstrstr、C++のstd::string::find、Pythonのindex等）を標準搭載
  • これらAPIは 一度きりの検索用 に設計されている
  • 代表的なアルゴリズムは大きく2系統
    • 決定性有限オートマトン系 （Knuth-Morris-Pratt, Boyer-Moore等）
    • 単純比較系 （Karp-Rabin等）
  • 従来アルゴリズムは「 文字単位比較が安価、部分文字列比較が高価」という前提に基づく
  • しかし現代のCPU（特にSIMD命令対応）では、 複数バイト同時比較が非常に高速 であり、この前提が崩れている

SIMDを活用した部分文字列検索のアプローチ

  • SIMD命令を用いることで、 複数バイト（16, 32, 64バイト等）を同時比較 可能
  • Karp-Rabinアルゴリズムをベースに、 ハッシュ判定をSIMDベクトル判定に置換
  • 各SIMD命令セット（SSE, AVX2, AVX512F, SWAR, ARM Neon等）に最適化した実装が可能
  • 部分文字列長が既知の場合、memcmp呼び出しを省略し、数命令で比較が完了 する

アルゴリズム1：汎用SIMDアルゴリズムの流れ

  • 検索対象部分文字列（needle）の 先頭・末尾文字（または最適な2文字） を抽出

  • それぞれの文字をベクトルレジスタに複製（例：SSE/AVX2なら16/32バイト分）

  • 対象文字列（haystack）の該当範囲から 2つのチャンク（先頭・末尾位置） をロード

  • 各チャンクとneedle先頭・末尾文字を ベクトル比較 し、両方一致した位置をマスクで抽出

  • マスクで抽出された位置のみ 厳密な部分文字列比較 を実施

    • 例：「cat」を8バイトレジスタで検索する場合、先頭・末尾文字を複製し、比較結果マスクから候補位置を抽出

  • 先頭・末尾以外も、 needle内で最も遠い異なる文字 を末尾として選択することで、パターンによる無駄な比較を削減

各種SIMD命令セットへの実装例

  • SSE/AVX2 ：_mm256_set1_epi8, _mm256_loadu_si256, _mm256_cmpeq_epi8等を活用し、32バイト単位で高速検索
  • SWAR ：64ビット整数演算でxorとビットマスクを駆使し、8バイト単位で比較
  • AVX512F ：32ビット単位の比較を工夫し、4バイトごとに部分文字列比較を並列化
  • ARM Neon ：128ビットSIMDレジスタを使い、比較結果をメモリに一旦保存して順序を維持

実装上の工夫点

  • memcmpの呼び出し回数削減、部分一致時のみ厳密比較
  • needle長に応じた分岐や特殊化 により命令数・分岐数を最小化
  • キャッシュ効率 や 分岐予測回避 にも配慮したループ設計
  • パターンが単一文字のみの場合 は専用ルーチンで最適化

まとめ

  • 現代CPUのSIMD命令を活用することで、 従来アルゴリズムより高速な文字列検索 が実現可能
  • needle長やパターン特性に応じて 複数の最適化手法を組み合わせることが鍵
  • 実装例はC++で提供されており、 SSE/AVX2/AVX512F/Neon/SWAR それぞれの特徴を活かした構造
  • SIMD命令による並列比較と、 無駄な比較回数削減 がパフォーマンス向上のポイント

Hackerたちの意見

Wasm/WASI libcのSIMD最適化を試みる中で、これを実装したよ。 https://github.com/ncruces/go-sqlite3/tree/main/sqlite3/libc 既知のハヤシの長さと大きなニードルに対して、クイックサーチを使うと役立つことがわかった。 https://igm.univ-mlv.fr/~lecroq/string/node19.html

ストリングの検索や分割のために、SMIDメソッドを使ったいろんなアルゴリズムも実装したよ。 https://github.com/naver/tamgu/blob/06aedf2f14895925d7b5a8e2... ここで紹介されているアルゴリズムとは別のものを使ったんだ。

└

あなたのアルゴリズムをざっくりまとめてもらえる？ 高レベルな説明で。記事のアルゴリズム1は、最初と最後の文字をマッチさせてN個の可能な位置を同時にチェックする感じ。アルゴリズム2は、代わりに先頭の4文字をテストするんだ。

└

数年前にZigのジェネリックSIMDを使ってLZ77ウィンドウ検索の修正版を実装しようとしたことがあるよ: https://news.ycombinator.com/item?id=44273983

libcのstrstrがひどいのは知ってるけど、muslは速くて最先端だよね。 今は名前が必要なだけで、スマートシュートアウトに追加できる。 これが最高のSIMDアルゴリズムと比べてどうなるか気になるな。

└

おおまかなベンチマークに興味があれば、muslの「二方向」とこのアルゴリズムのバリエーションを比較したよ。 私のSIMD最適化されたlibcについては、別のコメントでリンクしてある。 そのファイルのこの行を見つけるベンチマークだよ： https://github.com/ncruces/go-sqlite3/blob/v0.26.1/sqlite3/l... muslに対する改善点はこの表にあるよ： https://github.com/ncruces/go-sqlite3/tree/v0.26.1/sqlite3/l... まあ、そこそこ改善されてると思うけど、特別なわけじゃないかな。 muslは既知の長さの文字列（memmem）には特に強いけど、私は不明な長さの文字列（strstr）でちょっとズルできるからね。 Wasm環境ではいくつかの未定義動作を回避できるんだ。 NUL終端の文字列の曲者が多くの良いアルゴリズムを台無しにするんだよね。

└

SIMDアルゴリズムがもっとあったらいいな。時間があれば、ちょっと試してみようかな。

missing (2018) ?

└

実際には2016年で、2018年にスペルの修正があったんだ。まだいくつかのエラーを見逃してるけどね。「二つのサブストリングを比較するのはexpansive」→ expensive とか、「memcmpのコストは単にridden off」→ written みたいな。stdlibに対するbuldozerのひどさは興味深いけど、SSE2があればWestmereともっと競争力があったんだね。

効率のための文字列サイズの閾値はどれくらい？ SIMD（アライン、サイズ計算など）のセットアップコードは、通常「小さい」文字列のバイト指向の基本検索よりもコストが高いからね。 そう、ハードウェアアーキテクチャに大きく依存するんだ。

└

ここでは、逆のことが多いんだ。 これらのアルゴリズムは基本的にブートフォースで、セットアップがほとんどいらないから、大きくて周期的なニードルに対して二次的になることがある。 二次的な挙動を避けるストリング検索アルゴリズム（場合によってはサブリニアになることもある）は、ニードルの構造を探るために高いコストのセットアップが必要なんだ。

swarアルゴリズムは、1バイトアラインのデータを8バイトアラインにキャストするから、未定義動作（UB）が発生するんだよね。もしかしたら、アラインされてないロードからパフォーマンスの問題が出てるかも？

└

俺はこれらを「理想化された」アルゴリズムや擬似コードとして捉えてたんだ。正しい未アラインのロード（memcpyを使う）をしてないのに加えて、境界チェックも間違ってる。コードは干し草の長さが8の倍数であることを前提にしてるし、針が空だと符号なし整数のオーバーフローが起きて、針に対して範囲外アクセスが発生するんだ。これで未定義動作が3つも出ることになる。これは、SIMDコードを示すときに結構よくあることだと思う。関連する部分だけが示されて、境界ケースを正しくするための努力があまりされてないことが多い。明示的に認められることは少ないけど、境界条件はベクトルを面白い方法で使う「肉」の部分よりもあまり面白くないからだと思う。

「AVX2（一般）」のアプローチは、ripgrepが使ってるやつに近いね（Rustのregexクレート経由で）。例えば、\w+\s+Sherlock\s+\w+みたいなパターンでも、ripgrepがSherlockを正規表現から抜き出して検索するから効果があるよ。実際の実装はここにあるよ: https://github.com/BurntSushi/memchr?tab=readme-ov-file#algo... ここで紹介されているアルゴリズムとの主な違いは、針の最初と最後のバイトを常に使うのではなく、背景の頻度分布に基づいてあまり頻繁に出現しない2バイトを選ぼうとするヒューリスティックを使っているところ。これのおかげで、単純なTwo-WayやGNU libcのmemmemの実装よりもかなり速くなるんだ。memchrリポジトリのルートから: $ rebar rank benchmarks/record/x86_64/2023-12-29.csv -e '^rust/memchr/memmem/(oneshot|prebuilt|twoway)' -e '^libc/memmem/oneshot' エンジンバージョン 速度比の幾何平均 ベンチマーク数 ------ ------- ------------------------------ --------------- rust/memchr/memmem/prebuilt 2.7.1 1.07 57 rust/memchr/memmem/oneshot 2.7.1 1.39 54 libc/memmem/oneshot unknown 3.15 54 rust/memchr/memmem/twoway 2.7.1 5.26 54 「prebuilt」のベンチマークは、memmemのようなルーチンのAPIの欠陥も示してるよ。APIのせいで、与えられた針の検索を実行するために必要な状態を再構築する必要があるんだ。でも、針は異なる干し草の山での繰り返し呼び出しの間で不変であることが多いから、無駄な作業を繰り返すことになるんだよね。

└

面白いね。どうやってバイトの背景分布を知るの？干し草の山をスキャンして分布を取得するのにかなりの時間がかかるんじゃない？

もしPythonから直接SIMDを使えるなら、他の言語に呼び出さずに済むのに。

└

なんでそんなことしたいの？Pythonのコードでパフォーマンスがボトルネックになってるなら、言語を切り替えるだけで20〜50倍のパフォーマンス向上が見込めるよ。

└

やあ、オースティン！ブログと母音検出の投稿をチェックしてたんだけど（https://austinhenley.com/blog/vowels.html）。「別の言語に呼び出さずにSIMDを直接使う」ってどういう意味なの？アセンブリは結局別の言語になると思うけど…まあ、それは細かいことだね。Pythonに関連するSIMDの仕事はかなり幅広いと思う。PeachPyみたいに、Pythonでx86アセンブリを書くのを手助けするプロジェクトや、Mojoみたいな新しいPython風の言語、薄いCPythonバインディングのSIMDライブラリとか。そういうのを指してるのかな？追記：私は最後の方だよ。それと、もしASCIIに焦点を当ててるなら、母音検索のためにStringZillaのfind_first_of（https://github.com/ashvardanian/StringZilla/blob/960967d78c7...）を試してみた？結構いいパフォーマンス出ると思うよ ;)

これを思い出したよ：https://github.com/nikneym/hparse SIMDアルゴリズムを使って高速HTTPパースをしてるやつ。

C#はIndexOfのためにいくつかのSIMDを実装してるよ：https://github.com/dotnet/runtime/pull/63285