正規表現でアトミックグループが高速になる理由
2009年2月28日 22:41理論的に高速になる表現だとしても、実際に高速になるかはベンチマークで確かめる必要があります。
404 Blog Not Found:regexp - possessive quantifier (独占的|絶対最大)量指定子とは何か?
'<img alt="backtrack" src="bt.png">' =~ /"([^\"]+)"/;と
'<img alt="backtrack" src="bt.png">' =~ /"([^\"]++)"/;は、どちらも
backtrackを見つけますが、後者の方が高速です。
うーん。この例だと両方ともマッチするするから、ステートを破棄することで高速になるというのが分かりにくいのかも。
そこで、Perl 5.8.8 でベンチマークの例を挙げながら、アトミックグループでステートを破棄した事により高速になる理由について掘り下げたいと思います。
ベンチマークスクリプト
まずは次のベンチマークスクリプトを走らせてみましょう:
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw/:all/;
my $length = shift;
my $count = shift;
unless ($length) { $length = 1000; }
unless ($count) { $count = 0; }
my $str = 'x' x $length . 'm';
cmpthese( timethese($count, {
' mache + ' => sub { $str =~ /x+m/ },
' mache ?>' => sub { $str =~ /(?>x+)m/ },
'not mache + ' => sub { $str =~ /x+n/ },
'not mache ?>' => sub { $str =~ /(?>x+)n/ },
}));
my $line = '-' x 30;
print <<PRINT_END
$line
Perl Version: $]
string length: $length
$line
PRINT_END
__END__
このスクリプトでは引数を二つ渡すことができます。
一つ目は量指定子がマッチする文字数です。
二つ目はベンチマークを実行する回数か秒数を指定するもので、正数を指定すると回数となり、負数を指定すると秒数となります。0を指定した場合はデフォルトの3秒として実効されます。
例えば、次のように実効します:
100文字に対して100万回実効する。 $ ./pq_benchmark.pl 100 1000000 1万文字に対して5秒実効する。 $ ./pq_benchmark.pl 10000 -5
引数を渡さない場合、初期値として文字列の長さは1000文字で3秒実効します:
1000文字に対して3秒実効する。 $ ./pq_benchmark.pl こうするのと同じこと。 $ ./pq_benchmark.pl 1000 -3
ステートを破棄して高速になる理由
私の環境でベンチマークスクリプトを引数無しで実行すると次のような結果になりました:
1000文字に対して3秒実効する。 $ ./pq_benchmark.pl
Benchmark: running mache + , mache ?>, not mache + , not mache ?> for at least 3 CPU seconds...
mache + : 3 wallclock secs ( 3.14 usr + 0.01 sys = 3.15 CPU) @ 403200.00/s (n=1270080)
mache ?>: 3 wallclock secs ( 3.17 usr + 0.00 sys = 3.17 CPU) @ 389251.10/s (n=1233926)
not mache + : 2 wallclock secs ( 3.13 usr + 0.00 sys = 3.13 CPU) @ 196736.74/s (n=615786)
not mache ?>: 3 wallclock secs ( 3.23 usr + 0.00 sys = 3.23 CPU) @ 449383.90/s (n=1451510)
Rate not mache + mache ?> mache + not mache ?>
not mache + 196737/s -- -49% -51% -56%
mache ?> 389251/s 98% -- -3% -13%
mache + 403200/s 105% 4% -- -10%
not mache ?> 449384/s 128% 15% 11% --
------------------------------
Perl Version: 5.008008
string length: 1000
------------------------------
このスクリプトでは次の四つのパターンで速度を競います:
x+m (?>x+)m x+n (?>x+)n
末尾が m となっているものがマッチするパターンで、n はマッチしないパターンです。
結果を見比べてみるとマッチする場合はそれほど差はありません:
mache ?> 389251/s 98% -- -3% -13% mache + 403200/s 105% 4% -- -10%
しかし、マッチしない場合は倍以上の差があります:
not mache + 196737/s -- -49% -51% -56% not mache ?> 449384/s 128% 15% 11% --
これは、文字の比較をする位置としてステートを保持しているかどうかで、バックトラックが多いか少ないかの違いがある為です。
例えば次の文字列に対してマッチするか試すとき:
xxxxxm
次のパターンがマッチします:
x+m (?>x+)m
仮に次のようなアンダーバーで表したステートがあると想像してください:
_x_x_x_x_x_m
マッチする場合は、x+ でも (?>x+) でも始めに x の文字列がマッチして:
パターン: x+m (?>x+)m 文字列: xxxxxm
最後に末尾の m がマッチします:
パターン: x+m (?>x+)m 文字列: xxxxxm
左から順にマッチ成功しており、後戻りして試すバックトラックは必要ありません。
次に、マッチしないパターンは x の文字列がマッチした後、末尾の n がマッチしません:
パターン: x+n (?>x+)n 文字列: xxxxxm
この n がマッチかったとき x+ のパターンではステートが残っています:
パターン: x+n 文字列: _x_x_x_x_x_m
これに対して (?>x+) ではステートが残っていません:
パターン: (?>x+)n 文字列: xxxxx_m
x の文字列がマッチしたときに、アトミックグループ(?>)の中にあるステートは破棄されているので、バックトラックは行われません。
しかし、x+ のパターンでは一つ前のステートに戻り:
_x_x_x_x_x_m
5番目のx が n とマッチするか試すのです:
パターン: x+n 文字列: xxxxx_m
正規表現エンジンは比較を繰り返すだけなので、バックトラックしながら最終的にマッチするものが無いと判定するまで続けられます。
以上のように、後ろに x しかないので n があるかを探すのは無駄だとはっきりしている状況では、無駄なステートを破棄してバックトラックを避けることでマッチしないという判定が速くなるという訳です。
ベンチマークに関する注意
これまでの説明から、アトミックグループにした方が高速になると鵜呑みにした方。
次のベンチマーク結果にご注目ください:
10文字に対して3秒実効する。 $ ./pq_benchmark.pl 10
Benchmark: running mache + , mache ?>, not mache + , not mache ?> for at least 3 CPU seconds...
mache + : 3 wallclock secs ( 3.25 usr + 0.00 sys = 3.25 CPU) @ 1613600.31/s (n=5244201)
mache ?>: 3 wallclock secs ( 3.15 usr + 0.00 sys = 3.15 CPU) @ 1390154.29/s (n=4378986)
not mache + : 2 wallclock secs ( 3.13 usr + 0.00 sys = 3.13 CPU) @ 2798077.64/s (n=8757983)
not mache ?>: 3 wallclock secs ( 3.17 usr + 0.00 sys = 3.17 CPU) @ 3074657.41/s (n=9746664)
Rate mache ?> mache + not mache + not mache ?>
mache ?> 1390154/s -- -14% -50% -55%
mache + 1613600/s 16% -- -42% -48%
not mache + 2798078/s 101% 73% -- -9%
not mache ?> 3074657/s 121% 91% 10% --
------------------------------
Perl Version: 5.008008
string length: 10
------------------------------
これは x の文字数を10にして実効した結果です。
マッチしないパターンでは相変わらずアトミックグループにした方が高速ですが、その差は大きくありません:
not mache + 2798078/s 101% 73% -- -9% not mache ?> 3074657/s 121% 91% 10% --
さらに、マッチしたパターンでは差が開いて遅くなっています:
mache ?> 1390154/s -- -14% -50% -55% mache + 1613600/s 16% -- -42% -48%
実際に正規表現を使用する場面でマッチする処理の方が多いなら、アトミックグループにしない方が高速という結果になってしまいます。文字列の長さやマッチする割合によって使い分ける必要もあるということですね。
今回はアトミックグループを利用した正規表現の効率化について、抽象的な説明をしたに過ぎません。詳説 正規表現でも十分言及されていますが、利用する場面に合わせたベンチマークでお確かめください。
オライリー・ジャパン - 詳説 正規表現 第3版 - 目次より抜粋:
6章 効率のよい正規表現の作り方 6.1 酔いも醒めるようなサンプル 6.1.1 簡単な変更――効き足を先に 6.1.2 効率と正しさ 6.1.3 さらに改良――欲張りな動作の局所化 6.1.4 現実性のチェック 6.2 バックトラックの全体像 6.2.1 POSIX NFAの余分な仕事 6.2.2 マッチ不成功のときに必要な仕事 6.2.3 より厳密に 6.2.4 選択は高くつく場合がある 6.3 ベンチマークテスト 6.3.1 何を計測しているのかを把握する 6.3.2 PHPによるベンチマークテスト 6.3.3 Javaによるベンチマークテスト 6.3.4 VB.NETによるベンチマークテスト 6.3.5 Rubyによるベンチマークテスト 6.3.6 Pythonによるベンチマークテスト 6.3.7 Tclによるベンチマークテスト 6.4 よく見られる最適化 6.4.1 タダでは手に入らない 6.4.2 実装による違い 6.4.3 正規表現適用のメカニズム 6.4.4 適用前の最適化 6.4.5 トランスミッションの最適化 6.4.6 正規表現自体の最適化 6.5 より高速な正規表現を書くためのテクニック 6.5.1 常識的なテクニック 6.5.2 リテラルテキストを目立たせる 6.5.3 アンカーを目立たせる 6.5.4 最小量指定子と最大量指定子の使い分け 6.5.5 複数の正規表現への分割 6.5.6 先頭文字の識別の模倣 6.5.7 アトミックグループと絶対最大量指定子を使う 6.5.8 エンジンをマッチに導く 6.6 ループ展開 6.6.1 方法1：過去の経験に基づいて正規表現を組み立てる 6.6.2 本物の"ループ展開"パターン 6.6.3 方法2：トップダウンの視点 6.6.4 方法3：インターネットのホスト名 6.6.5 所見 6.6.6 アトミックグループや絶対最大量指定子を使った方法 6.6.7 ループ展開の簡単なサンプル 6.6.8 Cコメントのループ展開 6.7 スムーズに流れる正規表現 6.7.1 マッチを導く救いの手 6.7.2 正規表現を適切な方向に導いて高速化する 6.7.3 最後に 6.8 まとめ：考えよ！
