4 に答える
strstrなぜ他のすべてよりも遅くすべきだと思いますか? strstrどんなアルゴリズムを使っているか知っていますか? 微調整された、プロセッサ固有の、アセンブリ コードのタイプまたはそれ以上strstrのアルゴリズムを使用する可能性が非常に高いと思います。KMPその場合C、そのような小さなベンチマークでそれを上回る可能性はありません.
(これが可能性が高いと思う理由は、プログラマーがそのようなことを実装するのが好きだからです。)
Horspool、KMP などは、バイト比較の数を最小限に抑えるのに最適です。
ただし、それは最新のプロセッサのボトルネックではありません。x86/64 プロセッサでは、文字列はキャッシュ ライン幅のチャンク (通常は 64 バイト) でL1 キャッシュに読み込まれます。アルゴリズムがどれほど巧妙であっても、それよりも大きなストライドが得られない限り、何も得られません。より複雑な Horspool コード (少なくとも 1 つのテーブル ルックアップ) は競合できません。
さらに、ヌル終了の「C」文字列制約にこだわっています。コードはすべてのバイトを調べる必要があります。
strstr()幅広いケースに最適であると予想されます。たとえば"\r\n"、短い文字列のような小さな文字列だけでなく、よりスマートなアルゴリズムが期待できるはるかに長い文字列も検索します。基本的な strchr/memcmp ループは、可能性のある入力の範囲全体で打ち負かすのはかなり困難です。
2003 年以降、ほぼすべての x86 互換プロセッサが SSE2 をサポートしています。strlen()/x86 をglibc用に逆アセンブルした場合、SSE2 PCMPEQ および MOVMASK 操作を使用して一度に 16 バイトのヌル ターミネータを検索していることに気付いたかもしれません。解決策は非常に効率的であるため、空の文字列よりも長いものについては、明らかな超単純なループを打ち負かします。
私はそのアイデアを採用し、1 バイトを超えるすべてのケースでstrstr()glibcに勝るa を思いつきました--- ここで、相対的な違いはほとんど意味がありません。strstr()興味がある場合は、以下をチェックしてください。
-
strstr()15 バイトを超えるターゲット文字列を支配する非 SSE2 ソリューションを確認したい場合は、以下を確認してください。ではなくマルチバイト比較を利用
strchr()して、memcmp を実行するポイントを見つけます。
ところで、x86 の REP SCASB/REP CMPSB ops は 32 バイトよりも長い場合はお尻に落ち、短い文字列ではあまり改善されないことをおそらく理解したでしょう。IntelがSSE4.2の「文字列」操作を追加するよりも、それにもう少し注意を払っていたらよかったのに。
十分な大きさの文字列の場合、パフォーマンス テストでは、BNDM が Horspool よりも全体的に優れていることが示されています。BNDM は、パターンの最後のバイトを頻繁に繰り返すターゲットなど、「異常な」ケースに対してより寛容です。BNDM は、効率と初期コストで 32 ビット レジスタと競合する方法で SSE2 (128 ビット レジスタ) を利用することもできます。ソースコードはこちら。
コードを見ないと、正確に言うのは難しいです。 strstr大幅に最適化されており、通常はアセンブリ言語で記述されています。一度に 4 バイトのデータを読み取り、それらを比較する (整列が正しくない場合は必要に応じてビットを調整する) などの処理を実行して、メモリの待機時間を最小限に抑えます。SSE などを利用して、一度に 16 バイトをロードすることもできます。コードが一度に 1 バイトしかロードしない場合は、メモリ レイテンシによって強制終了されている可能性があります。
デバッガーを使用して逆アセンブルを実行すると、strstrおそらくいくつかの興味深いものが見つかるでしょう。
何かをきれいにしたいと想像してみてください。自分で掃除することもできますし、10 人のプロの掃除人を雇って掃除することもできます。清掃作業がオフィス ビルの場合は、後者のソリューションが望ましいでしょう。清掃作業が 1 つの窓である場合、前者が望ましいでしょう。
仕事はそれほど長くはかからないため、仕事を効率的に行うための設定に費やした時間に対する見返りはありません。