并行Haskell - GHC GC'ing火花

Question

我有一个程序,我正在尝试并行化(这里完全粘贴可运行的代码).

我已经分析过并发现大部分时间花费在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

正如您所看到的,大多数火花在转换之前都是GC或fizzle.我已尝试尝试不同的严格性,findNearest返回自定义严格对数据类型而不是元组,或使用rdeepseq Control.Parallel.Strategies,但我的火花仍然是GC'd.

我想知道

• 为什么我的火花在被转换之前是GC？
• 如何更改程序以利用并行性？

Answer 1

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

如果您通过设置足够大的分配区域（例如使用-A20M运行时选项）来禁用 GC，您将看到大多数火花都失败了，而不是 GC。这意味着它们在相应的火花完成之前通过普通程序流程进行评估。

minimumByparMap立即得出结果，并开始对其进行评估。与此同时，火花被调度并执行，但为时已晚。当 Spark 完成时，主线程已经评估了该值。如果没有-A20M，spark 会被 GC 处理，因为甚至在调度 Spark 之前就会对值进行评估和 GC 处理。

这是一个简化的测试用例：

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

在这种情况下，所有的火花都会熄灭：

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

（有时它们会被 GC 处理）

但是如果我在打印结果之前放弃主线程，

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在我的示例中设置）。