Haskell程序的性能分析

Question

我有一段代码，用sequence从一个概率分布中重复采样。实际上，它做的事情类似于这样：

sampleMean :: MonadRandom m => Int -> m Float -> m Float
sampleMean n dist = do
  xs <- sequence (replicate n dist)
  return (sum xs)

除了这个问题有点复杂外，我感兴趣的实际代码是 likelihoodWeighting 函数，位于这个Github repo。

我发现运行时间与 n 的规模不成线性比例关系。特别是一旦 n 超过某个值，就会达到内存限制，并且运行时间急剧增加。我不能确定，但我认为这是因为 sequence 在建立一个长列表的 thunks，这些 thunks 直到调用 sum 之前都没有被求值。

一旦样本数超过约 100,000，程序就会变得非常缓慢。我想优化它（我认为 10,000,000 个样本不应该是问题），所以我决定对其进行分析 - 但我在理解分析器的输出方面遇到了一些困难。

---

分析器

我创建了一个名为 main.hs 的简短可执行文件，使用 100,000 个样本运行我的函数。这是执行的输出：

$ ghc -O2 -rtsopts main.hs
$ ./main +RTS -s

我注意到的第一件事是 - 它分配了近1.5GB的堆内存，并且将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秒。

有人可以帮助我解释分析器的输出吗？即识别瓶颈所在，并提供加速的建议？

- Chris Taylor

---

运行时间没有改变 - 这可能并不令人惊讶，因为 replicateM n 被定义为 sequence . replicate n。 - Chris Taylor

length xs 总是等于 n，不是吗？所以用 n 替换 (length xs)，这样 xs 就不必在任何时候完全驻留在内存中了。 - dave4420

@dave4420 这也可能触发列表融合优化，因为 sum 是一个列表消费者而 replicateM 是一个列表生成器。这将消除额外严格性的需要。 - dflemstr

@PeterHall 您对每次对 randomR 的调用都使用了相同的生成器，因此它每次生成的“随机”数都相同。您可以尝试类似以下代码（我没有测试过）： main = do { a <- sampleMean 10000 (randomRIO (0.0,1.0)); print a }。 - Chris Taylor

这句话的意思是：“它并不完全是这样，有点更加复杂，但我简化了它，因为额外的复杂性与我想要提出的问题无关。” - Chris Taylor

Answer 1

通过将JohnL的建议在likelihoodWeighting中使用foldM已经取得了巨大的进展。这在这里减少了约十倍的内存使用，并显著降低了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

通过-s报告的13MB内存使用和最大驻留量约为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函数的weight参数和赋值操作参数都没有被强制求值，因此它们可以积累thunk。让我们启用{-# LANGUAGE BangPatterns #-}并立即强制更新生效，同时在传递给probabilityIO之前对p进行求值：

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

在最后一行中，首先，在weightedSample中，w已经被求值了，因此我们不需要在这里再使用seq；键x需要用于计算更新后的map，因此也没有必要使用seq。该行代码的问题在于M.adjust。由于adjust无法强制执行更新函数的结果，因此会在map的值中构建thunk。你可以通过查找修改后的值并强制执行来评估这些thunk，但是在这里Data.Map提供了一个更便捷的方法，因为更新map的键保证已经存在，可以使用insertWith'来完成。

func !m _ = do
    (a, w) <- weightedSample bn fixed
    let x = a ! e
    return (M.insertWith' (+) x w m)

（注：在这里，使用对m使用严格模式比使用return $! ...更好地优化了 GHC。这略微降低了总分配量，并且不会显着改变运行时间，但对使用的总内存和最大驻留内存产生了巨大影响）：

 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*函数需要花费如此多的时间，但是没有看到明显的低效率。

- Daniel Fischer

---

谢谢你，Daniel。这非常有用。我已经按照你的建议进行了更改，并将研究如何摆脱 randomIO 的想法。现在感觉离编写“真正”的 Haskell 程序更接近了一些... - Chris Taylor

Answer 2

我很难消化这些概述，但因为Hackage上的MonadRandom是严格的，所以我以前曾被踢了一次。创建一个惰性版本的MonadRandom后，我的内存问题消失了。

我的同事还没有获得发布代码的许可，但我已经将Control.Monad.LazyRandom放在pastebin上。或者，如果您想看一些解释完全惰性的随机搜索的摘录，包括无限列表的随机计算，请查看Experience Report: Haskell in Computational Biology。

- Norman Ramsey

---

提出一个不那么严格的实现方案，而不是通常建议让它更加严格的建议，这样做会得到+1。 - Jan Christiansen

谢谢，这是一个有趣的想法。Daniel Fischer建议我摆脱对randomIO的调用，所以我想我的采样函数返回一个Rand a，然后使用evalRandIO调用它们是正确的方法。 - Chris Taylor

@Chris：我已经将我们的论文放到了网上；其中有一些使用 Rand a 进行计算的示例。我们只在顶层调用 evalRand，或者在分叉并行计算列表时才会调用它。 - Norman Ramsey

Answer 3

我整理了一个非常基础的例子，发布在这里：http://hpaste.org/71919。我不确定它是否和你的例子相似...它只是一个非常简单的东西，似乎能够工作。

使用-prof和-fprof-auto编译，并运行100000次迭代，产生以下剖析输出的头部（请原谅我的行数）：

  8 COST CENTRE                   MODULE               %time %alloc
  9 
 10 sample                        AI.Util.ProbDist      31.5   36.6
 11 bnParents                     AI.Probability.Bayes  23.2    0.0
 12 bnRank                        AI.Probability.Bayes  10.7   23.7
 13 weightedSample.go             AI.Probability.Bayes   9.6   13.4
 14 bnVars                        AI.Probability.Bayes   8.6   16.2
 15 likelihoodWeighting           AI.Probability.Bayes   3.8    4.2
 16 likelihoodWeighting.getSample AI.Probability.Bayes   2.1    0.7
 17 sample.cumulative             AI.Util.ProbDist       1.7    2.1
 18 bnCond                        AI.Probability.Bayes   1.6    0.0
 19 bnRank.ps                     AI.Probability.Bayes   1.1    0.0

以下是统计摘要：

1,433,944,752 bytes allocated in the heap
 1,016,435,800 bytes copied during GC
   176,719,648 bytes maximum residency (11 sample(s))
     1,900,232 bytes maximum slop
           400 MB total memory in use (0 MB lost due to fragmentation)

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    1.40s  (  1.41s elapsed)
GC      time    1.08s  (  1.24s elapsed)
Total   time    2.47s  (  2.65s elapsed)

%GC     time      43.6%  (46.8% elapsed)

Alloc rate    1,026,674,336 bytes per MUT second

Productivity  56.4% of total user, 52.6% of total elapsed

注意，性能分析器指向了sample。我通过使用$!在该函数中强制执行了return，以下是一些摘要统计信息：

1,776,908,816 bytes allocated in the heap
  165,232,656 bytes copied during GC
   34,963,136 bytes maximum residency (7 sample(s))
      483,192 bytes maximum slop
           68 MB total memory in use (0 MB lost due to fragmentation)

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    2.42s  (  2.44s elapsed)
GC      time    0.21s  (  0.23s elapsed)
Total   time    2.63s  (  2.68s elapsed)

%GC     time       7.9%  (8.8% elapsed)

Alloc rate    733,248,745 bytes per MUT second

Productivity  92.1% of total user, 90.4% of total elapsed

在垃圾回收方面更加高效，但时间上并没有太大改变。您可以继续在此配置/调整方式下迭代，以针对瓶颈并提高性能水平。

- jtobin

---

非常感谢！坦白地说，我很惊讶你读了我那么糟糕的代码，还能够组合出一个例子。 - Chris Taylor

快速提问 - 我正在使用“-prof -auto-all”编译我的测试脚本，但只有在添加显式的“{-# SCC #-}”注释时才能得到成本中心的分解。你是如何自动获取它们的？我尝试使用“-prof -fprof-auto”进行编译，但GCH无法识别第二个标志。 - Chris Taylor

你必须使用较旧的 GHC - 我正在使用支持这些分析选项的 7.4.1 版本。7.0.2 支持这些选项; 看起来 -auto-all 忽略了嵌套函数。 - jtobin

我一定做了什么愚蠢的事情 - 我正在使用 cabal install -p 安装库，然后使用 ghc -rtsopts -prof -fprof-auto --fforce-recomp -O2 --make main.hs 编译我的测试文件，但我仍然没有得到详细的性能分析信息。我有什么明显的错误吗？ - Chris Taylor

嗯，看起来没问题，而且这种方法在我的端口确实输出了所需的结果。不确定那里出了什么问题？ - jtobin

顺便说一下，我觉得我可能把错误的摘要统计信息复制到了我的答案中。再次检查后，强制在“sample”中使用“return”会使我们两个测试用例的速度提高约1.5倍，并且具有相同的高生产力。 - jtobin

Answer 4

我认为你的初步诊断是正确的，一旦内存效果开始发挥作用，我就再也没有见过有用的分析报告。

问题在于你正在遍历列表两次，一次是为了sequence，另一次是为了sum。在Haskell中，对大型列表进行多次遍历对性能非常不利。解决方案通常是使用某种类型的折叠函数，比如foldM。您的sampleMean函数可以编写为：

{-# LANGUAGE BangPatterns #-}

sampleMean2 :: MonadRandom m => Int -> m Float -> m Float
sampleMean2 n dist = foldM (\(!a) mb -> liftM (+a) mb) 0 $ replicate n dist

例如，只需遍历列表一次。

您也可以使用likelihoodWeighting执行相同的操作。为了防止thunks，重要的是要确保折叠函数中的累加器具有适当的严格性。

- John L

---

你的例子无法通过类型检查。step函数应该更像是liftM . (+)。它也可以更加严格；使用randomRIO进行测试时，较大的数字往往会导致堆栈溢出，也许可以尝试\a mb -> mb >>= \b -> return $! a + b？ - Vitus

谢谢，我会尝试使用fold重写likelihoodWeighting。 - Chris Taylor

@Vitus - 谢谢，已修复。我通常更喜欢使用惊叹号模式来增加严格性，但你的建议可能是相同的。 - John L