Parallel Haskell - GHC清理sparks

Question

我有一个程序，现在想要实现并行处理（完整的代码可运行粘贴在这里）。

经过分析，发现大部分时间都花费在findNearest函数上，它基本上是对一个庞大的Data.Map进行简单的foldr操作。

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的作用是对较大的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在大部分Spark转化为有用的并行性之前就对它们进行了垃圾回收。

以下是使用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

如您所见，大多数火花在转换之前都会被垃圾回收或无法完成。我尝试使用不同的严格性进行实验，使findNearest返回自定义的严格对数据类型而不是元组，或者使用Control.Parallel.Strategies中的rdeepseq，但我的火花仍然被垃圾回收。

我想知道：

为什么我的火花在转换之前会被垃圾回收？

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

- cdk

---

http://www.haskell.org/haskellwiki/ThreadScope 可能会有所帮助。 - Boyd Stephen Smith Jr.

1. splitRoot 通常生成一个包含三个元素的列表，即左子树、根节点和右子树。因此，您正在一个非常小的列表上使用 parMap。这些元素本身相当大，但是 findNearest 本身并不是并行的。
2. 如果未使用 Spark 表达式，则会进行垃圾回收。也许您根本没有使用结果？

- Zeta

@Zeta：是的，列表的大小很小（只有3个元素），但Map的大小很大（65k ~ 250k个元素），因此即使将其分成两个大小适中的子树，也应该提供一些有用的并行性。 - cdk

Answer 1

我不是并行策略方面的专家，所以我的理解可能完全错误。但是:

如果通过设置足够大的分配区域（例如使用 -A20M runtime 选项）来禁用 GC，你会发现大多数火花都熄灭了，而不是被 GC 掉。这意味着它们在相应的火花完成之前就被普通程序流评估了。

minimumBy 立即强制执行 parMap，开始评估结果。同时，火花已经被调度和执行，但为时已晚。当火花完成时，该值已经被主线程评估。如果没有 -A20M，则火花将被 GC，因为该值已经在火花被调度之前被评估和 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)

有时它们会被垃圾回收。

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

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）。

- Yuras

---

我相信这就是火花被垃圾回收的原因。主线程在预定的火花有机会完成之前评估了'parMap'中的thunks。所以这回答了我的第一个问题，但第二个问题仍然存在：我如何高效地并行化这个过程？ - cdk

我认为这是不可能的。你的并行性太细粒度了，所以你需要重新思考你的算法。 - Yuras