数字版权声明 图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使 用，未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产 权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。 图书在版编目（ＣＩＰ）数据 垃圾回收的算法与实现 / (日) 中村成洋, (日) 相 川光编 ; 丁灵译. -- 北京 : 人民邮电出版社, 2016.7 （图灵程序设计丛书） ISBN 978-7-115-42747-2 Ⅰ. ①垃… Ⅱ. ①中… ②相… ③丁… Ⅲ. ①计算机 算法 Ⅳ. ①TP301.6 中国版本图书馆CIP数据核字(2016)第132397号 内 容 提 要 本书分为“算法篇”和“实现篇”两大部分。算法篇介绍了标记 - 清除算法、引用计数法、复制算 法、标记 - 压缩算法、保守式 GC、分代垃圾回收、增量式垃圾回收、RC Immix 算法等几种重要的算法； 实现篇介绍了垃圾回收在 Python、DalvikVM、Rubinius、V8 等几种语言处理程序中的具体实现。 本书适合各领域程序员阅读。 ◆ 著 ［日］ 中村成洋 相川光（著） 竹内郁雄（审校） 译 丁 灵 责任编辑 乐 馨 执行编辑 杜晓静 责任印制 彭志环 北京市丰台区成寿寺路 11 号 ◆ 人民邮电出版社出版发行 邮编 100164 网址 http://www.ptpress.com.cn 电子邮件 北京 [email protected] 印刷 ◆ 开本：800×1000 1/16 印张：28.5 2016 年 7 月第 1 版 字数：620 千字 印数：1 - 4 000 册 2016 年 7 月北京第 1 次印刷 著作权合同登记号 图字：01-2014-5626 号 定价：99.00 元 读者服务热线：(010)51095186转600 印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广字第 8052 号 审校者前言 计算机的进步，特别是硬件的发展之快总是让我们感到惊讶。在这波不断向前涌动的洪 流中，技术领域的浮沉也愈发激烈。本书涉及的垃圾回收（Garbage Collection，GC）与其说是 理论，其实更偏向技术层面，然而它却有着令人吃惊的漫长历史。GC 在计算机发展的激流 中没有浮起，也没有沉下。直到 1995 年 Java 发布，因为其内藏 GC，人们才开始意识到 GC 的作用。 追溯 Lisp 语言的秘史我们会发现，GC 这种让已经无法利用的内存实现自动再利用（可 能称为“内存资源回收”更恰当）的技术，是于 Lisp 的设计开始约 1 年后，也就是 1959 年的 夏天首次出现的。实现 GC 的是一个叫 D. Edwards 的人。至今已经经过了 50 多年的漫长岁月。 这期间人们进行了海量的研究和开发，与其相关的论文也堆积如山。这么说来，我也 写过几篇关于 GC 的论文。然而让我吃惊的是，这么久以来竟然没有一本关于 GC 的教科 书 或 专 业 书 籍。英 语 界 曾 于 1996 年 首 次 针 对 GC 出 版 了 一 本 Garbage Collection（Richard E. Jones、Rafael D. Lins 著），这是 37 年来在 GC 领域的一次破天荒的壮举，本书也将其作为 了参考文献。然而在日本，本书可以说是第一本用日语写的 GC 专业图书，可谓五十年磨一剑， 在此也对年轻有为的二位作者致以深深的敬意。 如果看看某本教科书中的一节或者读读几篇论文就能明白 GC 是什么东西，那么或许就 不需要这本书了，但 GC 并没有那么简单。在学习或工作中不得不使用 GC 的人，首先就必 须看两三篇有名的论文，之后还要去研究那些可能与其有关的原著。也就是说，从某种意义 上而言，最后还是需要自己去想很多东西。 尽管如此，还是有许多真心喜欢编程的人士，他们之中有一大群叫作 GCLover 的人。因 为 GC 基本上没有什么教科书，所以这群人之间似乎有着一种地下组织般的团队意识。总而 言之，对他们来说，GC 是个非常有意思、充满乐趣的程序。你读过本书后就会明白，GC 算 法会根据自动内存回收所需的环境（机器、语言、应用等）的不同而不同。到具体的程序层面， GC 则为程序员提供了一个最佳的游乐场所，令其尽情地发挥编程技巧，大展身手。事实上 我也属于长年乐在其中的一份子。GC 这东西很麻烦，但却是必需的。它就像一个幕后英雄， 默默地做着贡献，用户并不会期待它变得显眼。但因为它进行的是幕后工作，所以编程老手 们或许会为之心动。 如上所述，因为 Java 的出现，人们开始普遍认识到 GC 的可贵，自此多数的脚本语言都 具备了 GC。看到这种情形，我这个跟 GC 拉拉扯扯了近 40 年的人真是感慨万千。虽然没有 什么切实的根据，但是我一直认为，具备 GC 的语言要比不具备 GC 的同等语言生产效率高 百分之三十。 iv 审校者前言 既然话说到这里了，我就再介绍一下我的个人看法吧。实际上，GC 相当于虚拟内存。 一般的虚拟内存技术是在较小的物理内存的基础上，利用辅助存储创造一片看上去很大的“虚 拟”地址空间。也就是说，GC 是扩大内存空间的技术，因此我称其为空间性虚拟存储。这 样一来，GC 就成了永久提供一次性存储空间的时间轴方向的时间性虚拟存储。神奇的是， 比起称为“垃圾回收”，把 GC 称为“虚拟内存”令人感觉其重要了许多。当初人们根据计算 机体系结构开发了许多关于空间性虚拟存储的支持，所以大部分的计算机都标配了空间性虚 拟存储。只要硬件支持，GC 性能就能稳步提升，然而现实情况是几乎没有支持 GC 的硬件， 这不能不令人感到遗憾。 要说本书与涵盖面较广的 Garbage Collection 有什么不同，那就是本书涉及的面不那么 广，但“算法篇”中对 GC 的基础内容进行了详实的讲解。另外，“实现篇”是本书的一大特色， 其中解读了实际的 GC 代码。总体而言，本书作为一本教科书有着教育和现实意义。我作为 本书审校者，全方位检查、琢磨了书中的内容，担保这是一本通俗易懂的书。我深信，本书 作为一本 GC 专业图书，能让读者了解到 GC 是何物，体味到它的有趣之处以及它的重要性。 如果能让更多读者了解到 GC 的重要性，那么由硬件和 OS 支持 GC 的真的时间性虚拟 存储总有一天会实现吧。这就是我发自肺腑想说的话。开拓新技术的原石正在滚滚前进哦！ 东京大学情报理工学系研究科教授 竹内郁雄 2010 年 2 月 注意 1. 本书是作者个人的研究成果。 2. 本书内容已经过严格的审查和勘误，如发现内容缺失、错误等，请以书面形式联络出版方。 3. 关于运用本书内容所造成的任何结果，作译者及出版社不承担与上述两项无关的责任，敬请谅解。 4. 未经出版方书面许可，不得擅自盗印本书内容。 关于商标  本书中省略了 ®、©、™ 等符号，敬请谅解。  关于本书中涉及的程序名称、系统名称及 CPU 名称等，书中一律使用其最常用的称呼。  一般情况下，本书中使用的程序名称、系统名称及 CPU 名称等为各公司的商标或注册商标。 前言 净是拿比自己弱的人当对手，不可能有意思。 没有人能一看到谜题就瞬间解出答案。 读到一半就知道犯人的推理小说真是无聊透顶。 将自身能力发挥至极限去解开问题，这时才能把知识变成自己的东西。 —青木峰郎《Ruby 源代码完全解读》A 本书中涉及以下两个主题。 1. GC 的算法（算法篇） 2. GC 的实现（实现篇） 在“算法篇”中，我们从众多的 GC 算法中严格挑选了一些重要的算法来介绍，包括传 统算法和基本算法，以及稍微难一些的算法。“算法篇”最大的目的是让你了解 GC 独特的思 维方式和各算法的特性。 在“实现篇”中，你需要逐步阅读我们选择的语言处理程序的 GC 算法。因为我们在“算 法篇”中扎实地学习了理论，所以需要在“实现篇”中检验一下能把理论运用到什么程度。 特地设计“实现篇”还有一个目的，就是想让你亲身感受“理论和实现的不同”。要成功 实现，不仅要使用 GC 算法，还要在细节上下很多功夫，以与硬件环境和语言功能相协调。 通过学习更有实践性意义的知识，希望能进一步加你对 GC 的理解。 此外，随着深入阅读 GC，你会有另一种惊喜，即加深了对语言处理程序的认识。语言 处理程序是由数万行代码群构成的巨大程序。在阅读这样巨大的程序时，如果没有一个明确 的目标，那么就很难继续往下读。这就好比挖坑，如果往深处挖，坑的直径就会自然而然地 扩大。同理，如果我们去深入理解某一点，那么也就会逐渐理解其整体。“实现篇”就是在 持续挖掘 GC 这个深坑。我们深信，这项工作有助于加深我们对语言处理程序的整体理解。 中村成洋、相川光 2010 年 1 月 A 原书名为『Ruby ソースコード完全解説』 （Ruby Hacking Guide），目前尚无中文版。—译者注 谢辞 来自二位笔者的谢辞 首先要感谢本书中参考的论文和图书的作者，以及本书中引用的源代码的编写者。 感谢以下阅读本书原稿，给出众多评论的人士： 齐藤 tadashi、中川真宏、三浦英树、k.inaba、mokehehe（按五十音和字母顺序排列）。 上述人士也在“本书评论”中有所赠言。 感谢来自东京大学（2010 年 2 月）的本书审校者竹内郁雄教授。竹内教授痛快地接下了 本书审校的工作，还给予了我们很多意见。感谢 Ruby 的设计者松本行弘先生为本书所做的 推荐。此外，还要感谢秀和 SYSTEM 株式会社第二出版编辑部的各位，特别是本书的编辑 K。 来自中村成洋的谢辞 感谢在笔者写作第 12 章时，通过邮件列表热心回答笔者问题的 Evan Phoenix。 感谢在我小时候给我买了昂贵的 PC 的妈妈。感谢喜欢新事物但已故去的爸爸。感谢同 爸爸一样喜欢新事物的哥哥。感谢与我一起成长的伙伴们。 来自相川光的谢辞 在此向京都大学的汤浅太一老师致以谢意，是您令我邂逅了 GC。 在此对东京大学的本位田真一教授和本位田研究室的各位致以诚挚的感谢。感谢各位在 本书执笔期间给予的全面支持。 从心底感谢远在滋贺县、一直温柔守护我的爸爸妈妈以及妹妹。 本书评论 在这里，我们请阅读过本书原稿的人士发表了一下他们对本书的看法，如下所示（姓名 按五十音顺序和字母顺序排列，敬称略去）。 齐藤 Tadashi 我是个门外汉，所以刚开始还挺担心自己能不能理解呢！不过书中的讲解十分细致，作 者把每个知识点都掰开嚼