问题标签 [space-leak]

我最近一直在玩 Writer Monad，我遇到了似乎是空间泄漏的问题。我不能说我完全理解这些事情，所以我想知道这里发生了什么，以及如何解决它。

首先，这是触发此错误的方法：

我得到：

为了更好地理解这一点，我在没有 Writer 或 Sum 的情况下重新实现了类似的功能，如果我保持良好和懒惰，我会得到同样的错误：

但我可以通过添加seq等式来解决这个问题：

我已经尝试seq了我的foo功能的各个部分，但这似乎没有帮助。另外，我尝试过使用Control.Monad.Writer.Strict，但这也没有什么不同。

Does Sum need to be strict somehow? Or am I missing something completely different?

Notes

• I may have my terminology wrong here. According to Space leak zoo, my problem would be classified as a 'stack overflow', and if that's the case, how would I convert foo to a more iterative style? Is my manual recursion the problem?
• After reading Haskell Space Overflow, I had the idea to compile with -O2, just to see what happens. This may be a topic for another question, but with optimizations, even my seq'd bar function fails to run. Update: This issue goes away if I add -fno-full-laziness.

我已经读过很多次了，Haskell 中的惰性求值有时可能会导致空间泄漏。什么样的代码会导致空间泄漏？如何检测它们？程序员可以采取哪些预防措施来避免它们？

我将这段代码输入解释器，内存很快被消耗：

我不明白为什么这需要超过 O(1) 的空间。如果我这样做（应该是一样的，因为 Show 强制弱头部正常形式，所以 seq 是多余的？）：

...它工作正常。

我无法在口译员之外重现这种情况。

这里发生了什么？

以下是一些测试用例： http ://hpaste.org/69234

注意事项：

• 通过在解释器中运行，我加载 wtf.hs 而不编译它，然后输入wtf<n>ghci。
• 通过编译，我做到了ghc --make wtf.hs && ./wtf。
• last可以sum用严格的累加器或在列表中找到最大元素的函数替换，空间泄漏仍然发生
• 使用$!而不是seq.
• 我尝试添加一个虚拟()参数，因为我认为这可能是 CAF 问题。没有任何改变。
• 上的函数可能不是问题Enum，因为我可以用和以后重现该行为，而这些行为wtf5根本不使用Enum。
• , 或可能不是问题Num，因为我可以在没有它们的情况下重现行为and 。IntIntegerwtf14wtf16

我尝试使用 Peano 算法重现问题，以将列表和整数排除在等式之外（获取 10^9 末尾的 ），但在尝试实现时遇到了我不理解的其他共享/空间泄漏问题*。

下面mapAndSum代码块中的函数结合了mapand sum（别介意sum在主函数中应用了另一个，它只是为了使输出紧凑）。是惰性计算的map，而sum是使用累加参数计算的。这个想法是，map可以在内存中没有完整列表的情况下使用结果，并且（仅）之后sum可以“免费”使用。main 函数表明我们在调用mapAndSum. 让我解释一下这个问题。

根据 Haskell 标准，无可辩驳的模式示例let (xs, s) = mapAndSum ... in print xs >> print s被翻译成

因此，两个print调用都携带对整个对的引用，这导致整个列表被保存在内存中。

我们（我的同事 Toni Dietze 和我）使用明确的case声明（比较“bad”与“good2”）解决了这个问题。顺便说一句，发现这一点花了我们相当多的时间..！

现在，我们不明白的是两个方面：

• 为什么mapAndSum首先工作？它还使用了一种无可辩驳的模式，因此它也应该将整个列表保存在内存中，但显然不是。并且将 the 转换let为 acase会使函数表现得完全不懒惰（以至于堆栈溢出；没有双关语的意思）。

  我们查看了 GHC 生成的“核心”代码，但据我们所知，它实际上包含与上述相同的翻译let。所以这里没有线索，而是更多的混乱。

• 为什么会“坏”？关闭优化时工作，但打开时不工作？

关于我们的实际应用的一个评论：我们希望实现一个大文本文件的流处理（格式转换），同时还积累一些值，然后写入一个单独的文件。如前所述，我们成功了，但两个问题仍然存在，答案可能会提高我们对 GHC 的理解，以应对即将到来的任务和问题。

谢谢！

I'm new to Haskell and I'm trying to implement Euler's Sieve in stream processing style.

When I checked the Haskell Wiki page about prime numbers, I found some mysterious optimization technique for streams. In 3.8 Linear merging of that wiki:

And it says

“<strong>The double primes feed is introduced here to prevent unneeded memoization and thus prevent memory leak, as per Melissa O'Neill's code.”</p>

How could this be? I can't figure out how it works.

这是完整的存储库。这是一个非常简单的测试，它使用 postgresql-simple 数据库绑定将 50000 个随机事物插入到数据库中。它使用 MonadRandom 并且可以懒惰地生成事物。

这是惰性事物生成器。

这是 case1和使用事物生成器的特定代码片段：

这是 case2，它只是将事物转储到标准输出：

在第一种情况下，我的 GC 时间非常糟糕：

在第二种情况下，时间很好：

我曾尝试应用堆分析，但什么都不懂。看起来所有 50000 个事物都是先在内存中构建的，然后通过查询转换为 ByteStrings，然后将这些字符串发送到数据库。但为什么会发生呢？如何确定有罪代码？

GHC 版本是 7.4.2

所有库和包本身的编译标志为 -O2（由沙箱中的 cabal-dev 编译）

我对以下片段的行为感到困惑：

使用它编译-O2时堆栈溢出（显示 20M 内存在使用中）。令人困惑的部分是，如果进行以下任何更改，它实际上会按预期工作（没有堆栈溢出和 9M 内存正在使用） ：

• Int64用于代替Int: （给出evalFib :: Int64 -> Int和STUArray s Int64 Int）。事实上，任何Int*( Int32, Int16, etc) 都可以像Wordor Word*;
• newtype C a从图片中删除；
• data C a = C !a被用来代替newtype

我试图弄清楚这种行为：它是 GHC/array 模块中的错误（它在7.4.2and中显示相同的行为7.6.2）还是应该以这种方式工作？

PS 有趣的是，当我尝试编译它ghc array.hs -O2 -fext-core以查看产生的核心差异时，两个 GHC 版本都以“ghc：恐慌！（'不可能'发生）”失败。这里也没有运气..

我一直在实现 Brent 的“瞬移海龟”算法的一个变体，通过 N 树映射到所有深度路径，以便比较两种不同数据结构的值，使用我自己的回溯算法来回滚循环而不排除非循环路径与循环路径部分重叠。从各方面来看，我的算法都是正确的（尽管我觉得我应该证明这一点，即使我没有证明任何关于代码的背景），但我今天注意到，当我尝试运行 1000000 次相等测试周期时，而不是 -testCount在 1-1024 个节点（由 控制）和maxNodeCount每个节点 2-5 个分支（由nodeSizeRange迅速吃掉了我系统上所有 8 GB 的 RAM，并迅速开始使用大量交换空间，迫使我将其杀死。当我将节点数量减少到 1-512 时，它仍然很快，但不是那么快，开始在我的系统上使用 RAM，直到它看起来达到 6 GB RAM 的最大值（我不确定它会真正使用多少 RAM，因为我把它留在家里运行）。在 1-256 个节点上，它似乎使用了几 GB 的空间，但还不够，我实际上注意到了很多。

问题是，为什么它使用如此大量的 RAM，而它的空间需求应该按 O(n) 扩展，其中 n 是在捕获任何循环之前通过树的最深路径的深度的函数，树中最大循环的大小，以及树中循环起点的数量。我找不到任何明显的地方会在代码中发生空间泄漏行为。我唯一能想到的是布伦特算法本身的性质，以及我为给定的深度路径保留堆栈；海龟之间的增量增加了 2^n 的组合，具有非常深的循环路径和非常大的循环，它们实际上可以循环很长时间，导致大量堆栈在循环被捕获之前被累积。但是由于 Haskell因空间泄漏而臭名昭著，这可能只是正常的空间泄漏，而不是我可能遗漏原因的算法性质的东西。

（编辑；我意识到这不可能是算法，因为海龟深度和海龟尺度之间的关系是这样的，对于给定的海龟深度 d，下一个海龟深度是 ((d + 1) * 2) - 1；例如，在深度1023 下一个海龟深度是 2047。）

这是我的算法代码：

这是测试程序使用的算法的简单版本。

这是测试程序的代码。请注意，这在不等于测试中偶尔会失败，因为它旨在生成具有显着共性程度的节点集，由maxCommonPortion.

我想使用Vectors 在 Haskell 中编写 Floyd-Warshall 所有对最短路径算法的有效实现，以期获得良好的性能。

实现非常简单，但不是使用 3 维 |V|×|V|×|V| 矩阵，使用二维向量，因为我们只读取前一个k值。

因此，该算法实际上只是传入 2D 向量并生成新的 2D 向量的一系列步骤。最终的 2D 向量包含所有节点 (i,j) 之间的最短路径。

我的直觉告诉我，确保在每一步之前评估先前的 2D 向量很重要，所以我在函数BangPatterns的prev参数fw和 strict上使用了foldl'：

但是，当使用 1000 个节点和 47978 条边的图运行这个程序时，事情看起来一点也不好看。内存使用率非常高，程序运行时间太长。该程序是用ghc -O2.

我重建了分析程序，并将迭代次数限制为 50：

然后我用+RTS -p -hcand运行程序+RTS -p -hd：

这……很有趣，但我想这表明它正在积累大量的 thunk。不好。

好的，所以在黑暗中拍摄了几张照片后，我添加了一个deepseqinfw以确保prev 真的被评估：

现在情况看起来好多了，我实际上可以在不断使用内存的情况下运行程序完成。很明显，prev论点的轰动是不够的。

为了与之前的图表进行比较，以下是添加 50 次迭代后的内存使用情况deepseq：

好的，事情好多了，但我还有一些问题：

1. 这是这个空间泄漏的正确解决方案吗？我觉得插入deepseqa 有点难看是错误的？
2. 我Vector在这里使用 s 是惯用的/正确的吗？我正在为每次迭代构建一个全新的向量，并希望垃圾收集器会删除旧Vector的 s。
3. 我还能做些什么来让这种方法运行得更快吗？

作为参考，这里是graph.txt：http ://sebsauvage.net/paste/?45147f7caf8c5f29#7tiCiPovPHWRm1XNvrSb/zNl3ujF3xB3yehrxhEdVWw=

这里是main：

回想起来，整个问题可以归结为更简洁的东西。我正在寻找一个 Haskell 数据结构

• 看起来像一个列表
• 有 O(1) 查找
• 有 O(1) 元素替换或O(1) 元素追加（或前置......如果是这种情况，我可以反转我的索引查找）。我总是可以考虑其中一种或另一种来编写我以后的算法。
• 内存开销很小

我正在尝试构建图像文件解析器。文件格式是基本的 8 位彩色 ppm 文件，但我打算支持 16 位彩色文件以及 PNG 和 JPEG 文件。现有的 Netpbm 库，尽管有很多拆箱注释，但在尝试加载我使用的文件时实际上会消耗所有可用内存：

3-10张照片，最小的45MB，最大的110MB。

现在，我无法理解 Netpbm 代码中的优化，所以我决定自己尝试一下。这是一个简单的文件格式...

我首先决定无论文件格式是什么，我都将以这种格式存储未压缩的最终图像：

然后我写了一个解析器，它可以处理三个向量，如下所示：

在解析器结束时，我像这样构造 RGB8：

像这样写的程序，加载这些 45MB 图像中的一个，将消耗 5GB 或更多的内存。如果我更改了Progressso that redC、greenC和blueCare all的定义!(Vector Word8)，那么程序将保持在合理的内存范围内，但加载单个文件需要很长时间，以至于我不允许它实际完成。最后，如果我用标准列表替换这里的向量，我的内存使用量会回升到每个文件 5GB（我假设......我实际上在点击之前用完了空间），加载时间大约为 6 秒. Ubuntu 的预览应用程序一旦启动，就会几乎立即加载和呈现文件。

根据每次对 V.// 的调用实际上每次都完全复制向量的理论，我尝试切换到Data.Vector.Unboxed.Mutable，但是......我什至无法进行类型检查。文档不存在，理解数据类型在做什么也需要与多个其他库进行斗争。而且我什至不知道它是否能解决问题，所以我什至都不愿意尝试。

基本问题实际上非常简单：

我如何在不使用大量内存的情况下快速读取、保留并可能操作非常大的数据结构？我发现的所有示例都是关于临时生成大量数据，然后尽快将其删除。

原则上，我希望最终表示是不可变的，但我不太关心是否必须使用可变结构才能到达那里。

为了完整起见，完整的代码（BSD3 许可）位于https://bitbucket.org/savannidgerinel/photo-tools的 bitbucket 上。该分支包含一个严格版本的解析器，performance可以通过快速更改Progress.Codec.Image.Netpbm

运行性能测试