並行哈斯克爾 - GHC GC'ing火花

我有一個程序，我試圖並行化（完全粘貼可運行代碼here）。並行哈斯克爾 - GHC GC'ing火花

我已經介紹過並發現大部分時間都花在findNearest之上，這實際上是一個簡單的foldr，而不是一個大的Data.Map。

findNearest :: RGB -> M.Map k RGB -> (k, Word32) 
findNearest rgb m0 = 
    M.foldrWithKey' minDistance (k0, distance rgb r0) m0 
    where (k0, r0) = M.findMin m0 
      minDistance k r [email protected](_, d1) = 
      -- Euclidean distance in RGB-space 
      let d0 = distance rgb r 
      in if d0 < d1 then (k, d0) else x

parFindNearest應該並聯在較大Map的子樹執行findNearest。

parFindNearest :: NFData k => RGB -> M.Map k RGB -> (k, Word32) 
parFindNearest rgb = minimumBy (comparing snd) 
        . parMap rdeepseq (findNearest rgb) 
        . M.splitRoot

不幸的是，GHC GC是我的火花之前，他們轉換成有用的並行。

下面是與ghc -O2 -threaded編譯並與+RTS -s -N2

839,892,616 bytes allocated in the heap 
123,999,464 bytes copied during GC 
    5,320,184 bytes maximum residency (19 sample(s)) 
    3,214,200 bytes maximum slop 
      16 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  1550 colls, 1550 par 0.23s 0.11s  0.0001s 0.0004s 
    Gen 1  19 colls, 18 par 0.11s 0.06s  0.0030s 0.0052s 

    Parallel GC work balance: 16.48% (serial 0%, perfect 100%) 

    TASKS: 6 (1 bound, 5 peak workers (5 total), using -N2) 

    SPARKS: 215623 (1318 converted, 0 overflowed, 0 dud, 198111 GC'd, 16194 fizzled) 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 3.72s ( 3.66s elapsed) 
    GC  time 0.34s ( 0.17s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 4.07s ( 3.84s elapsed) 

    Alloc rate 225,726,318 bytes per MUT second 

    Productivity 91.6% of total user, 97.1% of total elapsed 

gc_alloc_block_sync: 9862 
whitehole_spin: 0 
gen[0].sync: 0 
gen[1].sync: 2103

運行正如你所看到的結果，大多數火花都GC'd或轉換之前以失敗告終。我嘗試過使用不同的嚴格性，讓findNearest返回一個自定義嚴格配對數據類型而不是元組，或使用Control.Parallel.Strategies的rdeepseq，但我的火花仍然是GC'd。

我想知道

爲什麼我的火花被轉換之前GC'd？
我該如何改變我的程序以利用並行性？

來源

2014-03-25 cdk

http://www.haskell.org/haskellwiki/ThreadScope可能會有所幫助。 –

1.'splitRoot'通常生成一個包含三個元素的列表，即左樹，右樹和右樹。所以你通過_very_小列表使用'parMap'。元素本身非常大，但是'findNearest'又不是平行的。 2.如果未使用，則觸發的表達式爲GC'd。也許你畢竟沒有使用結果？ – Zeta

@Zeta：是的，列表的大小很小（只有3個元素），但Map的大小很大（65k〜250k元素），所以即使將它分割成兩個大的子樹也應該提供一些有用的並行性。 – cdk

我並不擅長並行策略，所以我可能完全錯誤。但是：

如果您通過設置足夠大的分配區域來禁用GC（例如，使用-A20M運行時選項），您將看到大部分火花熄滅，而不是GC'd。這意味着它們在相應的火花完成之前通過普通程序流程進行評估。

minimumBy強制parMap結果立即開始評估它們。同時，火花計劃和執行，但已爲時過晚。火花完成後，該值已由主線程評估。如果沒有-A20M，則火花是GC'd，因爲即使在計劃火花之前，也會評估該值並GC'd。

這裏是一個簡化的測試案例：

import Control.Parallel.Strategies 

f :: Integer -> Integer 
f 0 = 1 
f n = n * f (n - 1) 

main :: IO() 
main = do 
    let l = [n..n+10] 
     n = 1 
     res = parMap rdeepseq f l 
    print res

在這種情況下，所有的火花告吹：

（有些時候，他們是GC'd）

但是，如果我打印結果前產出主線，

import Control.Parallel.Strategies 
import Control.Concurrent 

f :: Integer -> Integer 
f 0 = 1 
f n = n * f (n - 1) 

main :: IO() 
main = do 
    let l = [n..n+10] 
     n = 1 
     res = parMap rdeepseq f l 
    res `seq` threadDelay 1 
    print res

然後所有的火花轉換：

SPARKS: 11 (11 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

所以，看起來你有沒有足夠的火花（嘗試設置l = [n..n+1000]在我的例子），他們沒有足夠的重（嘗試設置n = 1000在我的例子）。

來源

2014-03-26 11:50:10 Yuras

我相信這就是爲什麼火花正在GC'd。主線程在計劃的火花有機會完成之前正在評估'parMap'中的thunk。所以這回答了我的第一個問題，但第二個問題仍然存在：我如何有效地將其並行化？ – cdk

我不認爲這是可能的。你有太細的並行性，所以你必須重新考慮你的算法。 – Yuras

並行哈斯克爾 - GHC GC'ing火花

回答

相關問題