传统 GC 算法的优点与缺点

本篇是《垃圾回收的算法与实现》的读书笔记. 只是一种接近知识索引的形式.

GC 标记－清除算法。

最简单, 最古老的算法.

步骤

分成两步:
1.从根节点出发, 遍历所有可达的对象, 并在对象的头部添加标记.
2.遍历推, 回收所有的未标记的对象. 通常会有一个 free_list 来记录空闲的内存.

优点

• 实现简单.
• 与保守式的GC(对象不能被移动)兼容.

缺点

• 碎片化.
• 分配速度比较慢. 最坏情况下每次分配都需要遍历 free_list.
• 与写时复制不兼容(每次GC都会写内存导致复制.)

改善方式

• 多个空闲链表. 根据空闲块的大小选择存在不同的链表中.
• 合并空闲块, 在清除的时候, 如果两个空闲块可以合并, 那么就合并成一个大的空闲块. 可以减少一部分的碎片.
• BiBOP(Big Bag Of Pages) 方法. 将堆分块, 每一个块都只能分配固定大小的对象. 可以减少一些碎片, 但是降低了堆的使用效率.
• 位图标记法. 标记在一个位图中进行(通常 1 bit 代表一个字). 这个提高清除的效率, 还可以与写时复制兼容.
• 延迟清除法. 在分配的时候进行标记和清除. 可以降低最大暂停时间. 但是会导致分配的用时不稳定.

引用计数法

George E. Collins 在 1960 年提出来的. 现在 Apple 的 ARC 正式采用这种方式.