博士

やあ、ロボ子。今日のニュースはSIMDを使った文字列検索アルゴリズムじゃ。

ロボ子

SIMD、ですか。Single Instruction, Multiple Dataの略ですよね。一つの命令で複数のデータを処理する。

博士

そうじゃ！この記事では、SSE, AVX2, AVX512F, ARM Neonなど、色々なSIMD命令セットを使って文字列検索を高速化しているのじゃ。

ロボ子

へえ、そんなに多くの種類があるんですね。具体的にはどんなアルゴリズムを使っているんですか？

博士

Algorithm 1はGeneric SIMDといって、文字列の先頭と末尾をSIMDで比較して、候補を見つけるのじゃ。その後、正確な比較をする。

ロボ子

なるほど。先頭と末尾で絞り込むんですね。効率が良さそうです。

博士

Algorithm 2はSSE4.1のMPSADBW命令を使うのじゃ。4バイトのサブベクトル間のManhattan距離を計算して、距離が0の場所を候補にする。

ロボ子

Manhattan距離ですか。ちょっと計算コストが高そうですが、SSE4.1に特化している分、最適化されているんでしょうね。

博士

Algorithm 3はSSE4.2のPCMPESTRM命令を使うのじゃ。"range ordered"アルゴリズムでsubstringを検索するぞ。

ロボ子

SSE4.2ですか。ずいぶんとニッチな命令を使うんですね。

博士

パフォーマンスの結果を見ると、Generic SIMDアルゴリズムがCのstrstr関数より速いらしいぞ。特にAVX2版が最速じゃと。

ロボ子

strstr関数よりも速いとはすごいですね。SIMDの恩恵ですね。

博士

ARM Neon版も高速らしいぞ。でも、AArch64のSWAR64は32-bit SIMDと同程度の性能みたいじゃ。

ロボ子

アーキテクチャによってSIMDの効率も変わるんですね。面白いです。

博士

結論としては、Generic SIMDアルゴリズムはCのstrstr関数より優れていて、利用可能な最高のSIMDバージョンを使うべき、とのことじゃ。

ロボ子

勉強になります。文字列検索でSIMDを使うという発想がありませんでした。

博士

ソースコードはGitHubで公開されているから、ロボ子も見てみると良いぞ。[https://github.com/WojciechMula/sse4-strstr](https://github.com/WojciechMula/sse4-strstr)じゃ。

ロボ子

ありがとうございます。後で確認してみます。

博士

しかし、SIMDって奥が深いのじゃ。まるで、私の知識の泉のようじゃな！

ロボ子

博士、その泉、たまに藻が生えてますよね。

博士

むむ、それは言いすぎじゃ！藻ではなく、貴重な栄養分じゃ！