5
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的,但是为什么和直接使用的一样消耗越来越多的内存,和直接导入的相比,消耗的内存越来越多。elemfilter

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

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

正如上面的filterandelem的定义所暗示的, p = filter (==1000000000000) [0..]ands = 1000000000000 `elem` [0..][0..]应该逐渐被垃圾回收。但两者都p消耗s越来越多的内存。而r其中定义的直接导入filter会消耗一定数量的内存。

我的问题是为什么 GHC 中直接导入的函数与我使用从 GHC 库复制的源代码编写的函数有很大不同。我想知道GHC是否有问题?

我还有一个问题:上面的代码是从我写的一个项目中抽象出来的,这个项目也面临着“消耗越来越多的内存,理论上应该是垃圾回收”的问题。所以我想知道有没有办法找到 GHC 中哪个变量占用了这么多内存。

感谢您的阅读。

4

1 回答 1

1

ghci 中内存消耗的原因不是filteror的代码elemfilter(尽管in的重写规则GHC.List通常使它更好一点。)

让我们看一下使用 ( ) 生成的核心 ghc-7.4.2 的(部分-O2-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.p30 :: Integer,并且Has.p21 :: Integer。重写规则 (for filterand 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

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

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

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

在此处输入图像描述

所以ghci中内存消耗的原因是要过滤的列表的硬编码。如果您使用Has.filter提示符处提供的列表,则内存使用量与预期一样是恒定的。

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

于 2013-03-26T15:46:43.950 回答