什么是空间泄漏？

Question

我发现了空间泄漏的haskell wiki页面,它声称列出了真实世界泄漏的例子,但事实并非如此.它并没有真正说明空间泄漏是什么; 它只是链接到内存泄漏的页面.

什么是空间泄漏？

Answer 1

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

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

它有助于考虑一个具体的例子.这个Haskell程序:

main = print $ sum [1..1000000000]

是第一个十亿整数的惯用方法.编译时-O2,它会在几秒钟内在常量内存中运行(几兆字节,基本上是运行时开销).

现在,任何程序员都希望程序能够在没有占用内存的情况下对第一个十亿个整数进行求和,但实际上这个Haskell版本的表现确实有点令人惊讶.毕竟,从字面上看,它在总结之前构造了十亿个整数的列表,因此它应该至少需要几千兆字节(仅用于存储十亿个整数,更不用说Haskell链表的开销).

但是,延迟评估确保列表仅在需要时生成- 同样重要的是 - 编译器执行的优化确保将列表元素添加到累积总和时,程序会识别它们不再需要并允许它们垃圾收集而不是保持它们直到计算结束.因此,在计算过程中的任何时刻,只需要在列表中间的滑动"窗口"保存在内存中 - 先前的元素已被丢弃,后来的元素尚未被懒惰地计算.(事实上​​,优化比这更进一步:甚至没有构建列表,但这对程序员来说并不明显.)

Soooo ...... Haskell程序员已经习惯了这样的想法,即只使用他们需要的内存,只需在巨型(甚至无限)数据结构周围进行自动"计算".

但是,对程序进行了一些微小的改动,比如打印列表的长度作为我们正在做的所有艰苦工作的证明:

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

突然导致空间使用爆炸到几十千兆字节(或者在我的笔记本电脑的情况下,大约13Gigs,然后开始无望地交换,我杀了它).

这是空间泄漏.计算此列表的总和和长度显然是可以使用"滑动窗口"视图进入列表的恒定空间中完成的事情,但上述程序使用的内存比需要的多得多.事实证明,原因是一旦列表被赋予了vals在两个地方使用的名称,编译器就不再允许立即丢弃"used"元素.如果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'是不是(虽然它略微改善表演)等

Answer 2

当计算机程序使用的内存超过必要时,就会发生空间泄漏.与内存泄漏相反,泄漏的内存从未被释放,空间泄漏所消耗的内存被释放,但比预期的要晚.*资源