问题标签 [space-leak]

空间泄漏通常是由执行一个消耗比必要空间更多的程序来定义的。这种定义是否与需要延迟评估以实现摊销时间效率的算法兼容？

我想知道这些是否倾向于在 thunk 结构中表现出不同的模式。例如，一个微不足道的空间泄漏可能如下所示：

像树搜索这样的惰性算法会产生相似大小的 thunk 结构吗？

我怀疑适当的惰性评估模式看起来会有所不同，从而更容易发现实际泄漏。例如，结构可能如下所示：

其中[...]part 是没有引用并且可能已经被垃圾收集的前缀。在这种情况下，惰性算法可以很好地在O(1)空间上运行，并且不会出现空间泄漏，从而使区别非常明显。

我想知道这是否很常见，或者在惰性语言中需要在空间和时间效率之间进行更广泛的权衡。

编辑：一个可能的反例 - 持久结构。它们容易与空间泄漏区分开来吗？

我正在尝试解决 Haskell 中的整个 Advent of Code 系列。

我在解决2015/06 练习时遇到了内存问题，其中有一堆指令可以打开、关闭和切换网格上的灯。目标是计算最后点亮的灯的数量。

给定指令被解析并存储在一个Instruction类型中，这是类型定义：

这是计算结果的代码。我试图通过使用类型类来抽象出灯光是布尔值的事实

解决方案将是由 inside 返回的整数partA。parse工作并且有类型parse :: String -> [Instruction]

代码编译并使用小矩阵（例如 10x10）运行，一旦我转向1000 gridWidth，gridHeight我就会遇到out of memory错误，显然是从allStepsMatrix函数生成的。

这里有什么可能出错的提示吗？完整代码在 GitHub 上

我最近读到了Writer/ WriterTmonad 的空间泄漏问题。如果我正确理解了这个问题，那是因为绑定运算符，即(>>=)不是尾递归：

定义WriterT和Writer：

我很好奇在第二个参数上引入惰性是否mappend会解决这个空间泄漏问题。

通过引入惰性，我的​​意思是类似于(++)运算符：

结果是在没有实际接触第二个参数的情况下产生的。

现在，如果我们使用m带有惰性单子绑定的单子（例如m ~ Identity，它给了我们普通的旧Writer单子），并使用mappend上面提到的，那么f a部分 ( w2) 在评估时可以保持 thunk mappend w1 w2，因此结果可以部分消耗 ( w1) 而没有实际上强制其余表达式（w2）。

我对此是否正确？Writer在这样的monad中是否避免了空间泄漏？

如何在使用单子时避免空间泄漏foldM？mapMState

去年的第 20 天代码出现有一个难题，即根据如何穿过迷宫的说明生成迷宫地图。例如，说明NN给出了迷宫

（一条笔直的走廊往北两步），指示NNN(EE|WW)S给了迷宫

（向北走一点，然后向东然后向南或向西然后向南）。

我试图解决这个问题的方法包括有一个State单子，其中状态是Set所有走廊部分的状态（Door下面称为 s），值是您可以工作的位置列表。

如果你只是沿着一条走廊走Path，我foldM会沿着它走，更新当前位置。如果你在一个路口，沿着路口的每个分支，收集你最终到达的所有位置。

此代码在小测试输入上产生正确的结果，但在处理完整示例时存在巨大的空间泄漏。

分析表明它大部分时间都花在includeDoor.

所以，问题。

1. 有空间泄漏吗？如果是这样，在哪里，你怎么知道。
2. 我如何解决它？

（我认为正在发生的事情是 Haskell 并没有尽快将完全评估Door的 s 添加到 s 中Set。在这种情况下，我不想在任何地方有任何懒惰。）

（我将输入解析为一组二元素向量，这些向量指示每条指令要执行的步骤。该代码运行良好且快速。）

我希望尝试在大量输入上运行一个中等成本的函数，使用该函数的部分输出作为其输入之一。代码按预期运行，不幸的是它在进程中消耗了大量内存（堆上略低于 22GiB，最大驻留略高于 1GiB）。这是我的意思的简化示例：

请注意，在 where 子句中，showInts作为参数， where本身取决于在整个列表上运行的输出。showIntmaxwidthmaxwidthshowInt maxwidth

另一方面，如果我做一些幼稚的事情并将定义替换为maxwidth，foldl' max 0 $ map (snd . expensiveShow) [0..10^7]那么最大驻留量将降至 44KiB。我希望这样的性能可以在没有像预计算这样的变通方法的情况下实现expensiveShow，然后将它与列表一起压缩[0..10^7]。

我尝试严格使用列表（使用foldl包），但这并没有改善情况。

我想吃我的蛋糕并吃掉它：利用懒惰，同时也让事情变得足够严格，以免我们堆积如山。这可能吗？还是有更好的技术来实现这一点？

首先是问题 - 以下行为是逻辑上预期的，还是要为 GHC 报告的错误？

下面的代码将泄漏内存（在 上测试ghc-8.8.4），因为ghc似乎join point在循环结束时添加并跳转到它，构建堆栈。

编译-O2 -rtsopts -threaded和运行+RTS -s -hT -N会因为堆栈的增长而显示空间泄漏。

查看核心输出，似乎泄漏是由于join（我猜它是 a join point）并且在循环结束时跳转到它会增加堆栈（如果我已经正确读取了核心）。删除最后一条语句loop1可以修复泄漏。

ghc core输出在这里。

更新：根据评论中的反馈，这似乎是合乎逻辑的行为，而不是ghc. 因此，最好有一个解释堆栈增加的答案。这有助于我们了解这里发生了什么。ghc core输出已在上面发布。