垃圾回收
# Garbage Collection
- 程序吞吐量：回收算法会在多大程度上拖慢程序？有时候，这个是通过回收占用的 CPU 时间与其它 CPU 时间的百分比来描述的。
- GC 吞吐量：在给定的 CPU 时间内，回收器可以回收多少垃圾？ 堆内存开销：回收器最少需要多少额外的内存开销？如果回收器在回收垃圾时需要分配临时的内存，对于程序的内存使用是否会有严重影响？
- 停顿时间：回收器会造成多长时间的停顿？
- 停顿频率：回收器造成的停顿频率是怎样的？
- 停顿分布：停顿有时候很短暂，有时候很长？还是选择长一点但保持一致的停顿时间？
- 分配性能：新内存的分配是快、慢还是无法预测？
- 压缩：当堆内存里还有小块碎片化的内存可用时，回收器是否仍然抛出内存不足(OOM)的错误？如果不是，那么你是否发现程序越来越慢，并最终死掉，尽管仍然还有足够的内存可用？
- 并发：回收器是如何利用多核机器的？
- 伸缩：当堆内存变大时，回收器该如何工作？
- 调优：回收器的默认使用或在进行调优时，它的配置有多复杂？
- 预热时间：回收算法是否会根据已发生的行为进行自我调节？如果是，需要多长时间？
- 页释放：回收算法会把未使用的内存释放回给操作系统吗？如果会，会在什么时候发生？
- 可移植性：回收器是否能够在提供了较弱内存一致性保证的 CPU 架构上运行？
- 兼容性：回收器可以跟哪些编程语言和编译器一起工作？它可以跟那些并非为 GC 设计的编程语言一起工作吗，比如 C++？它要求对编译器作出改动吗？如果是，那么是否意味着改变 GC 算法就需要对程序和依赖项进行重新编译？
# Reference Counting Collector:引用计数
Mark Sweep:标记清除
第一批垃圾回收算法是为单核机器和小内存程序而设计的。那个时候，CPU 和内存价格昂贵，而且用户没有太多的要求，即使有明显的停顿也没有关系。这个时期的算法设计更注重最小化回收器对 CPU 和堆内存的开销。也就是说，除非内存不足，否则 GC 什么事也不做。而当内存不足时，程序会被暂停，堆空间会被标记并清除，部分内存会被尽快释放出来。这类回收器很古老，不过它们也有一些优势——它们很简单，而且在空闲时不会拖慢你的程序，也不会造成额外的内存开销。像 Boehm GC 这种守旧的回收器，它甚至不要求你对编译器和编程语言做任何改动！这种回收器很适合用在桌面应用里，因为桌面应用的堆内存一般不会很大。比如虚幻游戏引擎，它会在内存里存放数据文件，但不会被扫描到。标记并清除算法存在的最大问题是它的伸缩性很差。在增加 CPU 核数并加大堆空间之后，这种算法几乎无法工作。不过有时候你的堆空间不会很大，而且停顿时间可以接受。那么在这种情况下，你或许可以继续使用这种算法，毕竟它不会造成额外的开销。反过来说，或许你的一台机器就有数百 G 的堆空间和几十核的 CPU，这些服务器可能被用来处理金融市场的交易，或者运行搜索引擎，停顿时间对于你来说很敏感。在这种情况下，你或许希望使用一种能够在后台进行垃圾回收，并带来更短停顿时间的算法，尽管它会拖慢你的程序。不过事情并不会像看上去的那么简单！在这种配置高端的服务器上可能运行着大批量的作业，因为它们是非交互性的，所以停顿时间对于你来说无关紧要，你只关心它们总的运行时间。在这种情况下，你最好使用一种可以最大化吞吐量的算法，尽量提高有效工作时间和回收时间之间的比率。问题是，根本不存在十全十美的算法。没有任何一个语言运行时能够知道你的程序到底是一个批处理作业系统还是一个对延迟敏感的交互型应用。这也就是为什么会存在“GC 调优”——并不是我们的运行时工程师无所作为。这也反映了我们在计算机科学领域的能力是有限的。
Generational Garbage Collection:分代垃圾回收
从 1984 年以来，人们就已知道大部分的内存对象“朝生夕灭”，它们在分配到内存不久之后就被作为垃圾回收。这就是分代理论假说的基础，它是整个软件产品线领域最贴合实际的发现。数十年来，在软件行业，这个现象在各种编程语言上表现出惊人的一致性，不管是函数式编程语言、命令式编程语言、没有值类型的编程语言，还是有值类型的编程语言。
这个现象的发现是很有意义的，我们可以基于这个现象改进 GC 算法的设计。新的分代回收器比旧的标记并清除回收器有很多改进：
- GC 吞吐量：它们可以更快地回收更多的垃圾。
- 分配内存的性能：分配新内存时不再需要从堆里搜索可用空间，因此内存分配变得很自由。
- 程序的吞吐量：分配的内存空间几乎相互邻接，对缓存的利用有显著的改进。分代回收器要求程序在运行时要做一些额外的工作，不过这点开销完全可以被缓存的改进所带来的好处抵消掉。
- 停顿时间：大多数时候(不是所有)停顿时间变得更短。
不过分代回收器也引入了一些缺点：
- 兼容性：分代回收器需要在内存里移动对象，在某些情况下，当程序对指针进行写入时还需要做一些额外的工作。也就是说，GC 必须跟编译器紧紧地绑定在一起，这也就是为什么 C++里没有分代回收器。
- 堆内存开销：分代回收器通过在内存空间里移动对象实现垃圾回收。这个要求有额外的空间用来拷贝对象，所以这些回收器会带来一些堆内存开销。另外，它们需要维护指针映射表，从而带来更大的开销。
- 停顿时间分布：尽管大部分 GC 停顿时间都很短，不过有一些仍然要求在整个堆内进行彻底的标记并清除操作。
- 调优：分代回收器引入了“年轻代”，或者叫“eden 空间”，程序性能对这块区域的大小非常敏感。
- 预热时间：为了解决上述的调优问题，有一些回收器根据程序的运行情况来决定年轻代的大小，而如果是这样的话，那么 GC 的停顿时间就取决于程序的运行时间长短。在实际当中，只要不是作为基准，这个算不上什么大问题。
因为分代算法的优点，现代垃圾回收器基本上都是基于分代算法。如果你能承受得起，就会想用它们，而一般来说你很可能会这样。分代回收器可以加入其它各种特性，一个现代回收器将会集并发、并行、压缩和分代于一身。
现代计算机使用的默认算法是吞吐量回收算法。这种算法是为批处理作业而设计的，默认情况下不对停顿时间做任何限制(不过可以通过命令行指定)。跟这种默认行为相比较，人们会觉得 Java 的 GC 简直有点糟糕了：默认情况下，Java 试图让你的程序运行尽可能的快，使用尽可能少的内存，但停顿时间却很长。
如果你很在意停顿时间，或许可以使用并发标记并清除回收器(CMS)。这种回收器跟 Go 的回收器最为接近。不过 CMS 也是分代回收器，所以它的停顿时间仍然会比 Go 的要长一些：在年轻代被压缩时，程序会被暂停，因为回收器需要移动对象。CMS 里有两种停顿，第一种是快速的停顿，可能会持续 2 到 5 毫秒，第二种可能会超过 20 毫秒。CMS 是自适应的，因为它的并发性，它需要预测何时需要启动垃圾回收(类似 Go)。你需要对 Go 的堆内存开销进行配置，而 CMS 会在运行时自适应调整，避免发生并发模式故障。不过 CMS 仍然使用标记并清除策略，堆内存仍然会出现碎片化，所以还是会出现问题，程序还是会被拖慢。
最新的 Java 回收器叫作“G1”(Garbage First)。在 Java 8 和 Java 9 里，它都是默认的回收器。它是一种“一刀切”的回收算法，它会尽量满足我们的各种需求。它几乎集并发、分代和堆空间压缩于一身。它在很大程度上可以自我调节，不过因为它无法知道你的真正需求(这个跟其它所有的回收器一样)，所以你仍然可以对它做出折衷：告诉它可用的最大内存和预期的停顿时间(以毫秒为单位)，它会通过自我调节来达到预期的停顿时间。
默认的预期停顿时间是 100 毫秒，只有指定了更低的预期停顿时间才能看到更好的效果：G1 会优先考虑程序的运行速度，而不是停顿时间。不过停顿时间并非一直保持一致，大部分情况下都非常短(少于 1 毫秒)，在压缩堆空间时停顿会长一些(超过 50 毫秒)。G1 具有良好的伸缩性，有人在 TB 级别的堆上使用过 G1。G1 还有一些很有意思的特性，比如堆内字符串去重。
Java:Concurrent Mark Sweep
Go:Tri-Color Incremental GC
Go 的新回收器是一种并发的、三基色的、标记清除回收器，它的设计想法是由 Dijkstra 在 1978 年提出的。它有别于现今大多数“企业”级垃圾回收器，而且我们相信它跟现代硬件的属性和现代软件的低延迟需求非常匹配。
什么是存活引用
所谓“GC roots”，或者说 tracing GC 的“根集合”，就是一组必须活跃的引用。例如说，这些引用可能包括：所有 Java 线程当前活跃的栈帧里指向 GC 堆里的对象的引用；换句话说，当前所有正在被调用的方法的引用类型的参数/局部变量/临时值。VM 的一些静态数据结构里指向 GC 堆里的对象的引用，例如说 HotSpot VM 里的 Universe 里有很多这样的引用。JNI handles，包括 global handles 和 local handles（看情况）所有当前被加载的 Java 类（看情况）Java 类的引用类型静态变量（看情况）Java 类的运行时常量池里的引用类型常量（String 或 Class 类型）（看情况）String 常量池（StringTable）里的引用注意，是一组必须活跃的引用，不是对象。
Tracing GC 的根本思路就是：给定一个集合的引用作为根出发，通过引用关系遍历对象图，能被遍历到的（可到达的）对象就被判定为存活，其余对象（也就是没有被遍历到的）就自然被判定为死亡。注意再注意：tracing GC 的本质是通过找出所有活对象来把其余空间认定为“无用”，而不是找出所有死掉的对象并回收它们占用的空间。GC roots 这组引用是 tracing GC 的起点。要实现语义正确的 tracing GC，就必须要能完整枚举出所有的 GC roots，否则就可能会漏扫描应该存活的对象，导致 GC 错误回收了这些被漏扫的活对象。这就像任何递归定义的关系一样，如果只定义了递推项而不定义初始项的话，关系就无法成立——无从开始；而如果初始项定义漏了内容的话，递推出去也会漏内容。那么分代式 GC 对 GC roots 的定义有什么影响呢？答案是：分代式 GC 是一种部分收集（partial collection）的做法。在执行部分收集时，从 GC 堆的非收集部分指向收集部分的引用，也必须作为 GC roots 的一部分。
具体到分两代的分代式 GC 来说，如果第 0 代叫做 young gen，第 1 代叫做 old gen，那么如果有 minor GC / young GC 只收集 young gen 里的垃圾，则 young gen 属于“收集部分”，而 old gen 属于“非收集部分”，那么从 old gen 指向 young gen 的引用就必须作为 minor GC / young GC 的 GC roots 的一部分。继续具体到 HotSpot VM 里的分两代式 GC 来说，除了 old gen 到 young gen 的引用之外，有些带有弱引用语义的结构，例如说记录所有当前被加载的类的 SystemDictionary、记录字符串常量引用的 StringTable 等，在 young GC 时必须要作为 strong GC roots，而在收集整堆的 full GC 时则不会被看作 strong GC roots。
为什么需要分代？
对传统的、基本的 GC 实现来说，由于它们在 GC 的整个工作过程中都要“stop-the-world”，如果能想办法缩短 GC 一次工作的时间长度就是件重要的事情。如果说收集整个 GC 堆耗时太长，那不如只收集其中的一部分？于是就有好几种不同的划分（partition）GC 堆的方式来实现部分收集，而分代式 GC 就是这其中的一个思路。这个思路所基于的基本假设大家都很熟悉了：weak generational hypothesis——大部分对象的生命期很短（die young），而没有 die young 的对象则很可能会存活很长时间（live long）。这是对过往的很多应用行为分析之后得出的一个假设。基于这个假设，如果让新创建的对象都在 young gen 里创建，然后频繁收集 young gen，则大部分垃圾都能在 young GC 中被收集掉。由于 young gen 的大小配置通常只占整个 GC 堆的较小部分，而且较高的对象死亡率（或者说较低的对象存活率）让它非常适合使用 copying 算法来收集，这样就不但能降低单次 GC 的时间长度，还可以提高 GC 的工作效率。