haskell - 什么是空间泄漏？

Question

我找到了有关空间泄漏的 haskell wiki 页面，该页面声称列出了真实世界泄漏的示例，但事实并非如此。它并没有真正说明什么是空间泄漏；它只是链接到内存泄漏页面。

什么是空间泄漏？

Answer 1

正如@Rasko 的回答中所指出的，空间泄漏是指程序或特定计算使用比计算所需和/或程序员预期更多(通常更多)的内存的情况。

Haskell 程序往往特别容易受到空间泄漏的影响，主要是因为惰性求值模型(有时会因 IO 与此模型交互的方式而变得复杂)以及语言的高度抽象性使程序员难以确切地确定如何可能会执行特定的计算。

考虑一个具体的例子会有所帮助。这个 Haskell 程序:

main = print $ sum [1..1000000000]

是对前十亿个整数求和的惯用方法。编译 -O2 ，它在恒定内存中运行几秒钟(几兆字节，基本上是运行时开销)。

现在，任何程序员都希望程序对前十亿个整数求和而不消耗内存，但实际上这个 Haskell 版本表现良好，这有点令人惊讶。毕竟，从字面上看，它在汇总之前构建了一个十亿整数的列表，因此它应该至少需要几 GB 的空间(仅用于存储十亿个整数，更不用说 Haskell 链表的开销了)。

但是，惰性求值确保列表仅在需要时生成，同样重要的是，编译器执行的优化确保当列表元素添加到累加总和时，程序会识别出不再需要它们并允许它们被垃圾收集而不是将它们保留到计算结束。因此，在计算过程中的任何时候，只有一个滑动到列表中间的“窗口”需要保存在内存中——前面的元素已经被丢弃，后面的元素还没有被懒惰地计算。 (实际上，优化比这更进一步:甚至没有构造列表，但这对程序员来说远非显而易见。)

Soooo... Haskell 程序员已经习惯了这样的想法，即在巨大的(甚至无限的)数据结构周围折腾将“仅使用”他们需要的内存自动进行计算。

但是，程序的一个小改动，比如还打印了列表的长度，作为我们正在做的所有努力工作的证明:

main = let vals = [1..1000000000]
       in print (sum vals, length vals)

突然导致空间使用量激增至数十 GB(或者在我的笔记本电脑的情况下，在它开始无望地交换之前达到大约 13Gigs，我将其杀死)。

这是空间泄漏。计算这个列表的总和和长度显然是可以在常量空间中使用列表中的“滑动窗口” View 来完成的，但是上面的程序使用的内存比需要的要多得多。事实证明，原因是一旦列表被命名为 vals这在两个地方使用，编译器不再允许立即丢弃“使用”的元素。如果 sum vals首先评估，列表被懒惰地生成和求和，但是整个巨大的列表然后被保留直到 length vals可以评估。

作为一个更实际的例子，你可以编写一个简单的程序来计算文件中的单词和字符:

main = do txt <- getContents
          print (length txt, length (words txt))

这在高达几兆字节的小型测试文件上运行良好，但在 10meg 文件上明显缓慢，如果您尝试在 100meg 文件上运行它，它会缓慢但肯定会开始吞噬所有可用内存。同样，问题是——即使文件内容被懒惰地读入 txt -- 因为 txt使用两次，整个内容作为 Haskell 读入内存 String类型(大块文本的内存低效表示)，例如 length txt被评估，并且直到 length (words txt) 之前都不能释放任何内存也计算过。

请注意:

main = do txt <- getContents
          print $ length txt

和:

main = do txt <- getContents
          print $ length (words txt)

即使在大文件上，它们都可以在恒定空间中快速运行。

作为旁注，修复上述空间泄漏通常涉及重写计算，以便通过内容计算字符和单词，因此编译器可以确定已处理的文件内容不需要保存在内存中直到计算结束。一种可能的解决方案是:

{-# LANGUAGE BangPatterns #-}

import Data.List
import Data.Char

charsWords :: String -> (Int, Int)
charsWords str = let (_, chrs, wrds) = foldl' step (False, 0, 0) str
                 in (chrs, wrds)
  where step (inWord, cs, ws) c =
          let !cs' = succ cs
              !ws' = if not inWord && inWord' then succ ws else ws
              !inWord' = not (isSpace c)
          in (inWord', cs', ws')

main = do txt <- getContents
          print $ charsWords txt

这个解决方案的复杂性(使用 bang ( ! ) 模式和显式折叠而不是 length 和 words )说明了空间泄漏是多么严重，尤其是对于新的 Haskell 程序员。而且使用 foldl' 一点也不明显。而不是 foldl没有区别(但使用 foldr 或 foldr' 将是一场灾难!)， cs' 之前的刘海和 ws'避免空间泄漏至关重要，但之前的爆炸 inWord'不是(虽然它稍微提高了性能)等。