Haskell による並列・並行プログラミング #15 13章 スレッドを用いた並列プログラミング
担当: wado さん
並行性を使って並列性を得るモチベーション
IO 付きの計算、アルゴリズムに非決定がある場合、など
並列性を得るには
作業スレッドを複数つくる
GHCのランタイムシステムは、飢餓状態を無くすようには動いてくれるが、公平性は保証しない
例題:ファイル探索
find ファイル名 ルートパス
直列版
並列版
振る舞いが直列版と同じになるように
withAsyncを使う
subfind
部分適用して、AsyncのリストからIOアクションを返す「関数」に畳み込む(そこに空リストを適用する)
foldr で subfind のはしごをつくる(withAsync のはしごになっている)
reverse して実行するとで内側から発火させる
innerに当たる部分は内側のsubfindの呼び出しに該当する
foldr :: (a -> b -> b) -> b -> [a] -> b
bをb->cに置き換えてみると
foldr :: (a -> (b -> c) -> (b -> c)) -> (b -> c) -> [a] -> (b -> c)
括弧をとると
foldr :: (a -> (b -> c) -> b -> c) -> (b -> c) -> [a] -> b -> c
ここに foldr (subfind s) dowait ps [] が入る感じ
セマフォを用いたスレッド数の制限
今の実装は粒度が細かすぎる(並列のオーバーヘッドが大きい)
ディレクトリツリーは不均衡なので、ツリーの深さなどを使うとうまく行かない恐れがある
生成できるスレッドの数を制限して、使い切ったら直列版を動かす、という仕組みにしてみる
セマフォ
特に、ノンブロッキングセマフォ(使えるリソースがなかったら直列版へフォールバックする)
セマフォをMVarで実装すると、ブロックが多数発生する
STMを用いた解決策もあるが、IORefを使うと軽い
atomicModifyIORef を使うとトランザクションが実現できる
ParIO モナド
Par モナド:Eager実行による決定的な並列
ParIO モナドでは liftIO で IO操作できる
決定性は保証されていない
おさらい:IVar一度しかデータを入れることができない
セマフォより早くなった
ParIO内のforkが非常に軽量(スレッドよりも)
ParIO を用いた実装にはエラー処理がない
解決策
ParIO に (Either SomeException a)を積む
EParIOとする
MonadIO のインスタンスで、try io することでEither化する
IVarに(Either SomeException a)を積む
EVarとする
Monadのインスタンスで、EitherのLeftが来たらLeftを優先するように実装することでエラーが伝搬される?