本書從近年來硬件與軟件的發(fā)展給垃圾回收所帶來的新挑戰(zhàn)出發(fā)，探討了這些挑戰(zhàn)給高性能垃圾回收器的設計者與實現(xiàn)者所帶來的影響。在簡單的傳統(tǒng)回收算法之外，本書還涵蓋了并行垃圾回收、增量式垃圾回收、并發(fā)垃圾回收以及實時垃圾回收。書中配備了豐富的偽代碼與插圖，以描述各種算法與概念。
目 錄
The Garbage Collection Handbook: the Art of Automatic Memory Management
出版者的話
譯者序
前言
作者簡介
第1章 引言 1
1.1 顯式內存釋放 1
1.2?自動動態(tài)內存管理 3
1.3 垃圾回收算法之間的比較 5
1.3.1 安全性 5
1.3.2 吞吐量 5
1.3.3 完整性與及時性 5
1.3.4 停頓時間 6
1.3.5 空間開銷 7
1.3.6 針對特定語言的優(yōu)化 7
1.3.7 可擴展性與可移植性 8
1.4 性能上的劣勢 8
1.5 實驗方法 8
1.6 術語和符號 10
1.6.1 堆 10
1.6.2 賦值器與回收器 11
1.6.3 賦值器根 11
1.6.4 引用、域和地址 11
1.6.5 存活性、正確性以及可達性 12
1.6.6 偽代碼 12
1.6.7 分配器 13
1.6.8 賦值器的讀寫操作 13
1.6.9 原子操作 13
1.6.10 集合、多集合、序列以及元組 14
第2章 標記–清掃回收 15
2.1 標記–清掃算法 16
2.2 三色抽象 18
2.3 改進的標記–清掃算法 18
2.4 位圖標記 19
2.5 懶惰清掃 21
2.6 標記過程中的高速緩存不命中問題 24
2.7 需要考慮的問題 25
2.7.1 賦值器開銷 25
2.7.2 吞吐量 26
2.7.3 空間利用率 26
2.7.4 移動，還是不移動 26
第3章 標記–整理回收 28
3.1 雙指針整理算法 29
3.2 Lisp 2算法 30
3.3 引線整理算法 32
3.4 單次遍歷算法 34
3.5 需要考慮的問題 36
3.5.1 整理的必要性 36
3.5.2 整理的吞吐量開銷 36
3.5.3 長壽數(shù)據(jù) 36
3.5.4 局部性 37
3.5.5 標記–整理算法的局限性 37
第4章 復制式回收 38
4.1 半?yún)^(qū)復制回收 38
4.1.1 工作列表的實現(xiàn) 39
4.1.2 示例 40
4.2 遍歷順序與局部性 42
4.3 需要考慮的問題 46
4.3.1 分配 46
4.3.2 空間與局部性 47
4.3.3 移動對象 48
第5章 引用計數(shù) 49
5.1 引用計數(shù)算法的優(yōu)缺點 50
5.2 提升效率 51
5.3 延遲引用計數(shù) 52
5.4 合并引用計數(shù) 54
5.5 環(huán)狀引用計數(shù) 57
5.6 受限域引用計數(shù) 61
5.7 需要考慮的問題 62
5.7.1 應用場景 62
5.7.2 高級的解決方案 62
第6章 垃圾回收器的比較 64
6.1 吞吐量 64
6.2 停頓時間 65
6.3 內存空間 65
6.4 回收器的實現(xiàn) 66
6.5 自適應系統(tǒng) 66
6.6 統(tǒng)一垃圾回收理論 67
6.6.1 垃圾回收的抽象 67
6.6.2 追蹤式垃圾回收 67
6.6.3 引用計數(shù)垃圾回收 69
第7章 內存分配 72
7.1 順序分配 72
7.2 空閑鏈表分配 73
7.2.1 首次適應分配 73
7.2.2 循環(huán)首次適應分配 75
7.2.3 最佳適應分配 75
7.2.4 空閑鏈表分配的加速 76
7.3 內存碎片化 77
7.4 分區(qū)適應分配 78
7.4.1 內存碎片 79
7.4.2 空間大小分級的填充 79
7.5 分區(qū)適應分配與簡單空閑鏈表分配的結合 81
7.6 其他需要考慮的問題 81
7.6.1 字節(jié)對齊 81
7.6.2 空間大小限制 82
7.6.3 邊界標簽 82
7.6.4 堆可解析性 82
7.6.5 局部性 84
7.6.6 拓展塊保護 84
7.6.7 跨越映射 85
7.7 并發(fā)系統(tǒng)中的內存分配 85
7.8 需要考慮的問題 86
第8章 堆內存的劃分 87
8.1 術語 87
8.2 為何要進行分區(qū) 87
8.2.1 根據(jù)移動性進行分區(qū) 87
8.2.2 根據(jù)對象大小進行分區(qū) 88
8.2.3 為空間進行分區(qū) 88
8.2.4 根據(jù)類別進行分區(qū) 89
8.2.5 為效益進行分區(qū) 89
8.2.6 為縮短停頓時間進行分區(qū) 90
8.2.7 為局部性進行分區(qū) 90
8.2.8 根據(jù)線程進行分區(qū) 90
8.2.9 根據(jù)可用性進行分區(qū) 91
8.2.10 根據(jù)易變性進行分區(qū) 91
8.3 如何進行分區(qū) 92
8.4 何時進行分區(qū) 93
第9章 分代垃圾回收 95
9.1 示例 95
9.2 時間測量 96
9.3 分代假說 97
9.4 分代與堆布局 97
9.5 多分代 98
9.6 年齡記錄 99
9.6.1 集體提升 99
9.6.2 衰老半?yún)^(qū) 100
9.6.3 存活對象空間與柔性提升 101
9.7 對程序行為的適應 103
9.7.1 Appel式垃圾回收 103
9.7.2 基于反饋的對象提升 104
9.8 分代間指針 105
9.8.1 記憶集 106
9.8.2 指針方向 106
9.9 空間管理 107
9.10 中年優(yōu)先回收 108
9.11 帶式回收框架 110
9.12 啟發(fā)式方法在分代垃圾回收中的應用 112
9.13 需要考慮的問題 113
9.14 抽象分代垃圾回收 115
第10章 其他分區(qū)策略 117
10.1 大對象空間 117
10.1.1 轉輪回收器 118
10.1.2 在操作系統(tǒng)支持下的對象移動 119
10.1.3 不包含指針的對象 119
10.2 基于對象拓撲結構的回收器 119
10.2.1 成熟對象空間的回收 120
10.2.2 基于對象相關性的回收 122
10.2.3 線程本地回收 123
10.2.4 棧上分配 126
10.2.5 區(qū)域推斷 127
10.3 混合標記–清掃、復制式回收器 128
10.3.1 Garbage-First回收 129
10.3.2 Immix回收以及其他回收 130
10.3.3 受限內存空間中的復制式回收 133
10.4 書簽回收器 134
10.5 超引用計數(shù)回收器 135
10.6 需要考慮的問題 136
第11章 運行時接口 138
11.1 對象分配接口 138
11.1.1 分配過程的加速 141
11.1.2 清零 141
11.2 指針查找 142
11.2.1 保守式指針查找 143
11.2.2 使用帶標簽值進行精確指針查找 144
11.2.3 對象中的精確指針查找 145
11.2.4 全局根中的精確指針查找 147
11.2.5 棧與寄存器中的精確指針查找 147
11.2.6 代碼中的精確指針查找 157
11.2.7 內部指針的處理 158
11.2.8 派生指針的處理 159
11.3 對象表 159
11.4 來自外部代碼的引用 160
11.5 棧屏障 162
11.6 安全回收點以及賦值器的掛起 163
11.7 針對代碼的回收 165
11.8 讀寫屏障 166
11.8.1 讀寫屏障的設計工程學 167
11.8.2 寫屏障的精度 167
11.8.3 哈希表 169
11.8.4 順序存儲緩沖區(qū) 170
11.8.5 溢出處理 172
11.8.6 卡表 172
11.8.7 跨越映射 174
11.8.8 匯總卡 176
11.8.9 硬件與虛擬內存技術 176
11.8.10 寫屏障相關技術小結 177
11.8.11 內存塊鏈表 178
11.9 地址空間管理 179
11.10 虛擬內存頁保護策略的應用 180
11.10.1 二次映射 180
11.10.2 禁止訪問頁的應用 181
11.11 堆大小的選擇 183
11.12 需要考慮的問題 185
第12章 特定語言相關內容 188
12.1 終結 188
12.1.1 何時調用終結方法 189
12.1.2 終結方法應由哪個線程調用 190
12.1.3 是否允許終結方法彼此之間的并發(fā) 190
12.1.4 是否允許終結方法訪問不可達對象 190
12.1.5 何時回收已終結對象 191
12.1.6 終結方法執(zhí)行出錯時應當如何處理 191
12.1.7 終結操作是否需要遵從某種順序 191
12.1.8 終結過程中的競爭問題 192
12.1.9 終結方法與鎖 193
12.1.10 特定語言的終結機制 193
12.1.11 進一步的研究 195
12.2 弱引用 195
12.2.1 其他動因 196
12.2.2 對不同強度指針的支持 196
12.2.3 使用虛對象控制終結順序 199
12.2.4 弱指針置空過程的競爭問題 199
12.2.5 弱指針置空時的通知 199
12.2.6 其他語言中的弱指針 200
12.3 需要考慮的問題 201
第13章 并發(fā)算法預備知識 202
13.1 硬件 202
13.1.1 處理器與線程 202
13.1.2 處理器與內存之間的互聯(lián) 203
13.1.3 內存 203
13.1.4 高速緩存 204
13.1.5 高速緩存一致性 204
13.1.6 高速緩存一致性對性能的影響示例：自旋鎖 205
13.2 硬件內存一致性 207
13.2.1 內存屏障與先于關系 208
13.2.2 內存一致性模型 209
13.3 硬件原語 209
13.3.1 比較并交換 210
13.3.2 加載鏈接/條件存儲 211
13.3.3 原子算術原語 212
13.3.4 檢測–檢測并設置 213
13.3.5 更加強大的原語 213
13.3.6 原子操作原語的開銷 214
13.4 前進保障 215
13.5 并發(fā)算法的符號記法 217
13.6 互斥 218
13.7 工作共享與結束檢測 219
13.8 并發(fā)數(shù)據(jù)結構 224
13.8.1 并發(fā)棧 226
13.8.2 基于單鏈表的并發(fā)隊列 228
13.8.3 基于數(shù)組的并發(fā)隊列 230
13.8.4 支持工作竊取的并發(fā)雙端隊列 235
13.9 事務內存 237
13.9.1 何謂事務內存 237
13.9.2 使用事務內存助力垃圾回收器的實現(xiàn) 239
13.9.3 垃圾回收機制對事務內存的支持 240
13.10 需要考慮的問題 241
第14章 并行垃圾回收 242
14.1 是否有足夠多的工作可以并行 243
14.2 負載均衡 243
14.3 同步 245
14.4 并行回收的分類 245
14.5 并行標記 246
14.6 并行復制 254
14.6.1 以處理器為中心的并行復制 254
14.6.2 以內存為中心的并行復制技術 258
14.7 并行清掃 263
14.8 并行整理 264
14.9 需要考慮的問題 267
14.9.1 術語 267
14.9.2 并行回收是否值得 267
14.9.3 負載均衡策略 267
14.9.4 并行追蹤 268
14.9.5 低級同步 269
14.9.6 并行清掃與并行整理 270
14.9.7 結束檢測 270
第15章 并發(fā)垃圾回收 271
15.1 并發(fā)回收的正確性 272
15.1.1 三色抽象回顧 273
15.1.2 對象丟失問題 274
15.1.3 強三色不變式與弱三色不變式 275
15.1.4 回收精度 276
15.1.5 賦值器顏色 276
15.1.6 新分配對象的顏色 276
15.1.7 基于增量更新的解決方案 277
15.1.8 基于起始快照的解決方案 277
15.2 并發(fā)回收的相關屏障技術 277
15.2.1 灰色賦值器屏障技術 278
15.2.2 黑色賦值器屏障技術 279
15.2.3 屏障技術的完整性 280
15.2.4 并發(fā)寫屏障的實現(xiàn)機制 281
15.2.5 單級卡表 282
15.2.6 兩級卡表 282
15.2.7 減少回收工作量的相關策略 282
15.3 需要考慮的問題 283
第16章 并發(fā)標記–清掃算法 285
16.1 初始化 285
16.2 結束 287
16.3 分配 287
16.4 標記過程與清掃過程的并發(fā) 288
16.5 即時標記 289
16.5.1 即時回收的寫屏障 290
16.5.2 Doligez-Leroy-Gonthier回收器 290
16.5.3 Doligez-Leroy-Gonthier回收器在Java中的應用 292
16.5.4 滑動視圖 292
16.6 抽象并發(fā)回收框架 293
16.6.1 回收波面 294
16.6.2 增加追蹤源頭 295
16.6.3 賦值器屏障 295
16.6.4 精度 295
16.6.5 抽象并發(fā)回收器的實例化 296
16.7 需要考慮的問題 296
第17章 并發(fā)復制、并發(fā)整理算法 298
17.1 主體并發(fā)復制：Baker算法 298
17.2 Brooks間接屏障 301
17.3 自刪除讀屏障 301
17.4 副本復制 302
17.5 多版本復制 303
17.6 Sapphire回收器 306
17.6.1 回收的各個階段 306
17.6.2 相鄰階段的合并 311
17.6.3 Volatile域 312
17.7 并發(fā)整理算法 312
17.7.1 Compressor回收器 312
17.7.2 Pauseless回收器 315
17.8 需要考慮的問題 321
第18章 并發(fā)引用計數(shù)算法 322
18.1 簡單引用計數(shù)算法回顧 322
18.2 緩沖引用計數(shù) 324
18.3 并發(fā)環(huán)境下的環(huán)狀引用計數(shù)處理 326
18.4 堆快照的獲取 326
18.5 滑動視圖引用計數(shù) 328
18.5.1 面向年齡的回收 328
18.5.2 算法實現(xiàn) 328
18.5.3 基于滑動視圖的環(huán)狀垃圾回收 331
18.5.4 內存一致性 331
18.6 需要考慮的問題 332
第19章 實時垃圾回收 333
19.1 實時系統(tǒng) 333
19.2 實時回收的調度 334
19.3 基于工作的實時回收 335
19.3.1 并行、并發(fā)副本回收 335
19.3.2 非均勻工作負載的影響 341
19.4 基于間隙的實時回收 342
19.4.1 回收工作的調度 346
19.4.2 執(zhí)行開銷 346
19.4.3 開發(fā)者需要提供的信息 347
19.5 基于時間的實時回收：Metronome回收器 347
19.5.1 賦值器使用率 348
19.5.2 對可預測性的支持 349
19.5.3 Metronome回收器的分析 351
19.5.4 魯棒性 355
19.6 多種調度策略的結合：“稅收與開支” 355
19.6.1 “稅收與開支”調度策略 356
19.6.2 “稅收與開支”調度策略的實現(xiàn)基礎 357
19.7 內存碎片控制 359
19.7.1 Metronome回收器中的增量整理 360
19.7.2 單處理器上的增量副本復制 361
19.7.3 Stopless回收器：無鎖垃圾回收 361
19.7.4 Staccato回收器：在賦值器無等待前進保障條件下的盡力整理 363
19.7.5 Chicken回收器：在賦值器無等待前進保障條件下的盡力整理（x86平臺） 365
19.7.6 Clover回收器：賦值器樂觀無鎖前進保障下的可靠整理 366
19.7.7 Stopless回收器、Chicken回收器、Clover回收器之間的比較 367
19.7.8 離散分配 368
19.8 需要考慮的問題 370
術語表 372
參考文獻 383
索引 413
新書資訊