问题标签 [space-leak]

如何制作自己的流式代码？我正在生成大约 1,000,000,000 对随机的战争套牌，我希望它们能够懒惰地流入 foldl'，但我遇到了空间泄漏！这是代码的相关部分：

当我使用 -O2 运行它时，它首先开始冻结我的计算机，然后程序死掉，计算机又恢复了活力（然后谷歌浏览器就有了它需要的资源来对我大喊大叫，因为我用光了它的所有资源。）

注意：我尝试了 unsafeInterleaveIO，但没有成功。

完整代码在： http: //lpaste.net/109977

为了好玩，我正在尝试编写朴素最长路径算法的实现（用于查找循环图中最长非循环路径的长度）。我从命令式算法的直接移植开始，该算法运行良好且执行得相当好。

wherevisited是一个未装箱的 bool 可变向量，表示图中的每个节点当前是否已被访问，全部初始化为 false，nodes 是一个节点向量。

然后，我尝试使其更具功能性，方法是将其max作为折叠传递的值，而不是作为 IORef，如下所示：

但是，此版本无法完成，运行了几分钟（另一个版本为相同的输入需要几秒钟），然后以out of memory (requested 1048576 bytes). lPathFun如果有人可以查看我的代码并查看我做错了什么，我将不胜感激。我已经尝试将其中的所有内容都严格化，但这并没有帮助，并且还尝试使所有内容变得懒惰，没有任何改变。我什至尝试更改type node为V.Vector route并对其使用严格foldM'，但无济于事。

我怀疑问题是空间泄漏。这是因为我尝试翻译lPathFun成 OCaml 并且效果很好（OCaml 版本使用手动递归这一事实不应该有所作为：我的功能性 Haskell 版本最初也使用手动递归，但遇到了与使用 foldM 相同的问题）：

我使用的 GHC 版本是 7.8.3。

我的空间泄漏发生在我的一个个人项目中。但我不希望有人在我的项目中解决它。我想了解它。

我通过制作这个算法重现了我的空间泄漏：

u 是由以下定义的序列：

• u(0) = 1
• u(1) = 2
• u(2) = 1
• u(4) = 3
• …</li>
• u(19) = 11

在此之后，定义 u：u(n) = u(n-5) + u(n-10) - u(n-15)

在haskell中很容易实现对吧？

不幸的是，这个空间泄漏：

看起来 haskell 正在缓存整个列表，而我希望它只缓存最后 20 个元素。

例如，这是我在 C 中的实现：

我的 C 实现使用 O(n) 时间和 O(1) 空间。但看起来我的 haskell 实现正在使用 O(n) 空间。

为什么 Haskell 能够为fibonnacci 计算出它，但不能为我编造的序列计算出来？我做错了什么？你将如何在 Haskell 中实现这个算法？

考虑以下 Haskell 程序（我这样做主要是为了学习目的）：

当我运行它时，内存迅速攀升至数 GB。我尝试了各种组合以确保丢弃中间计算的结果（打印操作）。为什么还漏空间？

全部。

在尝试解决一些编程测验： https ://www.hackerrank.com/challenges/missing-numbers 时，我遇到了空间泄漏。

主要功能是difference，实现多集差分。我发现 List ':' 和 Triples (,,) 使用 -hT 选项进行分析。但是，只有大列表是的两个参数，并且随着尾递归difference的不断进行而缩小。difference但是列表消耗的内存随着程序的运行而不断增加。

Triples 是临时数组结构，用于记录多重集每个元素的计数。但是三元组消耗的内存也在不断增加，我不知道为什么。

虽然我在 stackoverflow 中浏览过类似的“空间泄漏”问题，但我无法理解这个想法。我当然有很多东西要学。

我感谢任何评论。谢谢你。

ps) 可执行文件使用 -O2 开关编译。

.

[编辑] 感谢 Carl 的建议，我对 value 和 Array 进行了排序。我附上堆图。

[原始堆分析] [ ] 1

[在seq'ing值之后v]

[在seq'ing值v和之后Array]

我在理解 Haskell 惰性评估方面遇到了困难。

我写了简单的测试程序。它读取 4 行数据，第二和第四输入行有很多数字。

words并且map在字符流上懒惰地执行，该程序使用常量内存。

但是当我添加参数t时，情况发生了变化。我的期望是因为tismap并且words在惰性流上，并且t没有在 中使用consumeList，所以这个更改不应该改变内存使用。但不是。

Q1) 为什么这个程序在t完全不使用的时候一直在分配内存？

我有另一个问题。当我模式匹配惰性流时[,]，不使用(:)内存分配行为会改变。

Q2）在惰性评估方面有什么不同(:)？[,]

欢迎任何意见。谢谢

[编辑]

Q3) 那么，是否可以先处理第 4 行，再处理第 2 行，而不增加内存消耗？

Derek指导的实验如下。通过从第二个示例切换 y 和 k，我得到了相同的结果：

I posted this question a few days ago: Haskell performance using dynamic programming and was recommended to use ByteStrings instead of Strings. After implementing the algorithm with ByteStrings, the program crashes, going over the memory limits.

The memory consumption appears to scale with n. The length of the input strings are 1000 characters. I would expect Haskell to free all memory used in editDistance after each solution is printed. Is this not the case? If not, how can I force this?

The only other real calculation I see is for cost but forcing that with seq did nothing.

抱歉，如果这太具体了，我是新来的，不确定什么是合理的。几个小时以来，我一直在抨击这个问题，却没有任何表现。以下代码是我对竞争性编程问题的实现。

其目的是，这就像一个自下而上的动态规划解决方案，使用求解中的折叠从前一个生成 DP 表的每一行。理论上 GHC 应该能够优化掉表的所有旧行。然而，在一个中等大的输入上运行这个程序，大约l = 2000和length f = 5000，我得到这个：

那是在峰值使用 878 MB 内存！我正在生成的表只有 10,000 个 Ints，理论上我一次只需要一行！很明显，这是某种形式的 thunk 泄漏或其他空间泄漏。分析显示，run它消耗了 99% 的总运行时间和内存。进一步挖掘表明，其中 98% 都在zipWith通话中。有趣的是，zipWith min用我的自定义zipMin函数替换调用会产生显着的改进：

这只是 70% 的运行时间和 60% 的内存！我尝试了各种方法来完成这项工作。我知道(++)这通常是一个坏主意，所以我run用Data.Sequence.Seq Int... 替换了列表，它变得更慢并且使用了更多内存。我对 Haskell 不是特别有经验，但我在这里束手无策。我确信这个问题的答案存在于 SO 上，但我对 Haskell 太陌生了，无法找到它，看来。

非常感谢你们提供的任何帮助。我很想解释一下我做错了什么，将来如何诊断它，以及如何解决它。

提前致谢。

编辑：

在遵循史蒂文的优秀建议并用未装箱的向量替换我的列表后，性能......呃......显着改善：

我最近参加了一场竞争性的编码比赛。

这个 Haskell 在运行 ghc 7.6.3 的法官系统上给出了空间泄漏：

比赛结束后，公布了测试用例。其中一个失败案例是：（包含 10^5 个关闭括号的文件）：https ://cses.fi/download/1/b575d19a75bf724b50fa4a399f8187b6d6edb4ccb62bd1a774f9294969152e46

错误是

我也知道代码是使用 -O2 和 -Wall 在我认为是 GHC 7.6.3 上编译的。

在我的一生中，我无法在我的机器上重现 GHC 8.0.2 或 7.10.3 的错误。

代码中是否存在明显的空间泄漏？

编辑：

我按照以下建议测试了代码，并因此实现了折叠：

bang 模式和严格的重新实现都没有foldl'解决问题，尽管 bangy 获得了更多的测试用例。原来还是WOMM。诚然，这超出了通常有用的堆栈交换问题的范围，并且开始看起来像是很好的旧作业。如果没有更多的判断系统知识，这也是相当不可调试的。

在Google 的 C++ 测试框架中，我的眼睛读到：

.. 立即从当前函数返回，可能会跳过后面的清理代码，这可能会导致空间泄漏。

而我的大脑预计会看到内存泄漏。

C++ 中是否使用了该术语？如果是这样，它是什么意思（换句话说，它如何与内存泄漏区分开来）？

在Haskell中，空间泄漏是指程序或特定计算使用的内存比必要的多得多的情况。

在Java中，使用“空间泄漏”这个短语没有意义。