PHP7調査(39) strposやstrstrに高速っぽい実装が入ったけど実は遅いのでは疑惑 #PHP

（2016/7/26 9:15）タイトルを変更して所感などを追記しました

PHPのソースコードを眺めていたところ、PHP7からstrposやstrstrの内部実装が変更されており、高速「っぽい」文字列マッチングアルゴリズムが導入されていることに気づきました。

具体的には、Zend/zend_operators.hにあるzend_memnstrの実装が変更されており、検索文字列が3バイト以上かつ検索対象の文字列が1024バイト以上の場合にSunday algorithmで文字列マッチングを行います。

Sunday algorithmとは

アルゴリズムの教科書にも出てくる文字列マッチングアルゴリズムとしてBM法（Boyer-Moore algorithm）がありますが、Sunday algorithmはBM法の派生アルゴリズムの一つです。

Sunday algorithm

このアルゴリズムの概要は、事前に探索文字列に応じた辞書を作っておき、マッチングに失敗したら辞書に応じて何文字かズラして再度マッチングを試みる、というものです。

たとえば検索文字列が「abc」で、検索対象文字列のi文字目から(i+2)文字目までが検索文字列と一致しなかった場合に、(i+3)文字目が「d」だったとすれば、次のマッチングは(i+4)文字目から試みれば良いことがわかります（検索文字列に「d」は含まれていないのだから、(i+3)文字目を含むようなマッチングを試みる必要はない）。このように、マッチングを試みた場所の次の文字によって次に何文字ズラしてチェックするかを決めながら文字列を探していくわけです。

文章にすると面倒そうに思えるかもしれませんが、上記URLに示されている擬似コードを読めば大体何をしているかわかると思います。

旧実装の紹介

一方、PHP 5のstrpos/strstrではナイーブな実装が採用されています。

具体的には、検索対象の文字列から検索文字列の1文字目を探し、見つかったらそこから検索文字列全体がマッチするかを調べる、を繰り返すというものです。単純といえば単純ですが、そこまで悪い実装とも言えないでしょう。

BM法とナイーブ実装の比較

上の説明だけではナイーブ実装とBM法の具体的な違いがわかりにくいかもしれません。

BM法やその変形は、ナイーブ実装よりもメモリ参照と比較演算の回数が抑えられるアルゴリズムになっています。

たとえば、「defdabc」から「abc」を探す場合、ナイーブ実装では「a」を探し続ける必要があるので、全メモリのスキャンが必須です。

一方、Sunday algorithmの例で言えば1文字目の「d」を見れば「abc」とはマッチングしないことがわかるので、次に4文字目の「d」を確認してから5文字目から「abc」との比較を再開するという流れになります。ここで2文字目と3文字目に何が書いてあるか確認せずに文字列検索できている点が重要です。このように、検索文字列がn文字のときに検索対象文字列を最長(n-1)文字読み飛ばせる分、メモリ参照と比較演算の回数を抑えられる点がBM法の強みだと言えるでしょう。

ちなみに、オリジナルのBM法よりもSunday algorithmの方が平均的に読み飛ばせる量が大きくなっています。

ベンチマークテスト

さて、PHP 7から賢いアルゴリズムが採用されたならきっと速くなってるんですよね！ということでベンチマークテストを行ってみました。「abcd1234」の8文字を巨大な文字列から探してみましょう。

strlen($haystack)	PHP 5.6.24	PHP 7.0.9
10000	0.000004 sec	0.000011 sec
100000	0.000048 sec	0.000115 sec
1000000	0.000689 sec	0.001138 sec
10000000	0.007117 sec	0.011703 sec

予想に反し、むしろ遅いという結果になりました。

念のため、新実装に有利そうな検索文字列「abcd1234abcd」でも実験してみました。

strlen($haystack)	PHP 5.6.24	PHP 7.0.9
10000	0.000004 sec	0.000009 sec
100000	0.000047 sec	0.000088 sec
1000000	0.000697 sec	0.000849 sec
10000000	0.007126 sec	0.008521 sec

若干差が詰まった感はありますが、それでも新実装の方が遅いのは変わりません。逆転するにはかなり意図的な例が必要そうです。

単に僕の環境（MacOSX+php-build）や実験方法がイケてない可能性もあるので、ベンチマークに使ったコードを貼り付けておきます。追試したいという物好きな方、よろしくお願いいたします。

<?php
function gen_random_bytes($length) {
    $result = "";
    $charset = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    $nchar = strlen($charset);
    for ($i = 0; $i < $length; $i++) {
        $result .= $charset[mt_rand(0, $nchar-1)];
    }
    return $result;
}

mt_srand(1234);
$haystack_len = 10000; // これを1000万まで変化させる
$needle = "abcd1234";
$haystack = gen_random_bytes($haystack_len-strlen($needle)).$needle;
$benchmark_times = (int)(10000000 / $haystack_len);

for ($i = 0; $i < 5; $i++) {
    $start = microtime(true);
    for ($j = 0; $j < $benchmark_times; $j++) {
        strpos($haystack, $needle);
    }
    $end = microtime(true);
    printf("%.f sec\n", ($end-$start)/$benchmark_times);
    usleep(100000);
}

所感など

まだ結論を出せるだけの材料が揃っていない気もしますが、もし本当にナイーブ実装の方が早いとすれば次のような理由が考えられると思っています。

ナイーブ実装で利用しているmemchr(3)はSIMD実装されており、下手な自前実装より高速
- 参考：「標準ライブラリ関数のstrchrは何故速いのか」（ここではstrchrを取り上げているが、memchrも同様）
現代のCPUではキャッシュラインサイズも大きく演算器も複数あるため、アルゴリズムの工夫で多少メモリ参照や比較演算を減らしても影響が小さい
- 逆に、直線的な実装の方がCPUの仕組みにマッチして速かったりする（分岐予測・ハードウェアプリフェッチャー）
現代のCPUではテーブル参照は不利

筆者が人生で最初に感心したアルゴリズムがBM法だったので、もし本当にBM法が現代のCPUでは速くないとすれば個人的にはショックです。教科書に載っているアルゴリズムだからといって無批判に信用してはならない、測定せよというのは示唆的だとも思います。