并行哈斯克尔 - 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火花

回答

相关问题