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

Jun Inoue @jun0inoue

#PCPjH 今日は研究室行くのでまとめはまた後で。

Hideyuki Tanaka @tanakh

#PCPjH 本日はいつにもまして遅くなって申し訳ありませんでした。STMまで終わって、いよいよ残すところは並行による並列と分散あたりの話になってまいりました。残りあと二回ほどで終わりそうです。次回も二週間後になると思いますので、よろしくお願いいたします。

コスモ @cosmo__

#PCPjH お疲れ様でした。STMまで抽象化していてもやはり地雷が潜むので並行処理難しいですね。。。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ1 スレを中止させるには被害者が中止条件を定期的に調べて自殺する方法と加害者が突然殺す方法がある。前者ではpollし忘れるとデッドロック、後者ではデータ更新中に殺すと整合性破壊。命令型言語ではデータ更新が頻繁なので前者一択。Haskellでは後者デフォ。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ2 スレを殺すにはthrowToで例外を投げつける。このように外的要因で発生する例外が非同期例外。一方、被害スレ自身の処理が引き起こす例外が同期例外。非同期例外の処理方法は同期例外と同じくcatchだが、例外発生許可のタイミング制御が必要でこれが激ムズ。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ3 例えばdo a <- takeMVar m; x <- f a `catch` h; putMVar m xは例外処理できてそうに見えるがtakeとfの間で非同期例外が飛ぶとMVarが空のままになる。bind中は非同期例外をマスクする必要がある。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ4 mask $ \r -> …とするとλの実行中は非同期例外が留め置かれ、マスクが外れると溜まってた例外が飛ぶ。r引数の評価中マスクを外す恒等関数。前出の例ではr $ f aとするとfの実行中はマスクが外れる。hでaをputすれば空MVarが無くなる。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ5 こうして不可分処理にしたtake→f→putはmodifyMVar/modifyMVar_として提供されてる。前者を使えば自明なコードでcmp-and-swapが書ける。modifyMVarの実装でrを全く使わなくても不可分性は保たれるが良くない。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ6 maskは一時的にpoll型のスレ中止プロトコルに移行するのと同じ事。マスクする時間が短いほど応答性は良くなる。rが使えるなら使うべし。その関係で、takeMVar等がブロックした時もマスクが外れるようになってる。応答性には良いがトリッキーでもある。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ7 例えばmask $ \_->do takeMVar a; takeMVar b; putMVar a; putMVar bはtake bで非同期例外が飛ぶ可能性がありaが空になりうる。modifyMVarを二変数に使うときはネストせよ(詳細は本参照)

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ8 使用例:timeout t mはt[μs]後に主スレに非同期例外を飛ばすタイムキーパースレを作り、mを実行する。但し制限時間内にmを抜ける場合は主スレからタイムキーパーに非同期例外を飛ばして殺す。タイミング次第では例外投げ合いになるが必ず一方が勝つ。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ9 ど〜してもtakeMVarで外れないマスクが欲しければuninterruptibleMaskを使う。但し安全性的にunsafePerformIOとかと同じ扱いの模様。例外ハンドラの中では自動的にマスクがかかる。じゃないとPGが泣く。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ10 但しこれは例外ハンドラがいつまでも終わらない時(再帰関数fの中でセットされたハンドラがfを再帰呼び出ししてしまうなど)、いつまでもマスクが外れないという意味でもあるので注意。げに非同期例外処理の難きことよ。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ11 STMは本来実装技術の名前だけど言語機能の名前として定着。TVarというIORef的な型を提供するが、これはSTMモナド中でしか操作できず、STMではTVarの読み書き以外の副作用ができない。ロールバックなどのためこうして型で副作用を制限している。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ12 readTVar/writeTVarで一頻りデータ更新するSTMアクションを作ってそれをatomicallyに渡すとそのアクション全体が不可分に実行される。超簡単。特定条件で待機するには現在のSTMアクションを丸ごとやり直すretryを使う。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ13 readTVarしまくって変数を調べ、続行できる条件が整ってなければretry。すると変数が他スレの手で変えられるまで眠る。変数の値が変われば再挑戦、以下繰り返し。orElse a bはaがretryした場合(=aの実行条件が不足の場合)bを実行。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ14 orElseはretryした方はロールバックするので、複数のチャンネルをpollするのに使える。fを「チャンネルを読む→調べて値を返すか値が良くない場合retry」関数とするとwaitAny = foldr orElse retry . map f

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ15 retryしたチャンネルへのアクセスはロールバックするので完全peek扱い。一方MVarではwaitAnyに渡されたMVarは全部takeしてしまう関数しか書けない。しかも渡されたMVarを一元化用MVarに転送するスレをO(n)個作るので重い。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ16 複数のMVarをtake/putするコードでは全てのスレが同じ順序でMVarをアクセスするよう取り計らわないとデッドロックする(Linuxカーネルのロックプロトコル参照)が、TVarでは複数のアクセスが一不可分処理になるのでデッドロックはしない。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ17 MVarは「エクストリーム・mask配置ゲー」をプレイしないと非同期例外安全にならないがSTMはデフォで安全。非同期例外安全にするためには「何もしない」、それが正解。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ18 MVarとは一体何だったのか。STMチートすぎるんじゃないのか、MVar要らねーだろもう、という声が聞こえてきそうだがMVarはfairnessの保証がある点で優れているし、正しく使えばSTMより速い。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ19 STMアクションのサイズをnとするとreadTVarはO(n)--但しO(log n)になる予定あり(?)--writeTVarはO(1)、retryも何とO(1)。しかしnが大きいほどretryせざるを得なくなる確率は高くなる。nは小さくしよう。

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ20 STMを小さくするコツの一つ。例えばTVar+リストで作ったChanは内部でreverseするが、この結果をcaseではなくletで分解すると分解自体はreverseを強制しない。分解結果が(あわよくばSTMの外で)強制されるまで遅延される。ウマー

Jun Inoue @jun0inoue

#PCPjH 今回はここまで。次は第11章から。 エクストリーム・mask配置ゲーの話が長すぎた…MVarの話だけで11ツイートってどういうことやねんorz

Jun Inoue @jun0inoue

#PCPjH 今回のまとめ、おまけ まとめで一切言及しなかったけど、以前例外処理のところで見た bracket は mask 使って実装されてるので見とくとよいでしょう。(本参照)