Haskellの並列・並行処理

1. Shuntaro Nishizawa (@shun_shobon) Haskellの並列・並行処理 〜Eval / IO / STM モナドのご紹介〜
2. アジェンダ - 並列処理と並行処理の違い - Haskell基礎知識 - Haskellの評価戦略 - Evalモナドを使った並列処理 - IOモナドを使った並行処理 - MVarを使った共有メモリ - STMモナドを使った共有メモリ 2
3. アジェンダ - 並列処理と並行処理の違い - Haskell基礎知識 - Haskellの評価戦略 - Evalモナドを使った並列処理 - IOモナドを使った並行処理 - MVarを使った共有メモリ - STMモナドを使った共有メモリ 3
4. 並列処理と並行処理の違い、 わかってますか？ 4
5. 今更聞けない並列処理と並行処理の違い - 計算を速くするための処理 - 結果は決定的 - 基本的に複数コアが前提 - 効率化のための技術 5 並列処理 - 複数の対話を同時に扱う - 結果は非決定的 - 複数コアが必要とは限らない - 構造化のための技術 並行処理
6. Haskellにはこのどちらも楽に書ける仕組みが用 意されています 6
7. アジェンダ - 並列処理と並行処理の違い - Haskell基礎知識 - Haskellの評価戦略 - Evalモナドを使った並列処理 - IOモナドを使った並行処理 - MVarを使った共有メモリ - STMモナドを使った共有メモリ 7
8. 基本文法 - インデントに意味がある - <:より先は型の世界 - doはasyncの一般化(モナドで使用) - <-はawait+変数拘束の一般化(モナ ドで使用) - 関数適用は最も優先度が高い - $は括弧の省略(に使える) - <>の左側は型クラス制約 8 main <: IO () main = do let x = 5 y = 10 result <- ioAdd x y putStrLn $ show result add <: (Num a) <> a <> a <> a add x y = x + y ioAdd <: (Num a) <> a <> a <> IO a ioAdd x y = pure $ add x y
9. アジェンダ - 並列処理と並行処理の違い - Haskell基礎知識 - Haskellの評価戦略 - Evalモナドを使った並列処理 - IOモナドを使った並行処理 - MVarを使った共有メモリ - STMモナドを使った共有メモリ 9
10. Haskellは非正格言語 - 中でもGHCは遅延評価を採用している - GHCiで:sprintを使うと非破壊で式を調べることができる 10 Prelude> x = 5 + 3 <: Int Prelude> :sprint x x = _ Prelude> x 8 Prelude> :sprint x x = 8
11. Haskellは非正格言語 11 Prelude> x = 5 + 3 <: Int Prelude> y = x + 3 Prelude> :sprint x x = _ Prelude> :sprint y y = _ Prelude> y 11 Prelude> :sprint x x = 8 Prelude> :sprint y y = 11
12. アジェンダ - 並列処理と並行処理の違い - Haskell基礎知識 - Haskellの評価戦略 - Evalモナドを使った並列処理 - IOモナドを使った並行処理 - MVarを使った共有メモリ - STMモナドを使った共有メモリ 12
13. Evalモナドとrpar / rseq - 並列性はEvalモナドで表現される - rparは並列性を作り出す - rseqは直列評価を強制する - runEvalでEvalモナドから値を取り出 す - Haskellではモナドから値を取り出す関数 の名前をrunFooやunFooなどにする習慣 がある 13 data Eval a instance Monad Eval runEval <: Eval a <> a rpar <: a <> Eval a rseq <: a <> Eval a
14. 普通の計算プログラム - 未最適化のフィボナッチ数列のn番目 を求める関数を用意 - 僕のマシンでは約10秒ほどかかる 14 module Main where main <: IO () main = do print $ fib 45 print $ fib 44 fib <: Int <> Int fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1)
15. 並列性のある計算プログラム - rparを使うとその式が並列処理できる ことを表す - rparに渡す式は未評価の計算である ことが望ましい(というか意味がない) - runEvalすると値が取り出せる 15 module Main where import Control.Parallel.Strategies main <: IO () main = do let (x, y) = runEval $ do x <- rpar $ fib 45 y <- rpar $ fib 44 pure (x, y) print x print y
16. 並列性のある計算プログラム 16 module Main where import Control.Parallel.Strategies main <: IO () main = do let (x, y) = runEval $ do x <- rpar $ fib 45 y <- rpar $ fib 44 pure (x, y) print x print y
17. 並列性のある計算プログラム - rseqを使うと評価の完了を待つように なる - この場合はxとyの評価が終わるまで pureには行かない 17 module Main where import Control.Parallel.Strategies main <: IO () main = do let (x, y) = runEval $ do x <- rpar $ fib 45 y <- rpar $ fib 44 rseq x rseq y pure (x, y) print x print y
18. 並列性のある計算プログラム 18 module Main where import Control.Parallel.Strategies main <: IO () main = do let (x, y) = runEval $ do x <- rpar $ fib 45 y <- rpar $ fib 44 rseq x rseq y pure (x, y) print x print y
19. 並列性のある計算プログラム - -threadedをコンパイルオプションで付けるだけで並列プログラムの完成 - +RTS -Nnで使用するコア数を指定可能 19 $ time ./haskell-test 1134903170 701408733 10.17s user 0.04s system 99% cpu 10.275 total $ time ./haskell-test +RTS -N2 1134903170 701408733 +RTS -N2 12.24s user 0.43s system 197% cpu 6.415 total
20. Haskellの並列処理の仕組み - rparに渡された引数はスパークと呼ばれる - スパークはランタイムによってプールされる - ワークスチールと呼ばれる手段でプロセッサに割り当てられる - スパークの生成コストは非常に安い - Haskell公式パッケージであるparallelには他にも並列処理のための便利関数が多 数用意されているのでお試しあれ - Strategy型シノニムによって評価戦略の入れ替えも容易 20
21. アジェンダ - 並列処理と並行処理の違い - Haskell基礎知識 - Haskellの評価戦略 - Evalモナドを使った並列処理 - IOモナドを使った並行処理 - MVarを使った共有メモリ - STMモナドを使った共有メモリ 21
22. IOモナドとは - 副作用がある(かもしれない)動作「そのもの」 - IOモナドが作られ、評価されるだけでは副作用は発生しない - 副作用の発生はmain関数(≒ランタイム)の仕事 22 main <: IO () main = do let _ = putStrLn “Hello, world!” `seq` () putStrLn “done” $ cabal run done
23. IOモナドを使った並列処理の実現方法 - forkIOで新しいスレッドを生成すること ができる - 渡すのはIOモナド - 帰ってくるのはThreadId(IOモナドに 包まれている) - forkIOは非常にプリミティブで、join等 の機能は無い - 共有メモリや別ライブラリを使う 23 forkIO <: IO () <> IO ThreadId
24. GHCのスレッドについて - forkIOで作られるスレッドはいわゆる「グリーンスレッド」 - 大量に作成しても大きなオーバーヘッドはない - I/OライブラリはLinuxのepoll、BSD系のkqueue等を使用しているため、スレッド間 でI/Oを同時処理しても性能劣化が少ない - ネイティブスレッドが欲しい場合はforkOSという関数も提供されている - なお、IOモナド内に並行処理不可能な処理を入れてもforkIOは成功してしまうので 注意 - Haskellで提供されているライブラリや関数全てがスレッド安全ではない - 例) IORef: IOモナド内で使用可能な可変参照 24
25. アジェンダ - 並列処理と並行処理の違い - Haskell基礎知識 - Haskellの評価戦略 - Evalモナドを使った並列処理 - IOモナドを使った並行処理 - MVarを使った共有メモリ - STMモナドを使った共有メモリ 25
26. MVarを使った共有メモリ - MVarはスレッド間通信で使用できる 共有メモリ - 値が入ってるか・空であるかのどちら かの状態を取る - 空の時にtakeしようとするとブロック - 値が入ってる時にputしようとするとブ ロック - 単一項チャンネルとしてやロック機構 としても使用可能 26 data MVar a newEmptyMVar <: IO (MVar a) newMVar <: a <> IO (MVar a) takeMVar <: MVar a <> IO a putMVar <: MVar a <> a <> IO ()
27. MVarの特徴(安全性) - ランタイムはデッドロックを検知すると BlockedIndefinitelyOnMVarという例 外を投げる - うっかりデッドロックしても例外が飛ぶ のでデバッグに便利 27 main = do x <- newEmptyMVar takeMVar x $ cabal run haskell-test: thread blocked indefinitely in an MVar operation
28. MVarの特徴(公平性) - GHCはラウンドロビン方式のスケ ジューラを使用している - CPU時間の割当を受けられないスレッ ドがないことを保証する - MVarには公平性がある - 他スレッドが永遠にMVarを抱え込 むことが無い限り、スレッドが永遠 にブロックされることはない - ブロックされたスレッドはキューに入 れられる - ブロック解除されるのは必ず 1つのス レッドだけ 28 main = do hSetBuffering stdout NoBuffering forkIO $ replicateM_ 100 $ putChar ‘A’ replicateM_ 100 $ putChar ‘B’ $ cabal run BABABABABABABABABABABABABABABABABABABABA BABABABABABABABABABABABABABABABABABABABA BABABABABABABABABABABABABABABABABABABABA BABABABABABABABABABABABABABABABABABABABA BABABABABABABABABABABABABABABABABABABABA
29. MVarの特徴(遅延) - putMVarした時、xに入るのは未評 価の式fib 45 - この場合、putMVarによるロックが 短時間で済む - ただしスペースリークに注意 - $!で正格評価可能 29 main <: IO () main = do x <- newEmptyMVar putMVar x $ fib 45 main <: IO () main = do x <- newEmptyMVar putMVar x $! fib 45
30. アジェンダ - 並列処理と並行処理の違い - Haskell基礎知識 - Haskellの評価戦略 - Evalモナドを使った並列処理 - IOモナドを使った並行処理 - MVarを使った共有メモリ - STMモナドを使った共有メモリ 30
31. STM: ソフトウェアトランザクショナルメモリとは - DBのトランザクションに似た並列性制御機構 - MVarやMutexなどのロックベースの代替手段 - 原理的にデッドロックが生じない - 複数の状態変更操作をグループ化し、単一の不可分操作として実行できる 31
32. STMモナドを使った共有メモリ - STMはモナド - TVarがトランザクション変数 - 基本的にSTMに関連する変数やチャ ンネルはSTMモナド内でのみ読み書 きが可能 - STMモナド内の計算はatomically関 数で実行できる - 名前の通り、操作全体が不可分になる 32 data STM a instance Monad STM atomically <: STM a <> IO a data TVar a newTVar <: a <> STM (TVar a) readTVar <: TVar a <> STM a writeTVar <: TVar a <> a <> STM () retry <: STM a orElse <: STM a <> STM a <> STM a
33. STMモナドの良さ data Account = Account (TVar Int) transferSTM <: Account <> Account <> Int <> STM () transferSTM (Account from) (Account to) amount = do from' <- readTVar from to' <- readTVar to writeTVar from $ from' - amount writeTVar to $ to' + amount transfer <: Account <> Account <> Int <> IO () transfer from to amount = atomically $ transferSTM from to amount - 銀行の送金システムを考える - もしAccountがMVarやMutexだと、デッドロックの可能性がある - STMならデッドロックの心配がない！ 33
34. STMモナドの良さ transfer <: Account <> Account <> Int <> IO () transfer from to amount = atomically $ transferSTM from to amount transferToMany <: Account <> [Account] <> Int <> IO () transferToMany from toList amount = atomically $ forM_ toList $ \to <> transferSTM from to amount - STMモナドは合成することが可能 - 合成可能性という - STM操作をatomicallyに包まずに提供することで利用側が自由に合成することが できる 34
35. STMモナドの良さ transferSTM' <: Account <> Account <> Int <> STM () transferSTM' (Account from) (Account to) amount = do from' <- readTVar from to' <- readTVar to when (from' < amount) retry writeTVar from $ from' - amount writeTVar to $ to' + amount - retryは現在のトランザクションを破棄してもう一度やり直す - ランタイムはトランザクション内で読み込まれたTVarを知っているので、他のトラン ザクションでTVarが変更されるまでスレッドをブロックする 35
36. STMの特徴色々 - STMトランザクションはreadTVarとwriteTVarのログを蓄積しながら動いている - writeTVarはすぐにメモリへ書き込むのではなく、ログを蓄積することでトランザク ションの破棄をしやすくしている - readTVarはログの走査をして、前のwriteTVar処理を検査する - よって、raedTVarはログの長さに対して O(n)のコストがかかる - トランザクションの最後まで来ると、ログとメモリの内容を比較する - メモリの内容とreadTVarで読みだした値が一致するならば、メモリへコミットされる - 一致しない場合、トランザクションは retryされる - 上記の工程中のみトランザクションに含まれるTVarをロックする - トランザクションが長時間に渡る場合、無限に再実行される可能性がある 36
37. STMの特徴色々 - それぞれTVarは自身が変更された際に起こす必要のあるスレッドの監視リストを 持っている - retryは現在のスレッドをトランザクション中に含まれる全てのTVarの監視リストに追 加する - つまりretryはTVarの数に対してO(n)の操作 - トランザクションがコミットされた時、変更を受けたTVarの監視リストにあるスレッド をすべて起こしに行く 37
38. その他Haskellの並列・並行処理色々 - Parモナド: FutureやPromiseと似た並列処理が可能 - asyncパッケージ: forkIOを抽象化し、便利な関数を多数用意したパッケージ - 例外処理や並列処理用の関数があり便利、というか普通はこれを使う 38
39. まとめ - Haskellの遅延評価は並列・並行処理に一役買っている - 並列処理はEvalモナドを使うと嬉しい - 並行処理はIOモナドを使うと嬉しい - STMが安全に処理できる言語はHaskellくらい - 純粋性と柔軟な型システムのおかげ - ぶっちゃけ困ったらasyncパッケージ使ってればいいと思います 39
40. 質問あればどうぞ - 前提としてWeb Frontend屋さんの僕は並列・並行処理に詳しくありません 40
41. 参考資料 - Haskellによる並列・並行プログラミング、オライリー・ジャパン - マルチコア時代の最新並列並行技術 Haskellから見える世界 - Control.Parallel.Strategies - Control.Concurrent - Control.Concurrent.MVar 41