为什么在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相比会消耗越来越多的内存，而直接导入的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 却消耗着越来越多的内存。而直接导入 filter 定义的 r 则消耗着恒定的内存。

我的问题是，为什么 GHC 中直接导入的函数与我从 GHC 库中复制源代码编写的函数有这么大的差别。我想知道 GHC 是否出了什么问题。

我还有一个进一步的问题：上面的代码摘自我编写的一个项目，该项目也面临“理论上应该被垃圾回收的内存消耗增长”的问题。所以我想知道在 GHC 中有没有一种方法可以找到哪个变量占用了如此多的内存。

感谢您的阅读。

- TorosFanny

---

GHC版本，操作系统？我无法像那样复现实现elem时的内存增长。 - Koterpillar

从 GHC 库中复制的吗？实际上里面有比这些定义更多的内容，例如 {-# RULES "filter" [~1] forall p xs. filter p xs = build (\c n -> foldr (filterFB c p) n xs) #-}，这意味着你引用的定义通常不会被使用。 - 话虽如此，我也无法重现您的内存消耗问题。您使用了什么优化标志？ - leftaroundabout

我认为他指的是标准Prelude中的定义。顺便说一下，我也无法重现这个问题。 - mrueg

请注意，您简化实际代码的确切方式可能会产生很大的差异！例如，“大列表” [0..] 是否为 r、p 和 s 新计算的；还是以某种方式共享（作为顶级定义或作为函数的参数？）我想我们需要看到更多您的代码…… - yatima2975

你是用 -O2 编译的，但当你在 ghci 中运行时，内存消耗增加了，对吧？ - Daniel Fischer

Answer 1

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

让我们看一下使用-O2（-ddump-simpl）生成的ghc-7.4.2核心部分，首先是使用GHC.List.filter的r：

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 :: 整数，而 Has.p2 是 1 :: 整数。重写规则（针对于 filter 和 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被内联，效率可能会更高，但重点是要过滤的列表并不存在，因为它已经被融合掉了。

另一方面，对于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）和应用于(== 1000000000000)和列表的Has.filter创建了一个顶级CAF。

因此，这个函数确实创建了要过滤的实际列表，因此它的效率略低。

但通常（运行编译后的二进制文件），在内存消耗方面这并不是问题，因为列表在被使用时会进行垃圾回收。然而，由于某些我无法理解的原因，当评估p或s时，ghci会保留列表[0 .. ]（但它有自己的[0 .. ]副本，因此这里没有不需要的共享），这可以从-hT堆分析中得出（评估s，因此只有一个可能的列表单元来源。ghci使用+RTS -M300M -hT -RTS调用，因此在内存使用量达到300M后，ghci终止）。

因此，ghci中内存消耗的原因是将要过滤的列表硬编码。如果您在提示符提供的列表中使用Has.filter，则内存使用量与预期相同。 我不确定ghci保留列表[0 .. ]是错误还是有意为之。

- Daniel Fischer