ACM通信

实践

泄漏的空间

尼尔·米切尔
美国ACM通信，2013年11月，第56卷第11期，第44-52页
10.1145/2524713.2524722
评论

当计算机程序使用的内存超过所需时，就会发生空间泄漏。与内存泄漏(泄漏的内存永远不会被释放)相反，空间泄漏消耗的内存会被释放，但比预期的要晚。本文介绍了示例空间泄漏以及如何发现和消除它们。

让我们首先考虑两个“现实生活中的”空间泄漏。木琴爱好者Xena买了一本26卷的印刷百科全书，但她只想读关于木琴的那篇文章。这本百科全书在她的书架上占了很大的地方。Xena可以扔掉除X卷外的所有卷，减少对货架的要求;或者她可以剪掉木琴的文章，只留下一张纸。在本例中，Xena存储了大量信息，但只对其中的一小部分感兴趣。

Xena的朋友Shawn是一名统计学家，他很好奇Xena存储了多少多余的页面。为了确定百科全书的总页数，Shawn买了一本26卷的百科全书，尽管他只对每卷的页数感兴趣。实际上，Shawn不需要知道26卷的大小，只需要知道邮票背面的大小信息就可以了。

在本例中，Shawn存储了大量信息，虽然每个卷都包含有用的信息，但是可以更紧凑地存储结果。

图1描述了如果希娜和肖恩是计算机程序，他们可能表示的内存布局。在这两种情况下，都有一个纯蓝色箭头指向百科全书，表示被保留的内存。红色虚线箭头指向实际有用的信息。

如果程序加载了百科全书，但没有立即将其减少到感兴趣的部分，就会发生空间泄漏，导致百科全书在内存中保存的时间超过必要的时间。消除空间泄漏就是控制计算发生的时间，减少分配内存和丢弃内存之间的时间间隔。不出所料，使计算顺序复杂化的特征特别容易受到空间泄漏的影响。本文关注的两个示例是懒惰的评价(表达式的求值被延迟到需要它的值时)和闭包(与其环境相结合的函数值)。这两个特性都可以在Haskell等懒函数式语言中找到。

回到顶部

例1:删除

延迟求值如何导致空间泄漏?考虑以下Haskell定义:

这个片段创建了一个变量xs和一个使用(_, _)符号，包含两者活着而且死了。然后是元素死从列表中删除时使用删除。呼唤xs长度返回1，表示只有一个元素xs。在没有惰性求值的情况下，内存布局看起来像这样图2一个,在那里xs引用包含alive作为唯一元素的列表;Dead不被引用，因此可以被垃圾回收。

然而，Haskell使用惰性求值(也称为按需调用)，所以在之后xs是定义的，内存是什么样的图2 b．而不是指向a价值，xs点在表达式，稍后可能会替换为实际值。还有两条路xs来死了;因此,死不能被垃圾回收，即使我们知道它永远不会被使用。的变量死部分空间泄漏是因为删除正在比预期的时间晚进行评估。

如前所述，长度xs会返回1，但是作为计算长度的结果，它会求值删除。计算长度的行为xs减少了xs值，该值将消除空间泄漏。如果使用列表的程序频繁添加和删除元素，但从不使用列表计算长度或查找值，则可能导致空间泄漏。

更一般地说，当内存中包含一个表达式，其中该表达式有规律地增长，但计算的值不会增长时，就会发生空间泄漏。强制评估通常可以解决此类泄漏;这就需要对一些变量求值严格的而不是懒惰。

回到顶部

迫使评价

消除空间泄漏通常需要将表达式的求值时间提前。在描述如何强制求值之前，有必要定义表达式的求值方式:

• 表达式是in标准形式如果不能进一步评估。例如，列表[1,2]是正常形式。列表由以下内容构建［］(读作“nil”)为空列表，和(:)(发音为“cons”)将头元素组合到列表的尾部，因此[1,2]可以等价地写出来吗1:2: []．
• 如果表达式最外层不需要进一步求值，则该表达式为WHNF(弱头正常形式)表达式。例如,(1 + 2): []在WHNF，因为最外面的部分是(:)，但它不是正常的形式，因为（+）可评估产生3。所有标准形式的值根据定义也在WHNF中。

为了强制对WHNF进行求值，Haskell提供了带有常用的爆炸模式扩展。^3.你可以定义一个函数输出，输出“Output”到控制台，后跟它的参数:

印刷x评估x对于正常形式，函数输出会先打印“输出”，然后求值x打印出来。添加感叹号作为严格注释将强制评估x早:

现在评估输出x首先会评估x输出到WHNF，然后打印“Output”，然后求值x打印出来。

回到顶部

为什么懒惰?

既然严格避免了例1中的空间泄漏和(稍后将显示)其他几个空间泄漏，为什么不使所有值都严格呢?当然，大多数语言都有严格的值，甚至Haskell的一些变体也默认采用严格的求值。¹与所有的语言设计决策一样，延迟求值是一种权衡空间——漏洞是一个缺点，但也有很多优点。其他文章深入讨论了惰性求值的优点，^2，6但简单地说，这是一个不错的选择的几个原因:

• 在严格的语言中定义新的控制结构通常需要宏或将宏构建到编译器中，而惰性求值则允许直接表示这种模式。
• 懒惰使得在进行变量绑定时不考虑在哪个代码路径中计算哪个绑定，这在与复杂条件结合时极大地简化了变量绑定。
• 在一种严格的语言中模拟惰性通常比在一种惰性语言中强制执行惰性要困难得多，因此惰性可以作为一种更好的默认值。
• 在组合函数时，严格的语言通常要求简单的组合比懒惰语言占用更多的内存，例2中将演示这一点。

回到顶部

例2:求和

考虑以下代码:

在Haskell中，这个表达式创建了一个包含数字1到的列表n，然后把它们加起来。严格来说，这个操作需要O (n)Space:它首先会生成一个长度列表n，然后打电话求和。然而，在惰性语言中，列表中的项可以根据需要一次生成一个总和，导致O（1)空间使用情况。即使你替换了[1 . ncn]。从文件中读取数字后，程序仍然可以运行O（1)空间作为惰性自动交错从文件中读取数字和计算和。

不幸的是，这段代码在用格拉斯哥Haskell编译器(GHC)编译时O (n)空间泄漏的结果，但当使用-O1优化标志占用O（1)空间。更令人困惑的是，对于某些定义总和代码接受O（1)在所有优化设置，和其他定义的代码总是采取O（n)．

为什么会出现空间泄漏?考虑下面的定义总结:

第一个方程表示，如果列表中至少有一个项，则将第一个项绑定到x和包含剩下项目的列表xs．然后递归地定义和，方法是将第一个元素与其余元素的和相加。第二个方程表示基本情况，空列表的和为0。让我们考虑一下计算sum1 [1 . . n]的大值n，其过程如图所示图3．您可以从表达式的左上角开始，通过查看程序接下来需要什么来跟踪求值。例如，最初sum1查看列表以确定要匹配哪个表达式:哪个表达式需要求值(1 . . n)生产1 (2 . . n):．随着评估的进行，它建立了术语1 + 2 + 3 + 4…,以O（n)空间。虽然程序不会一次将整个列表存储在内存中，但它会将列表中的所有项用“+”操作连接起来。

在确定空间泄漏后，可以使用严格来消除它。给定表达式1 + 2，可以简化为3.立即;如果程序在计算过程中一直执行加法运算，它将只使用固定内存。唉，用的定义sum1，表达式是actually1 +(2 +(3)…，这意味着1而且2不能减。幸运的是，加法是结合律，所以和可以重新定义(1 + 2 + 3)…：

定义sum2在辅助函数方面sum2需要额外的累加器一个，它是到目前为止处理的列表中所有元素的值。跟踪评估看起来更有希望:

现在将文字数字应用于加法，但仍然存在空间泄漏。幸运的是，现在有了一个适合于严格注释的目标。你可以定义:

累加器参数上的严格注释一个在处理列表的下一个元素之前计算累加器中的结果。重新查看跟踪:

显示,sum3需要O（1)，并没有空间泄漏。的定义总和在标准Haskell库中的定义等价于sum2；但是在优化打开的情况下，编译器会推断出严格注释，使其等价于sum3．

回到顶部

例3:Mean

再举一个例子:

这个函数计算的意思是列表的xs用和除以长度(周围的反嘀嗒声div允许函数作为中缀操作符使用)。假设没有空间泄漏的定义总和，多少空间才会的意思是[1 . . n]?

使用惰性求值，即先缩小左上角的表达式，答案是O（n)．评估xs总和需要计算整个列表xs，但因为这个列表也被长度为xs必须保留在内存中，而不是在生成时被收集。

在本例中，更智能的评估策略可以消除空间泄漏。的第一个元素xs，然后应用sum和长度对于它，函数占用的空间是常数。另一种计算均值的方法(1 . . n)是删除列表的共享:

这里列表被复制了，两个参数都被div在恒定空间中运行，允许整个计算在恒定空间中运行。不幸的是，计算列表所需的任何工作都是重复的。

真正的解决方案是采用用于sum3把它扩展，这样就不仅仅是累加和了，还累加了长度。完整的定义见图4．

这将累加总和(年代)和长度(左)作为局部形参，它们是辅助函数的严格实参。最终的定义没有空间泄漏，并运行在一起O（1)．

回到顶部

例4:空间泄漏和垃圾收集器

前面的示例插入了严格注释以消除空间泄漏。然而，并不是所有的空间泄漏都可以通过严格注释消除⁵；有时，垃圾收集器需要特殊的行为。¹⁰举个例子，让我们通过在标题后面加上感叹号来提高学术论文的影响力图5．

的改善函数获取纸张的来源并生成新的纸张。它将文本拆分为一个变量一对，由第一行和其余文字组成，使用助词得力．然后，该函数使用pair中的第一个元素置，第二个元素usingsnd，并使用字符串追加操作符“++”在它们之间插入感叹号。第一个方程得力匹配具有前导换行符的字符串，并生成第一行空，后跟文本。第二个方程递归地调用得力除了第一个字符，然后创建一个结果，其中第一个字符位于第一行的前面。最后一个方程确保空输入产生空输出。

---

与所有的语言设计决策一样，延迟求值是一种权衡空间——漏洞是一个缺点，但也有很多优点。

---

这应该是可能的改善磨合O（1)空间，在检查每个输入字符后产生一个输出字符，并且只需要少量的内存。在第二个方程中得力，匹配后y: y(也就是说，使用输入字符)，程序立即生成(y: _， _)，在进行递归调用之前通过延迟求值使输出字符可用。不幸的是，使用明显的实现技术，这个函数需要与第一行成比例的空间xs,所以O（置两）．

要了解空间的使用，考虑评估提高“abc……”中描述图6．

的每一步得力在生成pair时，该pair的第二个组件只是递归调用的第二个组件。结果是一个线性链snd调用和通过引用每个的第一个组件保留的所有字符休息变量。

如果snd函数被强制，那么这个空间泄漏将被消除，产生:

不幸的是，没有地方放置严格注释来执行适当的简化。虽然你想强迫评估snd的递归调用中，您还依赖于pair的惰性得力为了实现O（1)空间。幸运的是，垃圾收集器可以解决这个问题。这个函数snd是一个给定一对的选择器，它选择第二个组件。它不计算任何新值，不分配内存，计算成本低。因此，程序可以评估snd在垃圾收集期间，这样就消除了空间泄漏。在垃圾收集过程中减少选择器函数现在是惰性函数语言的一个标准特性，它会自动消除否则不可能消除的空间泄漏。

回到顶部

例5:空间泄漏和闭包

到目前为止，所有的例子都是在Haskell中，但是其他垃圾收集语言也容易受到空间泄漏的影响。虽然默认情况下很少有语言是惰性的，但许多语言都支持闭包一个lambda表达式或函数，加上一些绑定在环境中的变量。大量使用闭包的一种流行语言是JavaScript。

中的JavaScript代码图7使用Web Audio API⁸检索MP3文件并计算其持续时间:

此函数使用XMLHttpRequestAPI加载MP3文件，然后使用Web Audio API解码文件。使用已解码的音频值，您可以添加一个动作，在单击状态按钮时告诉用户MP3的持续时间。

该实现使用三个局部函数，其中两个引用局部定义的变量LoadAudio．当引用局部函数时，这些变量将在闭包中被捕获。例如，第一个函数被赋值给onreadystatechange并捕获请求变量在前面定义了三行。

后LoadAudio运行后，“status”按钮有一个onclick事件，该事件运行以下代码:

此代码引用音频对象，它存储的音频数据至少占用与原始MP3相同的内存。然而，唯一被访问过的东西是持续时间字段，它是一个数字，仅占用8个字节。结果就是空间泄漏。

此空间泄漏与延迟计算空间泄漏有许多共同之处。代码引用一个表达式audio.duration，它保持大量的内存，但在计算时只使用少量的内存。与前面一样，解决方案是强制在必要的时间之前进行评估，如中所示图8．

现在，持续时间在onclick事件已注册，并且音频元素不再被引用，从而允许它被垃圾回收。

回到顶部

JavaScript选择器

虽然可以修改代码以消除空间泄漏，但垃圾收集器是否已经消除了空间泄漏?答案是肯定的，前提是audio.duration计算成本低，将来不能更改，也不会造成任何副作用。因为没有其他的参考资料音频的值音频引用不能更改;由于audio.duration是只读字段，它可能是在音频价值是构建出来的。这个优化是示例4中的选择器求值的一个实例。

不幸的是，选择器优化在JavaScript中不像在Haskell中那么适用，因为大多数值都是可变的。考虑下面的例子图9．这段代码定义了一个包含这两者的字典π(一个数字)和fiveDigitPrimes(一个大数组)，然后添加一个使用π只有。如果常量是不可变的，那么垃圾收集器可以减少constants.pi并删除对常量的引用。唉，用户可以写常量= {pi: 3}变异常量,或constants.pi= 3突变π场，意味着提前评估是不安全的。

虽然变异的困难意味着JavaScript在实践中并没有减少这样的函数，但这并不是一个不可逾越的障碍。考虑这样一个内存布局，您知道哪些引用是作为只读使用的(例如，警报(constants.pi))而不是(也就是说，constants.pi= 3)。这个信息可以帮助确定哪些变量只能作为只读变量使用，因此保证是常量。如果常量而且constants.pi如果两者都被确定为不可变的，那么可以由垃圾收集器执行字段查找，从而释放两者常量而且fiveDigitPrimes。

在Haskell中，延迟求值是常见的(默认值)，由选择器引起的空间泄漏是不可避免的，这使得应用选择器优化的决定显而易见。在JavaScript等语言中，添加代码以解决可修复的空间泄漏，代价是使正常代码变慢或更复杂，这可能不是一个明智的权衡。

回到顶部

检测空间泄漏

这里介绍的五个空间泄漏的例子为空间泄漏发生的地点和如何修复提供了一些指导。然而，所有的例子都只有寥寥几行;对于大型程序中的空间泄漏，挑战往往是找到错误的代码。由于Haskell特别容易受到空间泄漏的影响，因此编译器提供了许多内置的分析工具来精确定位空间泄漏的来源。在查看哪些工具可用之前，让我们首先考虑哪些工具可能有用。

空间泄漏与内存泄漏非常不同——特别是，垃圾收集器仍然知道空间泄漏引用的内存，并且通常会在程序终止之前释放该内存。假设定义为总和包含空间泄漏;只要…总和产生一个结果，垃圾收集器将释放任何中间空间泄漏。有空间泄漏的程序通常会在执行过程中达到内存使用的峰值，而内存泄漏则永远不会减少。诊断内存泄漏的一种标准技术是在程序结束后查看内存，看看意外保留了什么。这种技术不适用于空间泄漏。

相反，在整个执行过程的中间点检查内存，寻找内存使用的峰值通常是有用的。频繁地捕获整个内存可能需要太多的磁盘空间，因此一种解决方案是定期记录汇总统计信息，例如每个函数分配了多少内存。

Haskell工具．Haskell编译器提供了几种生成总结内存使用情况图表的分析模式。要生成一个概要文件，首先用以下标志编译程序:

这些标志是:

• ghc使Main.hs．编译文件Main.hs到可执行文件中。
• -prof -fprof-auto -fprof- cafe。在可执行文件中打开分析，并确保它能够记录关于顶级定义的信息。
• -rtsopts．允许生成的可执行文件接受分析选项。

生成的程序可以正常运行，但是通过附加标志，它还可以生成配置文件信息:

使用的意思是中所示的第一个图图10．第一个命令运行结果主要可执行文件，带有运行时系统的一些标志(后面的任何东西)+ RTS)．的xtFlag包含概要文件输出中的任何堆栈(作者认为xt默认应该是打开的)，和沪元生成按类型总结的报告。第一个命令生成一个文件主要．惠普，第二个命令将其转换为PostScript文件main.ps(在颜色上，由于- c国旗)。在图中我也通过了-i0.01更频繁地对内存进行采样，这通常只在尝试快速运行的玩具示例时是必要的。

---

使用不同的优化设置进行编译可能会导致出现或消失空间泄漏，而且遗憾的是，为分析而编译也可能产生类似的效果(尽管这种情况相对较少)。

---

Haskell有许多分析模式，最简单的方法是尝试所有这些模式，看看哪一种能产生最有用的信息。四种标准类型的概要文件，见图10是:

• 沪元。按类型总结内存。该示例有一些列表([])和数字(Int)．这个摘要回答了……的问题什么是在回忆里。
• 高清．通过描述总结，显示出更精练的版本沪元．在这个例子中有一种密切的对应关系沪元，与所有Int条目匹配我#的内部构造函数Int)和匹配的列表(:)．低于阈值的任何组都被隐藏;否则，可能会有一个单身［］表示列表的结束。
• hc．按成本中心进行总结，这是一个源代码的命名区域，自动插入到所有顶级定义中。还可以在代码中使用注释手动插入它。在图10主要已归属所有的内存，可能是优化内联的结果的意思是在里面。这个摘要回答了……的问题在哪里记忆被创造出来了吗?
• 嗯．按模块总结，这是成本中心的一个更细粒度的版本。

从这些图的组合中，您可以看到模块中的main函数主要分配一个大的数字列表。它在0.4秒内分配列表，然后在0.1秒内快速消耗列表。的原始定义所期望的内存使用情况的意思是．

对于较大的程序，图中通常包含大量预期的内存使用，而与空间泄漏无关。为了简化绘图，您可以通过四种类型中的任何一种进行筛选:例如，传递hc衔接[]将生成按成本中心分组的图，但仅用于类型为列表的内存。

如在总和例如，使用不同的优化设置进行编译可能会导致空间泄漏的出现或消失，遗憾的是，为分析而编译也可能产生类似的效果(尽管这种情况相对较少)。作为备用方案，任何Haskell可执行文件都可以使用+ RTS ht，它生成按类型总结的图，而无需编译以进行概要分析。这将减少对程序行为的更改。

在使用分析工具之前，请阅读GHC手册的“分析”部分，其中涵盖了几种其他的分析方法。为了更好地理解如何将分析工具应用于大型程序以及如何解释结果，我推荐以下两个我和Edward Yang的“战壕故事”:

• http://blog.ezyang.com/2011/06/pinpointing-space-leaks-in-big-programs/
• http://neilmitchell.blogspot.com/2013/02/chasing-space-leak-in-shake.html

JavaScript工具．Haskell缺少的一个工具是在某个点暂停执行并探索内存的能力。这个特性在一些JavaScript实现中是可用的，包括在Chrome中作为堆分析器。

Chrome堆分析器允许内存的快照被获取和探索。分析器显示内存树，显示哪些值彼此指向。您可以按对象类型进行总结，查看关于内存消耗和特定值引用的统计信息，并按名称进行筛选。对于诊断空间泄漏特别有用的一个特性是，能够查看哪些引用使值保持活动。本文中的两个JavaScript空间泄漏产生的堆快照可以很容易地查明问题。

回到顶部

太空泄漏是不可避免的吗?

垃圾收集将程序员从手工管理内存的单调中解放出来，使语言更容易包含诸如延迟求值或闭包等高级特性。这些高级特性导致了更复杂的内存布局，使得预测内存的样子更加困难，从而可能导致空间泄漏。

懒函数语言的编译器处理空间泄漏问题已经有30多年的历史了，并开发了许多策略来提供帮助。编译技术发生了变化，垃圾收集器和剖析器也进行了修改，以便在发生空间泄漏时精确定位。其中一些策略可能也适用于其他语言。尽管有所有的改进，空间泄漏仍然是懒惰评估的一个刺，提供了一个与好处相权衡的显著缺点。

虽然空间泄漏令人担忧，但并不致命，而且可以被发现和消除。惰性求值的存在并没有阻止Haskell在许多项目中被成功地使用(你可以在函数式编程的商业用户的会议记录中找到许多例子)。虽然没有明显的解决空间泄漏的灵丹妙药，但有三种方法可以有所帮助:

• 一些复杂的问题域具有通过设计消除大量空间泄漏的库。一个例子是函数式反应式编程，它用于构建交互式应用程序，如用户界面和声音合成器。通过改变库的定义方式，您既可以保证某些时态属性，又可以消除常见的空间泄漏源。⁷另一个例子是流处理，它在Web服务器中大量使用，用于使用流(例如JavaScript文件)并生成新的流(例如最小化的JavaScript文件)，而不将整个流保存在内存中。Haskell有几个相互竞争的流库。所有这些都确保内存的保留时间不会超过必要的时间，并且结果会尽快流到用户。
• 空间泄漏通常是在开发过程的较晚阶段检测到的，有时是在代码编写和部署数年后才检测到，而且通常只是在响应用户对高内存使用的抱怨时才检测到。如果能够更早地发现空间泄漏——理想情况下，一旦它们被引入，就会更容易修复，并且永远不会到达最终用户手中。某些类型的高级分析信息可以检测到可疑的内存模式，⁹一些实验性工具可以注释预期的堆使用情况，⁴但这些都没有进入主流使用。Haskell编译器对内存进行分区时，会检测到一些空间泄漏总和对于长度为508146及以上的列表，示例失败并提示堆栈溢出，但本文中的其他示例在失败前使用了所有可用内存。
• 精确定位空间泄漏的工具是强大的，但肯定不是完美的。交互式观众可以探索现有的情节，¹¹但是在运行程序之前，用户仍然需要指定内存的分组方式。如果能同时捕获所有四组，那就容易得多了。Haskell程序缺少的一个特性是对内存进行快照以供以后检查的能力，如果将其与在内存超过某个阈值时进行快照的能力相结合，将会更加强大。精确定位空间泄漏是一项需要实践和毅力的技能。更好的工具可以大大简化这个过程。

相关文章
在queue.acm.org

NUMA(非统一内存访问):概述
Christoph Lameter
http://queue.acm.org/detail.cfm?id=2513149

软件事务性记忆:为什么它只是一个研究玩具?
Calin Cascaval, Colin Blundell, Maged Michael, Harold W. Cain, Peng Wu, Stefanie Chiras和Siddhartha Chatterjee
http://queue.acm.org/detail.cfm?id=1454466

你对共享变量和内存模型一无所知
Hans-J Boehm和Sarita V. Adve
http://queue.acm.org/detail.cfm?id=2088916

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2013 ACM, Inc.

---

没有找到条目