この記事は当初Qiitaに掲載していたものです。blogに移設しました。

「PHP7調査(39) strposやstrstrに高速っぽい実装が入ったけど実は遅いのでは疑惑」で、strpos()の実装がPHP7で変わったことにより遅くなったのでは、という話があげられています。

  • PHP5はC言語のmemchr()とmemcmp()によるナイーブ実装（ソースコード）
  • PHP7は検索対象1024Byte以上または検索文字3Byte以上でSunday algorithm自前実装を使用（ソースコード）

そして、実測としてPHP5のほうがPHP7より高速であるということが示されています。

しかし個人的にもBM法は初学のころにワクワクしたアルゴリズムであることと、計測もせずにPHP7に実装したとは思えなかったことから、少しずつ調査をしていました。本記事ではそれをまとめます。

glibcの工夫：32bit(64bit)まとめて比較

PHP5はナイーブ実装とはいえ、glibcの関数をそのまま利用しています。様々なソフトウェアから使われるglibcではもちろん実装に工夫がしてあります。

https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memchr.c;h=ca9fd99f2105003d0b56285ff3f41ba10dad8685;hb=HEAD#l46

このソースコードはCPUアーキテクチャ非依存で、64bit CPUにはこれが使われるようです。x386向けにはインラインアセンブラのコードになっているので、CPUごとにも高速化が図られています。

ソースコードを読むのは一苦労ですが、次のコメントだけ読めばその高速化のキモはわかります。

 100   /* Instead of the traditional loop which tests each byte, we will test a
 101      longword at a time.  The tricky part is testing if *any of the four*
 102      bytes in the longword in question are equal to c.

「伝統的なbyteごとのループに代えて、longwordでの確認をするよ。このトリッキーなパートではlongwordの4つのbyteのどれかが変数cと等しいかどうかを確認していくよ」

longword型はtypedefで次のように定義されています。

  55   typedef unsigned long int longword;

つまりはunsigned char（1Byte）ごとの比較ではなく、unsigned long（32bit/64bit）ごとに比較することでナイーブ実装より4倍(8倍)速い比較を行います。charではなくintでの操作なので、よりCPUにとって取り扱いやすい単位であるというのも効いているかもしれません。

BM法では比較bit数に応じたサイズのテーブルが必要になるため、せいぜい16bit（64KBのテーブル）まででしょう。同じアプローチは取れません。

それでもBM法を用いるメリット：最悪のパターンに強くなる

ここまでの話では、ナイーブ実装したほうが高速でありコードも短くすむ、つまりSunday algorithmはやめたほうがいいという話になってしまいます。
そうではなく、Sunday algorithmを採用したほうがいいという結論ありきな考え方でメリットがないか進めてみます。

BM法（Sunday algorithm）のメリットはマッチしなかった場合により多くを読み飛ばせるという点にあります。読み飛ばせる大きさは検索文字列に依存し、検索文字列が長ければ長いほど有利になります。

そこで、元記事のベンチマークコードを極端にしてみます。比較文字列を「abcd1234」から64Byteのランダム文字列に変えて計測しました。

<?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 = 10000000; // これを1000万まで変化させる
//$needle = "abcd1234";
$needle = gen_random_bytes(64);
$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);
}
strlen($haystack)PHP 5.6.26PHP 7.0.11
100000000.004817 ～ 0.010386 sec0.002315 ～ 0.006861 sec

検索文字列をさらに長くすればPHP7はより有利になります。

これ自体は元記事にも

逆転するにはかなり意図的な例が必要そうです

とあるように、予想されていた結果です。これに意味づけをするならば「ナイーブ実装の不得意な”検索文字列、検索対象が大きな場合”により強くなった」です。汎用ライブラリを提供する立場から見ると、これは採用するに十分なメリットと思います。ナイーブ実装で速いパターンはSunday algorithmでも十分な速度を確保できます。

欲をいえば、Sunday algorithmとナイーブ実装を選択する境界値「検索対象1024Byte以上または検索文字3Byte以上」をもっと調整したほうがよいのでしょう。計測ターゲット環境により大きく変わりそうですが、少なくとも「検索文字3Byte以上」は小さすぎると思います。ナイーブ実装は4Byte(8Byte)まとめ読みしてくるので、平均9Byte以上読み飛ばしてようやく同等です。明確に優位に立つには数十Byte読み飛ばす必要があります。

所感：ナイーブ実装に戻すとき

BM法（Sunday algorithm）が考えられたときはせいぜい16bit CPUであることを考慮すると、今回みたglibcの高速化手法は通用せず、インラインアセンブラでどこまで戦えるかということになります。ほとんどの場合でBM法が高速だったことでしょう。

古典的な高速アルゴリズムの多くはメモリ空間とCPU能力のバーターによるものですが、CPUの能力アップによってバーターとなるメモリ空間は大きくなります。CPUが32bit、64bitになったことでBM法の優位は薄れていきました。

今後128bit CPUが普及すると、BM法は検索文字列が巨大な場合でしか通用しなくなります。PHP8が登場するときにはCPUパワーに物を言わせるナイーブ実装に戻されるかもしれません。