为什么在GHC中直接导入的函数与我用GHC库复制的源代码编写的函数差别很大

Question

module Has (r,p,s) where

import Prelude ((==),Bool(..),otherwise,(||),Eq)
import qualified Data.List as L

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

问题1:这filter是从GHC库中复制的,但与直接导入的内存相比,为什么它会消耗越来越多的内存filter,这会占用一定数量的内存.

elem :: (Eq a) => a -> [a] -> Bool
elem _ []       = False
elem x (y:ys)   = x==y || elem x ys

问题2:这filter是从GHC库中复制的,但为什么它会消耗越来越多的内存,就像直接使用的内存一样elem,与直接导入相比,它也消耗了越来越多的内存.filter

r = L.filter (==1000000000000) [0..]
p = filter (==1000000000000) [0..]
s = 1000000000000 `elem` [0..]

GHC版本:7.4.2操作系统:Ubuntu 12.10用-O2编译进行优化

作为上述filter和elem的定义暗示两个p = filter (==1000000000000) [0..]和s = 1000000000000 `elem` [0..]的[0..]应垃圾收集逐渐.但两者p并s消耗越来越多的内存.并且r使用直接导入定义filter的内存消耗恒定的内存.

我的问题是为什么GHC中直接导入的函数与我用GHC库复制的源代码编写的函数差别很大.我想知道GHC是否有问题？

我还有一个问题:上面的代码是从我所编写的项目中抽象出来的,而且该项目还面临着"消耗越来越多的内存,这应该是理论上的垃圾收集"的问题.所以我想知道有没有办法找到哪个变量在GHC中占用了如此多的内存.

谢谢你的阅读.

Answer 1

ghci 中内存消耗的原因不是filteror的代码elem。filter（尽管in的重写规则GHC.List通常会使其好一些。）

-O2让我们看看用( )生成的核心ghc-7.4.2（部分）-ddump-simpl。首先对于r，使用GHC.List.filter：

Has.r1
  :: GHC.Integer.Type.Integer
     -> [GHC.Integer.Type.Integer] -> [GHC.Integer.Type.Integer]
[GblId,
 Arity=2,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [0 0] 60 30}]
Has.r1 =
  \ (x_awu :: GHC.Integer.Type.Integer)
    (r2_awv :: [GHC.Integer.Type.Integer]) ->
    case GHC.Integer.Type.eqInteger x_awu Has.p5 of _ {
      GHC.Types.False -> r2_awv;
      GHC.Types.True ->
        GHC.Types.: @ GHC.Integer.Type.Integer x_awu r2_awv
    }

Has.r :: [GHC.Integer.Type.Integer]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 40 0}]
Has.r =
  GHC.Enum.enumDeltaIntegerFB
    @ [GHC.Integer.Type.Integer] Has.r1 Has.p3 Has.p2

Has.p3是0 :: Integer，并且Has.p2是1 :: Integer。重写规则（ forfilter和enumDeltaInteger）将其变成（名称更短）

r = go fun 0 1
  where
    go foo x d = x `seq` (x `foo` (go foo (x+d) d))

fun n list
    | n == 1000000000000 = n : list
    | otherwise          = list

如果内联，这可能会更有效一些fun，但关键是要编辑的列表本身filter并不存在，它被融合了。

另一方面，如果p没有重写规则，我们得到

Has.p1 :: [GHC.Integer.Type.Integer]
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Has.p1 = GHC.Enum.enumDeltaInteger Has.p3 Has.p2

Has.p :: [GHC.Integer.Type.Integer]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Has.p = Has.filter @ GHC.Integer.Type.Integer Has.p4 Has.p1

列表的顶级 CAF [0 .. ]( Has.p1)，并Has.filter应用于(== 1000000000000)该列表。

所以这个确实创建了要过滤的实际列表 - 因此它的效率有点低。

但通常（运行已编译的二进制文件），这在内存消耗方面没有问题，因为列表在消耗时会被垃圾收集。然而，出于我无法理解的原因，ghci[0 .. ]在评估por时确实保留了该列表s（但它有自己的 副本[0 .. ]，因此这里不是不需要的共享），正如可以从-hT堆配置文件中收集到的那样（评估s，因此只有一个列表单元格的可能来源。ghci 使用 调用+RTS -M300M -hT -RTS，因此在内存使用量达到 300M 后不久，ghci 终止）：

所以ghci中内存消耗的原因是要过滤的列表的硬编码。如果您使用Has.filter提示时提供的列表，则内存使用量将按预期保持不变。

我不确定 ghci 保留列表[0 .. ]是错误还是有意行为。