krの日記： Haskellで速いwcを書いてみよう(8) 2
前回のエントリの続きです。
前回のprog7はそれなりの速度で走りましたが、もっと速くできないでしょうか。 いくつかの改善点を思い付きますが、ここではまずwc'のイタレーションを高速化することを考えてみます。
で、まあちょっと反則気味ではあるのですが、ここでghcの独自仕様部分を使ってみることにします。具体的には、unboxed typeを使って、 wc'の引数処理を高速化を試みます。これはてっとり早く言えば、HaskellのInt型でなく、Cのintと同様のビット表現を使うことにしちゃえということです。
{-# OPTIONS_GHC -fglasgow-exts #-}
-- prog8
import Data.Char
import GHC.Base
wc:: String -> ( Int, Int, Int )
wc = wc' 1# 0# 0# 0#
where
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は変わらないので今回も省略です。このプログラムをprog8とします。
このプログラム、前回のprog7よりむしろ最初に書いたprog6に似ています。 wc'の最初の4つの引数について、unbox型にしたおかげ(?)で、正格適用オペレータを使わずに、却って(見掛け上)簡単になりました。 その分、整数の加算などに特別な演算子を使わなくてはならなくなりましたが、例えばOCaml使いの人にとっては、むしろ親近感の湧く(?)コードになったかもしれません。:-)
実行時間を測定すると、こんなです。
% time ./prog8 < /usr/share/doc/en/books/handbook/book.txt
72266 323341 3196121
0.478u 0.007s 0:00.50 94.0% 337+264k 0+0io 0pf+0w
0.484u 0.001s 0:00.50 96.0% 346+272k 0+0io 0pf+0w
0.463u 0.022s 0:00.50 96.0% 346+272k 0+0io 0pf+0w
0.478u 0.007s 0:00.50 94.0% 342+268k 0+0io 0pf+0w
0.484u 0.002s 0:00.50 96.0% 346+272k 0+0io 0pf+0w
ということで、実時間でおよそ0.50秒です。C版の約0.18秒には及ばないものの、 C++版の約0.71秒は追い抜いて、Haskell版の方が速くなってしまいました。
もっと速くすることもできるでしょうか? まだいくつか速くできるポイントがありますが、それは一先ず置いておいて、ここでちょっと別の確認をしておきます。
ということで、更に続きます。
遅延評価を捨てたって事？ (スコア:0)
Re:遅延評価を捨てたって事？ (スコア:1)
確かに、一つ前のエントリ [srad.jp]の prog7からは、遅延させたくない箇所を一部だけ先行評価にしています。
では遅延評価を捨てたのか、というと、そういうわけでもありません。 入力文字列(ここではwc'関数の最後の引数)はあくまで遅延評価になっています。prog7からprog9まで一環してこの点は変えてません。 先行評価に負けたというよりは、 両方の戦略を適材適所で使い分けてます、という感じでしょうか。
もうちょっと中身に踏み込むと、 「普通」のHaskellは、基本的に「必要な時、必要な部分だけ」評価していきます。 このプログラムの場合だと、csのreductionと wc'の計算がそれぞれ対応して進んでいきます。 そうすると、「数を数える」という枝葉の部分が後回しになります (この計算結果はプログラム終了時にしか使わないので)。 とはいえ、はっきり言って「整数を1増やす」なんて処理は、 「後で計算できるように計算内容を積んでおこう」とするより、 いっそ計算してちゃった方がメモリにもCPUにも優しいです。 というわけで、この辺りは、 パフォーマンス向上のため人間側が補助してやって、 「結果は使わんかもしれんがここは先行評価したまえ」と指示してるわけです。
-- そんな補助をしなくても処理系で良きに計らって欲しいというのも当然の欲求で、
-- 例えば「結果が無駄になったら捨てりゃいいんだし、投機的に実行してもいいんじゃね?」
-- という投機的実行版Haskellとか、別のCPUに計算させちゃえとか、色々な研究があるようです。
-- 「最終形に辿りつく限り、どんな順序で評価しても結果は同じ」
-- という純粋関数型ならではの研究と言えるかもしれません。
さて、このエントリのprog8から使っているunboxed typeは、 さらに一歩機械べったりに歩み寄ったデータ型です。 Haskell内の普通のデータには、 内部的には「評価済みか未評価か」の区別がありますが、 unboxed typeは常に評価済みの、 C言語等と同様の生のデータだということになっています。 「評価済みかどうか」といった余分な情報を持っていないので、 整数型のような小さなデータなら、 コンパイラがregisterに格納するよう最適化することもできます。 そうなると、加算などは機械語1命令で実行できたりします。
-- GHCのユーザガイドでは、とある数値計算主体のプログラムで、
-- 標準の型を使うより「3倍速かった」とか言ってます。
-- 多分赤いです。(意味不明)
ついでに、本文中で説明し忘れましたが、プログラム先頭の
の部分は、(unboxed typeのような)GHCの拡張機能を使うよ、 というコンパイラディレクティブです。 コンパイル時のオプションに直接-fglasgow-extsオプションを 指定しても同じです。