krの日記： Haskellで速いwcを書いてみよう(10) 6
前回のエントリの続きです。
もうちょっと高速化できないか考えてみます。
どんなプログラムでも、高速化の要は「頻繁に実行される箇所を少しでも速くする」ことです。 そういう点では、tanakh氏が試みていたように、文字入力処理の高速化を図るのは正しい方向性と言えます。 しかし、そこに手をつけると、一通りの入出力処理をすべて再実装することになり、大変な変更が必要になるのは目に見えています。
もっと楽をして速くできる箇所があれば、それに越したことはありません。そんな目で再びprog8を見てみると、 整数の加算やリストの分解と言った、比較的軽い処理の中にあって、なんとなくisSpaceが目立っていることに気付きました。
isSpaceはCのisspace(3)と同様な文字種判定関数ですが、Haskellは建前上Unicode文字を扱うことになっているので、 実際にはUnicode文字に対するiswspace(3)と同様な処理をしていることになります。ちなみにghcではISO-8859-1の範囲の空白文字をHaskellで判定した後、その他の文字をすべて、Cで書かれた判定関数に回してしまいます。ここは外部関数呼び出しになるので、頻繁に呼び出すとそれなりのコストが掛かるのではないかと想像されます(本当かどうかは未確認(_ _))。
どうせ今回のwcは8ビット文字前提ですし、ここを端折った処理にしてしまえば高速化できないでしょうか?
というわけで書いてみたのが以下のコードです。
{-# OPTIONS_GHC -fglasgow-exts #-}
-- prog9
import GHC.Base
wc:: String -> ( Int, Int, Int )
wc = wc' 1# 0# 0# 0#
where
isSpace:: Char -> Bool
isSpace ' ' = True
isSpace '\t' = True
isSpace '\n' = True
isSpace '\r' = True
isSpace '\f' = True
isSpace '\v' = True
isSpace _ = False
wc':: Int# -> Int# -> Int# -> Int# -> String -> (Int, Int, Int)
wc' s# nl# nw# nc# [] = (I# nl#, I# nw#, I# 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は同じなので省略しています。このプログラムをprog9とします。 isSpaceを、かなり直截的な内部関数に置き換えた以外は、ほぼ何も変わっていません。 isSpaceのためにimportしていたData.Charモジュールは不要になりました。実行時間を測ってみましょう。
% time ./prog9 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
0.103u 0.023s 0:00.13 92.3% 298+272k 0+0io 0pf+0w
0.105u 0.022s 0:00.13 92.3% 317+286k 0+0io 0pf+0w
0.120u 0.007s 0:00.13 92.3% 317+289k 0+0io 0pf+0w
0.103u 0.023s 0:00.13 92.3% 298+272k 0+0io 0pf+0w
0.110u 0.017s 0:00.13 92.3% 298+269k 0+0io 0pf+0w
実行時間は実時間で0.13秒のようです。prog8がおよそ0.50秒でしたから、 isSpaceの改良だけで案外と速くなるものです。 ところで、C版がおよそ0.18秒でしたから、 おや、どうしたことでしょう、いつの間にかC版より速くなってしまいました。:-)
最初の版prog6と比べてみても、prog9には、さほどびっくりするような変化はありません。 プログラムの基本構造にはほぼ違いはなく、必要な正格評価のための修飾がちりばめられたものの、動作を理解するのは相変わらず簡単です。
もちろん、まだまだチューニングできる箇所は残っています。このエントリの冒頭で挙げた入出力処理の高速化などもその一つでしょう。 その辺りの高速化については、Library/Streamsとして、より一般的で高機能な形で取り組んでいるプロジェクトがあるので、その成果を取り入れてみるのも一案です。
でも、まあ、Cより速くなったということで、個人的にはこの辺りで満足してしまいました。
# 定数オーダとはいえ、メモリフットプリントはCより大きいため、
# 「HaskellがCに勝った」とはまでは言えないかもしれせんが。:-)
一つ心残りは、最初のprog6の時点ですでに少々Haskellらしくないコードになっている点です。気がむいたら、その点もうちょっとどうにかできないか、考えてみたい気もします。でも、まあ今回はここまでです。
長い一連のエントリを読んで下さり有難うございました。
# 初めて/.Jの日記を書いたけど、最初から(だけ)飛ばしすぎだ……。