X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938-2号

《垃圾回收算法与实现》读书笔记(第 6-9 章)


书接上回,第 6-9 章的笔记。

Chapter 6:保守式 GC(Conservative GC)

为了实现某一个 GC 算法,需要首先选择 GC 的种类。这里的种类指的是 “保守式 GC” 和 “准确式 GC”。其中,“保守式 GC” 指的是 “不能识别指针和非指针的 GC”。

  1. (Page:120)不明确的根root):
  1. (Page:120)保守式 GC 在检查不明确的根时进行的基本项目:
  1. (Page:122)保守式 GC 的优缺点:
  1. (Page:123)准确式 GC:能正确识别指针和非指针的 GC。
  1. (Page:125)间接引用:可解决保守式 GC 无法使用“复制算法”的问题。

  1. (Page:127)MostlyCopyingGC:保守式 GC 复制算法,可在不明确的根的环境中运行 GC 复制算法。思路是:把那些不明确的根指向的对象以外的对象都复制的 GC 算法。MostlyCopyingGC 会抛开那些不能移动的对象,而将其他“大部分”的对象都进行复制

  1. (Page:139)黑名单:可改善“指针错误识别”的问题。
// 伪代码。若该对象地址未曾使用过,则将其加入黑名单;
if (!is_used_object(obj)) 
  obj.next = $blacklist 
  $blacklist = obj

Chapter 7:分代垃圾回收(Generational GC)

即在对象中引入了“年龄”的概念,通过优先回收容易成为垃圾的对象,提高垃圾回收的效率。这基于一个总结出的经验:“大部分对象在生成后马上就变成了垃圾,很少有对象能活得很久。”

  1. (Page:143)分代
  1. (Page:143)Ungar 的分代垃圾回收

- 堆结构

- 实现细节

A write barrier in a garbage collector is a fragment of code emitted by the compiler immediately before every store operation to ensure that (e.g.) generational invariants are maintained.

  1. (Page:154)一些可以替代“记录集”的方式(标记需要遍历的某一块老年代空间):
  1. (Page:156)多代垃圾回收:可以相对减少在老年代对象上消耗的垃圾回收时间。除了最老的那一代之外,每代都有一个记录集。X 代的记录集只记录来自比 X 老的其他代的引用。综合来看,少设置一些分代能得到更优秀的吞吐量,据说分为 2 代或者 3 代是最好的
  2. (Page:157)列车垃圾回收Train GC):为了在分代垃圾回收中利用老年代 GC 而采用的算法,可以控制老年代 GC 中暂停时间的增长。

- 堆结构

- 实现细节

Chapter 8:增量式垃圾回收(Incremental GC)

是将 GC 和 mutator 一点点交替运行的手法,GC 的执行不会导致 mutator 的暂停。“停止型 GCStop-The-World-GC)” 与 “增量式 GC”。

  1. (Page:168)增量式 GC 标记-清除算法
  1. (Page:174)Steele 算法
// 伪代码;
write_barrier(obj, field, newobj) { 
  if (
    $gc_phase == GC_MARK && 
    obj.mark == TRUE && 
    newobj.mark == FALSE
  ) {
    obj.mark = FALSE  // 将当前对象标记为“灰色”;
    push(obj, $mark_stack)  // 重新搜索;
  }
  *field = newobj
}
  1. (Page:176)汤浅的算法(又名“快照 GC”):

Chapter 9: RC Immix 算法

  1. (Page:180)RC Immix 算法(合并型引用计数法 + Immix 算法)将引用计数法的一大缺点 — “吞吐量低”(由于引用计数频繁变化引起),改善到了实用级别
  2. (Page:181)合并型引用计数法:将注意力放在某一时期最初和最后的状态上,在该期间内不进行计数器的增减。指针改动时的信息(对象和其子对象)会被注册到“更改缓冲区”(Modified Buffer)。当更改缓冲区满时,执行 GC 查找更改缓冲区,并正确设置计数器的值。

  1. (Page:185)RC Immix 算法


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)