GHC 垃圾收集器/运行时如何知道它可以创建一个数组“inplace”

Question

例如

main = do
  let ls = [0..10000000]
  print ls

这将使用 O(1) 内存创建数组 'inplace'。

以下编辑导致程序在执行时运行内存不足。

main = do
  let ls = [0..10000000]
  print ls
  print ls

ls 在这种情况下必须保存在内存中以便再次打印。再次重新计算数组 'inplace' 比尝试将其保持在原位实际上会提高内存效率。不过那是一个旁白。我真正的问题是 "how and when does GHC communicate to the runtime system that ls can be destroyed while it's created in O(1) time?" 我知道活性分析可以找到这些信息，我只是想知道这些信息用在哪里。传递此信息的是垃圾收集器吗？它以某种方式被编译掉了吗？（如果我查看来自 GHC 的编译核心，那么两个示例都使用 eftInt，因此如果它是一个编译器工件，那么它一定发生在更深层次上）。

编辑：我的问题更多是关于查找优化发生的位置。我想也许是在 GC 中，它从编译步骤中的一些活动检查中获得了一些信息。由于到目前为止的答案，我可能是错的。这很可能发生在核心之前的某个较低级别，所以也许是 cmm？

edit2：这里的大部分答案都假定 GC 知道 ls 在第一个示例中不再被引用，并且在第二个示例中再次被引用。我知道 GC 的基础知识，我知道数组是链表等。我的问题正是 HOW GC 知道这一点。答案可能只是 (a) 它正在从编译器获取额外信息，或者 (b) 它不需要知道这一点，该信息由编译器 100% 处理

Answer 1

ls 这里是一个 惰性列表 ，不是数组。实际上，它更接近于另一种语言的流或生成器。

第一个代码工作正常的原因是它实际上从未在内存中拥有整个列表。 ls 被延迟定义，然后由 print 逐个元素地消费。随着 print 的进行，没有其他对 ls 开头的引用，因此可以立即对列表项进行垃圾回收。

理论上，GHC 可以意识到在两次打印之间不将列表存储在内存中而是重新计算它会更有效。然而，这并不总是可取的——如果事情只被评估一次，很多代码实际上会更快——而且，更重要的是，这会使程序员的执行模型更加混乱。

Answer 2

这个解释可能是个谎言，尤其是因为我正在编造它，但这应该不是问题。

您所犯的根本错误是假设如果绑定到某个值的变量在活动表达式的范围内，则该值是活动的。这是完全错误的。绑定到变量的值只有在在实时表达式中实际提到时才会作为结果存在。

runtime的工作很简单

执行绑定到main的表达式。
没有2.

我们可以将此执行视为涉及反复重复的几个不同步骤：

弄清楚现在要做什么。
找出下一步该做什么。

所以我们从一些 main 表达式开始。从一开始，GC 的 "root set" 包含那些在 main 表达式中使用的名称， 而不是 范围内的东西 在该表达式中。如果我写

foo = "Hi!"
main = print "Bye!"

那么因为 foo 没有在 main 中提到，它不在开始的根集中，而且因为它甚至没有被 main 提到的任何东西间接提到, 从一开始就死定了。

现在假设我们举一个更有趣的例子：

foo = "Hi!"
bar = "Bye!"
main = print foo >> print bar

现在 main 中提到了 foo，因此它开始直播。我们将 main 评估为 weak head normal form 以找出要做什么，我们大约得到

(primitive operation that prints out "Hi!") >> print bar

注意foo不再提了，就死了！

现在我们执行原始操作，打印 "Hi!"，我们的 "to do list" 减少为

print bar

现在我们将其计算为 WHNF，并大致得到

(primitive operation to print "Bye!")

现在 bar 已经死了。我们打印 "Bye!" 并退出。

现在考虑您描述的第一个程序：

main = do
  let ls = [0..10000000]
  print ls

这脱糖到

main =
  let ls = [0..10000000]
  in print ls

这是我们的起点。开头的 "root set" 是表达式的 in 子句中提到的所有内容。所以我们在概念上有 ls 和 print 开始。现在我们可以想象 print，专用于 [Integer]，看起来有点像下面这样的东西（这已经大大简化了，并且会以不同的方式打印出列表，但这并不重要）。

print xs = case xs of
  [] -> return ()
  (y:ys) = printInteger y >> print ys

所以当我们开始执行main（我们现在做什么？之后我们会做什么？）时，我们正在尝试计算print ls。为此，我们在 ls 的第一个构造函数上进行模式匹配，这会强制将 ls 计算为 WHNF。我们发现第二个模式 y:ys 匹配，所以我们将 print ls 替换为 print Integer y >> print ys，其中 y 指向 ls 和 [=47 的第一个元素=] 指向表示 ls 的第二个列表构造函数的 thunk。但请注意 ls 本身现在已经死了！没有任何东西指向它！因此，当 print 强制列表的位时，它已经通过的位变为死。

相比之下，当你有

main =
  let ls = ...
  in print ls >> print ls

然后开始执行，首先计算要执行的操作 (print ls)。你得到

(printInteger y >> print ys) >> print ls

一切都一样，除了表达式的第二部分现在指向 ls。因此，即使第一部分会随着列表的进行而丢弃列表的一部分，第二部分也会继续保持开头，保持所有内容。

编辑

让我试着用比 IO 更简单的东西来解释。假设您的程序是 [Int] 类型的表达式，运行时系统的工作是将每个元素打印在自己的行上。所以我们可以写

countup m n = if m == n then [] else m : countup (m+1)
main = countup 0 1000

运行时系统拥有一个代表它应该打印的所有内容的值。让我们调用"current value" whatPrint。 RTS需要遵循一个流程：

将 whatPrint 设置为 main。
whatPrint是空的吗？如果是这样，我就完成了，可以退出程序了。如果不是，那就是缺点，printNow : whatPrint'.
计算printNow并打印出来
将whatPrint设置为whatPrint'
转到步骤 1。

在此模型中，用于垃圾收集的 "root set" 只是 whatPrint。

在实际程序中，我们不会生成列表；我们产生一个 IO 动作。但是这样的动作也是一个懒惰的数据结构（概念上）。您可以将 >>=、return 和每个原语 IO 操作视为 IO 的构造函数。把它想象成

data IO :: * -> * where
  Return :: a -> IO a
  Bind :: IO a -> (a -> IO b) -> IO b
  PrintInt :: Int -> IO ()
  ReadInt :: IO Int
  ...

whatShouldIDo的初始值是main，但它的值会随着时间的推移而演变。只有它直接指向的内容在根集中。不需要神奇的分析。

GHC 垃圾收集器/运行时如何知道它可以创建一个数组“inplace”

How does the GHC garbage collector / runtime know that it can create an array `inplace'

haskell

runtime

ghc

编辑