GHCの最適化

『Beautiful Code』にカーニハンの正規表現マッチャに関するエッセイがのってるのを思い出し，さっそく読んだ。どうやら，『プログラミング作法』の最終章にも正規表現について書かれているらしい。もちろん，私は『プログラミング作法』も持っているので，読もうと思ったのだが，本棚に見当たらない。暇なときに読もうと思って会社に持っていったんだった。。。はあ，ほとんど読む機会がないので家に持って帰ってくるか。
エッセイにのっているマッチャは実装している記法は次の５つ（Beautiful Code, P.3より）。

• c（文字cそのもの）
• .
• ^
• $
• *

カーニハン先生が言うには，正規表現の95%はこの５つで成り立ってるそうな。私がつくったやつはそのうちの２つしか実装してないんだが。
とりあえず，素で忘れていた"."を実装してみる。任意の１文字なので，

do { Parser.char '.'
   ; return (Parser.satisfy (const True))
   }

んな感じ。実行結果は下記のとおり。

$ time ./Main "a.*a" prtrt11.txt
6648

real	0m1.876s
user	0m1.836s
sys	0m0.030s

任意の１文字は別にParser側にあっても良さそうな機能。こんな具合に。

any :: -> Parser a a
any = Parser (\xs -> case xs of
                       [] -> []
                       (x:xs) -> [(xs,x)])

実行結果。

$ time ./Main "a.*a" prtrt11.txt
6648

real	0m1.086s
user	0m1.064s
sys	0m0.020s

時間がだいぶ違う。あまり変わらないと思ったのだが。と，ここで思い出したのが最適化。最適化についてなんにも考えてなかった（いや，正確にはなんにも考えていなかったわけではない。GHCは最適化をしてくれているとなぜか信じていたのだ。最適化オプションも与えていないのに。。。なぜだ！？）。
というわけで，anyを書き換えて，-O2でコンパイル。

any :: Parser a a
any = satisfy (const True)

$ time ./Main "a.*a" prtrt11.txt
6648

real	0m1.028s
user	0m0.959s
sys	0m0.036s

おお，だいぶ違う。最適化すげー，という話でした。

ビューティフルコード (THEORY/IN/PRACTICE)

プログラミング作法