まだ重たいCMSをお使いですか?
毎秒1000リクエスト を捌く超高速CMS「adiary

2006/11/05(日)perlの長所と短所

所詮Perl?

ネットをみていると「所詮Perl」的な発言をみかけるのですが、いやいやマテマテマテマテ。かと思うと、はてなmixiもPerlだ! 的な肯定意見があったりして、それもまた視点としておかしいような。

Perlの長所

  • Rubyなどのスクリプト言語と比べ速く動作する(時に数倍以上)。
  • CやC++に比べはるかに開発が容易。
  • CやC++に比べどうしても遅くなるものの、重い計算をループ処理させなければ実用上そこまで大きく変わらない。
  • PHPに比べ、MVC的なソース(ソースとHTML部分を分離させるコード)を書くのに適当である。
  • 世の中のほとんどのサーバで動作する

という特徴があります。adiaryの基礎になっているスケルトンシステム(Satsuki-system)開発時、本当はRubyも検討したんですが、簡単なテストスクリプトをいくら走らせてもRubyの処理速度はPerlのそれに到底及びません。Perlは隅々まで最適化が行き届いていて、うまく書いてやれば相当早く動作します。

Perlの短所

  • 言語仕様が非常にきたない(アセンブラおなじくスクリプト言語として原始的)。
  • 標準ではCGIとして動作させるため、スクリプトとしての起動が遅い。処理が遅いのではない

ほとんどこの2点に尽きると思います。1つめは対Rubyで考えると非常に分かりやすい。互換性を保ってきた結果が現在のPerl 5+オブジェクト指向という複雑な状況なんですが、それでもこのゆるゆるのオブジェクト指向がまた逆手に取ってうまく使うと非常に効率的なシステムが作れます。

2つめはネットを検索すると沢山出てきますが、「PHPはPerlより速い」という意味での速いです。起動が速い。ネット上の共有レンタルサーバでなければmod_perlなどを使うことで解決できますし、うまく書けばCGIとして動かしてもそこまで重くなりません。*1

結局

Perlってのは使い倒せば大規模開発にも十二分にも耐えられる言語です。ただこの辺は適切に判断すべきで、仕様をきっちり決めることで綺麗なメンテ性を取るならRubyもありですし、Webアプリとして手軽に作りたいならPHP、処理速度と開発効率を同時に求めるならPerlということになると思います。*2

*1 : 起動=コンパイルが遅いということは、ライブラリが必要になるまで極力ロードしないことで改善できるということです

*2 : おまけに配布を考えなければCのルーチンを呼び出すことで処理速度は必要な部分でいくらでも速められますしね。

adiaryを開発する人間としては

「早くPerl6出ないかなぁー」ってのが本音です(笑) Satsuki-systemが全面書き直しになりそうで怖いのは怖いけども(苦笑)

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

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

perlfaq6によると

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

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

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

*1 : 現在のバージョンでは全く使用していません

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

この記事のソースを$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)

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

  • ソース自身の他、使用しているライブラリの1ヶ所でも $` $& $' が使われていれば、Perlの正規表現は常にそれらを返すようになり(正規表現を使用しているすべての場所で)オーバーヘッドが発生する。
  • $&等によるオーバーヘッドは1回のマッチング当たり最大2倍程度、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)

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

おまけで、こんな実験もしてみました。/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ではまた事情が違ってくるでしょう(^^::

2006/07/29(土)Perlの迷信

迷信というか勘違いなのか、PerlのVersionがあがって最適化されたのか。Perl 5.8にて確認。

foreach(0..n) vs for(my $i=0; $i<n+1; $i++)

前者は (0..n) の配列が作られるのでその分遅くなるだろうと思っていました。後述しますが、keys(%HASH) は配列生成が発生するので必ずしも効率がよくないという話を読んだりもしていたので。ところが実際に計測してみると……

use strict;
use Benchmark;
my %test;
my $count = 10000;
$test{test1} = sub {
	my $x; foreach(my $i=0; $i<100; $i++) { $x+=$i; }
};
$test{test2} = sub {
	my $x; foreach(0..99) { $x+=$_; }
};
$test{test3} = sub {
	my $x; foreach my $i (0..99) { $x+=$i; }
};
timethese($count, \%test);

実行結果

test1:  3 wallclock secs ( 3.13 usr +  0.00 sys =  3.13 CPU) @ 3194.89/s (n=10000)
test2:  3 wallclock secs ( 2.35 usr +  0.00 sys =  2.35 CPU) @ 4255.32/s (n=10000)
test3:  2 wallclock secs ( 2.44 usr +  0.00 sys =  2.44 CPU) @ 4098.36/s (n=10000)

ループ変数を指定したとしても、foreach の方が速いです。多分 perl の最適化が効いてるんでしょうねぇ……。固定数ではなく、配列に対してforeach(0..$#ary)としても結果は一緒でした。

keys(%hash) は遅い?

ハッシュのすべてのkeyからなる配列を作る keys は遅いといわれ、実際perlのマニュアルにも遅いかもしれないとかかれています。ですから

foreach(keys(%ENV)) { }

ではなく

while(my($k,$v)=each(%ENV)) { }

とした方が効率がいいとばかり思っていました。使う側としてはkeys(%HASH)の方が楽なのですが、eachを使うように心がけていました。ところが、次のようにベンチマークをとってみると、

$test{test1} = sub {
	my $x;
	while(my ($k,$v) = each(%ENV)) { if ($v) { $x++; } }
};

$test{test2} = sub {
	my $x;
	foreach(keys(%ENV)) { if ($ENV{$_}) { $x++; } }
};
timethese($count, \%test);

実行結果

test1:  2 wallclock secs ( 2.25 usr +  0.00 sys =  2.25 CPU) @ 4444.44/s (n=10000)
test2:  2 wallclock secs ( 1.51 usr +  0.00 sys =  1.51 CPU) @ 6622.52/s (n=10000)

これまた非常に悲しい結果に。$ENV は23個ぐらいしか定義されてないので、要素数の多いハッシュならどうなるか試してみました。

my %h;
foreach(0..999) {
	$h{crypt($_, '00')} = $_;
}

として任意数のハッシュを生成します。実行結果

●10要素
test1:  1 wallclock secs ( 0.95 usr +  0.00 sys =  0.95 CPU) @ 10526.32/s (n=10000)
test2:  1 wallclock secs ( 0.66 usr +  0.00 sys =  0.66 CPU) @ 15151.52/s (n=10000)
●100要素
test1:  9 wallclock secs ( 8.77 usr +  0.00 sys =  8.77 CPU) @ 1140.25/s (n=10000)
test2:  6 wallclock secs ( 5.73 usr +  0.00 sys =  5.73 CPU) @ 1745.20/s (n=10000)
●1000要素(計測ループ数1000回)
test1:  9 wallclock secs ( 8.85 usr +  0.00 sys =  8.85 CPU) @ 112.99/s (n=1000)
test2:  7 wallclock secs ( 6.72 usr +  0.00 sys =  6.72 CPU) @ 148.81/s (n=1000)
●10000要素(計測ループ数100回)
test1: 10 wallclock secs (10.09 usr +  0.00 sys = 10.09 CPU) @  9.91/s (n=100)
test2:  8 wallclock secs ( 8.62 usr +  0.00 sys =  8.62 CPU) @ 11.60/s (n=100)
●100000要素(計測ループ数10回)
test1: 10 wallclock secs (10.27 usr +  0.00 sys = 10.27 CPU) @  0.97/s (n=10)
test2:  9 wallclock secs ( 8.99 usr +  0.02 sys =  9.01 CPU) @  1.11/s (n=10)

10万要素でも逆転する様子を見せません(汗) 通常10万要素なんてあり得ないわけで、keysを積極的に使うべしという結論になりました。

結論

どちらも、わざわざ速くするために書きにくい方を選んで、結果的に遅くしてたという情けない結果になりました(汗) んー、こういう基礎研究的なことは悩んだときにきちんとやった方がいいんですねぇ(汗*1

それと、アセンブラ好き好き(謎)な人間には、インタプリタの実行速度は若干奇妙に映ります。まあ、こんなもんなんでしょうけど(笑

*1 : 実際問題として、これらを全部修正したところで全体で1ms速くなるかといわれたら疑問ですけど、でもなんか悔しい(笑)

2006/07/28(金)マニュアルから知らなかった関数

perlの関数メモ

知らなかった関数から抜粋。もっと早く読んでおけばよかったなぁ。

lc/uc

最初が小文字変換、後者が大文字変換。要するに次と等価。

$x=lc($x) : $x =~ tr/A-Z/a-z/;
$x=uc($x) : $x =~ tr/a-z/A-Z/;

study SCALAR

何回も文字列に対するパターンマッチを行なうアプリケーションで、そのような文字列 SCALAR を予め学習しておきます。(中略)別のスカラを study した場合には、以前に学習した内容は「忘却」されてしまいます。

(この study の仕組みは、まず、検索される文字列内のすべての文字のリンクされたリストが作られ、たとえば、すべての 'k' がどこにあるかがわかるようになります。各おのの検索文字列から、C プログラムや英語のテキストから作られた、頻度の統計情報に基づいて、もっともめずらしい文字が選ばれます。 この「めずらしい」文字を含む場所だけが調べられるのです。)

日本語の場合……難しいところですが、同じ(短めの)文字列に対して予めリンクリストを作っておけば、次からのパターンマッチが高速化されるようです。実際には計測して速いかどうか確認してから使えと書いてあります。

ループ関連

redo

redo コマンドは、条件を再評価しないで、ループブロックの始めからもう一度実行を開始します。 continue ブロックがあっても、実行されません

ラベル指定 last/next/redo

last などのコマンドは、ラベルによって抜けるループを指定できるようです。多段ループから抜けたいときいつも

my $z;
foreach my $x (1..9) {
  my $flag;
  foreach my $y (1..9) {
    if ($x*$y>50) { $z=$x*$y; $flag=1; last; }
  }
  if ($flag) { last; }
}

と書いてたのですが、ラベル指定を使えば

my $z;
OUT_LOOP:
foreach my $x (1..9) {
  foreach my $y (1..9) {
    if ($x*$y>50) { $z=$x*$y; last OUT_LOOP; }
  }
}

と書けばよかったようです。

正規表現/パターンマッチ

$&

$cookie_val =~ s/(\W)/ '%' . unpack('H2', $1)/eg;

とかやって URI エンコードをするのは有名ですか、わざわざ $1 のフレーズホルダーを使わなくても、

$cookie_val =~ s/\W/ '%' . unpack('H2', $&)/eg;

とすればよかったようです。$&というのはマッチした文字列そのものを示す特殊変数で、マッチ部より手前と後ろを示す $`, $' を使えば、

$cookie_val == "$`$&$'"

はマッチングが成功すれば常に成り立つことを意味してます。

:$&は正規表現の動作速度を低下させる恐れがあります。URIエンコード程度ならば$1を使いましょう(コメントでの指摘ありがとうございま)。→参考

m//;

m//; はマッチングをとる演算子で、何も付けずに//;したときと一緒。つまりは

if ($str =~ /<(\w+)>(.*?)<\/\w+>/) { print "$1 = $2\n"; }

としたときは暗黙に m が指定されているということです。/ がセパレーターなので\/エスケープしなければなりません。しかし置換表現ならば、

$str =~ s#<(\w+)>(.*?)</\w+>#print "$1=$2\n"#eg;
$str =~ s|<(\w+)>(.*?)</\w+>|print "$1=$2\n"|eg;
$str =~ s!<(\w+)>(.*?)</\w+>!print "$1=$2\n"!eg;
$str =~ s[<(\w+)>(.*?)</\w+>][print "$1=$2\n"]eg;
$str =~ s{<(\w+)>(.*?)</\w+>}{print "$1=$2\n"}eg;

などとセパレーターを変更することで、/をエスケープする必要がないわけです。でもマッチングを取るときは

if ($str =~ |<(\w+)>(.*?)<\/\w+>|) { print "$1 = $2\n"; }

とかできないで不便だなぁと思ってたのですが、つまり次みたいにすればよかったようです。

if ($str =~ m|<(\w+)>(.*?)<\/\w+>|) { print "$1 = $2\n"; }

q//;

q//; は正規表現をコンパイルした状態で保存する演算子です。正規表現をあたかもオブジェクトのように扱えます。/o オプションを使えば正規表現をコンパイルして保持できるのですが、2度とその場所の正規表現を変更できなくなるので使えませんでした。*1

@urlsを正規表現が格納された配列、@aryがマッチング処理をする配列だとします。

my $match;
LABEL: foreach my $line (@ary) {
  foreach(@urls) {
    if ($line =~ /$_/) { $match=1; last LABEL; }
  }
}

とすると、中のif文を実行する度に正規表現がコンパイルされ、@ary が大きいときに大変なロスとなります。

# 先にコンパイルしておく
foreach(@urls) { $_ = qr/$_/; }
my $match;
LABEL: foreach my $line (@ary) {
  foreach(@urls) {
    if ($line =~ /$_/) { $match=1; last LABEL; }
  }
}

とすることで、正規表現のコンパイルが1度のみとなり大きな速度向上が見込めます。ちなみにこのときのコンパイルされた正規表現式はref($str)に対して'Regexp'を返します。

my $reg = qr#<(\w+)>(.*?)</\w+>#;
print "$reg\n", ref($reg), "\n";

実行結果

(?-xism:<(\w+)>(.*?)</\w+>)
Regexp

pos SCALAR

対象の変数に対して、前回の m//g が終了した場所のオフセットを返します。また、代入することでオフセットを変えることも可能です。

と書かれています。/g 付きの正規表現は、連続マッチングを取るオプションですが、前回マッチングを取った場所より後ろが次のマッチング開始位置になります。無限ループなどにならない、至極当然の方式なのですが、極希にこの仕様が困ったことになります。

my $str = <<TEXT;
>>
1
<<
>>
2
<<

>>
3
<<
TEXT

という文字列から「>>のみの行で始まり<<のみの行で終わる」ブロックを抽出することを考えます。こののみの行ってのが厄介です。

$str = "\n$str";  # 前処理*2
$str =~ s/\n>>\n(.*?)\n<<\n/print "$1 "; "\n"/esg;

とすれば、うまく行きそうに見えます*3。ですが実際には、

1 3 

と見えて表示されません。というのも、1つめのブロックとマッチする最後の"\n"と、2つめのブロックをマッチするときの最初の"\n"が同じものを示しているためです。ここで pos 関数の出番です。

while($str =~ m|\n>>\n(.*?)\n<<\n|g) {
	print "$1(pos:", pos ($str), ")  ";
	pos($str) = length($`);
	$str = $` . "\n" . $';
}

とすれば、

1(pos:9)  2(pos:9)  3(pos:10)

となり正しく認識出来ます。

追記:もっとスマートな方法

前回マッチした部分とマッチする "\G" という要素を使えば、もっとスマートな方法で実現可能でした。

my $str = "aaa0bbb0ccc0ddd1eee0fff0ggg";
$str =~ s/(?:\G|0)(\w\w\w)0/
	print "$1\n";
	/eg;

実行結果は、

aaa [0]
bbb [4]
ccc [8]
fff [19]

また、(?:...|...)は$1などへの割り当てない部分正規表現で、マッチ部の割り当てという無駄な処理が減るので処理が効率化できます*4。また\Gを使うことで ^\w\w\w とマッチする効果があり、前処理として\nを追加する必要がなくなります。

.......ソース書きなおそ(笑

*1 : クロージャと /o オプションを組み合わせればいいかなーとか最初思ってたのですが、コンパイルしてしまう方法の方がよっぽどスマートでした

*2 : ^を使った正規表現式を書けばいいのですが、正規表現の式が2倍になるより、予め前処理した方が効率的なのでこうしています

*3 : /e は置換文を実行するオプション。/gは連続置換するオプション。/sは改行を含めてマッチングするオプション。

*4 : 知らなかった

2006/07/28(金)map関数の使い方

perl の map 関数の使い方

map関数の説明は他を参照してもらうとして。

$categories->[n] = { cat_ID  => カテゴリID, cat_name => カテゴリ名 };
$post2cat->[n]   = { post_id => 記事ID,  category_id => カテゴリID };

という2つのハッシュリファレンスからなる配列があったとき、記事ID→カテゴリ名という変換テーブル(ハッシュ)を作る方法。

my %cat2name  = map { $_->{cat_ID}  => $_->{cat_name} } @categories;
my %post2name =	map { $_->{post_id} => $cat2name{ $_->{category_id} } } @post2cat;

とすると、$post2name{記事ID} → カテゴリ名となります。でもこの場合、@post2cat の最後に出た要素が優先されるので、最初に出た要素を優先するために、

map { $post2name{ $_->{post_id} } ||= $cat2name{ $_->{category_id} } } @post2cat;

と書けます。

foreach(@ary) で回してるものは、mapに置き換えた方がスマートかつ効率的かも知れもません。

grep

grepは別に正規表現なだけではなく、格納条件を指定することもできるらしい。

my @newary = grep { $_ > 100 } @ary;

my @newary;
foreach(@ary) {
	if ($_ > 100) { push(@newary, @ary); }
}

と等価らしい。grep コマンドの印象が強かったから全然気づかなかった。

追記

んー便利だ。今まで foreach(@ary) で書いてたところが、いくつも書き直せそうだけど……まぁいいや。*1

とりあえず、まだ知らないことがありそうなのでPerl5の関数リストでも眺めておこう。

*1 : ハッカーのために可読性優先で書いてる部分もあったりするので。