haskell - 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

我们需要查看 Integer 的 enumFromTo 实例，最后:

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，它使用一个worker来展开一个列表直到达到其限制。

但是 up_list 在 go 帮助器中的 x 中是严格的(请参阅与 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 情况下保留列表，而不是在常规情况下？常规情况在恒定空间中运行良好，依赖于 Integer 和 last 的 enumFromTo 的惰性。该案例的 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 _ -> ()

这使其保留值(value)。

正如我们所见，up_list 的实现在其累加器中是严格的(因为它与 lim 进行比较，并且列表是惰性展开的 - 所以 last 应该能够在恒定的空间中消耗它)。手写表达式证实了这一点。

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

这至少告诉我们，它不是一个重击链，而是整个列表被严格构建并保留，直到被丢弃。

所以谜团是:在 ghci 中，什么在保留 last 的列表参数，而在 ghc 中则不然？

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