那什么是空间泄漏呢?
正如@Rasko的回答中所指出的那样,空间泄漏指的是程序或特定计算使用的内存比计算和/或程序员期望的内存多(通常是远远超过)。
Haskell程序往往特别容易受到空间泄漏的影响,主要原因是惰性求值模型(有时与IO交互的方式使其变得复杂)和语言的高度抽象性质,这可能使得程序员难以确定特定计算将如何执行。
考虑一个具体的例子会有所帮助。 这个Haskell程序:
main = print $ sum [1..1000000000]
这是一种惯用方法来对前十亿个整数求和。使用-O2
编译,它在恒定的内存(几兆字节,基本上是运行时开销)中运行几秒钟。
现在,任何程序员都希望对前十亿个整数求和的程序不会耗尽内存,但这个Haskell版本的良好表现实际上有点令人惊讶。毕竟,从字面上来看,它构建了一个含有十亿个整数的列表,然后再将其求和,因此它应该至少需要几千兆字节(只是为了存储十亿个整数,更不用说Haskell链接列表的开销了)。
然而,惰性求值确保只有在需要时才生成列表,同样重要的是,编译器执行的优化确保当列表元素添加到累加和中时,程序会意识到它们不再需要,并允许它们被垃圾回收,而不是保留它们直到计算结束。因此,在计算过程的任何时刻,只需要保留一个滑动“窗口”进入列表的中间部分——先前的元素已被丢弃,后续的元素还未被惰性计算。(事实上,这些优化还可以更进一步:甚至没有构建列表,但这对程序员来说很难发现。)
因此,Haskell程序员习惯于摆弄巨大(甚至是无限的)数据结构,计算自动使用所需的内存。
但是,对程序进行微小的更改,例如打印列表的长度作为我们所做的所有艰苦工作的证明:
main = let vals = [1..1000000000]
in print (sum vals, length vals)
突然间,空间使用量激增到数十GB(或在我的笔记本电脑上,激增到大约13GB,然后无望地开始交换并杀死进程)。
这是一个空间泄露。显然可以使用“滑动窗口”视图来计算该列表的总和和长度,并且可以在常量空间中完成,但是上面的程序使用的内存比所需的多得多。原因是,一旦列表被赋予名称vals并在两个位置使用,编译器就不再允许立即丢弃“已使用”的元素。如果首先计算sum vals
,则列表将被惰性生成并求和,但整个庞大的列表会保留下来,直到length vals
可以被计算。
作为一个更实际的例子,你可能会编写一个简单的程序来统计文件中的单词和字符:
main = do txt <- getContents
print (length txt, length (words txt))
这段代码对于小的测试文件(数兆字节以内)运行良好,但在10M大小的文件上表现明显缓慢。如果你尝试在100M文件上运行它,程序会慢慢地占用所有可用内存。问题在于,即使文件内容被惰性地读入到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
这个解决方案的复杂性(使用感叹号(!
)模式和显式折叠而不是length
和words
)说明了空间泄漏对于新手Haskell程序员来说有多么棘手。 而且,很明显使用foldl'
而不是foldl
没有任何区别(但使用foldr
或foldr'
将是灾难性的!),在cs'
和ws'
之前的感叹号是避免空间泄漏的关键,但在inWord'
之前的感叹号不是(尽管它略微提高了性能),等等。