在 GHC 解释器中使用 seq 导致空间泄漏问题

Question

我将这段代码输入解释器，内存迅速消耗：

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

我不明白为什么这需要超过O(1)的空间。如果我只执行以下操作（应该是相同的，因为Show强制使用弱头正常形式，所以序列是多余的？）：

last [1..10^7]

...它可以正常工作。

我无法在解释器外重现这种情况。

这里发生了什么？

---

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

需要注意的事项：

• 通过在解释器中运行，我在不编译代码的情况下加载 wtf.hs，并在 ghci 中键入 wtf<n>。
• 通过编译，我执行 ghc --make wtf.hs && ./wtf。
• last 可以被一个具有严格累加器的 sum 或者一个查找列表中最大元素的函数所替代，但空间泄漏仍然会发生。
• 使用 $! 代替 seq 后，我没有看到这种行为。
• 我尝试添加一个虚拟的 () 参数，因为我认为这可能是 CAF 问题。但是没有任何变化。
• 这可能不是与 Enum 上的函数有关的问题，因为我可以在完全不使用 Enum 的情况下在 wtf5 和之后重现这种行为。
• 这可能不是与 Num、Int 或者 Integer 有关的问题，因为我可以在 wtf14 和 wtf16 中没有使用它们的情况下重现这种行为。

我尝试使用 Peano 算术来消除列表和整数的影响（在 10^9 结束时获取值），但在尝试实现 * 时遇到了其他共享/空间泄漏问题，我不理解这些问题。

- L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳

---

这可能与扩展默认规则有关吗？ - Lambda Fairy

@ChrisWong 嗯，如果类型默认值是罪魁祸首，那么修复类型，例如 seq (last [1::Int ..10^8]) () 应该已经解决了这个问题... - hvr

我尝试了不同的无限列表示例。使用 repeat 1 没有空间泄漏，而使用 [1,1..] 则有。也许 enumFrom 和相关函数的算术运算在某种程度上负责？ - n. m.

@n.m. 这是因为 repeat 生成的无限列表由于共享而占用恒定的空间。如果您尝试使用 map id (repeat 1) 来破坏共享，则会再次泄漏。 - hammar

当执行 last (map id (repeat 1)) ^seq^ () 时会发生泄漏，但是执行 last (map id (repeat ())) ^seq^ () 不会。然而，当执行 last (map id (repeat Wtf)) ^seq^ () 时，其中 data Wtf = Wtf，仍会发生泄漏。 - L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳

Answer 1

我们需要查看针对整数的 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是完全惰性的，这一点是可以预料的。

对于整数枚举类，我们为enumFrom（显式地）设置了一个严格的累加器。在有界情况下（例如[1..n]），它调用enumDeltaToInteger然后进入up_list，up_list使用一个worker来展开列表直到达到其限制。

但是在go辅助函数中，up_list对x是严格的（请参见与lim的比较）。

在GHCi中运行时，所有这些都没有得到优化，导致会调用naive的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 _ -> ()

这使得它保留值。

正如我们所看到的，up_list 的实现在累加器方面非常严格（因为它与 lim 进行比较，并且该列表是惰性展开的 -- 因此 last 应该能够在常数空间中使用它）。手动编写表达式可以确认这一点。

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

至少可以确定它不是惰性求值的一系列延迟计算，而是整个列表被严格构建并保持，直到被丢弃。

所以谜团是：在 ghci 中是什么将列表参数保留给了 last，而在 ghc 中没有呢？

我怀疑这是 ghci 的一些内部（或微妙）细节问题-- 我认为这值得一个 ghci ticket。

- Don Stewart

---

我认为枚举或整数根本与此无关。问题在于我不确定Haskell应该如何工作，因此很难向我报告错误。 - L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳

也许尝试使用带有 -frewrite-rules 的 ghci？ - Chris Kuklewicz

Answer 2

我认为 @n.m 是正确的。 没有强制在列表中使用 value，因此 1+1+1+1+... 的惰性求值最终会消耗空间。

我会快速进行一项测试。

- Chris Kuklewicz

---

seq只需要它的左参数在WHNF中。从逻辑上讲，如果要求seq(last[1..10^9])x的结果会导致空间泄漏，那么任何要求last[1..10^9]结果的东西也会导致空间泄漏（但事实并非如此）。*对于我的写法与上面的讨论不同表示抱歉，这个markdown格式使我无法使用反引号。 - L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳

我尝试了与enumDeltaInteger相同的元素严格策略，但在ghci中没有任何作用。所以我猜测ghci很蠢。甚至可能有bug。 - Chris Kuklewicz

它必须强制计算值是否已达到上限，因此我认为这不是一个可能的解释。 - Ben Millwood