Note on GHC GC

01 Jul 2018 by fleuria

前段时间看了一下 haskell 的 gc，简单记一下。

比较特色的地方来自对象的不变性。如果所有对象不可变，GC 在设计上是否能有简化？ 其实 haskell 对象也并非完全不可变，一个惰性求值的 thunk 可以求值一次，也仅能求值一次，这便足以简化掉 remember set 的设计。相对于 jvm 那样的 dirty card，ghc 更容易做到这样的不变式：年轻代单向引用老年代，老年代的 thunk 如果求值生成的新引用，直接 eager promotion 给提升到老年代即可。这样 minor GC 扫描的范围可以更少。

函数式里的临时对象多，请求生命周期的话，临时对象都在年轻代，拷贝式 gc 相比 mark & sweep 理论上会更轻快。block 的堆布局在这方面能更精细回收掉旧的数据，也会作为并行分工的单位。

与 jvm 年轻代走拷贝 / 老年代走 mark & sweep 不同，ghc 的不同代都是拷贝式。

堆布局

ghc 的堆有被分成等大小的 block，并非 CMS 那样连续的堆。堆的每代都由离散的 block 链成，如果空间不足，可以新增分配 block。

对象的年龄信息 “step” 并未存放于对象元信息内，而是划分 generation 为 k 个 step 区域，一次 gc 之后仍存活的对象，会被拷贝到 step + 1 表示寿命提高，当 step 超过 k 之后，将这些对象整体提升到老年代。

Evacuate & Scavenge

Evacuate 和 Scavenge 拷贝式 GC 中常见的两个词：

  • Evacuate 是 “拷贝” 的近义词，将对象拷贝到 to-space，同时将 from-space 的旧对象修改成 forwarding-pointer 指向对象的新地址，也返回这个新地址。

  • Scavenge 是 “scan” 的近义词，遍历对象所引用的所有对象执行 evacuate，并修改对象引用的地址。

当 to-space 的所有对象都已经过 scavenge 之后，整个 gc 过程结束。

Parallel Copying

一个经过 evacuate 但仍未 scavenge 的对象，视为处于 pending 状态。

多个 gc 线程做的事情，都是原子取一个 pending 状态的对象 p，执行 scavenge(p)，将它引用的对象列表加入 pending set：

while (pending set is non-empty) {
  remove an object p from the pending set
  scavenge(p)
  add any newly-evacuated objects to the pendings set
}

用 block 来维护 pending set 这个 “任务队列” 是这里精巧的地方。

pending set 中等待 scavenge 的对象，一定会位于 to-space 的 block 之中。在链表相连的 block 之内按顺序遍历这些对象，就形成了一个 “任务队列“ 的形状，两个指针维护已遍历执行 evacuate 的对象的指针 S，加一个 pending 对象末尾的 SL 指针。

每个线程并发拷贝的逻辑相同，但是每个线程有自己私有的 to-space，都会拷贝向自己的 block。拷贝过程中生成的新的 block 可以加入队列的尾部作为新的 work 单位，这里似乎可以选择 work-stealing 的方式去提高并行。

References