Parallel and Concurrent Programming in Haskell 読書会 第6回

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ2 bracket (async io) cancel bodyとすると親と一蓮托生のスレができる。親がbodyから戻るか何らかの理由で死ぬかすればbodyから出る際ioのスレもcancelで一緒に殺される。この処理はwithAsync関数として提供。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ3 withAsyncをネストしたら一蓮托生の姉妹ができる。例えば withAsync task_a $\a -> (withAsync task_b $\b -> c)でcの実行中aかbが死ねばもう一方も死ぬ。ただし親が死亡通知をc内で処理したら別。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ4 親が死亡通知を正しく処理しないと不公平になる。前出のコードのcの部分で aval <- wait a; bval <- wait b しただけではaの死はすぐbに伝播するが逆はaが死ぬまで親がbの死亡通知を調べないから配達が遅れる。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ5 waitBoth a bはa,b両方の値を待つが一方が死ねば即座にもう一方も殺して例外を飛ばす。実装はwaitSTMでaを調べ(ここでaが死んでれば例外が飛ぶ)、retry(=a終わってない)ならbを調べ、例外が飛ばなければretry(=aに戻る)。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ6 注: waitSTMはAsync内のTMVarをreadTMVarで調べてるけど、この関数の定義は見当たらない。動作はデータが来るまでブロックして読み、読んだ値のコピーを即座に戻す。単にreadMVarのTMVar版。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ7 concurrentはwithAsyncでスレ二つ作ってwaitBothで両方の値を返す。代わりにwaitEither(第8章参照)するのがraceで、先に終わった方の値だけを返す早い者勝ちを行う。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ8 Asyncの中身をTVarからSTMアクションに変えればAsyncをFunctorにすることもできる。こうすると一旦作ってしまったAsyncの戻り型を後から変更できる。ただし計算コストを払うのはAsyncに入ってるスレではなくfmapした側のスレ。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ9 Asyncの変遷まとめ。 ・最初はasync+waitだけ ・waitで子の例外の親へ伝播 ・STM化し公平な待機waitBoth,waitEither追加 ・一蓮托生スレwithAsync ・作成から待機まで面倒見るconcurrent,race

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ10 例:ウェブサーバー。各クライアントが独立ならワーカーをforkしまくるだけ。一方共有状態がある場合はいくつか戦略が考えられる。が、全部 STM の噛ませ犬だから気をつけろ!ここでは数値を一つ共有し、その値の変更を常に全クライアントに通知しよう。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ11 噛ませ犬のデザインは省略してSTM。共有されてる数値をTVarで持ち、各サーバースレが前読んだ時と値が変わってるか自分で調べて必要に応じて通知を出力。但しソケットからの読み込みはガチI/OなのでSTM内でできない。Chanに転送するスレが一個必要。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ12 この転送スレと実際の仕事するスレをraceで一蓮托生の姉妹スレにすると何か有った時心中してくれるので資源漏れが無い。The ImplementationのコードではSTMからIOアクションを返すという重要テクも使われているので見ておくべし。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ13 ソケットからの転送とTVarの変化の二つの同時待ちではorElseの出番無し。(if A then retry else B) `orElse` C==if A then C else Bなので。但しこれはBがretryする可能性がある場合は無効。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ14 例:チャットサーバー。発話はそれを受け取ったスレが自力で皆のChanに書き込みに行く。250行程度で数千接続を捌けるサーバーの出来上がり。+RTS -Nしたらありったけのコアを使う。broadcast Chanでの高速化は読者への課題と(ry

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ15 StrategiesやParなどの並列プログラミングモデルは便利だが ・I/Oを含む計算 ・非決定性アルゴリズム の並列化には使えない。そういう時は並行プログラミングで並列化する。 補足:並列=速く　並行=論理的に同時実行可能、実際の実行は知らん

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ16 例:ディレクトリツリーから特定の名前のファイルを探す。ディレクトリの中身を列挙してそれぞれにwithAsyncで子スレを当て、出来たAsyncを一つづつwaitしていく(waitEitherだと答えが複数ある場合の優先順位が逐次実行版と異なる)。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ17 withAsyncはネストしないといけないのでmapではなくfoldすること。findpar.hsの(2)の行ではpsまでがwithAsync(を呼び出すsubfind)を合成していくfold、そのあとの[]が出来上がったパイプラインへの入力。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ18 これでもスケールするが粒度が小さすぎるので、セマフォを使って一定数以上スレが溜まったら逐次版に切り替えさせよう。セマフォの実装はMVarにInt置くだけ(但し要seq)。しかしthreadscope見ると今度はセマフォの争奪が重い。どうしよう?

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ19 答えは、STM!!と言いたいところだが、この場合STMよりatomicModifyIORefのが速い。動作は名前通り。ad-hocさが微妙にキモいけど使える時は使おう。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ20 最後に趣向を変えてParIO。Parとほぼ一緒だがIO可、但し決定性は保証されない。asyncをfoldしてたのをforkをmapするよう変え、runParIOする。Par同様軽量スレができるのでセマフォとか何とかしなくてもこれでスケールする。

Jun Inoue @jun0inoue

#PCPjH 次回は第14章、分散コンピューティングから。あと一回で終われるかどうか微妙な線です。多分できる。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ13 の補足 よく見たらこの retry って限定継続と同じような動作してるな…同じものと考えていいのか? ちょと気になる。