推荐！可视化垃圾回收算法

　　英文原文： http://spin.atomicobject.com/2014/09/03/visualizing-garbage-collection-algorithms/

　　大部分开发者都认为自动垃圾回收器是理所当然的。实际上，这只是语言运行时提供的一项实用功能，旨在简化我们的开发工作。

　　但是如果尝试着了解垃圾回收器的内部原理，你会发现很难弄明白。除非熟悉它的工作流程和错误处理方式，否则内部成千上万的实现细节会让你不知所措。

　　我编译了一个有五种不同的垃圾回收算法工具。程序运行时会创建一个动画界面。你可以从 github.com/kenfox/gc-viz上获取动画和代码来实现。非常让我惊讶的是，这个简单的动画显现出这些重要的算法。

　　任务完成后清理: aka No GC

　　清理垃圾最简单可行的方法就是等一项任务完成之后，一次性处理所有的垃圾。这项技术非常有用，特别是如果能将一项任务分解成许多小任务。例如，Apache网络服务器在每次请求时创建一个小内存池并在请求完成后将创建的整个内存池完全释放。

　　上图的动画显示了一个正在运行的程序。整张图片代表程序的内存区。内存区在开始时是黑色，黑色表明内存尚未被使用。闪着鲜绿色和黄色的区域表明该内存区域正在读写。颜色随着时间变化，你可以观察内存的使用情况，也可以看到当前的活动情况。如果仔细观察，你会发现内存区域中开始出现一些程序执行过程中会忽略的区域。这些区域就成了所谓的垃圾——程序不能访问和使用。垃圾区域之外的的内存区域是可用的。

　　该程序的内存充足，所以不必担心程序运行时垃圾的清理。在后面的例子中我将一直使用这个简单的程序。

　　引用计数回收器

　　另一个简单的解决方案是对你使用的资源(此处指内存中的对象)进行计数，当计数值变为0时，对其进行处理。这是一项广泛使用的技术，当开发者将垃圾回收添加到现有系统中时——这是唯一一个容易与其他资源管理器和现有代码库集成的垃圾回收器。苹果在为Objective-C发布了标志-擦除垃圾回收器后明白这个事实。发布产品出现很多问题以致于他们不得不废弃该项特性，取而代之的是性能良好的自动引用计数回收器。

　　上面的动画显示了相同的程序，但是此时它将通过对内存中每一对象引用计数来处理垃圾。红色闪烁表示引用计数行为。引用计数的优势在于垃圾会被很快检测到——你可以看到红色闪烁过后紧接着该区域变黑。

　　遗憾的是引用计数存在诸多问题。最糟糕的是，它不能处理循环结构。而循环结构非常常见——继承或反向引用都将建立一个循环，该结构将造成内存泄露。引用计数的开销也很大 ——从动画中可以看到即使当内存使用不在增长时，红色闪烁一直持续。CPU运算速度很快，但内存读写很慢，而计数器不断被加载并保存至内存。所有这些计数器的更新很难保证数据的只读或线程安全。

　　引用计数是一种分摊算法（开销遍布整个程序运行时），但这是种分摊算法具有偶然性，不能保证反应时间。例如，程序中存在一个很大的树型结构。最后一段使用树的程序将触发对整个树的处理，墨菲说过事情如果有变坏的可能，不管这种可能性有多小，它总会发生。这里没有其他的分摊算法,所以分摊的偶然特征可能取决于数据。（所有这些算法有并发或部分并发的命令,但这些都是超出了程序可演示的范围。）

　　标记-擦除回收器

　　标记-擦除消除了引用计数存在的一些问题。它能够轻松解决循环结构在引用技术中存在的问题，由于不需维持计数，系统开销比较低。

　　该算法舍弃垃圾检测的实时性。动画中，有一段运行时间没有任何红色的闪烁，然后突然出现许多红色闪烁表明当前正在标记活动对象。在标记完成后，程序要遍历整个内存空间并处理垃圾。在动画中你还将注意到—— 许多区域立刻变黑而不像引用计数方式那样随着时间慢慢变黑。

　　标记-擦除比引用计数要求更高的一致性实现，而且很难移植到现有系统中。在标记阶段需要遍历所有活动数据，甚至是封装在对像中的数据。如果一个对象不支持遍历，那么尝试将标记-擦除移植到代码中风险太大。标记-擦除的另一个不足之处在于擦除阶段必须遍历整个内存来查找垃圾。对于一个产生垃圾较少的系统，这不是问题，但现在的函数式编程风格产生了大量的垃圾。

　　标记-压缩回收器

　　在前面的动画中你可能注意到一点，对象从不移动。一旦对象在内存中分配，该对象的存储位置就不会再改变，即使被散步在黑色区域的内存碎片包围。下面两种算法用完全不同的方式改变了这种现象。

　　标记-压缩算法不是仅通过标记内存区域是否空闲来处理内存，而是通过将对象移动到空闲表来实现。对象通常按照内存顺序存储,先分配的对象在内存的低地址空间——但是处理对象造成的空缺将随着对象的移动变大。

　　移动对象意味着新对象只能在已使用内存的末尾创建。这就是所谓的“bunp”分配器，和栈分配器一样，但不限制栈空间。有些使用bump分配器的系统甚至不用调用栈存储数据，他们只在堆中分配调用帧,像其他对象一样对待。

　　有时理论高于实践，另一个优势是当对象被压缩后，程序能够像访问硬件高速缓存一样访问内存。不确定你能否看到这个好处——尽管引用计数和标记-擦除使用的内存分配器很复杂,但调试效果很好，效率也很高。

　　标记-压缩是算法很复杂，需要多次遍历所有分配对象。在动画中可以看到紧随红色闪烁的活动对象其后的是大量读和写标记为目的地计算，对象被移动，最终引用固定指向移动后的对象。这个复杂程序背后最大的优点是内存开销非常小。Oracle的Hotspot JVM使用了多种不同垃圾回收算法。而全局对象空间使用标记-压缩回收算法。

　　拷贝回收器

　　最后使用动画显示的算法是大多数高性能垃圾收集系统的基础。它和标记-压缩是一样的移动回收器，但是相比之下实现却非常简单。它使用两块内存空间，在两个内存间交替复制活动对象。实际上，空间不止两块，这些空间用于不同代对象，新的对象在一个空间中创建，如果生命周期没有结束就会被复制到另一个空间，如果长期存在就会被复制到一个永久性空间。如果你听说一个垃圾收集器是分代的或短暂的,通常是多空间拷贝回收器。

　　除了简单性和灵活性，该算法的主要优势在于只要在活动对象上花时间。没有独立的标记阶段必须被擦除或压缩。在遍历活动对象期间，对象会被立即复制，弥补了以往对象在引用计数时的不足。

　　在动画中，你可以看到回收过程中乎所有的数据从一个空间复制到另一个空间。对该算法来说是个糟糕的情况，这是人们谈论优化垃圾收集器的一个原因。如果你能调整内存并有优化分配，使得在回收开始前大部分对象都废弃了，那么你就能兼顾安全函数式编程风格和高性能。