我有一个程序,现在想要实现并行处理(完整的代码可运行粘贴在这里)。
经过分析,发现大部分时间都花费在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,但我的火花仍然被垃圾回收。我想知道:
splitRoot
通常生成一个包含三个元素的列表,即左子树、根节点和右子树。因此,您正在一个非常小的列表上使用parMap
。这些元素本身相当大,但是findNearest
本身并不是并行的。Map
的大小很大(65k ~ 250k个元素),因此即使将其分成两个大小适中的子树,也应该提供一些有用的并行性。 - cdk