下载本文的PDF版本 PDF

泄漏空间

消除内存占用大户


尼尔·米切尔


当计算机程序使用的内存超出必要量时，就会发生空间泄漏。与内存泄漏（泄漏的内存永远不会被释放）不同，空间泄漏消耗的内存会被释放，但释放时间晚于预期。本文介绍了空间泄漏的示例，以及如何发现和消除它们。

现实世界的空间泄漏

首先考虑两个“现实世界”的空间泄漏。热衷于木琴的西娜买了一套26卷的印刷百科全书，但她只想阅读关于木琴的文章。这套百科全书占据了她书架上的大量空间。西娜可以扔掉除了 X 卷之外的所有卷，从而减少书架需求，或者她可以剪下木琴的文章，只留下一张纸。

在这个例子中，西娜存储了大量信息，但只对其中的一小部分感兴趣。

西娜的朋友肖恩是一位统计学家，他很好奇西娜存储了多少冗余页面。为了确定百科全书的总页数，肖恩买了一本26卷百科全书，即使他只对每卷的页数感兴趣。实际上，肖恩不需要知道 26 卷书的大小，只需要知道总大小——信息可以写在邮票的背面。

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

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

如果程序加载了百科全书，但没有立即将其缩小到感兴趣的部分，从而导致百科全书在内存中保留的时间超过必要时间，则会发生空间泄漏。消除空间泄漏的关键在于控制何时进行求值，减少分配内存和丢弃内存之间的时间。毫不奇怪，使求值顺序复杂化的特性尤其容易受到空间泄漏的影响。本文重点关注的两个例子是惰性求值（表达式的求值被延迟到需要其值时）和闭包（函数值与其环境的组合）。这两种特性都可以在惰性函数式语言（如 Haskell）中找到。

Leaking Space: The Information of Interest to Xena and Shawn

示例 1：删除

惰性求值如何导致空间泄漏？考虑以下 Haskell 定义

xs = delete dead [alive, dead]

此代码片段创建一个变量xs和一个双元素列表，使用[_,_]表示法，包含alive和dead。然后使用dead从列表中删除元素delete。调用length xs返回 1，表明xs中只有一个元素。在没有惰性求值的情况下，内存布局如图 2a 所示，其中xs引用一个包含alive作为唯一元素的列表；dead未被引用，因此可以被垃圾回收。

Leaking Space: Lazy Evaluation

然而，Haskell 使用惰性求值（也称为按需调用），因此在xs被定义后，内存将如图 2b 所示。与指向值不同，xs指向一个表达式，该表达式稍后可能会被实际值替换。仍然有两条从xs到dead的路径；因此，dead不能被垃圾回收，即使我们知道它永远不会被使用。变量dead是空间泄漏的一部分，因为delete的求值晚于预期。

如前所述，length xs将返回 1，但由于计算长度，它将求值delete。求值length xs的行为将xs简化为一个值，从而消除空间泄漏。如果程序频繁地添加和删除元素，但从不使用列表来计算长度或查找值，则使用列表的程序最终可能会出现空间泄漏。

更普遍地说，当内存包含一个表达式时，可能会发生空间泄漏——其中表达式定期增长，但求值后的值不会增长。强制求值通常可以解决此类泄漏；这使得某些变量的求值是严格的，而不是惰性的。

强制求值

消除空间泄漏通常需要比正常情况下更早地强制求值表达式。在描述如何强制求值之前，有必要定义表达式的求值方式

• 如果表达式不能进一步求值，则该表达式处于范式。例如，列表[1,2]处于范式。列表由[](发音为“nil”)表示空列表，以及(:)(发音为“cons”)将头元素与列表的尾部组合，因此[1,2]可以等效地写成1:2:[].

• 如果最外层部分不需要进一步求值，则表达式处于 WHNF（弱头范式）。例如，(1+2):[]处于 WHNF，因为最外层部分是(:)，但它不处于范式，因为(+)可以求值以产生3。范式中的所有值根据定义也处于 WHNF。

为了强制求值到 WHNF，Haskell 提供了严格性注解，使用了常用的 bang patterns 扩展3。您可以定义一个函数output，它将“Output”打印到控制台，后跟其参数


output x = do
   print “Output”
   print x

打印x会将x求值到范式，因此函数output将首先打印“Output”，然后将x求值到范式并打印它。添加感叹号作为严格性注解将强制x更快地

求值

output !x = ...现在求值output xx将首先将x求值到 WHNF，然后打印“Output”，然后将

为什么选择惰性？

鉴于严格性避免了示例1 中的空间泄漏——以及（稍后会显示）其他几个空间泄漏——为什么不将所有值都设为严格的？当然，大多数语言都有严格的值，甚至 Haskell 的某些变体默认使用严格求值1。与所有语言设计决策一样，惰性求值是一种权衡——空间泄漏是一个缺点，但也有许多优点。其他文章深入讨论了惰性求值的优点2,6，但这里简要列举了几个使其成为一个好选择的原因

• 在严格语言中定义新的控制结构通常需要宏或将其构建到编译器中，而惰性求值允许直接表达此类模式。

• 惰性允许在不考虑哪些绑定在哪些代码路径中求值的情况下进行变量绑定，这在与复杂的条件语句结合使用时会大大简化。

• 在严格语言中模拟惰性通常比在惰性语言中强制严格性更困难，因此惰性可能是一个更好的默认选择。

• 当组合函数时，严格语言通常需要比惰性语言占用更多内存的简单组合，这将在示例 2 中演示。

示例 2：求和

考虑以下代码

sum [1..n]

在 Haskell 中，此表达式创建一个包含数字 1 到 n 的列表，然后将它们相加。在严格语言中，此操作占用 O(n) 空间：它首先生成一个长度为 n 的列表，然后调用sum。然而，在惰性语言中，列表中的项可以在sum需要时一次生成一个，从而导致 O(1) 空间使用量。即使您将[1..n]替换为从文件中读取的数字，程序仍然可以在 O(1) 空间中运行，因为惰性会自动交错从文件中读取数字和计算总和。

不幸的是，当使用 GHC（Glasgow Haskell Compiler）编译此代码时，由于空间泄漏，它会占用 O(n) 空间，但当使用-O1优化标志时，它会占用 O(1) 空间。更令人困惑的是，对于某些sum的定义，该代码在所有优化设置下都占用 O(1) 空间，而对于其他定义，该代码始终占用 O(n) 空间。

为什么会出现空间泄漏？考虑以下sum:


sum1 (x:xs) = x + sum1 xs
sum1 [] = 0

的定义。第一个方程表示，如果列表至少包含一项，则将第一项绑定到x，并将包含剩余项的列表绑定到xs。然后通过将第一个元素添加到剩余元素的总和来递归定义总和。第二个方程表示基本情况，空列表的总和为 0。让我们考虑求值sum1 [1..n]，对于某个较大的n值，其过程如下


sum1 [1..n]            -- 初始值
sum1 (1:[2..n])        -- sum1 需要列表
1 + sum1 [2..n]        -- sum1 根据方程简化
1 + sum1 (2:[3..n])    -- + 需要它的两个参数
1 + (2 + sum1 [3..n])

您可以通过查看程序接下来需要什么来跟踪求值，从表达式的左上部分开始。例如，最初sum1查看列表以确定要匹配哪个表达式：哪个表达式需要求值[1..n]以产生1:[2..n]。随着求值的进行，它构建了项1 + 2 + 3 + 4 ...，占用 O(n) 空间。虽然程序永远不会一次将整个列表放在内存中，但它会将列表的所有项与“+”运算连接起来。

在识别出空间泄漏后，可以使用严格性来消除它。给定表达式1 + 2，它可以立即简化为3；并且如果程序在计算过程中不断执行加法运算，它将仅使用恒定内存。唉，使用sum1的定义，表达式实际上是1 + (2 + (3 ...，这意味着1和2无法简化。幸运的是，加法是结合律的，因此sum可以重新定义以构建((1 + 2) + 3) ...:


sum2 xs = sum2’ 0 xs
   where
       sum2’ a (x:xs) = sum2’ (a+x) xs
       sum2’ a [] = a

通过辅助函数sum2来定义sum2’，它接受一个额外的累加器a，它是到目前为止处理的列表的所有元素的值。跟踪求值看起来更有希望


sum2 [1..n]
sum2’ 0 [1..n]
sum2’ 0 (1:[2..n])
sum2’ (0+1) [2..n]
sum2’ (0+1) (2:[3..n])
sum2’ ((0+1)+2) [3..n]

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


sum3 xs = sum3’ 0 xs
   where
       sum3’ !a (x:xs) = sum3’ (a+x) xs
       sum3’ !a [] = a

累加器参数a上的严格性注解导致在处理列表的下一个元素之前对累加器进行求值。重新审视跟踪


sum3 [1..n]
sum3’ 0 [1..n]
sum3’ 0 (1:[2..n])
sum3’ (0+1) [2..n]
sum3’ 1 [2..n]
sum3’ 1 (2:[3..n])
sum3’ (1+2) [3..n]
sum3’ 3 [3..n]

表明sum3占用 O(1) 空间，并且没有空间泄漏。标准 Haskell 库中的sum的定义等效于sum2；但在启用优化的情况下，编译器会推断出严格性注解，使其等效于sum3.

示例 3：平均值

考虑另一个示例

mean xs = sum xs `div` length xs

此函数计算列表平均值通过取xs并除以sum长度（div周围的反引号允许将函数用作中缀运算符）。假设是无空间泄漏的定义，summean [1..n]将占用多少空间？使用惰性

求值——即，首先简化左上角的表达式——答案是 O(n)。求值sum xs需要求值整个列表，但由于该列表也被xs使用，length xs, xs因此必须将其保留在内存中，而不是在生成时被回收。

在此示例中，更智能的求值策略可以消除空间泄漏。如果程序求值xs的第一个元素，然后将sum和（应用于它，则该函数将占用恒定空间。计算将占用多少空间？的另一种方法是删除列表的共享

sum [1..n] `div` length [1..n]

。这里列表已被复制，并且周围的反引号允许将函数用作中缀运算符）。假设的两个参数都在恒定空间中运行，从而允许整个计算在恒定空间中运行。不幸的是，计算列表所需的任何工作都将被复制。

真正的解决方案是采用用于sum3的模式并对其进行扩展，以便除了累积总和之外，还可以累积长度。完整定义是


mean xs = mean’ 0 0 xs
   where
       mean’ !s !l (x:xs) = mean’ (s+x) (l+1) xs
       mean’ !s !l [] = s `div` l

这会将总和 (s) 和长度 (l) 累积为局部参数，这些参数是辅助函数的严格参数。生成的定义没有空间泄漏，并且在 O(1) 中运行。

示例 4：空间泄漏和垃圾回收器

前面的示例插入了严格性注解以消除空间泄漏。然而，并非所有空间泄漏都可以通过严格性注解来消除5；有时，垃圾回收器需要特殊的行为10。例如，让我们通过在标题末尾添加感叹号来提高学术论文的影响力


improve xs = fst pair ++ “!”++ snd pair
   where pair = firstLine xs
firstLine (‘\n’:ys) = ([], ‘\n’:ys)
firstLine (y:ys) = (y:fst rest, snd rest)
   where rest = firstLine ys
firstLine [] = ([], [])

函数improve接受论文的源代码并生成一篇新论文。它使用辅助函数pair将文本拆分为一个变量firstLine，该变量由第一行和剩余文本组成。然后，该函数使用fst获取对的第一个元素，并使用snd获取第二个元素，并使用字符串追加运算符“++”在它们之间插入感叹号。的第一个方程firstLine匹配带有前导换行符的字符串，并生成一个空的第一行，后跟文本。第二个方程递归调用firstLine，除了第一个字符之外的所有内容，然后创建一个结果，其中第一个字符位于第一行的前面。最后一个方程确保空输入产生空输出。

对于improve来说，应该有可能在 O(1) 空间中运行，在检查每个输入字符后生成一个输出字符，并且只需要少量内存。在firstLine的第二个方程中，在匹配y:ys（即，消耗一个输入字符）之后，程序立即生成(y:_, _)，在进行递归调用之前，通过惰性求值使输出字符可用。不幸的是，使用明显的实现技术，此函数需要与xs的第一行成比例的空间，因此为 O(fst pair)。

为了理解空间使用情况，请考虑对improve “abc...”/p>


let rest4 = firstLine “...”
let rest3 = (‘c’:fst rest4, snd rest4)
let rest2 = (‘b’:fst rest3, snd rest3)
let rest1 = (‘a’:fst rest2, snd rest2)
‘a’:’b’:’c’:fst rest4 ++ “!”++ snd rest1

的每个步骤中firstLine都会生成一个对，其第二个组件只是递归调用的第二个组件。结果既是一个snd调用的线性链，又是所有被对每个rest变量的第一个组件的引用所保留的字符。

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


let rest4 = firstLine “...”
‘a’:’b’:’c’:fst rest4 ++ “!\n”++ snd rest4

。不幸的是，没有地方可以放置严格性注解来执行适当的简化。虽然您想强制求值snd，但您也依赖于firstLine的递归调用中对的惰性来实现 O(1) 空间。幸运的是，垃圾回收器可以解决这个问题。函数snd是一个选择器——给定一个对，它选择第二个组件。它不计算任何新值，不分配内存，并且计算成本低。因此，程序可以在垃圾回收期间求值snd ，从而消除空间泄漏。在垃圾回收期间简化选择器函数现在是惰性函数式语言的标准功能，可以自动消除原本无法消除的空间泄漏。

示例 5：空间泄漏和闭包

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

以下 JavaScript 代码使用 Web Audio API8 来检索 MP3 文件并计算其持续时间


function LoadAudio(mp3)
{
   // 将 ‘mp3’ 文件加载到 ‘request.response’ 中
 var request = new XMLHttpRequest();
 request.open(‘GET’, mp3);
 request.responseType = ‘arraybuffer’;

 request.onreadystatechange = function(){
       if (request.readyState != 4) return;

       // 解码音频数据
       window.AudioContext = window.AudioContext || window.webkitAudioContext;
       var context = new AudioContext();
       context.decodeAudioData(request.response, function(audio){
           document.getElementById(“status”).onclick = function(){
               alert(“MP3 时长为 “ + audio.duration + “ 秒”);
           }
       });
   };
   request.send();
}

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

该实现使用了三个局部函数，其中两个引用了在LoadAudio本地定义的变量。当引用局部函数时，这些变量将被捕获在闭包内。例如，第一个函数被分配给onreadystatechange，并捕获了三行之前定义的request变量。

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

alert(“MP3 时长为 “ + audio.duration + “ 秒”);

此代码引用了audio对象，该对象存储音频数据——占用至少与原始 MP3 相同的内存。然而，唯一被访问的是duration字段，它是一个数字，仅占用八个字节。结果是空间泄漏。

此空间泄漏在许多方面与惰性求值空间泄漏相似。代码引用了一个表达式audio.duration，它使大量内存保持活动状态，但求值时仅使用少量内存。与之前一样，解决方案是比必要时更早地强制求值


var duration = audio.duration;
document.getElementById(“status”).onclick = function(){
   alert(“MP3 时长为 “ + duration + “ 秒”);
};

现在持续时间在onclick事件注册之前计算，并且audio元素不再被引用，从而允许它被垃圾回收。

JavaScript 选择器

虽然您可以修改代码以消除空间泄漏，但垃圾回收器是否可以消除空间泄漏？答案是肯定的，前提是audio.duration计算成本低，未来不会更改，并且不会导致任何副作用。由于没有对audio的其他引用，因此audio引用的值不会更改；并且由于audio.duration是一个是只读字段，因此它很可能在构造audio值时计算出来。此优化将是示例 4 中的选择器求值的一个实例。

不幸的是，选择器优化在 JavaScript 中的适用性不如在 Haskell 中，因为大多数值都是可变的。作为一个小例子，考虑


var constants = {pi : 3.142, fiveDigitPrimes : [10007,10009,10037,...]};
document.getElementById(“fire”).onclick = function(){
   alert(constants.pi);
};

此代码定义了一个字典，其中包含pi（一个数字）和fiveDigitPrimes（一个大型数组），然后添加一个事件处理程序，该处理程序仅使用pi。如果constants是不可变的，那么垃圾回收器可以简化constants.pi并删除对constants的引用。唉，用户可以编写constants = {pi : 3}来改变constants，或者constants.pi = 3来改变pi字段，这意味着提前求值是不安全的。

虽然突变的困难意味着 JavaScript 实际上不会简化此类函数，但这并不是不可逾越的障碍。考虑一种内存布局，您知道哪些引用用作是只读（即alert(constants.pi)），哪些不是（即constants.pi = 3）。此信息可以帮助确定哪些变量仅用作是只读，因此保证是常量。如果constants和constants.pi都被确定为不可变的，那么字段查找可以由垃圾回收器执行，从而释放constants和fiveDigitPrimes.

。在 Haskell 中，惰性求值很常见（默认），并且由选择器引起的空间泄漏是不可避免的，因此应用选择器优化的决定是显而易见的。在 JavaScript 等语言中，添加代码来解决可修复的空间泄漏，但以牺牲正常代码的速度或复杂性为代价，可能不是一个明智的权衡。

检测空间泄漏

此处介绍的五个空间泄漏示例提供了一些关于空间泄漏发生的位置以及如何修复它们的指导。然而，所有示例都只包含几行代码；对于大型程序中的空间泄漏，挑战通常在于找到有问题的代码。由于 Haskell 特别容易受到空间泄漏的影响，因此编译器提供了许多内置的性能分析工具，以查明空间泄漏的来源。在查看哪些工具可用之前，我们首先考虑哪些工具可能有用。

空间泄漏与内存泄漏截然不同——特别是，垃圾回收器仍然知道空间泄漏引用的内存，并且通常会在程序终止之前释放该内存。假设sum的定义包含空间泄漏；一旦sum产生结果，垃圾回收器将释放任何中间空间泄漏。与永不减少的内存泄漏相比，具有空间泄漏的程序通常在执行过程中达到其峰值内存使用量。诊断内存泄漏的标准技术是查看程序完成后内存，以查看哪些内容被意外保留。此技术不适用于空间泄漏。

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

Haskell 工具

Haskell 编译器提供了几种性能分析模式，这些模式生成汇总内存使用情况的图表。要生成性能分析图，请首先使用以下标志编译程序

ghc--makeMain.hs-prof -fprof-auto -fprof-cafs -rtsopts

这些标志是

•ghc --make Main.hs。像往常一样，将文件Main.hs编译为可执行文件。

• -prof -fprof-auto -fprof-caf. 在可执行文件中启用性能分析，并确保它能够记录有关顶层定义的信息。

• -rtsopts. 允许生成的可执行文件接受性能分析选项。

生成的程序可以像往常一样运行，但使用额外的标志，它还可以生成性能分析信息


main +RTS-xt -hy
hp2ps-cmain.hp

使用平均值前面介绍的示例生成图 3 中显示的第一个图。X 轴是时间（以秒为单位），Y 轴是内存（以 MB 为单位）。第一个命令使用一些标志运行生成的main可执行文件到运行时系统（+RTS之后的任何内容）。 -xt 标志将任何堆栈包含在性能分析输出中（作者认为 -xt 应该默认启用），并且 -hy 生成按类型汇总的报告。第一个命令生成一个文件main.hp，第二个命令将其转换为 PostScript 文件main.ps（由于 -c 标志，以彩色显示）。在显示的图中，我还传递了 -i0.01 以更频繁地采样内存，这通常仅在尝试快速运行的玩具示例时才需要。

Leaking Space: Profiles for the Mean Example with Different Memory Groupings

Haskell 有多种性能分析模式，最简单的方法是尝试所有模式，看看哪种模式产生最有用的信息。图 3 中显示的四种标准类型的性能分析图是

• -hy. 按类型汇总内存。示例中包含一些列表 ([]) 和数字 (Int）。此摘要回答了内存中是什么的问题。

• -hd. 按描述汇总，显示了 -hy. 的更精细版本。在示例中，与 -hy, 非常接近，所有Int条目都与I#（它是Int的内部构造函数）和与(:)匹配的列表匹配。任何低于阈值的组都会被隐藏；否则，可能会有一个[]表示列表的结尾。

• -hc. 按成本中心汇总，成本中心是源代码的命名区域，自动插入到所有顶层定义中。也可以使用代码中的注解手动插入。在图 3 中，main已归因所有内存，这可能是优化内联平均值的结果。此摘要回答了内存是在哪里创建的问题。

• -hm. 按模块汇总，这是成本中心的更精细版本。

从这些图表的组合中，您可以看到模块main中的函数Main分配了一个大型数字列表。它在 0.4 秒内分配列表，然后在 0.1 秒内快速消耗列表。此内存使用情况描述了从平均值.

的原始定义中预期的结果。对于较大的程序，该图通常会包含大量预期的内存使用情况——并且与空间泄漏无关。为了简化图表，您可以按四种类型中的任何一种进行过滤：例如，传递 -hc -hy[] 将生成按成本中心分组的图表，但仅适用于类型为列表的内存。

正如在sum示例中看到的，使用不同的优化设置进行编译可能会导致空间泄漏出现或消失，并且，可悲的是，为性能分析进行编译也可能具有类似的效果（尽管这种情况相对罕见）。作为后备方案，任何 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 在许多项目中成功使用（您可以在函数式商业用户会议的会议记录中找到许多示例

编程）。虽然没有明显的解决空间泄漏的灵丹妙药，但有三种方法可以提供帮助

• 一些复杂的问题领域拥有库，这些库通过设计消除了大量空间泄漏。

一个例子是函数式响应式编程，它用于构建交互式应用程序，例如用户界面和声音合成器。通过更改库的定义方式，您可以保证某些时间属性并消除常见的空间泄漏来源。7 另一个例子是流处理，它在 Web 服务器中被大量使用，用于消耗流（例如，一个

JavaScript 文件）并生成新的流（例如，一个最小化的 JavaScript 文件），而无需将整个流保存在内存中。Haskell 有几个竞争的流库可用。它们都确保内存保留的时间不超过必要的时间，并且结果会尽快流式传输给用户。

• 空间泄漏通常在开发过程的后期才被检测到，有时在代码编写和部署后的几年，并且通常仅在响应用户对高内存使用率的投诉时才被检测到。如果空间泄漏可以被检测到更早——理想情况下，一旦它们被引入——它们将更容易修复，并且永远不会到达最终用户。某些类型的高级分析信息可以检测可疑的内存模式9，并且一些实验性工具可以注释预期的堆使用情况4，但没有任何工具已达到主流使用水平。Haskell 编译器确实以某种方式对内存进行分区，以便检测到一些空间泄漏——检测到—— sum上面的示例因列表长度为 508146 及以上时出现堆栈溢出消息而失败，但本文中的其他示例在使用所有可用内存后才失败。

• 用于查明空间泄漏的工具功能强大，但肯定不是完美的。交互式查看器可以探索现有的图表11，但用户仍然需要指定在运行程序之前如何对内存进行分组。如果可以一次捕获所有四个分组，那就容易得多。Haskell 程序缺少一项功能，即拍摄内存快照以供以后检查，如果与在内存超过某个阈值时拍摄快照的功能相结合，这将更加强大。查明空间泄漏是一项需要实践和毅力的技能。更好的工具可以大大简化这个过程。

参考文献

1. Augustsson, L. 2011. 实用 Haskell。在 CUFP（函数式编程商业用户）会议上的演讲； http://www.youtube.com/watch?v=hgOzYZDrXL0。

2. Augustsson, L. 2011. 惰性求值的更多要点。让我开心的事； http://augustss.blogspot.co.uk/2011/05/more-points-for-lazy-evaluation-in.html。

3. Glasgow Haskell 编译器团队。2013. 光荣的 Glasgow Haskell 编译系统用户指南，版本 7.6.3； http://www.haskell.org/ghc/docs/latest/html/users_guide/index.html。

4. Hofmann, M., Jost, S. 2003. 一阶函数式程序堆空间使用量的静态预测。第 30 届 SIGPLAN-SIGACT 编程语言原理研讨会 (POPL) 会议论文集：185-197。

5. Hughes, J. 1983. 编程语言的设计与实现。博士论文。牛津大学。

6. Hughes, J. 1989. 为什么函数式编程很重要。计算机杂志 32(2)：98-107。

7. Liu, H., Hudak, P. 2007. 使用箭头堵住空间泄漏。理论计算机科学电子笔记 193:29-45。

8. Rogers, C. 2012. Web Audio API； http://www.w3.org/TR/2012/WD-webaudio-20120802/。

9. Röjemo, N., Runciman, C. 1996. 滞后、拖拽、空隙和使用——堆分析和空间高效编译再探。第 1 届 SIGPLAN 国际函数式编程会议 (ICFP) 会议论文集：34-41。

10. Wadler, P. 1987. 使用垃圾收集器修复一些空间泄漏。软件：实践与经验 17(9)：595-608。

11. Yang, E. 2013. hp/D3.js； http://heap.ezyang.com/。

喜欢它，讨厌它？请告诉我们
[email protected]

Neil Mitchell 是一位 Haskell 程序员，在渣打银行工作。他于 2008 年在约克大学获得函数式编程博士学位。他的开源项目包括搜索引擎 (Hoogle)、代码建议工具 (HLint) 和用于编写构建系统 (Shake) 的库。

© 2013 1542-7730/13/0900 $10.00

acmqueue

最初发表于 Queue vol. 11, no. 9——
在 数字图书馆 中评论本文





© 保留所有权利。

© . All rights reserved.