在GHC解释器中冗余使用seq时出现空间泄漏

Question

我将此代码键入解释器并快速占用内存:

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,Int或者Integer,因为我可以重现的行为,而他们wtf14和wtf16.

我尝试使用Peano算法重现问题,将列表和整数从等式中取出(在10 ^ 9的末尾取出),但遇到其他共享/空间泄漏问题,我在尝试实现时不明白*.

Answer 1

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

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然后进入up_list,它使用工人展开列表,直到达到其限制.

但是在帮助器中up_list是严格x的go(参见比较lim).

当在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案例中的列表,而不是常规案例？常规案例在constrant空间中很好地运行,依赖于enumFromTofor Integer和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,而是整个列表正在严格建立并保持不变,直到被丢弃.

所以神秘的是:什么是lastghci中的list参数,而不是ghc？

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

Answer 2

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

我将进行一个快速测试。