云风的 BLOG: 引用计数与垃圾收集之比较

本质上来说，引用计数策略和垃圾收集策略都属于资源的自动化管理。所谓自动化管理，就是在逻辑层不知道资源在什么时候被释放掉，而依赖底层库来维持资源的生命期。

而手工管理，则是可以准确的知道资源的生命期，在准确的位置回收它。在 C++ 中，体现在析构函数中写明 delete 用到的资源，并由编译器自动生成的代码析构基类和成员变量。

所以，为 C++ 写一个垃圾收集器，并不和手工管理资源冲突。自动化管理几乎在所有有点规模的 C++ 工程中都在使用，只不过用的是引用计数的策略而非垃圾收集而已。也就是说，我们使用 C++ 或 C 长期以来就是结合了手工管理和自动管理在构建系统了。无论用引用计数，还是用垃圾收集，软件实现的细节上，该手工管理的地方我们依旧可以手工管理。

为什么要用资源生命期自动管理？

让我们来看面向对象，如果一切皆对象，每个对象的生命期就应该由自己负责，我们是可以直接准确的死亡时间的。可惜，有很多东西不是纯粹的对象。最重要的一个就是对象容器。它们除了自身的属性，还保持了对一组同类对象的引用。

一个对象可以分别被几个容器引用，这使得容器区别于猫猫狗狗这些对象实体。因为容器引用一个东西不等于这个东西是这个容器的一部分（有时候可以，有时候不行）。当我们把希望整个世界分成一个个对象时，所有的原子被分到各层的对象上后，就会发现有零零总总的概念无法用对象提取。引用而非拥有，这是无法回避的。

面向对象的本质在于，对许多对象提取出共性放在一起处理。这样，各式容器的使用就是无可避免的了。

也正是如此，对象自己并不知道自己是否已经可以宣告死亡。除非了解自己和别的对象的联系（这种关系不是对象）。资源可以是对象，而自动化管理正是管理的这些对象和对象之间的关系。

引用计数就是最容易实现的一种方案：记录对象被引用的次数，而不具体记录是谁引用了它。这样，降低了建立和解除引用的代价。但是，有得必有失。在引用计数的过程中，我们也丢失了重要的信息：到底是谁引用了自己。所以，引用计数在处理间接引用的问题上代价增加。

对象死亡的判定是：对象和这个世界还有没有联系，无论是直接的还是间接的。所以，一个对象即使还有另外的对象直接引用它，它也可能已经脱离了世界。为了解决这个问题，使用引用计数的系统，必须在对象和世界脱离联系时，通知和它有关联的对象。对象的销毁代价增加，就是引用计数策略的短板。

对象的销毁频率，取决于对象的平均生存时间。而对象的生存时间，一方面受对象粒度的影响，往往对象粒度越细，对象平均生存时间越短（虽然表面上没有直接联系，但是实际设计时往往会导致这个结果）；另一方面，我们往往会把容器和引用关系也实现成一种对象（概念上本不应该是对象）。比如说许多自动维持引用计数的智能指针就是一个小容器，里面保持了对一个对象唯一的引用，它就被实现成一个小对象。

通常，对象本身的性质并不随自己在内存空间中的位置改变而改变。但是引用关系（通常用指针来实现）却和内存地址相关。C++ 缺乏一种对象在内存中移动的语义表达，等价物是，在新的内存块中拷贝构造一个新对象，并销毁原有的。

另一方面，程序的运行序中，函数调用造成的堆栈上的嵌套作用域也可以看成一个个容器，机器指令穿行于这些作用域间，临时构造出的对对象的引用（智能指针），就被放置于这些作用域内。函数调用越频繁，这些作用域的创建和销毁也就越频繁。

这些导致了 C++ 必须依赖大量的 inline 函数，让编译器了解更多的上下文信息，方能减轻小对象（智能指针）创建销毁的负担。 STL 库也必须为其做一些优化，例如 stl port 中，对 POD 类型就做了特例化处理。可惜，智能指针不是 POD ，让编译器聪明到合并执行序列中的引用加减，难度太大（考虑到多线程因素，除非编译器可以知道线程的信息，否则几乎不可能实现）。

C++ 在实现面向对象的编程上，比 C 提供了许多便利。其中之一就是，在描述一个对象是另一个对象的一部分时，通过构造和析构函数机制，可以自动化的维护这相关部分的生命期。但它没能在语言上解决的是，当两者之间只是引用关系时，生命期如何处理。前者，我们有几乎唯一的简洁明了的解决之道；而后者根据实际需要可以有多种选择，顾而 C++ 在语言层面不提供一致解决方案。可惜的是 C++ 却一直每能提供一个简洁好用，带有普适性的 GC 库。大家都偏向于更为容易实现的引用计数的方案，这个结果跟具体实现的复杂度有关。毕竟在实现 gc 的时候，C 缺乏必要的语言支持（而 C++ 在实现层面，是从 C 的基础上发展而来）。

再来看看垃圾收集，比较成熟的算法基于标记清除（或标记整理）或其变体。简单说，就是由收集器框架记录下对象和对象之间的联系（这些联系信息存放的位置不重要，可以在对象的内存布局空间上，也可以在独立的地方，关键在于这些信息可以被收集器访问）。确定一个世界的根，定期的从这个根开始遍历这个世界，把有关联的对象标记起来，最后回收没有被标记的对象。

从算法上来看，建立对象和对象之间的联系的时间代价和引用计数的时间代价数量级上是一致的，都是 O(1) 。但实际实现时，前者的代价通常要大一些。空间代价上也是前者略大，但也没有数量级上的差别。

而 GC 管理的对象，在销毁时的代价要小的多。它不需要通知和它有关联的对象。

这就是为什么，许多使用 GC 的软件有时候比使用引用计数的软件运行效率还高那么一点的缘故。

可是，GC 有一个额外的时间代价来源于标记的过程。完成完整的一次清理过程，必然遍历到世界中每一个活着的对象。代价是 O(N) ，N 随着对象总体数量的增加而增加。所以我们应该减少被 GC 管理的对象的数量，在这一点上，手工管理依然有意义。即，明确一个对象是另一个对象的组成部分时，可以考虑用手工管理的方式。

另一个糟糕的地方是，在实现时，我们往往把对象间的关联信息放在了对象本身的内存布局空间中，遍历这个世界中的对象意味着访问所有对象的内存。当虚拟内存空间大于实际物理内存空间时，这意味着页面交换。我觉得，很大程度上，java 或 C# 这样的语言搭建起来的庞大系统偶尔运行缓慢，根本原因就在这里。当然，这些是可以被改进的。并非算法本身的问题。

可以这样说，GC (garbage collection) 把 RC (reference counting) 中那些短期对象的销毁代价转嫁到了一次性的标记清除过程。这把逻辑处理和资源管理正交分解了。这种被分解的问题，会随着硬件的进步更容易提高性能（比如多核的发展）。但是，在较小规模的软件或独立模块中，这个优势并不会太明显。反而 GC 本身远高于 RC 的复杂性，会成为其软肋。

对于不需要面向对象的软件，甚至连资源自动化管理都不需要。这时，无论是 GC 还是 RC 都无用武之地。

我做的那个简陋的垃圾收集器，也只是想做些简单的尝试，为 C 或 C++ 语言构建软件时多一些选择。

Comments

最近项目中也用到了rc管理内存池对象,如一块相同的内存需要发送给1000个用户,如果将这块内存拷贝到1000个用户输出缓冲区,势必会很浪费,所以加了引用计数,来减少拷贝.似乎跟你们讨论的主题有点不一样,但是在我的这个项目场景中,RC确实提高了我的性能.不知道这是不是RC的另一种优势. 再说说GC,如c#,GC工作时将枚举每个Heap上的所有segement来进行内存回收或者代的重新计算,每个segment上的内存是相邻的所以,应该不会产生太多的内存换页,而且回收时有明确的目标(即不会所有的对象都扫一遍) ,但是搬迁的过程会影响每个对象的地址,势必需要锁住所有的线程堆栈而且需要做极其复杂的对象引用关系分析.所以我认为gc真正的瓶颈还是要看对象的数量和内存总量.如果对象总数不多或者内存总量不大时,gc工作频率和效率都是比较高的.要保证对象总量和内存总量较小,必须涉及到手工操作.即时在c#这种语言中也是鼓励大家手工释放的.特别是c#引用到c++对象时(即调用了非托管代码),必须释放.

Posted by: 塞外浪子 | (18) August 22, 2010 12:32 AM

争论的好激烈，不过感觉看看高手的想法是非常有利于像我这样的菜鸟成长的。

Posted by: starshine | (17) August 20, 2010 04:51 PM

后续我又查了一下，发现如果只是标记-清除，那么理论上的确不需要加锁，但是现在很多都是标记-整理，这样就会涉及到正在使用的内存空间，就必须暂停应用程序了。如果gc仅仅作为其他管理手段的一个补充，那么用标记-清楚可能是比较合适的折中。

Posted by: sjinny | (16) June 17, 2008 01:02 PM

Cloud：假设有一个核永远不停的跑 GC ，.... Java的GC还做不到这点。JVM启动垃圾收集时，必须stop whole world，暂停所有应用线程，由GC线程接管一切。

Posted by: Anonymous | (15) June 17, 2008 10:08 AM

反向记录对象的引用来实现GC绝对是低效笨拙的方案，主流的GC算法也不是这么实现的。由于C++缺乏metadata信息，使得扫描对象之间的引用关系变得不太可能。如果C++能够容易的实现GC的话，for C++的GC库早就满天飞了，实际情况则是for C++的GC库基本没人用。

Posted by: analyst | (14) June 16, 2008 11:06 PM

正文中提到了，RC 多出来的的代价存在于对象析构过程，这个过程其实就是对相关对象解引用。GC 是不需要析构过程的。 C++ 对指针产生不了自动化的代码，手工加减引用和使用 GC 时的增加解除引用，对程序员的负担是一样的。本质上说，RC 在每次被别人引用时，记录下次数。GC 在每次被人引用时记录下对象。如果前者可以由语言自动做到，那么后者也可以。C++ 这么强大，其实实现一个 C++ 用的完全取代 smartptr 的 gcptr 不是什么难事。（完全隐藏起 link, enter, leave 这些调用）如果我还是三年前的我，就发布一个 C++ 库了 :)

Posted by: Cloud | (13) June 16, 2008 06:41 PM

提点个人看法： 1、我不反对GC是比RC更好的对象生命期自动化管理机制。支持GC的主要理由是GC相比RC在使用上更简洁更方便，GC对用户来说几乎是透明的，而RC存在的一些硬伤（例如循环引用）使得在使用上要求程序员付出更多的思考。 2、对于RC来说，出于性能考虑，对象在穿越一个作用域的时候可以不需要增减引用计数，也就是说在函数参数里可以用原生指针传递对象，因此实际上引用计数的增减并不是频繁发生的事情，对性能的影响微乎其微。主观判断GC比RC更高效缺乏事实的依据。 3、由于C++缺乏一些必要的实现GC的语言特性，因此在C++里要方便、透明的使用GC是不现实的，付出的代价远比得到的多，对C++来说RC是最佳的选择。

Posted by: analyst | (12) June 16, 2008 05:45 PM

那个留言，更应该留在这里也适合留在这里但我就不重复了否则便认为心智有问题（其实是误解）

Posted by: big | (11) June 16, 2008 04:43 PM

mark是属于GC逻辑里的, sweep也是纯粹GC逻辑的, 原则上来说唯一需要保证的就是广义上new, delete操作的原子性.

Posted by: Xiaofeng | (10) June 15, 2008 11:13 PM

呃……sweep也不需要加锁吗？

Posted by: sjinny | (9) June 15, 2008 10:46 PM

ps. mark 的过程是独立于逻辑的，所以可以不需要加锁就能独立并行运行。 :) 是的, 这也就是在多核机器上可以放心高效回收的理由. 毫无疑问的，　如果自己用过GC的语言，　并且亲自实现过, 就知道GC纯粹的理由.

Posted by: Xiaofeng | (8) June 15, 2008 10:39 PM

GC 的过程是确定的，和系统中任何别的模块一样，GC 的运行过程是严格依赖初始状态并保证一致的。 GC 的实现是复杂的，但是是和其它部分正交的，可以正交分解的模块有很大的优化余地。由于内聚性提高，质量更容易趋于稳定，这也是使用 GC 的系统有更高的稳定性的缘故之一。其实保留一些内存不交还给 OS 是一种常用的优化手段，大部分情况下都可以提高性能。比如 stl port 里为 allocater 实现的小内存块的 freelist 。就是预先分配大量的小内存块，等待逻辑需要时立刻交给用户。也就是说，它和 GC 系统一样，进程中向 OS 申请的内存块永远比实际用的要多。关于 RAII 的问题，在实现 GC 时处理类似的问题应该分开处理。GC 回收的并不光是内存，也包括文件 handle ，网络 socket 等。比如给系统保留 10 个 file handle ，一旦分配出来的 file handle 超过 10 个，可以调用 mark-sweep 的过程。或采用独立线程，持续不段的跑 mark 循环，一旦检测到稀有（非内存）资源脱离世界，就立刻回收。 ps. mark 的过程是独立于逻辑的，所以可以不需要加锁就能独立并行运行。

Posted by: Cloud | (7) June 15, 2008 02:00 PM

感觉虚拟内存本来应该是透明的，现在如果要让应用程序的编写者考虑到虚拟内存的访问和页面交换，甚至要为此影响程序设计，感觉这是有点问题的。我觉得，页面交换的量和物理内存的占用量是有一定程度的关联的，如果系统里所有程序所占的内存总量比物理内存小很多，那么就可以避免页面交换；如果一个程序占用的页面越少，那么它运行期间需要进行页面交换的概率会相对小一点。当然这还和内存访问的范围有关系，但是问题的整体规模变小后很多问题就不成为问题了。把空间和时间折算到一起来评价是一种办法，但是用户的内存和CPU是无法互相替代的。我现在已经不想讨论gc的性能了，因为我没有真正用过gc，^_^。及时回收的问题，我是这样想的： gc管理的对象，其回收时机依赖于collect的时机，而collect的时机与被管理对象本身的生命期是没有本质关联的。collect就像轮询一样，系统需要的时候（比如可用内存太少了），就去轮询一下，看看有哪些内存可以腾出来用的；而rc则像回调（如果不考虑循环引用的问题），当一个对象的生命期结束时就会立即销毁它。所以我觉得至少理论上，rc的回收会比gc更及时。不过现在突然想到，gc和rc的特点似乎是这样的：gc针对吞吐量做优化，而以牺牲单个对象的回收及时性为代价；rc确保了单个对象的及时回收，但是其结构性成本可能会降低整体的吞吐量。所以这里有个假设，如果gc管理的资源是相当稀缺的资源，如果这种资源的回收不及时，那么就会有很大的代价，那么这时gc的效果就会很差，rc相对会好些。不过目前看到的gc主要是针对内存的，似乎很多人为了用gc宁愿放弃RAII。 “有了gc就放手不管是不负责任的”这句云风误会了，其实这句不是针对你的这篇文章说的，是针对java那种只提供gc这一种方式的语言的。另外，我觉得有一个概念应该明确一下：究竟什么是自动化的资源管理技术，自动化的资源管理技术究竟是什么。我觉得，栈本身是一种自动化的管理技术，内存池也是，rc和gc也是。如果自动化管理包括了这些，那么不管是面向什么的开发，我想都绕不过去。但是，gc和前面那些技术的很大区别是，gc的不确定性更高，个人感觉不太放心。自动化的资源管理技术我觉得是个好东西，无需回避，只是如果自动化是以牺牲确定性为代价的，我觉得会不放心。做个极端的假设，假如有一种硬件，它是具有自我意识的AI，实际运行时它能比任何人、任何技术更好地管理系统中的一切资源，但是任何人类都难以完全搞清楚它管理的具体过程，那么这时程序员会不会放心地使用它呢？ gc对资源的管理，其行为对运行期的状态有很大的依赖，换句话说在编写代码的时候其确定性相对较差。

Posted by: sjinny | (6) June 15, 2008 12:45 PM

一直对gc的概念不是很了解，想问一下云风如果想了解一下gc，是不是要深入了解一下使用gc的语言？还有对于rc也是仅仅知道概念，cloud能不能举一两个好懂的实际项目让我看看真实项目中的实现？

Posted by: nothanks | (5) June 15, 2008 12:42 PM

“ 如果你使用面向对象，回避使用自动化管理机制的可能性几乎为零。” 恩，同感。

Posted by: Anonymous | (4) June 15, 2008 11:56 AM

对于现代操作系统来说，你的应用程序浪费的都不是物理内存，而是虚拟内存。占用太多虚拟内存是以增加 IO 成本为代价的。那样会触发过多的页面交换。但，如果你占用了虚拟内存，而不去访问它们，这些交换同样也不会发生。所以优化的目标是尽量减少不必要的虚拟内存访问，而不必关心到底占用了多少虚拟内存空间。最终，空间消耗还是会被折算成时间消耗来评估性能。你让 gc 系统在合适的时间去回收它跟让 rc 系统在合适的时间去回收它，没有本质区别。在性能问题上，rc 未必比 gc 高，正是本文阐述的问题。担心内存不即时回收造成性能问题是可以理解的，但也应该相信，随着硬件技术的发展，这个问题很容易解决。假设有一个核永远不停的跑 GC ，平均每秒就可以做一次。又能浪费多少呢？（考虑一秒内软件可能构造的对象数目？） gc 和 rc 只是自动管理的一种手段而已。所谓 “有了gc就放手不管是不负责任的”是误解了 gc 。如果纠正一下，应该说“有了自动化管理就放手不管是不负责任的”这自动化管理，也包括了 RC 。至于系统中能不能避免使用自动化资源管理。呵呵，我的观点是，如果你使用面向对象，回避使用自动化管理机制的可能性几乎为零。

Posted by: Cloud | (3) June 15, 2008 12:03 AM

嗯，我觉得手动管理是程序员的责任，有了gc就放手不管是不负责任的。手动管理的特点应该是：在恰当的时机释放，同时不引入额外的代价。RC的特点则只有恰当时机的释放，但引入了额外的代价。而GC对对象的释放则会比RC的时机要晚一点，毕竟无法保证每个对象应该被销毁时都正好调用了collect。不管是GC还是RC，在大系统里滥用都不好，但是我觉得GC会更倾向于使用更多的内存，因为GC里对象的释放会相对滞后。虽说现在内存便宜了，但这不是浪费用户的机器资源的合适理由。另外，其实栈本身是非常好的一种自动机制，真正纯手工的管理应该只有一种：需要时malloc，不需要时free……在C++里，经常会自己制作一些小的单元来把一些资源管理做得自动化一点，比如RAII。我心目中的优先度是：栈>>内存池/对象池>RC>=GC

Posted by: sjinny | (2) June 14, 2008 10:52 PM

对C++的了解又深了一层。

Posted by: 魏献华 | (1) June 14, 2008 09:03 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

引用计数与垃圾收集之比较

Comments

Post a comment