认识达内从这里开始

我们在进行软件开发编程的过程中，一般会针对软件运行中产生的冗余数据进行清除处理，而这种功能就需要添加一些垃圾回收算法。所以，我们今天就一起来了解一下，这些垃圾回收算法都有哪些特点和作用。

垃圾回收算法的性能点

为什么会存在那么多的垃圾回收算法呢?我想这个问题的答案可能是没有任何一种内存回收算法是完美的，所以在针对不同的情景需求下，不同的内存回收算法有其独特的优势，所以最后就延续了多种回收算法。那么，在平时的大多数情况下，有哪些性能考虑点是我们关注的呢，下面就列举一下常见的性能指标

吞吐量：回收固定内存需要的时间

最大暂停时间：回收过程中需要暂停代码执行的时间

内存使用效率：真正用于逻辑的内存占总内存的比例

访问的局部性：与计算机各项缓存的友好程度

虽然这不是所有的关注指标，但是这些却是大部分情况下被关注的指标。而且，需要注意的是，这里面有一些指标是互斥的，例如我们会发现，最大吞吐量和最大暂停时间往往无法得到双赢，也就是说无法同时满足这两项的最优。所以，在选择具体的回收算法的时候，其实就是在这些指标之间进行权衡，然后根据自己的需求进行选择。下面就对常见的三种基本回收算法进行介绍。

基本GC算法

1.标记-清除

标记-清除算法是一个比较经典的算法了，在标记-清除算法中，一般都是有所谓的根对象，而且一般来说根对象都不止一个，有很多，以C语言来理解的话，我们可以理解成分配在栈中的对象和全局对象都是所谓的根对象。标记-清除算法从这些所谓的根对象出发，进行第一个阶段——标记阶段，也就是将这些根对象能够引用到的那些对象都作上标记，一般的做法是每个对象都有一个字段用于标识是否被标记，当然还有很多其他的做法，例如专门弄一张表来表示对象的标记等，这些都是后话啦，反正这个阶段就只做一件事情，那就是找出被使用的对象，作上标记，这样没有被标记的对象也就是不用的对象了。

在第一阶段标记完之后，那么进入标记-清除的第二个阶段——清除阶段，清除阶段其实也就是所谓的释放阶段，无非就是把不使用的对象所占用的内存释放掉，然后回收起来这么简单。

看上去标记-清除算法还是比较简单的，但是，这个简单背后也是有很多需要思考的问题：

对象的内存分配和对象的内存回收策略

从根对象开始标记对象的方式

这是两个比较常见的问题。第一个问题，对象的内存分配问题，假设现在我们的语言需要创建一个对象，那么自然需要分配一块内存给它，怎么分配这个内存呢?一个可能的做法就是从上次分配的位置往后直接分配一块，这样保证每次分配的内存都是往高位走，内存地址逐渐叠加。但是，这种方法带来了一个问题，那就是释放的时候就很尴尬了：

假设这里有一段内存，按照刚才的策略分配了A、B和C三个对象，当程序运行一段时间之后，我们想回收掉对象B，然后回收之后发现现在的内存是这样的：

这个时候，我们想再分配一个对象D，那么不巧，D的大小就比B大那么一点，所以原来B的位置不足以容纳D，所以也就不能使用B原来的位置，那么这样的话，内存结构可能就成了这样：

长此以往，我们会发现内存就会有一个一个的洞，碎片化会很严重，导致内存的利用率逐渐下降。同时，因为这里的内存是一块一块的，所以我们用链表来保存它的时候，分配内存查找又是一个问题，所以就很麻烦。

此外，周期性得标记对象，从而会周期性得改变对象的微小数据，所以导致操作系统COW体系不能得到较好的运用，从而导致性能的缺失。这是一方面，前面还有一个问题，那就是我们标记对象的时候以怎么样的顺序来查找活动对象，常见的查找方式有深度优先查找和广度优先查找，这两种查找在性能上可能没有太大区别，但是，对于临时空间的占用却是有较大的影响，所以一般来说，深度优先比广度优先更能压低内存使用量，所以经常使用的是深度优先搜索。

虽然有缺点，但是标记-清除的优点也是比较明显的，例如实现起来还是比较简单的，与保守式GC是兼容的，使得标记-清除算法在实际应用中还是得到大家的青睐的。

2.引用计数

除了标记-清除算法外，引用计数也是一种不错的方法，引用计数算法顾名思义就是在对象中额外记录自身被引用的次数，当次数减小到0的时候那么就知道自己已经没有用处了，可以被回收了。也是一种很简单很直观的方式，可以在对象不被使用的时候立刻回收掉内存，从而将垃圾回收的时间分散化，也不需要像标记-清除一样需要进行遍历查找。

但是这也带来了一定程度的麻烦，例如，我们需要使用内存屏障管理引用计数，对象的生成、赋值和引用都涉及引用计数的变化，从而导致引用计数的增减处理频繁;同时，因为引用计数的存在，我们还需要在对象的自身数据之外，为引用计数分配固定的空间来存放计数，这是固有损耗。还有一个致命的缺点就是，使用引用计数算法，无法清除循环引用的问题，从而导致内存一直占用，无法释放。

3.GC复制

前面介绍的两种方法都是在对象本身上操作的，也就是说清除和释放都是操作对象本身所在的位置，但是，GC复制算法就稍微复杂一些了，GC复制算法最原始的做法就是将内存一分为二，每次只使用其他一半，当要GC的时候就将使用着的一半中的活动对象复制到另外一半中，然后清理掉这一半中的所有对象，直接使用另外一半即可，重复这个操作。

这个我们一眼就可以看出问题，那就是空间的利用率不高，但是，好处也是非常明显的，首先是速度快，没有额外的标记-清理操作，就是直接的复制，高吞吐;分配对象直接分配，不需要考虑碎片化问题;还可以保持与OS的缓存兼容，优势还是比较明显的。然而，硬币总有正反面，除了空间利用率不高之外，这种方法不兼容保守式的GC算法，此外，对于递归调用还会有栈溢出的风险。

所以为了更好得完善了这个算法，还有有很多改进思路被提出的，例如不是将空间划分为两部分，而是划分为多个部分，从而提升空间的利用率就是其中的一个思路。

总结

本文就常见的三种垃圾回收基本算法以及经常需要考虑的几个性能指标进行介绍，从而为了解垃圾回收开一个头。其实看各种编程语言的GC实现都会发现本文中基本算法的身影，无非就是它们直接如何组合，所以，理解本文中的基本算法对于理解其他编程语言的GC实现还是很有帮助的。

作者：行者酱油君

来源：博客园

【免责声明】：本内容转载于网络，转载目的在于传递最新信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。