Perl正規表現「$& $` $'」のオーバーヘッド検証

2006/07/31(月)Perl正規表現「$& $` $'」のオーバーヘッド検証

プログラム::Perl

$&によるオーバーヘッドとは？

perlfaq6によると

なぜ $&とか$`、$'といった変数を使うとプログラムが遅くなるのですか?

プログラムのどこかでそういった変数が使われているのを見つけてしまうと、Perlはすべてのパターンマッチに対してそれに対処することをやらなければなりません。同様のからくりが、$1、$2などを使ったときにも行なわれます。このためすべての正規表現において、部分正規表現を捕捉するために同じコストがかかることになります。しかし、スクリプト中で $&などを全く使っていないのであれば、正規表現は部分正規表現を捕捉して不利になるようなことはしません。ですから、可能であれば $&や$'、$`を使わないようにすべきなのですが、それができないのであれば(一部のアルゴリズムはこれを使うのが便利なのです)、一度これらの変数を使ってしまったら好きなように使いましょう。なぜなら、罰金はすでに払ってしまったのですから。アルゴリズムの中にはこういった変数を使うことが適切であるものがあるということに注意してください。リリース5.005では、$&はもはや“高価な”ものではありません。

と書かれています。adiaryでは$' $` を多用しているので*1今更なのですが、使わないことでどれくらいの速度アップが見込めるか、実際に検証してみたいと思います（以下Perl5.8.xにて検証）。

$&等は実際どの程度のオーバーヘッドを発生するか？

この記事のソースを$textに代入した状態で、

$test{test} = sub {
	my $x = "\n" . $text;
	$text =~ s/\W/\./g;
};

のベンチマークを取ってみました。

同一ソース中に"$&"を書いた場合
test1:  3 wallclock secs ( 3.27 usr +  0.01 sys =  3.28 CPU) @ 304.76/s (n=1000)
同一ソース中に"$&"などを書かない場合
test2:  1 wallclock secs ( 1.52 usr +  0.00 sys =  1.52 CPU) @ 659.79/s (n=1000)
同一ソース中に"$&"などを書かず、$`などが使われたソースをrequireした場合
test3:  3 wallclock secs ( 3.27 usr +  0.01 sys =  3.28 CPU) @ 304.76/s (n=1000)

比較として、ほかの場所では$&などは使わずに、次のようなソースも検証してみました。

sub {
	my $x = $text;
	$text =~ s/\W/$&/g;
};
結果：7 wallclock secs ( 6.77 usr +  0.00 sys =  6.77 CPU) @ 147.64/s (n=1000)
sub {
	my $x = $text;
	$text =~ s/(\W)/$1/g;
};
結果：7 wallclock secs ( 7.35 usr +  0.00 sys =  7.35 CPU) @ 136.03/s (n=1000)

ここまでの結果をまとめると。

ソース自身の他、使用しているライブラリの１ヶ所でも $` $& $' が使われていれば、Perlの正規表現は常にそれらを返すようになり（正規表現を使用しているすべての場所で）オーバーヘッドが発生する。
$&等によるオーバーヘッドは１回のマッチング当たり最大２倍程度、Perlの正規表現式が複雑になればこの差は縮むと思われる。

$` や $' を置き換えたらどうなるか？

次のようなテストプログラムで検証しました。test1, test2 にそれぞれコメントアウトしてから検証しています。@aryには15件ほどのデータが入っています。

foreach(@ary) {
	if ($_ =~ /::/) {
		my $category_main = $`;
		my $category_sub  = $';
	}
}
●結果：1 wallclock secs ( 1.18 usr +  0.00 sys =  1.18 CPU) @ 8476.82/s (n=10000)
foreach(@ary) {
	if ($_ =~ /^(.*?)::(.*)$/) {
		my $category_main = $1;
		my $category_sub  = $2;
	}
}
●結果：2 wallclock secs ( 1.62 usr +  0.00 sys =  1.62 CPU) @ 6183.57/s (n=10000)

やはり、$` $' を使った方が速いという結果になりました。ただこれも正規表現が複雑になればなるほど、差は縮まっていくものと思われます。ただし $' などの与える影響の範囲はプログラム全体の正規表現に及ぶので、実際のプログラムを書いたときどちらが高速かは２パターン書いて比べてみないと分からないという結論になると思います。

おまけで、こんな実験もしてみました。/gとposについてはこちら。

foreach(@ary) {
	if ($_ =~ /::/g) {
		my $category_main = substr($_, 0, pos($_));
		my $category_sub  = substr($_, pos($_)+2);
		pos($_) = 0;	#記事初出時、この行がない不正確な計測していました。 
	}
}
●結果：1 wallclock secs ( 1.46 usr +  0.00 sys =  1.46 CPU) @ 6844.92/s (n=10000)

$1 $2を使うよりは速いですね。$` $'より遅くなってしまいますが、他の正規表現に影響を与えないという意味では良いかもしません。ただ$` $'よりもソースが分かりにくくなるので微妙ですね……。

結論としては

$` $'を使わないで済むのならば、なるべく使わないようにして、$` $'を使うのがスマートならば気にせず使えという感じですね。無理矢理$` $'を排除しても、その正規表現自体が遅くなっては意味がありませんからね。

ドキュメントにあるとおり、

リリース5.005では、$&はもはや“高価な”ものではありません。

古いPerlではまた事情が違ってくるでしょう(^^::