图缩减/棘手 space 泄漏示例

Question

我想知道我在这个页面上读到的 space 泄漏的例子（很遗憾，那里没有解释）： https://en.wikibooks.org/wiki/Haskell/Graph_reduction

Tricky space leak example:

(\xs -> head xs + last xs) [1..n]

(\xs -> last xs + head xs) [1..n]

The first version runs on O(1) space. The second in O(n).

我不确定我是否理解正确（希望您能提供帮助）。据我所知，延迟评估意味着最左边的最外层评估。因此，在这些示例中，我们将像这样减少这些 redexes：

(\xs -> head xs + last xs) [1..200]

=> ([1..200] -> head xs + last xs)

=> head [1..200] + last [1..200]

=> 1 + last [1..200]

=> 1 + last [2..200]

=> ... ...

=> 1 + last [199..200]

=> 1 + last [200]

=> 1 + 200

=> 201

和

(\xs -> last xs + head xs) [1..200]

([1..200] -> last xs + head xs)

last [1..200] + head [1..200]

last [2..200] + head [1..200]

... ...

last [199..200] + head [1..200]

last [200] + head [1..200]

200 + head [1..200]

200 + 1

201

也许我缩小的方式不对（如果我错了，请纠正我），但在这里我看不到可能的 space 泄漏。因此，我首先使用 ghci:

测试了运行时（不是 space）

1>> (\xs -> head xs + last xs) [1..50000000]
50000001
(10.05 secs, 4,003,086,632 bytes)
2>> (\xs -> last xs + head xs) [1..50000000]
50000001
(2.26 secs, 3,927,748,176 bytes)

根据 wikibooks，第二个版本中应该有 space 泄漏，但运行时要快得多（这可能是可能的，这里没有什么奇怪的）。

我有以下源代码：

module Main where

main = do
--  let a = (\xs -> head xs + last xs) [1..20000000]    -- space leak
let b = (\xs -> last xs + head xs) [1..20000000]    -- no space leak
--  putStrLn ("result for a - (\xs -> head xs + last xs): " ++ show a)
putStrLn ("result for b - (\xs -> last xs + head xs): " ++ show b)

...我没有优化编译它，然后我调用程序：

$ ghc -O0 --make -rtsopts -fforce-recomp Main.hs
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...

$ ./Main +RTS -sstderr
result for b - (\xs -> last xs + head xs): 20000001
   1,600,057,352 bytes allocated in the heap
         211,000 bytes copied during GC
          44,312 bytes maximum residency (2 sample(s))
          21,224 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      3062 colls,     0 par    0.012s   0.012s     0.0000s    0.0001s
  Gen  1         2 colls,     0 par    0.000s   0.000s     0.0002s    0.0002s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.518s  (  0.519s elapsed)
  GC      time    0.012s  (  0.012s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.534s  (  0.532s elapsed)

  %GC     time       2.3%  (2.3% elapsed)

  Alloc rate    3,088,101,743 bytes per MUT second

  Productivity  97.6% of total user, 98.0% of total elapsed

这是一个不错的结果，我们有 2.3% 的垃圾收集，使用的内存大约为 1 MB。然后我在没有优化的情况下编译了另一种情况，得到了以下结果：

module Main where

main = do
  let a = (\xs -> head xs + last xs) [1..20000000]    -- space leak
--  let b = (\xs -> last xs + head xs) [1..20000000]    -- no space leak
  putStrLn ("result for a - (\xs -> head xs + last xs): " ++ show a)
--  putStrLn ("result for b - (\xs -> last xs + head xs): " ++ show b)

$ ghc -O0 --make -rtsopts -fforce-recomp Main.hs
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...

$ ./Main +RTS -sstderr
result for a - (\xs -> head xs + last xs): 20000001
   1,600,057,352 bytes allocated in the heap
   2,088,615,552 bytes copied during GC
     540,017,504 bytes maximum residency (13 sample(s))
     135,620,768 bytes maximum slop
            1225 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      3051 colls,     0 par    0.911s   0.915s     0.0003s    0.0016s
  Gen  1        13 colls,     0 par    2.357s   2.375s     0.1827s    0.9545s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.434s  (  0.430s elapsed)
  GC      time    3.268s  (  3.290s elapsed)
  EXIT    time    0.094s  (  0.099s elapsed)
  Total   time    3.799s  (  3.820s elapsed)

  %GC     time      86.0%  (86.1% elapsed)

  Alloc rate    3,687,222,801 bytes per MUT second

  Productivity  14.0% of total user, 13.9% of total elapsed

这更糟，正在进行大量垃圾收集并且内存使用率更高。

这里到底发生了什么？我不明白为什么会有 space 泄漏。

P.S。如果您使用完全优化 (O2) 编译这两种情况，那么这两个程序的效率几乎相同。

Answer 1

xs也是一样。当您写出 [1..200] 两次时，您会感到困惑。最好在表达式求值过程中明确命名所有临时实体：

(\xs -> head xs + last xs) [1,2,3]
head xs + last xs        { xs = [1,2,3] }
(+) (head xs) (last xs)
(+) 1         (last xs)  { xs = 1:xs1 ; xs1 = [2,3] }
              (last xs1) { xs1 = 2:xs2 ; xs2 = [3] }
              (last xs2)
              3
4

在这里我们看到 xs（和 xs1）的绑定可以在我们继续前进时安全地忘记，因为任何地方都没有对 xs 的引用。

所以你确实正确地减少了它，除了第二个 [1..200] 与第一个相同，所以我们必须坚持下去，同时首先找到它的 last （在第二个变体），因此泄漏。

当然允许编译器对此进行优化，由于引用透明原则，用 equals 代替 equals，并执行枚举 [1..200] 两次，因此运行在 O(1) space 中也适用于第二个变体。

所以说到底，还是编译器的事。 space 泄漏可能发生（不是应该）。

图缩减/棘手 space 泄漏示例

Graph reduction / Tricky space leak example

memory

haskell

memory-leaks

graph-reduction