haskell - Parallel Haskell - GHC GC'ing sparks

Question

我有一个我正在尝试并行化的程序(带有可运行代码的完整粘贴 here )。

我分析并发现大部分时间都花在 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 x@(_, d1) =
            -- Euclidean distance in RGB-space
            let d0 = distance rgb r
            in if d0 < d1 then (k, d0) else x

parFindNearest应该执行 findNearest在较大的 Map 的子树上并行.

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

如您所见，大多数 Spark 在转换之前都经过 GC 处理或失败。我尝试过不同的严格性，有 findNearest返回自定义严格对数据类型而不是元组
, 或使用 Control.Parallel.Strategies 中的 rdeepseq ，但我的 Spark 仍然是 GC'd。

我想知道

为什么我的 Spark 在被转换之前会被 GC 处理？

如何更改我的程序以利用并行性？

Answer 1

我不是平行策略方面的专家，所以我可能完全错了。但:

如果您通过设置足够大的分配区域来禁用 GC(例如，使用 -A20M 运行时选项)，您会看到大多数 spark 已失败，而不是 GC。这意味着它们在相应的 Spark 完成之前通过普通程序流程进行评估。
minimumBy部队parMap立即获得结果，开始评估它们。同时，sparks被调度和执行，但为时已晚。当 spark 完成时，主线程已经评估了该值。没有 -A20M , sparks 是 GC'd 因为值是在调度 spark 之前评估和 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

在那种情况下，所有的 Spark 都消失了:

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

(有时它们是 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

然后所有的 Spark 被转换:

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

所以，看起来你没有足够的 Spark (尝试设置 l = [n..n+1000] 在我的示例中)，并且它们不够重(尝试设置 n = 1000 在我的示例中)。