NFDataクラス
ここからはControl.Parallel.Strategiesモジュールについて見ていきたいと思います。
単に粗い粒度の計算同士を並列化するだけであれば,par関数を使うだけで十分です。が,プログラムを並列化していく過程では,前回定義したquicksort'関数や上で定義したparallelMap関数のように,比較的粒度の細かい計算をも並列化させていくことになると思います。
なぜなら,粗粒度(coarse grain)では分割範囲が大きいためにプロセサなどの複数の計算資源ごとに動作する頻度に差ができたり,いずれかの資源が動作していないような空き時間が多く生まれるからです。つまり,粗粒度では並列化の負荷が無視できるほど小さくなる代わりに,プログラムの並列性そのものも下がります。これでは計算資源の能力を最大限に生かすことはできません。そこで負荷が大きくなりすぎないように調整しつつ,より細かい粒度での並列化を徐々に図っていくことになります。
ところが,粗粒度のプログラム同士を協調(coordinate)させる形で並列化させるだけならまだしも,細粒度や中粒度(middle grain)の計算にも並列化の手を伸ばそうとすると,どうしてもparやpseqをそのまま利用するのでは不便になってきます。そこで並列Haskellでのプログラミングを補助するために用意されているのが,Control.Parallel.Strategiesモジュールです。
parやpseqでは不便なのはどんなときでしょうか? 例えば,前回,クイックソートを先行評価させるために用いたforceList関数の定義は,Intのような正規形になることが明らかなデータ型に対してのみ有効です。リストのリストといった「リストの内部のデータ型が正規形でない可能性のある型」では,クイックソートを望みどおりに動かすことはできません。では,使用する型に応じて,別の種類のクイックソートを利用するべきでしょうか?
いえ,他にも方法はあります。第8回で「データ型の中身をすべて正規形にしていくための型クラス」を用意するという手法を紹介したことを思い出してください。Control.Parallel.Strategiesモジュールには,これを行うためのNFDataクラスが提供されています。
では,NFDataクラスの定義を見てみましょう。
class NFData a where -- | Reduces its argument to (head) normal form. rnf :: Strategy a -- Default method. Useful for base types. A specific method is necessay for -- constructed types rnf = rwhnf
NFDataクラスのメソッドは,コメントから「引数を(頭部)正規形に簡約する(Reduces its argument to (head) normal form)」という文の頭文字を取ったrnfの一つだけであることがわかりますね。頭部(head)に括弧が付いているのは,おそらくこの関数のデフォルトの定義が「弱頭部正規形(WHNF:Weak Head Normal Form)に簡約する」という意味のrwhnf関数であるためでしょう。
rwhnf関数の定義は以下の通りです。
rwhnf :: Strategy a rwhnf x = x `seq` ()
この関数の定義に使われているseq関数の実体はpseq関数なので,そのように読み替えてください。
seq = Parallel.pseq
これ以降の部分ではseqをpseqに置き換えた定義を提示することにします(なお,GHC6.6.xではpseqの代わりにseqが定義に使われています。なので,前回Control.Parallelモジュールに対して行ったようにCプリプロセサを利用し,GHC6.6.xでもここで示すような開発版での定義を利用できるようにしたほうがよいでしょう)。
pseqの第2引数に( )を与えているのは,rwhnfはあくまで「コンパイラに簡約の仕方を指示するのが目的の関数」であって,何か有効な値を返すことを目的としたものではないからです。
前回定義したquicksort'関数の定義を見ればわかるように,こうした簡約の指示はpar関数の第1引数として与えられることになります。parは第2引数のみを返すので,第1引数の評価戦略は使用されるものの,その結果は使われません。ならば,下手に有効な値を与えるよりも,何の意味もない( )を返すようにしたほうがよいでしょう。
quicksort' [] = [] quicksort' [x] = [x] quicksort' (x:xs) = (forceList losort) `par` (forceList hisort) `par` losort ++ (x:hisort) where losort = quicksort' [y|y <- xs, y < x] hisort = quicksort' [y|y <- xs, y >= x]
そういえば,forceListも( )を返す関数として定義していましたね。
forceList :: [a] -> () forceList [] = () forceList (x:xs) = x `pseq` forceList xs
forceListに対応するリスト型のインスタンスの定義は,以下の通りです。
instance NFData a => NFData [a] where rnf [] = () rnf (x:xs) = rnf x `pseq` rnf xs
リストだけではなく,リストの要素であるxに対しても簡約をうながすよう定義されているのがわかりますね。このとき,xの型であるaにNFDataクラスのインスタンスが定義されていなければWHNFまで簡約され,定義されていればそのインスタンスのメソッドの定義に従って簡約されることになります。
なお,簡約を行いたくない場合のため,r0という補助関数も用意されています。
r0 :: Strategy a r0 x = ()
NFDataクラスには,以下のようなインスタンスが定義されています。
Prelude Control.Parallel.Strategies> :i NFData class NFData a where rnf :: Strategy a -- Defined in Control.Parallel.Strategies instance NFData Char -- Defined in Control.Parallel.Strategies instance NFData Bool -- Defined in Control.Parallel.Strategies instance NFData () -- Defined in Control.Parallel.Strategies instance (NFData a) => NFData [a] -- Defined in Control.Parallel.Strategies instance (NFData a, NFData b) => NFData (a, b) -- Defined in Control.Parallel.Strategies instance (NFData a, NFData b, NFData c) => NFData (a, b, c) -- Defined in Control.Parallel.Strategies instance (NFData a, NFData b, NFData c, NFData d) => NFData (a, b, c, d) -- Defined in Control.Parallel.Strategies ~ 略 ~ instance NFData Int -- Defined in Control.Parallel.Strategies instance NFData Integer -- Defined in Control.Parallel.Strategies instance NFData Float -- Defined in Control.Parallel.Strategies instance NFData Double -- Defined in Control.Parallel.Strategies instance (NFData a, NFData b) => NFData (Assoc a b) -- Defined in Control.Parallel.Strategies
次に,これらの関数で使われているStrategy型の定義を見てみましょう。rwhnfやr0の定義などから予想は付いていると思いますが,Strategy型はaを取って( )を返す型として定義されています。
type Done = () type Strategy a = a -> Done
注目に値するのは,( )をそのまま使用するのではなく,Doneという別名を付けることで,簡約が終了した状態であることを明確にしている点です。
using関数
NFDataクラスはあるデータを先行評価させるのに便利ですが,欠点が一つあります。それは特定の型に対する評価戦略が常に固定されていることです。quicksort'関数の場合にはforceList関数やrnfメソッドのような先行評価が最適な戦略でしたが,リストを使用する関数では必ず先行評価が適切な戦略になる,というわけではありません。例えば,リストの中に格納したデータ構造は,ストリームのような無限の大きさを持つものかもしれません。あるいは,リストを対象とした関数の返す結果のうち,先頭のn個までしか必要ではないかもしれません。このようなとき,いくらプログラムを並列化させるからといって,遅延評価によって省けるはずの計算を行わせるのが賢明な判断であるとは思えません。
そこでControl.Parallel.Strategiesモジュールでは,「引数として評価戦略(Strategy型の値)を取ることで,型に対する評価戦略を自由にカスタマイズできる高階関数」をいくつか提供しています。
seqList :: Strategy a -> Strategy [a] seqList strat [] = () seqList strat (x:xs) = strat x `pseq` (seqList strat xs)
seqListの第1引数であるstratをrnfに置き換えれば,rnfメソッドと全く同じですね。同様にrwhnfを与えた場合には,リストの内部の値をWHNFまでしか簡約させないようにできます。
同様に,評価戦略を取るようparallelMapを変更したparMap関数も用意されています。こう書くと,parallelMapにStrategy型の値を取る引数を変数として加えたものをイメージするかもしれませんが,実際には以下のように定義されています。
parMap :: Strategy b -> (a -> b) -> [a] -> [b] parMap strat f xs = map f xs `using` parList strat parList :: Strategy a -> Strategy [a] parList strat [] = () parList strat (x:xs) = strat x `par` (parList strat xs) infixl 0 `using` using :: a -> Strategy a -> a using x s = s x `pseq` x
usingは,見ての通り,評価戦略を値に適用するための補助関数です。この関数を用いると,引数xとして与えられた本体の値の同一性をできるだけ保ったまま,評価戦略を変更させることができます(ただし,xを評価した結果が⊥である場合には,値の意味が変わる可能性があります)。usingの導入によって,parMap関数の定義は格段に簡潔になっています。
parMapでは,usingを使い,リストのそれぞれの値を並列に評価するためのparList関数を適用しています。parListはseqListのpseqをparに置き換えただけの定義になっています。このことからわかるように,parList自身も評価戦略を取る関数になっています。リスト内部の値に対する評価戦略はparListによって受け渡されることになります。
ついでに,usingを使った例をもう一つ見てみましょう。quicksort'関数は,usingおよびNFDataクラスを使うことで,こう書き直すことができます。
quicksort'' :: (Ord a, NFData a) => [a] -> [a] quicksort'' [] = [] quicksort'' [x] = [x] quicksort'' (x:xs) = losort ++ (x:hisort) `using` strategy where losort = quicksort [ y | y <- xs, y < x] hisort = quicksort [ y | y <- xs, y >= x] strategy result = rnf losort `par` rnf hisort `par` rnf result
parMapと同様に,本体と評価戦略を分けることで,すっきりした定義になっていますね。
また,par関数やpseq関数とは違い,第1引数が関数本体の返す値になっているものわかりやすさの一因であると思います。このことを考慮に入れて,Control.Parallel.Strategiesモジュールにはparやpseqの引数を入れ替えた関数も定義されています。
infixl 0 `demanding`,`sparking` demanding :: a -> Done -> a demanding = flip pseq sparking :: a -> Done -> a sparking = flip par
さて,ここでようやく粒度の話題に戻ることができます。parMapではリストのそれぞれの要素に対する関数fの適用を並列化していますが,関数fが行う計算によっては,このような定義は並列化の負荷ばかり大きくなる非効率的なものかもしれません。したがって,与えた数値によって並列化の粒度を調整できるparMapN関数が欲しくなると思います。
残念ながら,現在のControl.Parallel.Strategiesモジュールには,このような関数は定義されていません。ですが,Strategy型やusingを導入することで本体と評価戦略を分けられるようになるため,そのような関数も簡単に定義できます。
parMapN :: Int -> Strategy b -> (a -> b) -> [a] -> [b] parMapN n strat f xs = map f xs `using` parListChunk n strat
parListChunkは評価をn個ずつ並列化するための関数です。
parListChunk :: Int -> Strategy a -> Strategy [a] parListChunk n strat [] = () parListChunk n strat xs = seqListN n strat xs `par` parListChunk n strat (drop n xs) seqListN :: (Integral a) => a -> Strategy b -> Strategy [b] seqListN n strat [] = () seqListN 0 strat xs = () seqListN n strat (x:xs) = strat x `pseq` (seqListN (n-1) strat xs)
dropはtakeとは逆に先頭のn個を除いたリストを取得する関数です。seqListNではn個までの要素を逐次的に評価するよう定義しているので,seqListNとdropをと組み合わせることで,並列化の単位をn個ずつに区切ることができるのです。