krの日記： Haskellで速いwcを書いてみよう(7)

前のエントリの続きです。

前回のプログラムは、メモリ不足に陥って動きませんでした。何が悪かったかと言うと、wc'の各引数の評価が遅延され、 ファイルを読み込んでいる間、1文字毎に

(((( …… )+ 1) + 1) + 1)

という調子で未評価の式が溜ったまま延びていたのです。この式は、プログラムの最後で行数・単語数・文字数を表示する際に、 一気に評価されるハズではあるのですが、そこまで遅延されると未評価の式を保持するメモリが足りなくなります。

というわけで、ここで最初のチューニングは、「遅延させたくない部分を先に評価させる」ようにすることです。

-- prog7
import Data.Char

wc:: String -> ( Int, Int, Int )
wc = wc' !$ 1 !$ 0 !$ 0 !$ 0
    where
      infixl 0 !$               -- left-associative version of $!
      (!$):: (a -> b) -> a -> b
      f !$ x = x `seq` f x
      wc':: Int -> Int -> Int -> Int -> String -> (Int, Int, Int)
      wc' s nl nw nc [] = (nl, nw, nc)
      wc' s nl nw nc ('\n' : cs) = (wc' !$ 1 !$ (nl + 1) !$ nw !$ nc + 1) cs
      wc' s nl nw nc (c : cs)
          | isSpace c = (wc' !$ 1 !$ nl !$ nw !$ nc + 1) cs
          | otherwise = (wc' !$ 0 !$ nl !$ nw + s !$ nc + 1) cs

main関数はまったく変わらないので、省略しています。このプログラムをprog7とします。

普通の正則評価オペレータは$!ですが、 これは右結合で、今回は具合が悪いので、wcの中でだけ左結合のオペレータを定義しています。 また、wc'の引数の内、最後の引数は値渡しにしていないことに注意しましょう。 ここは遅延評価の利点を使って、余分な入力をメモリに読み込まないようにしなくてはいけません。

では実行時間を測ってみましょう。

% time ./prog7 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
0.769u 0.001s 0:00.80 95.0%     338+265k 0+0io 0pf+0w
0.763u 0.007s 0:00.80 95.0%     345+271k 0+0io 0pf+0w
0.769u 0.001s 0:00.79 96.2%     338+265k 0+0io 0pf+0w
0.762u 0.008s 0:00.79 96.2%     321+252k 0+0io 0pf+0w
0.762u 0.007s 0:00.79 96.2%     335+263k 0+0io 0pf+0w

実時間でおよそ0.79秒というところでしょうか。 C++版がおよそ0.71秒でしたから、それには惜しくも及びませんでしたが、 tanakh氏のHaskellチューニング版がおよそ3.79秒だったのと比べれば、 かなり良い成績と言えるかと思います。もっとも、tanakh氏は「チューニングしないといけない部分を分離」したいとおっしゃっていますので、 もしかすると、速度は犠牲にしても何かHaskellらしい実装方法はないかと模索していたのかもしれません。とはいえ、とりあえず速く走らせたいだけなら、難しいことは考えずに、素直に簡単なアプローチを採るのが(少なくとも今回は)良かったようです。

第2版でそれなりに性能向上したのに味をしめ、更に高速化できないか試みてみます。

ということで、続きます。