各种编程语言的实现都采用了哪些垃圾回收算法

Question

如题所述

Answer 1

从各种垃圾收集算法最基本的运行方式来说，大概可以分成三个类型：

1. 引用计数（reference counting）：

基本思路是为每个对象加一个计数器，记录指向这个对象的引用数量。每次有一个新的引用指向这个对象，计数器加一；反之每次有一个指向这个对象引用被置空或者指向其他对象，计数器减一。当计数器变为 0 的时候，自动删除这个对象。

引用计数的优点是 1）相对简单，不需要太多运行时（run-time）的支持，可以在原生不支持 GC 的语言里实现。2）对象会在成为垃圾的瞬间被释放，不会给正常程序的执行带来额外中断。它的死穴是循环引用，对象 A 包含一个引用指向对象 B ，同时对象 B 包含一个引用指向对象 A，计数器就抓瞎了。另外，引用计数对正常程序的执行性能有影响（每次引用赋值都要改计数器），特别是在多线程环境下（改计数器要加锁同步）。

现在仍然主要采用引用计数的例子有 Apple 的 ARC，C++ 新标准里的 std::shared_ptr。

2. 标记-清扫（mark-sweep）。

基本思路是先按需分配，等到没有空闲内存的时候从寄存器和程序栈上的引用出发，遍历以对象为节点、以引用为边构成的图，把所有可以访问到的对象打上标记，然后清扫一遍内存空间，把所有没标记的对象释放。

标记-清扫没有无法处理循环引用的问题，不触发 GC 时也不影响正常程序的执行性能。但它的问题是当内存耗尽触发 GC 时，需要中断正常程序一段时间来清扫内存，在内存大对象多的时候这个中断可能很长。

采用或者部分采用标记-清扫的例子非常多，不一一列举了。

3. 节点复制（copying）。

基本思路是把整个内存空间一分为二，不妨记为 A 和 B。所有对象的内存在 A 中分配，当 A 塞满的时候，同样从寄存器和程序栈上的引用出发，遍历以对象为节点、以引用为边构成的图，把所有可以访问到的对象复制到 B 去，然后对调 A 和 B 的角色。

相对于标记-清扫，节点复制的主要缺点是总有一半空间空闲着无法利用，另一个比较隐晦的缺点是它使用内存的方式与现有的内存换页、Cache 换入换出机制有潜在的冲突。但它有个很大的优点： 所有的对象在内存中永远都是紧密排列的，所以分配内存的任务变得极为简单，只要移动一个指针即可。对于内存分配频繁的环境来说，性能优势相当大。另外，由于不需要清扫整个内存空间，所以如果内存中存活对象很少而垃圾对象很多的话（有些语言有这个倾向），触发 GC 造成的中断会小于标记-清扫。

同样的，采用或者部分采用节点复制的例子也非常多，不一一列举了。