主流的垃圾回收机制都有哪些?

无意中看到JavaScript V8和Python中也是使用引用计数和标记清除作为垃圾回收的基础方法，想问问 是否还有其他的垃圾回收算法？

回复内容：

前面有不少回答了，其中有部分靠谱的内容，感觉要补充也挺麻烦的，俺就放个俺推荐的书单吧：
[Garbage Collection][垃圾回收][自动无用内存单元回收]相关读物
《The Garbage Collection Handbook》非常开眼界，能完美回答题主的问题。

不想买书的话从这个网站开始学习也行：Introduction to memory management

也欢迎关注这个HLLVM群组的论坛，高级语言虚拟机
我以前发过一些帖，例如说介绍copying GC的基础实现：HotSpot VM Serial GC的一个问题
以及G1 GC的实现：[HotSpot VM] 请教G1算法的原理
以及几种GC的比较：并发垃圾收集器（CMS）为什么没有采用标记

引用计数与tracing GC的讨论俺也就放个传送门好了：垃圾回收机制中，引用计数法是如何维护所有对象引用的？ - RednaxelaFX 的回答

=======================================================

另外对问题描述吐个槽：

无意中看到JavaScript V8和Python中也是使用引用计数和标记清除作为垃圾回收的基础方法，想问问 是否还有其他的垃圾回收算法？

(C)Python是用引用计数为主、mark-sweep为备份没错。

但是V8的GC并不是单纯基于mark-sweep的。

最初发布的时候，V8还比较简单，采用分两代的GC，其中new space用copying GC，然后global GC根据碎片化状况选择性使用mark-sweep或mark-compact。
其抽象思路可以看这个入口函数：v8/mark-compact.cc at 0.1 · v8/v8 · GitHub

<code class="language-cpp"><span class="kt">void</span> <span class="n">MarkCompactCollector</span><span class="o">::</span><span class="n">CollectGarbage</span><span class="p">()</span> <span class="p">{</span>
  <span class="n">Prepare</span><span class="p">();</span>

  <span class="n">MarkLiveObjects</span><span class="p">();</span>

  <span class="n">SweepLargeObjectSpace</span><span class="p">();</span>

  <span class="k">if</span> <span class="p">(</span><span class="n">compacting_collection_</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">EncodeForwardingAddresses</span><span class="p">();</span>

    <span class="n">UpdatePointers</span><span class="p">();</span>

    <span class="n">RelocateObjects</span><span class="p">();</span>

    <span class="n">RebuildRSets</span><span class="p">();</span>

  <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
    <span class="n">SweepSpaces</span><span class="p">();</span>
  <span class="p">}</span>

  <span class="n">Finish</span><span class="p">();</span>
<span class="p">}</span>
</code>

感觉 Wikipedia 上的 Reference counting 和 Tracing garbage collection 条目讲的还是挺好的。总的来说，GC 可以有很多种分类方式：

有一部分 GC 一定要遍历需要 GC 的对象的图，从而获得一个精确的哪个对象活着哪个对象死了的信息。我们称这种 GC 为 tracing GC，不需要遍历的称为 non-tracing GC （比如 reference counting，它只能获得一个近似的信息，所以无法处理图里的环）。

有的 GC 需要程序员/编译器提供合作，以精确的知道哪个 pointer 是对象（指需要 GC 的对象）。有的 GC 不需要，光靠猜（猜也是很难的！猜不出来就只能当做是 pointer 了），也能做到 GC。前者称之为 precise GC，后者称之为 conservative GC（比如 Boehm GC）。我们下面主要讨论 precise GC。

有的 GC 分配了内存之后，这块内存可能会被移动到另外一个地方去，防止内存碎片化，提高缓存局部性（cache locality，这个怎么翻译呢..），这种 GC 被称为 moving GC，而不这么做的 GC 就称为 non-moving GC。moving GC 自然都是 tracing GC，因为它们必须要知道怎么遍历需要 GC 的对象的图，不然没法移动（毕竟移动某个对象的时候，也要修改存有这个对象的地方的值，指向新的位置）。

有的 GC 一次处理整个对象图，有的 GC 则做了优化，一部分时间只处理较新的对象。这个优化是建立在一个现象上的：新的对象比较容易指向老的对象，而老的对象较少指向新的对象；新的对象比较容易死掉，而活了比较久的对象则很有可能会活更久。很多编程的方式都会造成这种现象，比如 immutable data structures 等等。那么针对性的，GC 就可以区分对象的年纪，把内存分配的区域分为（较大的）老区和（较小的，为了缓存局部性）新区，然后根据老区满了与否，每次 GC 判断到底是只需要 GC 新区还是全都需要 GC。如果只需要 GC 新区，那么遍历对象图的时候只要遇到了老区的对象，就直接当做这个对象是活着的，后面的图就不用看了，直接剪掉。遇到了新区的对象，就根据对象存活了几次 GC 来看要不要将其移动到老区里。当然这个现象并不是绝对的，还是会出现老对象指向新对象的情况，怎么办呢？这就要在每次修改对象的时候（这种做法被称为 GC write barrier，就是每次修改对象之前都要有个检查），检查被修改的对象是不是老对象，修改成的值是不是新对象，如果确实是这样，那么就用一种方法（比如 remembered set，card marking 等等）来记住这个例外的情况。这么做的 GC 称之为 generational GC。

最常见的 non-tracing GC 方式就是 reference counting 了，在 Python，Objective-C，C++，Rust 里都能见到。一个较为易读的实现是（玛德 libstdc++ 的 shared_ptr 真难看，真喜欢看 C++ 的话 protobuf 里的 protobuf/shared_ptr.h at master · google/protobuf · GitHub 可读性还不错） rust/rc.rs at master · rust-lang/rust · GitHub

Naive mark-and-sweep 是较为简单的一种 tracing GC，需要遍历两次对象图，第一次 mark，第二次 sweep。我有一个玩具 Scheme interpreter 里用到了它：overminder/sanya-c · GitHub ，详见 sgc.c （代码里还是有不少噪声的.. 因为 stack 并不完全是一个 root set，需要避开一些位置）

Cheney's semi-space copying GC 是较为简单的一种 moving GC，就是分配 2 块一样大的内存，第一块用完了就开始 GC，将活着的对象移动到第二块上去，死了的就不管了，周而复始。我有一个玩具 Scheme JIT 里用到了它：overminder/sanya-native · GitHub ，详见 gc.cpp。

我还有一个玩具 Scheme compiler 里实现了简单的 generational GC：YAC/scm_generational_gc.c at master · overminder/YAC · GitHub 。只有 2 代，用的是 remembered set。这个确实是比实现过的其他 GC 都复杂，当时也是各种 segfault，用 Valgrind debug 了好久...

——————————
晚上修改了一下，应该叫 precise GC 而不是 exact GC。添加了一个能看的 shared_ptr 的实现。 垃圾回收算法可以分为两类：一种是基于reference counting的引用计数法 一种是基于tracing的，这类展开的有拷贝收集，标记清扫，标记压缩，世代收集以及后来G1里的将整个堆做划分，对每个block做一个remember set进行管理。这些方法具体的展开和优缺点以及相对应的内存分配方法都可以在The Garbage Collection Handbook第二版（2011）里找到。G1得去搜sun公司的论文了。 之前回答过一个类似的问题，可以参考：各种编程语言的实现都采用了哪些垃圾回收算法？这些算法都有哪些优点和缺点？ - 谢之易的回答 引用计数是判断哪些对象需要被回收，而标记复制标记清理还有标记整理是垃圾回收方式。 Mark-and-Sweep Garbage Collection
CSAPP上提到过一点，不过我个人不记得了。。。 引用计数GC处理什么是引用计数

引用计数是一种垃圾回收的形式，每一个对象都会有一个计数来记录有多少指向它的引用。其引用计数会变换如下面的场景

• 当对象增加一个引用，比如赋值给变量，属性或者传入一个方法，引用计数执行加1运算。
• 当对象减少一个引用，比如变量离开作用域，属性被赋值为另一个对象引用，属性所在的对象被回收或者之前传入参数的方法返回，引用计数执行减1操作。
• 当引用计数变为0，代表该对象不被引用，可以标记成垃圾进行回收。

引用遍历GC处理什么是引用对象遍历

垃圾回收器从被称为GC Roots的点开始遍历遍历对象，凡是可以达到的点都会标记为存活，堆中不可到达的对象都会标记成垃圾，然后被清理掉。 GC Roots有哪些

• 类，由系统类加载器加载的类。这些类从不会被卸载，它们可以通过静态属性的方式持有对象的引用。注意，一般情况下由自定义的类加载器加载的类不能成为GC Roots
• 线程，存活的线程
• Java方法栈中的局部变量或者参数
• JNI方法栈中的局部变量或者参数
• JNI全局引用
• 用做同步监控的对象
• 被JVM持有的对象，这些对象由于特殊的目的不被GC回收。这些对象可能是系统的类加载器，一些重要的异常处理类，一些为处理异常预留的对象，以及一些正在执行类加载的自定义的类加载器。但是具体有哪些前面提到的对象依赖于具体的JVM实现。

了解详细可以访问 垃圾回收器如何处理循环引用 GC(Garage Collection)主要有四种吧

1. Reference Counting: 每个对象有个计数器, 记录引用次数, 计数器0的时候被GC.
2. Mark and Sweep: 遍历(能遍历到就说明还有reference存在)每个还能找到对象并标记, 然后GC所有不带标记的对象.
3. Copy Collection: 2的改版, 2在sweep的时候需要扫描heap中所有对象, 对CPU符合大.而CC的方式则是用复制代替标记, 直接把遍历到的对象复制到另一个heap区, 然后之前清空旧heap完成GC.
4. Generational Collection: 也是2的改版,因为3中的复制也很慢. 简单说就是把heap分成四个区域, Eden, Survivor1, Survivor2, Tenured. Eden满了就触发GC操作, 这个GC发生在 Eden, Survivor1,2区. 在GC中存活的Eden区对象移到Survivor1和2区, 而Survivor区的对象在多次GC后还存活, 则移到Tenured区. Tenured 也会有GC发生, 但是频率很低. 一句话说就是: 我查你好几遍没问题的话, 就降低查你的频率.

还有很多奇奇怪怪的GC一般都是在这几种上的改良.
比如现在的JVM一般是
Generational Collection + Parallel Collector + Concurrent Mark and Sweep Collector

我不太喜欢把回答说的太长太详细. 所以他们存在的缺点优点我就不细述了. 引用计数(reference counting)不是回收机制，它和根可达性分析(Root Reachability Analysis)是用来判断对象是否存活的算法。

往后才是垃圾回收算法：

1. 标记清除(Mark-Sweep)
2. 标记压缩(Mark-Compact)
3. 分代收集(Generational Collection)
4. 复制(Copying)

看三本书里的相关章节
1CLR via C#，只介绍了巨硬认为最好的
2深入理解Java虚拟机，JVM高级特性与最佳实践，讲了算法更多变种，演进优化的过程更详细。
3cocos2d-x 权威指南，可以当作是介绍oc，也就是ios开发的垃圾回收，介绍了基于计数的，更方便的用法。

一共也没多少页。