分析Haskell程序
Chr*_*lor 23 performance haskell strictness
我有一段代码,使用的概率分布重复采样sequence.在道德上,它做了这样的事情:
sampleMean :: MonadRandom m => Int -> m Float -> m Float
sampleMean n dist = do
xs <- sequence (replicate n dist)
return (sum xs)
除了它有点复杂.实际的代码我感兴趣的是函数likelihoodWeighting在此Github上回购.
我注意到运行时间非线性地缩放n.特别是,一旦n超过某个值,它就会达到内存限制,并且运行时间会爆炸.我不确定,但我认为这是因为sequence正在构建一长串的thunk,直到调用才会得到评估sum.
一旦我通过大约100,000个样本,该程序就会慢慢爬行.我想优化它(我的感觉是1000万个样本应该不是问题)所以我决定对它进行分析 - 但是我在理解分析器的输出方面遇到了一些麻烦.
剖析
我在一个main.hs运行我的函数的文件中创建了一个简短的可执行文件 这是做的输出
$ ghc -O2 -rtsopts main.hs
$ ./main +RTS -s
我注意到的第一件事 - 它分配了近1.5 GB的堆,并将60%的时间花在垃圾收集上.这通常表明懒惰太多了吗？
1,377,538,232 bytes allocated in the heap
1,195,050,032 bytes copied during GC
169,411,368 bytes maximum residency (12 sample(s))
7,360,232 bytes maximum slop
423 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 2574 collections, 0 parallel, 2.40s, 2.43s elapsed
Generation 1: 12 collections, 0 parallel, 1.07s, 1.28s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.92s ( 1.94s elapsed)
GC time 3.47s ( 3.70s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.23s ( 0.23s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 5.63s ( 5.87s elapsed)
%GC time 61.8% (63.1% elapsed)
Alloc rate 716,368,278 bytes per MUT second
Productivity 34.2% of total user, 32.7% of total elapsed
以下是结果
$ ./main +RTS -p
我第一次运行它时,结果发现有一个函数被重复调用,结果我可以记住它,加速了2倍.然而,这并没有解决空间泄漏问题.
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
main Main 434 4 0.0 0.0 100.0 100.0
likelihoodWeighting AI.Probability.Bayes 445 1 0.0 0.3 100.0 100.0
distributionLW AI.Probability.Bayes 448 1 0.0 2.6 0.0 2.6
getSampleLW AI.Probability.Bayes 446 100000 20.0 50.4 100.0 97.1
bnProb AI.Probability.Bayes 458 400000 0.0 0.0 0.0 0.0
bnCond AI.Probability.Bayes 457 400000 6.7 0.8 6.7 0.8
bnVals AI.Probability.Bayes 455 400000 20.0 6.3 26.7 7.1
bnParents AI.Probability.Bayes 456 400000 6.7 0.8 6.7 0.8
bnSubRef AI.Probability.Bayes 454 800000 13.3 13.5 13.3 13.5
weightedSample AI.Probability.Bayes 447 100000 26.7 23.9 33.3 25.3
bnProb AI.Probability.Bayes 453 100000 0.0 0.0 0.0 0.0
bnCond AI.Probability.Bayes 452 100000 0.0 0.2 0.0 0.2
bnVals AI.Probability.Bayes 450 100000 0.0 0.3 6.7 0.5
bnParents AI.Probability.Bayes 451 100000 6.7 0.2 6.7 0.2
bnSubRef AI.Probability.Bayes 449 200000 0.0 0.7 0.0 0.7
这是堆配置文件.我不知道为什么它声称运行时间是1.8秒 - 这个运行大约需要6秒.
任何人都可以帮我解释探查器的输出 - 即识别瓶颈的位置,并提供如何加快速度的建议？
Dan*_*her 13
一个巨大的进步已经通过合并实现JohnL的建议使用foldM在likelihoodWeighting.这减少了大约10倍的内存使用量,并使GC时间显着降低到几乎或实际上可以忽略不计.
使用当前源生成的分析运行
probabilityIO AI.Util.Util 26.1 42.4 413 290400000
weightedSample.go AI.Probability.Bayes 16.1 19.1 255 131200080
bnParents AI.Probability.Bayes 10.8 1.2 171 8000384
bnVals AI.Probability.Bayes 10.4 7.8 164 53603072
bnCond AI.Probability.Bayes 7.9 1.2 125 8000384
ndSubRef AI.Util.Array 4.8 9.2 76 63204112
bnSubRef AI.Probability.Bayes 4.7 8.1 75 55203072
likelihoodWeighting.func AI.Probability.Bayes 3.3 2.8 53 19195128
%! AI.Util.Util 3.3 0.5 53 3200000
bnProb AI.Probability.Bayes 2.5 0.0 40 16
bnProb.p AI.Probability.Bayes 2.5 3.5 40 24001152
likelihoodWeighting AI.Probability.Bayes 2.5 2.9 39 20000264
likelihoodWeighting.func.x AI.Probability.Bayes 2.3 0.2 37 1600000
报告的内存使用量为13MB -s,最大驻留时间约为5MB.那已经不是太糟糕了.
尽管如此,仍有一些我们可以改进的观点.首先,在宏观计划中,一个相对较小的事情AI.UTIl.Array.ndSubRef:
ndSubRef :: [Int] -> Int
ndSubRef ns = sum $ zipWith (*) (reverse ns) (map (2^) [0..])
反转列表,并映射(2^)到另一个列表是低效的,更好的是
ndSubRef = L.foldl' (\a d -> 2*a + d) 0
这不需要将整个列表保留在内存中(可能不是什么大问题,因为列表会很短)作为反转它,并且不需要分配第二个列表.分配的减少是显着的,大约10%,并且该部分运行速度明显更快,
ndSubRef AI.Util.Array 1.7 1.3 24 8000384
在修改后的运行的配置文件中,但由于它只占总时间的一小部分,因此整体影响很小.有潜在的更大的鱼鱼苗中weightedSample和likelihoodWeighting.
让我们添加一些严格性weightedSample来看看它是如何改变的:
weightedSample :: Ord e => BayesNet e -> [(e,Bool)] -> IO (Map e Bool, Prob)
weightedSample bn fixed =
go 1.0 (M.fromList fixed) (bnVars bn)
where
go w assignment [] = return (assignment, w)
go w assignment (v:vs) = if v `elem` vars
then
let w' = w * bnProb bn assignment (v, fixed %! v)
in go w' assignment vs
else do
let p = bnProb bn assignment (v,True)
x <- probabilityIO p
go w (M.insert v x assignment) vs
vars = map fst fixed
权重参数go永远不会被强制,也不是赋值参数,因此它们可以构建thunks.让我们启用{-# LANGUAGE BangPatterns #-}并强制更新立即生效,并p在将其传递给之前进行评估probabilityIO:
go w assignment (v:vs) = if v `elem` vars
then
let !w' = w * bnProb bn assignment (v, fixed %! v)
in go w' assignment vs
else do
let !p = bnProb bn assignment (v,True)
x <- probabilityIO p
let !assignment' = M.insert v x assignment
go w assignment' vs
这样可以进一步减少分配(~9%)和小幅加速(〜%13%),但总内存使用量和最大驻留时间并没有太大变化.
我没有看到任何明显改变的东西,所以让我们来看看likelihoodWeighting:
func m _ = do
(a, w) <- weightedSample bn fixed
let x = a ! e
return $! x `seq` w `seq` M.adjust (+w) x m
在最后一行,首先,w现在已经进行了评估weightedSample,所以我们不需要在seq这里,需要密钥x来评估更新的地图,因此seq也没有必要.那条线上的坏事是M.adjust.adjust无法强制更新函数的结果,因此在地图的值中构建thunk.您可以通过查找修改后的值并强制执行此操作来强制评估thunk,但这里Data.Map提供了一种更方便的方法,因为保证更新映射的键存在,insertWith':
func !m _ = do
(a, w) <- weightedSample bn fixed
let x = a ! e
return (M.insertWith' (+) x w m)
(注意:GHC在爆炸模式下m比在return $! ...这里更好地优化).这略微减少了总分配并且不会显着改变运行时间,但对使用的总内存和最大驻留时间有很大影响:
934,566,488 bytes allocated in the heap
1,441,744 bytes copied during GC
68,112 bytes maximum residency (1 sample(s))
23,272 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
运行时间的最大改进是避免randomIO,使用StdGen非常慢.
我很惊讶bn*功能花了多少时间,但没有看到任何明显的低效率.
我很难消化这些配置文件,但我之前已经把我的屁股踢了,因为MonadRandomHackage是严格的.创建一个懒惰的版本MonadRandom让我的记忆问题消失了.
我的同事还没有获得发布代码的许可,但我已经把它放在Control.Monad.LazyRandom了pastebin上.或者,如果你想看一些解释完全懒惰的随机搜索的摘录,包括无限的随机计算列表,请查看体验报告:计算生物学中的Haskell.