背景
最近看了一本书，《垃圾回收的算法和实现》，感觉挺有趣的，图示很多。很久没写笔记了，这本书看完了很多细节容易忘，而且有一些内容在书中描述的有些不太好理解，做笔记做备忘。
垃圾回收 (gc) 是一种很久历史的功能。早在 lisp 上就已经实现了。但是关于它的研究却未停止过。部分语言比如 Java/Python/Go 已经内置了 gc，使用者无需关心内存管理，放心 new 就是了。但是在 c++等语言上并没有垃圾回收，但是可以看到 c++的智能指针也参照了一些 gc 算法的实现。在后来我们会看到语言原生支持 gc 和给一个语言设计者没考虑过 gc 的语言加 gc 的困难程度是不一样的。
模型
此书的模型是很简单的。之后会补一些图，现在博客里图的方式太原始了。
堆就是一个类似数组的连续的内存空间。只有一个堆，我们假定其不能扩容。下文提到的遍历堆如果没有额外说明，就是自左到右遍历堆中的所有对象。对象就是由若干字节组成的整体。一个对象有头和若干个域.- 头往往用来存一些 gc 用的信息，而域才是代码中常常用到的，但是在很多算法中，垃圾的域会被重新利用来存储 gc 的信息。
- 一个域要么是指针类型，要么是基本类型（比如 int, float)，为了简单我们认为一个域只有一个字那么长。
- 我们暂且假设从内存中就能直接辨别一个域是指针还是非指针（到之后的保守式 gc 会探讨如果不能确定的情况）。我们首先假定对象至少存在一个域存放其大小。
- 本书假设是 32 位机，也就是指针长度为 4，一个字长也是 4 字节
此外还有一些概念
根可以理解为 寄存器，全局变量，当前栈中的变量等。其实可以简单理解为程序如果”解释”到这一行，那么在这一行所在的语境中，能够操作的对象。无法通过根中对象找到的对象，就视为垃圾，因为在之后的程序中不可能恢复对它们的使用权了（因为没有能操控它们的对象了）。child(obj)这个方法能够返回一个数组，数组里面是 obj 对象的儿子的引用。所谓儿子数组，也就是遍历 obj 的所有指针域，将指向的对象的引用加入数组，最后返回这个数组。- 值得注意的是，这本书中的指针与引用的关系有些混乱，很多地方的代码明明含义是传值，结果真正想表达的意思是传引用。实际上这本书中传递对象基本都看做引用就行，几乎没有传递一个对象的副本过去的。
- gc 除了考虑清理所需要的总时间外，还需要考虑最大暂停时间，可以想象如果是 java 写的游戏，那么玩家对 gc 就更敏感，所以要尽可能减少最大暂停时间
