前面几篇笔记里我们分别介绍了四种基本的 GC 算法：
本文将它们放在一起，做一个总结概括~
追踪式 VS. 引用计数式
| 类型 | 算法 | 特征 |
|---|---|---|
| 追踪式 GC | 标记-清除算法 复制算法 标记-整理算法 |
要先通过堆遍历找出所有的活动对象，然后在反向确定出未遍历到的垃圾 |
| 引用计数式 GC | 引用计数法 | 通过引用关系的创建或删除直接判定对象的存活性 |
移动式 VS. 非移动式
| 类型 | 算法 | 特征 |
|---|---|---|
| 移动式 | 复制算法 标记-整理算法 |
一定要找到并且更新指向被移动对象的全部引用 |
| 非移动式 | 标记-清除 引用计数法 |
只要找到某个活动对象的一个引用就足够了 |
四类基本算法的优缺点比较
| 算法 | 优点 | 局限性 | 其他 |
|---|---|---|---|
| 标记-清除算法 | 不会给赋值器带来任何额外的读写开销； 具有较高的吞吐量； 具有较高的空间利用率（相比于复制算法和引用计数法）； 不用移动对象，可与保守式回收器兼容； |
长期运行的程序堆可能会逐渐碎片化； 分配速度受限，因为分块不连续； |
一个通用方案：尽量长久地使用标记-清除算法进行水后，仅当碎片化到达一定程度时才使用标记-整理回收。 |
| 标记-整理算法 | 允许极为快速的顺序分配； 解决了碎片化问题； |
任意顺序算法只能处理单一大小的对象； 整理过程需要两次到三次整堆遍历，速度较慢，吞吐量较差； 对象头部可能需要额外的空间用于保存迁移信息； |
回收器遍历和分配对象的顺序会影响赋值器的局部性，对高速缓存命中率造成影响，从而影响程序性能； |
| 复制算法 | 消除碎片； 可实现高速分配； 较高的吞吐量； 不用引入额外的空间存放迁移信息； |
堆的利用率低（二分之一），导致回收次数比其他算法更多； | 可用空间减少，回收次数增多对性能的影响取决于赋值器与分配器之间的平衡、应用程序的特征和可用堆空间的大小等 |
| 引用计数法 | 可即刻回收垃圾（将内存管理开销分摊在程序运行过程中，垃圾被立即回收，因此可以持续操作即将填满的堆，而不必像追踪式GC需要一定的保留空间）； 具有较好的局部性； 不用沿指针查找； 可以在代码中实现，无需作为语言的运行时环境的一部分，开发者可以完全控制引用计数的使用（自主处理性能开销和安全性之间的平衡）； |
计数器更新频繁，给赋值器带来额外开销； 开发者必须避免在更新计数器值的过程中可能出现的竞争问题； 计数器值需要占用额外空间； 无法处理循环引用； |
即使系统部分不可用，引用计数法也能回收部分内存，这一特性对分布式系统十分有用； 引用计数法可以管理数量较少但所有者关系复杂的资源，这些资源通常较大，因此计数器值占用的额外开销可以忽略； |
四类基本算法的部分实现与优化
标记-清除算法
| 算法 | 优点 | 局限性 |
|---|---|---|
| 位图标记 | 位图使标记位更加密集； 标记过程不会修改任何对象，清除过程不会对任何活动对象进行读写操作，只会在释放垃圾时覆盖某些域，因此减少了内存中需要修改的字节数，减少了对高速缓存的写入，今儿减少需要写回内存的数据量 |
通常仅适用于单线程环境，因为多线程同时修改位图可能存在较大的写冲突风险 |
| 延迟清除 | 清除垃圾腾出的空间能立即得到复用，因而提升了程序的局部性；将标记-清除算法的复杂度降低到与堆中存活对象成正比的水平 | 延迟清除的效果是不均衡的，如果可回收对形成一片连续的空间，那么效率很高；如果进入大批活动对象范围，则很可能多次查询失败要直到遍历整个堆才找到合适的空间 |
标记-整理算法
| 算法 | 优点 | 局限性 |
|---|---|---|
| Two-Finger 算法 | 简单快速，每次遍历过程操作较少； forwarding 指针在对象移动后才写入，不会有信丢失，因此无需占用额外的空间来记录 forwarding 指针； 内存访问模式可预测，支持预取，进而提升回收器的告诉缓存友好性； |
重排对象为任意顺序，破坏了赋值器的局部性； 受制于“所有对象大小最好一致”的条件，如果对象大小不一致，在移动过程中还是难以避免产生碎片； |
| Lisp2 算法 | 可有效利用堆； | 需要在对象头中占用额外空间保存 forwarding指针； 整理过程需要进行三次遍历； |
复制算法
| 算法 | 优点 | 局限性 |
|---|---|---|
| 递归算法 | 深度优先遍历，有引用关系的对象会被安排在堆中离彼此较近的位置，有利于提高高速缓存命中率； | 递归调用函数消耗栈空间； |
| Cheney算法 | 采用迭代实现，消除了递归带来的额外负担和栈消耗； 直接把堆空间作为队列，省去了额外的内存空间开销； |
由于广度优先遍历的特点，Cheney复制算法中无法将有引用关系的对象复制到相邻的位置，降低了高速缓存的命中率； |
引用计数法
| 算法 | 优点 | 局限性 |
|---|---|---|
| 延迟引用计数（类似还包括合并引用计数） | 消除了操作局部变量时引用计数变更带来的开销； | 垃圾不能马上得到回收； ZCT 与日志缓冲区等带来额外的空间开销； 没有解决循环引用的问题； |
| 1-bit 引用计数法 | 不容易出现高速缓存缺失，因为它不需要在更新计数器时读取要引用的对象；不需要额外的给计数器留空间，节省了内存空间； | 如果有大量计数器溢出的对象，会给堆造成巨大的负担，甚至很难保证分块； |
以上只是列出了各类垃圾回收算法中典型的一两种实现，实际上多年来有很多研究针对每个算法的局限性做针对性的研究，还有非常多很细化的改进算法有待学习。
由于开这个系列的初衷，只是想拓宽一下自己对垃圾回收机制的了解，然而了解得越多越意识到这样一个主题若要深入研究下去，要学习的东西真的太多了。考虑到个人的精力，自己肯定做不到像研究生一样细啃论文，目前就先挖到这个尚浅的深度吧。
参考资料
- 垃圾回收的算法与实现
- 垃圾回收算法手册：自动内存管理的艺术