22

我将这段代码输入解释器,内存很快被消耗:

last [1..10^7] `seq` ()

我不明白为什么这需要超过 O(1) 的空间。如果我这样做(应该是一样的,因为 Show 强制弱头部正常形式,所以 seq 是多余的?):

last [1..10^7]

...它工作正常。

我无法在口译员之外重现这种情况。

这里发生了什么?


以下是一些测试用例: http ://hpaste.org/69234

注意事项:

  • 通过在解释器中运行,我加载 wtf.hs 而不编译它,然后输入wtf<n>ghci。
  • 通过编译,我做到了ghc --make wtf.hs && ./wtf
  • last可以sum用严格的累加器或在列表中找到最大元素的函数替换,空间泄漏仍然发生
  • 使用$!而不是seq.
  • 我尝试添加一个虚拟()参数,因为我认为这可能是 CAF 问题。没有任何改变。
  • 上的函数可能不是问题Enum,因为我可以用和以后重现该行为,而这些行为wtf5根本不使用Enum
  • , 或可能不是问题Num,因为我可以在没有它们的情况下重现行为and 。IntIntegerwtf14wtf16

我尝试使用 Peano 算法重现问题,以将列表和整数排除在等式之外(获取 10^9 末尾的 ),但在尝试实现时遇到了我不理解的其他共享/空间泄漏问题*

4

2 回答 2

15

我们需要查看enumFromTofor Integer 的实例,最后:

last []                 =  errorEmptyList "last"
last (x:xs)             =  last' x xs
  where last' y []     = y
        last' _ (y:ys) = last' y ys

它在 GHC.Enum 中定义为:

enumFrom x             = enumDeltaInteger  x 1
enumFromThen x y       = enumDeltaInteger  x (y-x)
enumFromTo x lim       = enumDeltaToInteger x 1 lim

在哪里

enumDeltaInteger :: Integer -> Integer -> [Integer]
enumDeltaInteger x d = x `seq` (x : enumDeltaInteger (x+d) d)
-- strict accumulator, so
--     head (drop 1000000 [1 .. ]
-- works

enumDeltaToInteger :: Integer -> Integer -> Integer -> [Integer]
enumDeltaToInteger x delta lim
  | delta >= 0 = up_list x delta lim
  | otherwise  = dn_list x delta lim

up_list :: Integer -> Integer -> Integer -> [Integer]
up_list x0 delta lim = go (x0 :: Integer)
                where
                    go x | x > lim   = []
                         | otherwise = x : go (x+delta)

last正如预期的那样,完全懒惰。

对于 Integer Enum 类,我们有一个严格的累加器(明确地)用于enumFrom. 在有界情况下(例如[1..n]),它调用enumDeltaToInteger然后 into up_list,它使用工作人员展开列表,直到达到其限制。

但是在助手up_list中是严格的(参见与 的比较)。xgolim

当在 GHCi 中运行时,这些都没有被优化,在返回之前产生对 enumFromTo 的天真的调用()

let
  it_ax6 :: ()      
  it_ax6 =
    case last
           @ GHC.Integer.Type.Integer
           (GHC.Enum.enumFromTo
              @ GHC.Integer.Type.Integer
              GHC.Num.$fEnumInteger
              (GHC.Integer.smallInteger 1)
              (GHC.Real.^
                 @ GHC.Integer.Type.Integer
                 @ GHC.Integer.Type.Integer
                 GHC.Num.$fNumInteger
                 GHC.Real.$fIntegralInteger
                 (GHC.Integer.smallInteger 10)
                 (GHC.Integer.smallInteger 7)))
    of _ -> GHC.Unit.()
in
  GHC.Base.thenIO
    @ ()
    @ [()]
    (System.IO.print @ () GHC.Show.$fShow() it_ax6)
    (GHC.Base.returnIO
       @ [()] (GHC.Types.: @ () it_ax6 (GHC.Types.[] @ ())))

那么,为什么我们在seq案例中保留列表,而不是在常规案例中?依靠enumFromToforInteger和 for的惰性,常规案例在恒定空间中运行良好last。该案例的 GHCi 核心如下所示:

let {
  it_aKj :: GHC.Integer.Type.Integer
  [LclId,
   Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False,
           ConLike=False, Cheap=False, Expandable=False,
           Guidance=IF_ARGS [] 170 0}]
  it_aKj =
    GHC.List.last
      @ GHC.Integer.Type.Integer
      (GHC.Enum.enumFromTo
         @ GHC.Integer.Type.Integer
         GHC.Num.$fEnumInteger
         (GHC.Integer.smallInteger 1)
         (GHC.Real.^
            @ GHC.Integer.Type.Integer
            @ GHC.Integer.Type.Integer
            GHC.Num.$fNumInteger
            GHC.Real.$fIntegralInteger
            (GHC.Integer.smallInteger 10)
            (GHC.Integer.smallInteger 7))) } in
GHC.Base.thenIO
  @ ()
  @ [()]
  (System.IO.print
     @ GHC.Integer.Type.Integer GHC.Num.$fShowInteger it_aKj)
  (GHC.Base.returnIO
     @ [()]
     (GHC.Types.:
        @ ()
        (it_aKj
         `cast` (UnsafeCo GHC.Integer.Type.Integer ()
                 :: GHC.Integer.Type.Integer ~ ()))
        (GHC.Types.[] @ ())))

所以这些几乎是相同的,不同之处在于:

  • seq版本中,last (enumFromTo ..)被强制在case.
  • 在普通版本中,它是一个懒惰的let.
  • 在该seq版本中,该值被计算然后丢弃,产生一个()-- 什么都不看结果
  • 在正常情况下,它会被检查并显示。

奇怪的是,没有什么神奇的:

let x = case last (enumFromTo 1 n) of _ -> ()

这使它保留了价值。

正如我们所看到的,up_list它的累加器中的实现是严格的(因为它与 比较lim,并且列表是延迟展开的——所以last应该能够在恒定空间中使用它)。手写表达式证实了这一点。

对 ghci 执行进行堆分析会显示整个列表被保留:

在此处输入图像描述

这至少告诉我们它不是一连串的 thunk,而是整个列表正在严格构建并保留,直到被丢弃。

所以谜团在于:last在 ghci 中,而不是在 ghc 中,是什么保留了 list 参数?

我现在怀疑 ghci 的一些内部(或微妙)细节——我认为这值得一张 ghci 票。

于 2012-05-29T12:56:14.490 回答
1

我认为@nm 是对的。没有什么会强制列表中的,因此 1+1+1+1+... thunk 最终会杀死空间。

我会做一个快速测试。

于 2012-05-29T11:28:27.133 回答