例如
main = do
let ls = [0..10000000]
print ls
这将使用 O(1) 内存创建数组“就地”。
以下编辑导致程序在执行时内存不足。
main = do
let ls = [0..10000000]
print ls
print ls
ls
在这种情况下必须保存在内存中才能再次打印。实际上,与尝试将其保持原位相比,再次“就地”重新计算数组的内存效率更高。不过那是旁观。我真正的问题是“GHC 如何以及何时与运行时系统通信,ls
可以在 O(1) 时间内创建时销毁?”我知道活性分析可以找到这些信息,我只是想知道这些信息在哪里使用。传递此信息的是垃圾收集器吗?它以某种方式编译了吗? (如果我查看来自 GHC 的编译核心,那么两个示例都使用 eftInt
,所以如果它是编译器工件,那么它必须发生在更深的层次上)。编辑:我的问题更多是关于找到进行此优化的位置。我想可能是在 GC 中,它从编译步骤中的一些活性检查中获得了一些信息。由于到目前为止的答案,我可能是错的。这很可能发生在核心之前的某个较低级别,所以也许是 cmm?
编辑 2:这里的大多数答案都假设 GC 知道
ls
在第一个示例中不再引用,而在第二个示例中再次引用。我知道 GC 的基础知识,我知道数组是链表等。我的问题正是 GC 是如何知道这一点的。答案可能只是 (a) 它从编译器获取额外信息,或者 (b) 它不需要知道这一点,该信息由编译器 100% 处理
最佳答案
ls
这是一个 懒人名单 ,不是数组。在实践中,它更接近于另一种语言的流或生成器。
第一个代码工作正常的原因是它实际上从未在内存中拥有整个列表。 ls
被延迟定义,然后通过 print
逐个使用元素.如 print
顺其自然,没有其他引用开头的ls
所以列表项可以立即被垃圾收集。
从理论上讲,GHC 可以意识到在两次打印之间不将列表存储在内存中而是重新计算它的效率更高。然而,这并不总是可取的——如果只计算一次,很多代码实际上会更快——而且,更重要的是,这会使执行模型对程序员来说更加困惑。
关于haskell - GHC 垃圾收集器/运行时如何知道它可以创建数组 `inplace',我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29153480/