简介

顾名思义，引用计数法就是通过在对象身上放置一个“计数器”来统计此对象被多少其他对象引用了

在引用计数法中没有明确启动GC的语句，它是通过计数器的增减来进行内存管理的，而在创建对象和更新指针时会修改计数器

分配内存

和标记-清除法相同，引用计数法在创建对象时回去寻找空闲分块，若找不到会直接认为分配失败了（因为在引用计数法中除了空闲链表外的对象都是活动对象）

当找到了合适的分块后会初始化其计数器为1

更新指针

在将一个对象obj赋值给一个指针*ptr前，会先增加新引用对象obj的计数器，然后减少ptr之前引用对象的计数器（这里的顺序不能变，否则在*ptr和obj是同一对象时会导致obj被错误回收了）

指针更新的重点在于减少计数器时的处理

减少计数器后，如果其值为0，就意味着此对象变成了”垃圾“，需要被回收，此时此对象引用的其他对象都会被递归减少计数器，最后会将此对象连接到空闲链表表示它已经被回收了

以上图为例，初始化状态下根引用了A和C，A持有唯一指向B的指针，假设现在将A的指针指向C，那么B就会因为计数器为0被回收至空闲链表中，同时C的计数器也变为了2

优点

可即刻回收垃圾

在引用计数法中，每个对象都始终知道自己的被引用数，只要计数器变为了0就可以马上将其回收，这就使得内存空间中不会被闲置的垃圾占据，垃圾全部都在变成垃圾的那一刻被连接到了空闲链表等待下一次使用

而在其他GC算法中，即使对象变成了垃圾也无法立马被识别，只有当分块用尽后需要GC执行才能知道哪些对象已经变成垃圾了

也就是说在GC执行前始终有一部分内存空间被垃圾占用

最大暂停时间短

引用计数法在回收垃圾时不需要遍历整个堆，只要对象不再被引用了就能马上将其回收，因此不会导致主线程长时间暂停

缺点

计数器的增减处理频繁

大多数情况下指针都会频繁更新，特别是有根的指针，这就导致了对于计数器的增减处理会非常频繁

计数器需要占用很多位

用于引用计数的计数器最大必须能数完整个堆的所有对象，也就是说必须能包含整个内存地址（比如32位机器的计数器就得有32位大小），这就使得对象占据的内存空间会变大

实现麻烦

虽然引用计数的算法本身简单，但实现起来却很麻烦

需要在每个赋值指针的地方*ptr = &obj都将其重写为更新指针的函数update_ptr(ptr,obj)，如果其中出现遗漏的地方就会引起内存泄露的Bug

循环引用无法回收

如果两个对象互相引用对方会导致两个对象都无法被回收掉，这点可以说是引用计数法的致命缺点了

改良

延迟引用计数法

针对计数器的增减处理频繁这个问题，有人提出了“延迟引用计数法”

如前所述，计数器值增减处理频繁的原因之一是从根出发的引用会频繁更新，因此，可以让从根引用的指针的变化不反应在计数器上，而是反应到ZCT(zero count table)上

ZCT是一个表，记录下所有计数器值被减少为0的对象

而在分配对象时，如果没在空闲链表中找到合适分块，就会去ZCT表里搜索一遍以再次分配分块（往ZCT里放对象时如果容量爆满了也会进行一次搜索），如果还不行就认为分配失败了

那么是如何搜索ZCT的呢？

会先把ZCT中所有通过根直接引用的对象的计数器都+1，这样才算把根引用反应到了计数器的值上，接下来会把ZCT中计数器还是0的对象都回收掉，最后将根引用对象的计数器都-1

优点

延迟了根引用的计数，将垃圾一并回收，减少了因根引用频繁发生变化而导致计数器增减带来的额外负担

缺点

为了延迟计数器增减，垃圾不能马上回收，这就失去了引用计数法的一大优点——可即刻回收垃圾，另外因为要搜索ZCT也导致了最大暂停时间延长了

要缩减暂停时间，就要缩小ZCT，但是这样搜索频率就会增加，导致压低了吞吐量

Sticky引用计数法

此方法是用来减少计数器位宽的，假设用于计数器的位数为5位，那么此计数器最多只能数到2的5次方减1，也就是31个引用数，如果被大于31个对象引用就会使得计数器溢出

针对计数器溢出，需要暂停对计数器的管理，对付这种对象主要有两种方法

什么都不做

对于计数器溢出的对象，可以对其什么也不做，但这样一来，即使它成为了垃圾也不能将其回收，也就是说，白白浪费了内存空间

然而事实表明，很多对象一生成马上就死了，也就是说很多对象的计数器值只会在0和1之间变化，很少出现计数器溢出的情况

此外，因为计数器溢出的对象在占有非常重要的地位，可想而知其成为垃圾的可能性也很低，所以放着不管也不会有什么大问题

使用标记-清除法管理

另一个方法是在适当时机使用标记-清除法来充当引用计数法的后援，但和通常的标记-清除法不同

首先，在标记阶段之前，会先把所有对象计数器重置回0

在标记阶段，会把所有从根出发能引用到的对象的计数器+1

在清除阶段，会遍历整个堆，回收计数器为0的对象

这个方法除了能回收计数器溢出的对象，还能处理循环引用，但是因为需要多次查找活动对象，会需要更长的暂停时间

1位引用计数法

这是Sticky引用计数法的一个极端例子

只使用1位来表示对象的被引用数是1个还是多个，因此于其叫它计数器不如叫它“标签”更合适

此外引用计数法一般让对象持有计数器，此方法不同，是让指针持有计数器的

设对象引用数为1时标签位为0，大于1时标签位为1，分别称以上两种状态为Unique和Multiple

复制指针

1位引用计数法也是在更新指针的时候进行内存管理的，不过它不是通过指定要引用的对象来更新指针（*ptr = &obj）,而是通过复制某个指针来更新指针（dest_ptr = src_ptr）

以上图为例，更新了A，使其从引用D变成了引用C，这里也可以看成是把B到C的指针复制给了A

具体步骤，就是：

  1. 先尝试回收A指针原来引用的对象(deletePtr(A))
  2. 将B复制给A(A = B)
  3. 将A设置为Multiple状态（因为这时A指向的对象至少是被A和B同时引用着了）
  4. 如果B是Unique，那么将其改为Multiple

回收对象

只有当指针的标签是Unique时才会进行回收，如果是Multiple就意味着还存在其他引用此对象的指针，无法进行回收

优点

1位引用计数法的优点是不容易出现高速缓存缺失(Cache Miss)

以往的引用计数法将计数器放在对象上，当A要引用在内存中离它很远的对象B时，需要在读取B然后增减B的计数器值，从而导致高速缓存缺失

但对于1位引用计数法来说，完全不需要再更新计数器时读取要引用的对象，只需要操作指针即可

此外因为没必要给计数器留出多余空间，所以节省了内存消耗量，也是此方法的一个优点

缺点

1位引用计数法的缺点和Sticky引用计数法一样，需要考虑如何处理计数器溢出的对象

部分标记-清除法

为了处理引用计数法不能回收循环引用的问题，可以采用只对“可能有循环引用的对象群”进行标记清除的方法，这就是“部分标记-清除法

一般的标记-清除法目的是查找活动对象，而此方法的目标则是查找非活动对象

前提

在部分标记-清除法中，对象会被涂成4种不同的颜色进行管理

  1. 黑：绝对不是垃圾的对象（对象产生时的初始颜色）
  2. 白：绝对是垃圾的对象
  3. 灰：搜索完毕的对象
  4. 阴影：可能是循环垃圾的对象

为了解释算法，我们先假设一个堆，它里面的对象和引用关系如图

计数器减少

接下来，删除由根到对象A的引用

在将计数器-1后，如果对象不是阴影的，那么就将其涂上阴影并放入阴影队列中

阴影队列的存在是为了存放那些可能是循环引用的一部分的对象，此队列内的对象会作为标记-清除法的对象，是的循环引用的垃圾被回收

创建对象

当有分块可以进行分配时，会将对象涂回黑色

若无法分配，会搜索阴影队列寻找分块，然后再次尝试分配

搜索阴影队列

搜索阴影队列时，会在找到阴影对象前一直从队列中取出对象

如果成功找到了阴影对象，会依次对其进行涂抹灰色对象，扫描灰色对象，回收白色对象的操作，最后找出循环引用的垃圾，将其回收

涂抹灰色对象

这个操作会把黑色或者阴影对象涂成灰色，对子对象进行计数器-1并对其进行涂抹灰色对象操作，最终有循环引用的对象计数器都被归0了

把对象涂成灰色是为了防止程序重复搜索

扫描灰色对象

这个操作会搜索灰色对象，把计数器为0的对象涂成白色

对于计数器大于0的对象，会将其涂成黑色，然后对子对象进行计数器+1并将其涂成黑色的操作，最终从那些可能被涂成了灰色的有循环引用的对象群里，找出不是垃圾的对象

不难看出，形成了循环垃圾的对象 A、B、C 被涂成了白色，而有循环引用的非垃圾对象 D、E、F 被涂成了黑色

回收白色对象

这个操作只会查找白色对象进行回收，循环垃圾此时也会被回收掉了

限定搜索对象

部分标记-清除法的优点，就是把要搜索的对象限定在阴影对象及其子对象，也就是可能产生循环垃圾的对象群中，那么要怎么发行这样的对象群呢？

问题的关键在于循环垃圾产生的过程

如上图，满足下面2种情况时就会产生循环垃圾

  1. 产生循环引用
  2. 删除从外部到循环引用的引用

注意在上图第2步时，A的计数器从2变成了1

这意味着如果对象的计数器值在减少后不为0，就说明它可能是循环引用的一份子，这时会先将其放入阴影队列，方便之后搜索它

局限性

部分标记-清除法从队列搜索对象付出的成本很大，因为队列里存放的都是候选垃圾，所以要搜索的对象绝对不在少数

而且总计需要查找3次对象，也就是说需要对从队列里取出的阴影对象分别进行涂抹灰色、扫描灰色和回收白色的操作，这大大增加了内存管理花费的时间

此外还失去了引用计数法暂停时间短的优点