Haskell：如何检测“惰性内存泄漏”

Question

经过几个小时的调试，我意识到一个非常简单的玩具示例由于表达式!中缺少return $ 1 + x而效率不高（感谢duplode！...但是ghc为何无法对此进行优化？） 。我也意识到了这一点，因为我将它与更快的Python代码进行了比较，但我不会总是编写Python代码来对我的代码进行基准测试...

所以这是我的问题：有没有一种方法可以自动检测这些“懒惰的内存泄漏”，从而无缘无故地降低程序运行速度？优化Haskell代码仍然很糟糕，而且即使您进行了实验，我也很可能忘记!。

我知道：

• +RTS -s，但我不确定如何解释：例如，对于一个简单的程序来说，看到内存79MB对我来说似乎很重要，但也许不是，因为这是我当前程序的原因……并且对于较大的程序，不可能以这种方式检测“惰性泄漏”，因为我不知道程序应该占用的内存量。
• cabal v2-run --enable-profiling mysatsolvers -- +RTS -p命令，但是似乎启用了探查器似乎会破坏GHC所做的一些优化，因此很难将这些值用于实际基准测试。而且，我仍然不清楚如何从该输出中查找泄漏。

例如，您能解释一下我如何在这样的玩具程序中发现“懒漏”吗？

{-# LANGUAGE DerivingVia, FlexibleInstances, ScopedTypeVariables #-}
module Main where

--- It depends on the transformers, containers, and base packages.
--- Optimisation seems to be important or the NoLog case will be way to long.
--- $ ghc -O Main.hs

import qualified Data.Map.Strict as MapStrict
import Data.Functor.Identity

import qualified Control.Monad as CM
import qualified Control.Monad.State.Strict as State
import qualified Data.Time as Time

-- Create a class that allows me to use the function "myTell"
-- that adds a number in the writer (either the LogEntry
-- or StupidLogEntry one)
class Monad m => LogFunctionCalls m where
  myTell :: String -> Int -> m ()

---------- Logging disabled ----------
--- (No logging at all gives the same time so I don't put here)
newtype NoLog a = NoLog { unNoLog :: a }
  deriving (Functor, Applicative, Monad) via Identity

instance LogFunctionCalls NoLog where
  myTell _ _ = pure ()

---------- Logging with Map ----------
-- When logging, associate a number to each name.
newtype LogEntryMap = LogEntryMap (MapStrict.Map String Int)
  deriving (Eq, Show)

instance LogFunctionCalls (State.State LogEntryMap) where
  myTell namefunction n = State.modify' $
    \(LogEntryMap m) ->
      LogEntryMap $ MapStrict.insertWith (+) namefunction n m

---------- Logging with Int ----------
-- Don't use any Map to avoid inefficiency of Map
newtype LogEntryInt = LogEntryInt Int
  deriving (Eq, Show)

instance LogFunctionCalls (State.State LogEntryInt) where
  myTell namefunction n = State.modify' $
    \(LogEntryInt m) -> LogEntryInt $! m + n

---------- Function to compute ----------
countNumberCalls :: (LogFunctionCalls m) => Int -> m Int
countNumberCalls 0 = return 0
countNumberCalls n = do
  myTell "countNumberCalls" 1
  x <- countNumberCalls $! n - 1
  return $ 1 + x

main :: IO ()
main = do
  let www = 15000000
  putStrLn $ "Let's start!"
  --- Logging disabled
  t0 <- Time.getCurrentTime
  let n = unNoLog $ countNumberCalls www
  putStrLn $ "Logging disabled: " ++ (show n)
  t1 <- Time.getCurrentTime
  print (Time.diffUTCTime t1 t0)
  -- Logging with Map
  let (n, LogEntryMap log) = State.runState (countNumberCalls www) (LogEntryMap MapStrict.empty)
  putStrLn $ "Logging with Map: " ++ (show n)
  putStrLn $ (show $ log)
  t2 <- Time.getCurrentTime
  print (Time.diffUTCTime t2 t1)
  -- Logging with Int
  let (n, LogEntryInt log) = State.runState (countNumberCalls www) (LogEntryInt 0)
  putStrLn $ "Logging with Int: " ++ (show n)
  putStrLn $ (show $ log)
  t3 <- Time.getCurrentTime
  print (Time.diffUTCTime t3 t2)

Answer 1

用于检测内存泄漏的主要方法是堆分析。具体来说，您正在寻找resident（主要是堆）内存量的意外增长，或者是+RTS -s统计信息输出中的最大驻留时间，或者-更可靠地-特征为“金字塔”形状使用+RTS -h<x>标志和hp2ps工具生成的堆概要文件输出中的时间。

如果我使用+RTS -s运行您的玩具程序，则会看到：

   3,281,896,520 bytes allocated in the heap
   3,383,195,568 bytes copied during GC
     599,346,304 bytes maximum residency (17 sample(s))
       5,706,584 bytes maximum slop
             571 MB total memory in use (0 MB lost due to fragmentation)

第一行通常可以忽略。 Haskell程序通常在运行时每秒分配大致恒定的内存量，并且该分配速率接近于零（对于某些异常程序而言）或每秒0.5-2.0 GB。该程序运行了4秒钟并分配了3.8 GB的数据，这并不稀奇。

不过，有关在GC和最大驻留期间复制的字节。假设您有一个程序希望在恒定的空间中运行（即，没有一个需要不断增长的数据结构，其全部内容都需要），那么运行正常的Haskell程序通常在垃圾回收期间将不需要复制大量数据，并且倾向于最大驻留时间只占分配的总字节数的一小部分（例如100 KB，而不是半GB），并且无论您要测试的是什么，“迭代次数”都不会大大增加。

您可以随时间生成快速的堆配置文件，而无需打开正式的性能分析。如果使用GHC标志-rtsopts进行编译，则可以使用：

./Toy +RTS -hT

然后使用hp2ps工具以图形方式显示结果：

hp2ps -c -e8in Toy.hp
evince Toy.ps &

这种金字塔图案是一个红旗：

请注意，堆的线性快速增长达到每秒数百兆字节，随后线性快速崩溃。这是您在一次强制执行整个计算之前不必要地构建巨大的惰性数据结构时看到的模式。您在这里看到两个金字塔，因为第二个和第三个测试都显示内存泄漏。

另外，x轴的单位为“ MUT秒”（“ mutator”正在运行的秒数，其中不包括垃圾回收），因此这比实际的4秒运行时间短。这实际上是另一个危险信号。花费一半时间进行垃圾收集的Haskell程序可能无法正确运行。

[要详细了解导致此堆金字塔的原因，您需要在启用概要分析的情况下进行编译。分析可能会导致程序运行速度变慢，但通常不会更改已进行的优化。但是，自动插入成本中心的标志-fprof-auto（及相关标志）可能会导致较大的性能变化（通过干扰内联等）。不幸的是，cabal --enable-profiling标志打开了性能分析（编译器标志-prof）和标志-fprof-auto-top会自动为顶级功能生成成本中心，因此对于您的玩具示例来说，这将大大改变行为第一个测试用例的运行时间（即使没有+RTS标志，运行时间也将从0.4秒增加到5秒）。这可能是您在分析中看到的问题会影响您的结果。对于其他几种堆配置文件，您不需要任何成本中心，因此您可以添加cabal标志--profiling-detail=none以将其关闭，然后，配置文件的程序应在运行时稍慢一些，但性能通常与未配置文件相似版本。

我不使用Cabal，但使用以下内容进行编译（应与--enable-profiling --profiling-detail=none等效：]

ghc -O2 -rtsopts -prof Toy.hs    # no -fprof-auto...

我可以通过数据类型来运行您的程序：

./Toy +RTS -hy

如果我查看堆配置文件图：

这将大部分堆归因于Int类型-这将我的问题缩小为一堆未经评估的懒惰Int计算，这可能会为我指明正确的方向。

如果我真的在缩小范围方面遇到困难，并且感觉像是技术上的深潜，我也可以通过闭包（标志-hd）运行堆概要文件。这告诉我，两个金字塔的罪魁祸首分别是Main.sat_s7mQ和Main.sat_s7kP。这看起来很神秘，但是它们是“ STG”中函数的名称，“ STG”是编译器生成的我的程序的低级中间表示。

如果我使用相同的标志重新编译，但添加-fforce-recomp -ddump-stg -dsuppress-all：

ghc -O2 -rtsopts -prof -fforce-recomp -ddump-stg -dsuppress-all Toy.hs
这将转储包含这两个函数的定义的STG。 （生成的标识符可能会随代码和/或编译器标志的微小变化而有所不同，因此最好使用转储的STG重新编译，然后重新配置该可执行文件，以确保标识符匹配。）

如果我在STG中搜索第一个罪魁祸首，则会找到定义：

sat_s7mQ =
    CCCS \u []
        case ww2_s7mL of {
          I# y_s7mO ->
              case +# [1# y_s7mO] of sat_s7mP {
                __DEFAULT -> I# [sat_s7mP];
              };
        };
是的，这都是非常技术性的，但这是表达式1 + y的STG代名词，它将帮助我零点查找罪魁祸首。

如果您不会讲STG，可以尝试引入一些费用中心。例如，我尝试使用-fprof-auto（Cabal标志--profiling-detail=all-functions）对您的第二个测试用例进行[[only

配置文件分析。 Toy.prof中的配置文件输出对于内存泄漏不是很有用，因为它处理的是总分配，而不是随着时间的推移进行活动（即，驻留且未收集垃圾）分配，但是您可以按成本创建堆配置文件通过运行居中：./Toy +RTS -hc 在这种情况下，它将所有内容都归于单个成本中心，即(315)countNumberCalls。如果名称中不清楚，您可以在Toy.prof输入中查找“ 315”是成本中心编号，以查找确切的源代码行。无论如何，这至少有助于将问题缩小到countNumberCalls。

对于更复杂的功能，有时可以通过手动指定成本中心来进一步缩小问题范围，例如：

countNumberCalls :: (LogFunctionCalls m) => Int -> m Int
countNumberCalls 0 = return 0
countNumberCalls n = do
  {-# SCC "mytell_call" #-} myTell "countNumberCalls" 1
  x <- {-# SCC "recursive_call" #-} countNumberCalls $! n - 1
  {-# SCC "return_statment" #-} return $ {-# SCC "one_plus_x" #-} 1 + x

这实际上将所有内容都归因于“ recursive_call”，因此它没有帮助。

不过，这没错。实际上，您在这里有两次内存泄漏-x <- countNumberCalls $! n - 1泄漏堆，因为没有强制使用x，而1 + x泄漏堆栈。您可以启用BangPatterns扩展名并输入：

!x <- countNumebrCalls $1 n - 1

这实际上将消除内存泄漏之一，将第二种情况从2.5秒加速到1.0秒，并将最大驻留时间从460兆降低到95兆（并且在GC期间复制的字节从1.5兆降低到73字节！） 。但是，堆概要文件将显示线性增长的堆栈，几乎占了所有常驻内存。由于堆栈的跟踪不如堆好，因此很难跟踪。

你问
[return $ 1 + x [...]，但是ghc如何无法优化它？？
答案是严格评估和惰性评估具有微妙的语义，因此使GHC优化可能会破坏您的程序。
区别在于未定义值的处理。任何评估undefined的尝试都会引发异常。在GHCi中：
Prelude> undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:1:1 in interactive:Ghci1
如果我的表达式包含未定义，则会发生相同的事情：
Prelude> 2 + undefined
*** Exception: Prelude.undefined [...]
但是，如果评估从未达到未定义状态，那么一切都很好：
Prelude> True || undefined
True
[Haskell使用“非严格语义”和“惰性评估”。从技术上讲，非严格语义是Haskell定义的一部分，而惰性评估是GHC中的实现机制，但是您可以将它们视为同义词。当您定义变量时，不会立即计算该值，因此，如果您从不使用该变量，则不会有问题：
Prelude> let b = undefined
Prelude> b
*** Exception: Prelude.undefined
let正常工作，但是评估其定义的变量将引发异常。
[现在考虑您未评估的1+来电高耸的堆栈。 GHC无法预先知道您是否将要使用该结果（请参见下文），也无法知道某个地方是否存在异常。作为程序员，您可能会知道有一个例外，并且依靠Haskell的非严格语义仔细地不看结果。如果GHC过早评估并获得异常，则您的程序在不应该执行的情况下将失败。
实际上，GHC编译器包含一个称为Demand Analyser的优化程序（以前称为“严格性分析器”），该优化程序以完全所需的方式寻找优化机会。但是它有局限性，因为它只能在可以[
这里的另一个皱纹是您使用了State monad。实际上，这有两个变体。懒惰和严格。 Strict变体在被写入时会强制状态，但是Lazy变体（默认）不会。

Answer 2