垃圾回收的算法与实现

更何况，GC 很有趣
读者对象
本书中的符号
图中的箭头
伪代码
命名规则
空指针和真假值
函数
缩进
指针
域
for 循环
栈与队列
特殊的函数
算法篇
1　学习 GC 之前
1.1　对象 / 头 / 域
1.1.1　头
1.1.2　域
1.2　指针
1.3　mutator
1.4　堆
1.5　活动对象 / 非活动对象
1.6　分配
1.7　分块
1.8　根
1.9　评价标准
1.9.1　吞吐量
1.9.2　最大暂停时间
1.9.3　堆使用效率
1.9.4　访问的局部性
2　GC 标记-清除算法
2.1　什么是 GC 标记- 清除算法
2.1.1　标记阶段
2.1.2　清除阶段
2.1.3　分配
2.1.4　合并
2.2　优点
2.2.1　实现简单
2.2.2　与保守式 GC 算法兼容
2.3　缺点
2.3.1　碎片化
2.3.2　分配速度
2.3.3　与写时复制技术不兼容
2.4　多个空闲链表
2.5　BiBOP 法
2.6　位图标记
2.6.1　优点
2.6.2　要注意的地方
2.7　延迟清除法
2.7.1　new_obj() 函数
2.7.2　lazy_sweep() 函数
2.7.3　有延迟清除法就够了吗
3　引用计数法
3.1　引用计数的算法
3.1.1　计数器值的增减
3.1.2　new_obj() 函数
3.1.3　update_ptr() 函数
3.2　优点
3.2.1　可即刻回收垃圾
3.2.2　最大暂停时间短
3.2.3　没有必要沿指针查找
3.3　缺点
3.3.1　计数器值的增减处理繁重
3.3.2　计数器需要占用很多位
3.3.3　实现烦琐复杂
3.3.4　循环引用无法回收
3.4　延迟引用计数法
3.4.1　什么是延迟引用计数法
3.4.2　dec_ref_cnt() 函数
3.4.3　new_obj() 函数
3.4.4　scan_zct() 函数
3.4.5　优点
3.4.6　缺点
3.5　Sticky 引用计数法
3.5.1　什么是 Sticky 引用计数法
3.5.2　什么都不做
3.5.3　使用 GC 标记 – 清除算法进行管理
3.6　1 位引用计数法
3.6.1　什么是 1 位引用计数法
3.6.2　copy_ptr() 函数
3.6.3　delete_ptr() 函数
3.6.4　优点
3.6.5　缺点
3.7　部分标记 – 清除算法
3.7.1　什么是部分标记 – 清除算法
3.7.2　前提
3.7.3　dec_ref_cnt() 函数
3.7.4　new_obj() 函数
3.7.5　scan_hatch_queue() 函数
3.7.6　paint_gray() 函数
3.7.7　scan_gray() 函数
3.7.8　collect_white() 函数
3.7.9　限定搜索对象
3.7.10　paint_gray() 函数的要点
3.7.11　部分标记 – 清除算法的局限性
4　GC 复制算法
4.1　什么是 GC 复制算法
4.1.1　copy() 函数
4.1.2　new_obj() 函数
4.1.3　执行过程
4.2　优点
4.2.1　优秀的吞吐量
4.2.2　可实现高速分配
4.2.3　不会发生碎片化
4.2.4　与缓存兼容
4.3　缺点
4.3.1　堆使用效率低下
4.3.2　不兼容保守式 GC 算法
4.3.3　递归调用函数
4.4　Cheney 的 GC 复制算法
4.4.1　copy() 函数
4.4.2　执行过程
4.4.3　被隐藏的队列
4.4.4　优点
4.4.5　缺点
4.5　近似深度优先搜索方法
4.5.1　Cheney 的 GC 复制算法（复习）
4.5.2　前提
4.5.3　执行过程
4.5.4　执行结果
4.6　多空间复制算法
4.6.1　multi_space_copying() 函数
4.6.2　mark_or_copy() 函数
4.6.3　copy() 函数
4.6.4　执行过程
4.6.5　优点
4.6.6　缺点
5　GC 标记 – 压缩算法
5.1　什么是 GC 标记 – 压缩算法
5.1.1　Lisp2 算法的对象
5.1.2　概要
5.1.3　步骤 1 —— 设定 forwarding 指针
5.1.4　步骤 2 —— 更新指针
5.1.5　步骤 3 —— 移动对象
5.2　优点
可有效利用堆
5.3　缺点
压缩花费计算成本
5.4　Two-Finger 算法
5.4.1　前提
5.4.2　概要
5.4.3　步骤 1——移动对象
5.4.4　步骤 2——更新指针
5.4.5　优点
5.4.6　缺点
5.5　表格算法
5.5.1　概要
5.5.2　步骤 1（前半部分）—— 移动对象群
5.5.3　步骤 1（后半部分）—— 构筑间隙表格
5.5.4　步骤 2——更新指针
5.5.5　优点
5.5.6　缺点
5.6　ImmixGC 算法
5.6.1　概要
5.6.2　堆的构成
5.6.3　对象的分类
5.6.4　分配
5.6.5　分配时的标记操作
5.6.6　步骤 1——选定备用 From 块
5.6.7　步骤 2 —— 搜索阶段
5.6.8　步骤 3 —— 清除阶段
5.6.9　优点
5.6.10　缺点
6　保守式GC
6.1　什么是保守式GC
6.1.1　不明确的根
6.1.2　指针和非指针的识别
6.1.3　貌似指针的非指针
6.1.4　不明确的数据结构
6.2　优点
语言处理程序不依赖于 GC
6.3　缺点
6.3.1　识别指针和非指针需要付出成本
6.3.2　错误识别指针会压迫堆
6.3.3　能够使用的 GC 算法有限
6.4　准确式 GC
6.4.1　正确的根
6.4.2　打标签
6.4.3　不把寄存器和栈等当作根
6.4.4　优点
6.4.5　缺点
6.5　间接引用
6.5.1　经由句柄引用对象
6.5.2　优点
6.5.3　缺点
6.6　MostlyCopyingGC
6.6.1　概要
6.6.2　堆结构
6.6.3　分配
6.6.4　new_obj() 函数
6.6.5　add_pages() 函数
6.6.6　GC 执行过程
6.6.7　mostly_copying() 函数
6.6.8　promote_page() 函数
6.6.9　page_scan() 函数
6.6.10　copy() 函数
6.6.11　优点和缺点
6.7　黑名单
6.7.1　指针的错误识别带来的害处
6.7.2　黑名单
6.7.3　面向黑名单内的地址的分配
6.7.4　优点和缺点
7　分代垃圾回收
7.1　什么是分代垃圾回收
7.1.1　对象的年龄
7.1.2　新生代对象和老年代对象
7.2　Ungar 的分代垃圾回收
7.2.1　堆的结构
7.2.2　记录集
7.2.3　写入屏障
7.2.4　对象的结构
7.2.5　分配
7.2.6　新生代 GC
7.2.7　老年代 GC
7.3　优点
吞吐量得到改善
7.4　缺点
在部分程序中会起到反作用
7.5　记录各代之间的引用的方法
7.5.1　卡片标记
7.5.2　页面标记
7.6　多代垃圾回收
7.7　列车垃圾回收
7.7.1　堆的结构
7.7.2　新生代 GC
7.7.3　老年代 GC
7.7.4　写入屏障
7.7.5　优点
7.7.6　缺点
8　增量式垃圾回收
8,1　什么是增量式垃圾回收
8.1.1　三色标记算法
8.1.2　GC 标记 – 清除算法的分割
8.1.3　根查找阶段
8.1.4　标记阶段
8.1.5　写入屏障
8.1.6　清除阶段
8.1.7　分配
8.2　优点和缺点
8.2.1　缩短最大暂停时间
8.2.2　降低了吞吐量
8.3　Steele 的算法
8.3.1　mark() 函数
8.3.2　写入屏障
8.4　汤浅的算法
8.4.1　标记阶段
8.4.2　从黑色对象指向白色对象的指针
8.4.3　写入屏障
8.4.4　分配
8.5　比较各个写入屏障
9　RC Immix 算法
9.1　目的
9.2　合并型引用计数法
9.2.1　伪代码
9.2.2　优点和缺点
9.2　合并型引用计数法和 Immix 的融合
9.3.1　新对象
9.3.2　被动的碎片整理
9.3.3　积极的碎片整理
9.4　优点和缺点
9.4.1　优点
9.4.2　缺点
实现篇
10　Python 的垃圾回收
10.1.1　Python 是什么
10.1.2　Python 的源代码
10.1.3　Python 的垃圾回收算法
10.2　对象管理
对象的结构
10.3　Python 的内存分配器
内存结构
10.4　第 0 层 通用的基础分配器
10.5　第 1 层 Python 低级内存分配器
10.5.1　内存结构
10.5.2　arena
10.5.3　pool
10.5.4　new_arena()
10.5.5　usable_arenas 和 unused_arena_objects
10.5.6　第 1 层总结
10.6　第 2 层 Python 对象分配器
10.6.1　block
10.6.2　usedpools
10.6.3　复杂的 usedpools
10.6.4　block 的状态管理
10.6.5　PyObject_Malloc()
10.6.6　（A）从 usedpools 中取出 pool
10.6.7　（B）返回 pool 内的 block
10.6.8　（C）调用 new_arena()
10.6.9　（D）初始化使用完毕的 pool
10.6.10　（E）初始化 pool 并返回 block
10.6.11　（F）初始化空 pool
10.6.12　PyObject_Free()
10.6.13　（A）把作为释放对象的 block 连接到 freeblock
10.6.14　（B）将 pool 返回 arena
10.6.15　（C）释放 arena
10.6.16　（D）移动到 usable_arenas 的开头
10.6.17　（E）对 usable_arenas 进行排序
10.6.18　（F）插入 pool
10.6.19　arena 和 pool 的释放策略
10.6.20　从 block 搜索 pool 的技巧
10.7　第 3 层 对象特有的分配器
分配器的总结
10.8　引用计数法
10.8.1　增量
10.8.2　Q：计数器不会出现溢出吗？
10.8.3　减量操作
10.8.4　终结器
10.8.5　插入计数处理
10.9　引用的所有权
10.9.1　传递引用的所有权（返回值）
10.9.2　出借引用的所有权（返回值）
10.9.3　占据引用的所有权（参数）
10.9.4　出借引用的所有权（参数）
10.9.5　使用引用计数法会留下 BUG 吗
10.10　如何应对有循环引用的垃圾对象
10.10.1　循环引用垃圾回收的算法
10.10.2　容器对象
10.10.3　生成容器对象
10.10.4　追踪容器对象
10.10.5　结束追踪容器对象
10.10.6　分代容器对象链表
10.10.7　何时执行循环引用垃圾回收
10.10.8　循环引用垃圾回收
10.10.9　gc_list_merge()
10.10.10　update_refs()
10.10.11　subtract_refs()
10.10.12　move_unreachable()
10.10.13　move_finalizers()
10.10.14　move_finalizer_reachable()
10.10.15　delete_garbage()
10.10.16　handle_finalizers()
10.10.17　循环引用中终结器的问题
10.10.18　不需要写入屏障吗
10.11　性能调整的建议
10.11.1　gc.set_debug()
10.11.2　gc.collect()
10.11.3　gc.disable()
11　DalvikVM 的垃圾回收
11.1.1　什么是 Android
11.1.2　Android 架构
11.1.3　DalvikVM的特征
11.1.4　Android 是多任务的
11.1.5　bionic
11.1.6　ashmem
11.1.7　dlmalloc
11.2　重新学习mmap
11.2.1　什么是 mmap
11.2.2　活用分配
11.2.3　请求页面调度
11.2.4　共享映射与私有映射
11.2.5　写时复制技术
11.3　DalvikVM 的源代码
11.3.1　获取源代码
11.3.2　源代码结构
11.4　DalvikVM 的 GC 算法
11.5　对象管理
11.5.1　对象的种类
11.5.2　对象结构
11.5.3　DalvikVM的内存结构
11.5.4　dvmHeapSourceStartup()
11.5.5　addNewHeap()
11.5.6　对象位图
11.5.7　dvmHeapBitmaplnit()
11.5.8　分配到 DalvikVM 的 VM Heap 空间
11.5.9　标记到对象位图
11.5.10　分配实例
11.6　标记阶段
11.6.1　启动 GC 的时机
11.6.2　标记的顺序
11.6.3　保守的根
11.6.4　DalvikVM是寄存器机器
11.6.5　VM的调用栈
11.6.6　初始标记
11.6.7　位图的标记
11.6.8　区别非指针和指向对象的指针
11.6.9　搜索对象
11.6.10　dvmHeapScanMarkedObjects()
11.6.11　dvmHeapBitmapXorWalk()
11.6.12　scanBitmapCallback()
11.6.13　scanObject()
11.6.14　processMarkStack()
11.7　清除阶段
11.7.1　在清除之前
11.7.2　开始清除
11.7.3　dvmHeapSweepUnmarkedObjects()
11.7.4　dvmHeapBitmapXorWalk()
11.7.5　sweepBitmapCallback()
11.7.6　dvmHeapSourceFree()
11.8　Q&A
11.8.1　终结器是什么？
11.8.2　为什么要准备两个位图？
11.8.3　碎片化的问题是？
11.8.4　为什么要采用位图标记？
12　Rubinius 的垃圾回收
12.1.1　什么是 Rubinius
12.1.2　获取源代码
12.1.3　源代码结构
12.2　Rubinius 的 GC 算法
12.3　对象管理
12.3.1　对象的结构
12.3.2　用于 GC 复制算法的内存空间
12.3.3　对象的分配器
12.3.4　GC 复制算法的分配器
12.4　走向准确式 GC 之路
12.4.1　根
12.4.2　CRuby 是保守式 GC
12.4.3　CRuby 的 C 语言扩展库
12.4.4　C 语言扩展库（准确式 GC 篇）
12.4.5　Rubinius 的解决方法
12.4.6　Hello Hello World
12.4.7　Rubinius 的处理器管理
12.4.8　与 GC 的关系
12.4.9　Rubinius 和 C 语言扩展库的交换
12.4.10　我们能实际运用 Rubinius 的 Ruby C-API 吗
12.4.11　FFI
12.4.12　内嵌对象和指针的区别
12.5　GC 复制算法
12.5.1　整体流程
12.5.2　collect()
12.5.3　(1) 搜索从记录集引用的对象
12.5.4　写入屏障
12.5.5　(2) 复制从根引用的对象
12.5.6　saw_object()
12.5.7　(3) 搜索复制完毕的对象
12.5.8　copy_unscanned()
12.5.9　scan_object()
12.5.10　(4) 垃圾对象的后处理
12.6　Q&A
12.6.1　该在何时启动各个 GC 算法呢 ?
12.6.2　为什么把执行 GC 复制算法的类叫作 BakerGC?
12.6.3　为什么是准确式 GC?
12.6.4　不解释一下如何实现 ImmixGC 吗 ?
12.6.5　为什么要把老年代对象存储在记录集里呢 ?
13　V8 的垃圾回收
13.1.1　什么是 Google Chrome
13.1.2　什么是 V8
13.1.3　获取源代码
13.1.4　源代码结构
13.2　V8 的 GC 算法
13.3　对象管理
13.3.1　持有不同分配器的两种类
13.3.2　Malloced 类
13.3.3　Object 类
13.3.4　其他特殊的类
13.3.5　VM Heap
13.3.6　老年代指针空间的结构
13.3.7　对象分配器
13.4　通往准确式 GC 之路（V8 篇）
13.4.1　HandleScope
13.4.2　HandleScope 的有效范围
13.4.3　HandleScope 的切换
13.4.4　打标签
13.4.5　控制对象内的域
13.4.6　与型相对应的访问器
13.4.7　域的位置和准确式 GC
13.5　GC 标记 – 压缩算法
13.5.1　GC 算法
13.5.2　启动 GC 的时机
13.5.3　GC 概要
13.6　标记阶段
13.6.1　标记阶段的概要
13.6.2　生成标记栈
13.6.3　标记根
13.6.4　标记对象
13.6.5　标记子对象
13.6.6　采用了标记栈的深度优先标记
13.6.7　标记栈的溢出
13.6.8　对象的标志位
13.7　压缩阶段
13.7.1　压缩阶段概要
13.7.2　(1) 设定 forwarding 指针
13.7.3　目标空间地址信息
13.7.4　map 地址信息
13.7.5　EncodeForwardingAddresses()
13.7.6　EncodeForwardingAddressesInRange()
13.7.7　EncodeForwardingAddressInPagedSpace()
13.7.8　(2) 更新指针
13.7.9　UpdatingVisitor
13.7.10　GetForwardingAddressInOldSpace()
13.7.11　(3) 移动对象
13.7.12　(4) 更新记录集
13.7.13　记录集的结构
13.7.14　RebuildRSets()
13.7.15　UpdateRSetVisitor
13.7.16　SetRSet()
13.8　Q&A
13.8.1　听说 V8 是在 Android 平台上运行的，是这样吗？
13.8.2　终结器是什么？
附录
附录 A　简单语言入门：Python 篇
内置数据类型
数值型
序列型
类
附录 B　简单语言入门：Java 篇
基本数据类型和引用类型
数组
类
附录 C　简单语言入门：Ruby 篇
全都是对象
类
附录 D　简单语言入门：JavaScript 篇
基本数据类型和引用类型
对象
参考文献
论文
图书