IMO、Parモナドは並列処理についての推論に役立ちます。parとを扱うよりも少しレベルが高いですpseq。
これはモナドをparfindDivisors使った書き直しです。Parこれは基本的にアルゴリズムと同じであることに注意してください。
import Control.Monad.Par
findDivisors :: Integer -> [Integer]
findDivisors n = runPar $ do
[f0, f1] <- sequence [new, new]
fork $ put f0 (filter g [1..(quot n 4)])
fork $ put f1 (filter g [(quot n 4)+1..(quot n 2)])
[f0', f1'] <- sequence [get f0, get f1]
return $ f0' ++ f1'
where g z = n `rem` z == 0
でコンパイルして-O2 -threaded -rtsopts -eventlog実行する+RTS -N2 -sと、次の関連するランタイム統計が得られます。
36,000,130,784 bytes allocated in the heap
3,165,440 bytes copied during GC
48,464 bytes maximum residency (1 sample(s))
Tot time (elapsed) Avg pause Max pause
Gen 0 35162 colls, 35161 par 0.39s 0.32s 0.0000s 0.0006s
Gen 1 1 colls, 1 par 0.00s 0.00s 0.0002s 0.0002s
Parallel GC work balance: 1.32 (205296 / 155521, ideal 2)
MUT time 42.68s ( 21.48s elapsed)
GC time 0.39s ( 0.32s elapsed)
Total time 43.07s ( 21.80s elapsed)
Alloc rate 843,407,880 bytes per MUT second
Productivity 99.1% of total user, 195.8% of total elapsed
生産性は非常に高いです。GC のワーク バランスをわずかに改善するために、GC 割り当て領域のサイズを増やすことができます。で実行します+RTS -N2 -s -A128M。例:
36,000,131,336 bytes allocated in the heap
47,088 bytes copied during GC
49,808 bytes maximum residency (1 sample(s))
Tot time (elapsed) Avg pause Max pause
Gen 0 135 colls, 134 par 0.19s 0.10s 0.0007s 0.0009s
Gen 1 1 colls, 1 par 0.00s 0.00s 0.0010s 0.0010s
Parallel GC work balance: 1.62 (2918 / 1801, ideal 2)
MUT time 42.65s ( 21.49s elapsed)
GC time 0.20s ( 0.10s elapsed)
Total time 42.85s ( 21.59s elapsed)
Alloc rate 843,925,806 bytes per MUT second
Productivity 99.5% of total user, 197.5% of total elapsed
しかし、これは本当に単なるつまらないものです。本当の話は ThreadScope から来ています:
使用率は基本的に 2 つのコアで最大になるため、追加の大幅な並列化 (2 つのコアの場合) はおそらく発生しません。
Parモナドに関するいくつかの良いメモはhereです。
アップデート
を使用して代替アルゴリズムを書き直すと、次のParようになります。
findDivisors :: Integer -> [Integer]
findDivisors n = let sqrtn = floor (sqrt (fromInteger n)) in runPar $ do
[a, b] <- sequence [new, new]
fork $ put a [a | (a, b) <- [quotRem n x | x <- [1..sqrtn]], b == 0]
firstDivs <- get a
fork $ put b [n `quot` x | x <- firstDivs, x /= sqrtn]
secondDivs <- get b
return $ firstDivs ++ secondDivs
しかし、これは に依存しているため、並列処理から何の利益も得られないという点で正しいですfirstDivs。
Strategiesリスト内包表記の要素を並行して評価することに関与することで、ここでも並列処理を組み込むことができます。何かのようなもの：
import Control.Monad.Par
import Control.Parallel.Strategies
findDivisors :: Integer -> [Integer]
findDivisors n = let sqrtn = floor (sqrt (fromInteger n)) in runPar $ do
[a, b] <- sequence [new, new]
fork $ put a
([a | (a, b) <- [quotRem n x | x <- [1..sqrtn]], b == 0] `using` parListChunk 2 rdeepseq)
firstDivs <- get a
fork $ put b
([n `quot` x | x <- firstDivs, x /= sqrtn] `using` parListChunk 2 rdeepseq)
secondDivs <- get b
return $ firstDivs ++ secondDivs
これを実行すると、次のような統計が得られます
3,388,800 bytes allocated in the heap
43,656 bytes copied during GC
68,032 bytes maximum residency (1 sample(s))
Tot time (elapsed) Avg pause Max pause
Gen 0 5 colls, 4 par 0.00s 0.00s 0.0000s 0.0001s
Gen 1 1 colls, 1 par 0.00s 0.00s 0.0002s 0.0002s
Parallel GC work balance: 1.22 (2800 / 2290, ideal 2)
MUT time (elapsed) GC time (elapsed)
Task 0 (worker) : 0.01s ( 0.01s) 0.00s ( 0.00s)
Task 1 (worker) : 0.01s ( 0.01s) 0.00s ( 0.00s)
Task 2 (bound) : 0.01s ( 0.01s) 0.00s ( 0.00s)
Task 3 (worker) : 0.01s ( 0.01s) 0.00s ( 0.00s)
SPARKS: 50 (49 converted, 0 overflowed, 0 dud, 0 GC'd, 1 fizzled)
MUT time 0.01s ( 0.00s elapsed)
GC time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
Alloc rate 501,672,834 bytes per MUT second
Productivity 85.0% of total user, 95.2% of total elapsed
ここでは、ほぼ 50 個の火花が変換されました。つまり、意味のある並列作業が行われましたが、計算は、並列処理による壁時計のゲインを観察するのに十分な大きさではありませんでした。スレッド化されたランタイムでのスケジューリング計算のオーバーヘッドによって、おそらくすべての利点が相殺されました。