GC算法笔记（二）引用计数法

什么是垃圾？不可能再被任何途径使用的对象。

由此很容易想到采用引用计数的方法：让对象记录下有多少其他对象引用自己。当引用数为0时，对象就被该作为垃圾回收了。

---

引用计数法

引用计数法的基本实现很简单，它不像标记-清除算法那样有明确的 GC 操作，而是在创建对象时和对指针进行更新时同时完成引用计数器的更新。

我们来看一下引用计数法的伪码：

// 创建对象时，将其引用计数赋值为1
new_obj(size) {
    obj = pickup_chunk(size, $free_list)
    if (obj == NULL) {
        allocation_fail()
    } else {
        obj.ref_cnt = 1
        return obj
    }
}

// 将对象赋值给一个指针时，将指针原来引用的对象的引用计数减一
update_ptr(ptr, obj) {
    // 对指针ptr新引用的对象的引用计数器加一（小P: 新墙头～我来了～
    inc_ref_cnt(obj)
    // 对指针ptr之前指向的对象的引用计数器减一（小P: 对不起，你失去本指针了
    dec_ref_cnt(*ptr)
    *ptr = obj
}

计数器增减操作：

// 引用计数器加一操作
inc_ref_cnt(obj) {
    obj.ref_cnt++
}

// 引用计数器减一操作
dec_ref_cnt(obj) {
    obj.ref_cnt--
    // 如果obj的引用数为0，那么它就要被回收了，所有被它引用的对象的引用计数器也要递减
    if (obj.ref_cnt == 0) {
        for (child: obj.children) {
            dec_ref_cnt(child)
        }
        // 回收obj，将obj连接到空闲链表
        reclaim(obj)
    }
}

那么问题来了，为什么在更新指针时要先增后减呢？先减后增不是一样的吗？
还真不一样哦，考虑 *ptr 和 obj 是同一对象时的情况。如果先减后增，而 obj 的引用计数在减一之后为 0 的话，它就直接被回收了，再执行inc_ref_cnt就要出错了。反过来，先增后减的话就可以避免这种情况发生。

通过更新指针，可能会产生没有被其他任何地方引用的“垃圾”，引用计数法会在指针更新时监督是否有垃圾产生，从而在垃圾产生时将其立刻回收。同时这也意味着，在为新对象申请空间时如果没有分块，就没法新分配对象，因为堆中所有的对象都为活动对象。

---

优缺点

优点

• 可即刻回收垃圾 - 当对象的被引用数变为 0 的那一刻，它就明白自己已经是个垃圾了，然后它就会非常自觉地把自己作为空闲空间连接到空闲链表中去。
• 暂停时间短 - 垃圾回收在每次指针变更时都会进行，因此单次垃圾回收量并不大，时间自然更短
• 不用沿指针查找 - 在需要减少沿指针查找的次数时，引用计数法就有优势了。（举个例子，在分布式环境中如果要沿节点之间的指针进行查找，成本就会很高。）

缺点

• 计数器值的更新太频繁 - 通常情况下指针的更新是非常频繁的，而任何指针的变动都会触发计数器的更新。
• 计数器需要占用很多空间 - 每个对象都要为计数器保留空间。而引用计数的最大值必须能涵盖堆中所有对象的引用数。比如一个 32 位的机器，可能就需要 32 位的计数器。假如一个对象自己本身大小才 2 个字长，那么引用计数器就占到该对象总空间的三分之一了。如果类似情况频繁出现，那么内存的实际利用率就相当低了。
• 无法回收循环引用的对象 - 对于循环引用的对象们，它们的引用计数器一定是非零的，针对这种情况，上述的引用计数法拿他们是没辙的。

循环引用举例

先看一段代码：

class Person {
    string name;
    Person lover;
}
Person A = new Person("Alice")
Person B = new Person("Bob")
A.lover = B
B.lover = A
A = null
B = null

在程序执行后，Alice 和 Bob 都不再被其他任何对象引用，按理说应该属于被回收的垃圾了。然而，由于他们彼此相依，互相引用，各自的引用计数器均为 1，所以依照上述引用计数法，他们不会被回收，就此成为一对“私奔”的恋人。

虽然引用计数法的缺点不少，但只要稍加改良，它还是一个非常实用的垃圾回收算法哒。

下面我们就来看看基于最基本的引用计数的思想，又孵化出了哪些改进算法呢？

---

优化

延迟引用计数法

延迟引用计数法 (Deferred Reference Counting) 是由 L.Peter Deutsch 和 Daniel G. Bobrow 1976 年在文章 An Efficient, Incremental, Automatic Garbage Collector 中提出来的。

前面提到引用计数法的一大缺点就是计数器值更新过于频繁，每一次对根引用的更新都要触发所有子节点引用数的更新。延迟引用计数法就是针对这一点进行的优化。
延迟引用计数法的改进基本思路主要是以下两点：

• 局部变量引用（variable reference）不计入引用计数，也就是说那些只被本地变量（操作栈和寄存器中）引用的对象不在延迟引用计数法管理范围内，默认他们随着栈弹出消亡，只有当堆中对象的引用计数发生变化时才进行更新。
• 用哈希表保存对象的引用数。

延迟引用计数法引入了两个表的概念：

• MRT (Multi-Reference Table) - MRT 是一个哈希表，key 为对象 (cell address)，value 为引用数，并且 MRT 中只记录引用数大于等于 2的对象。
• ZCT (Zero Count Table) - ZCT 是一个普通表，它记录的是所有引用数为 0 的对象。

再次强调，这里的提到的引用数都没有包括来自局部变量的引用，所以即使引用数为 0，ZCT 中记录的对象也不一定是垃圾，因此会被暂时保留。

这两张表的值在以下三类事务中进行维护：

• allocate 事务 - 在 ZCT 中增加一条记录，因为此时还没有任何指针引用新建的对象。
• created pointer 事务 - 分三种情况：
  1. 如果被引用的对象在 ZCT 中，那么将它从 ZCT 中移除，因为此时它的引用数为 1 了；
  2. 如果被引用的对象在 MRT 中，那么将它的引用数加一；
  3. 否则被引用的对象原来的引用数为默认值 1，将它加到 MRT 中并设置引用数为 2。
• destroy pointer 事务 - 分三种情况：
  1. 如果指针引用的对象在 MRT 中且引用数为 2，那么将它从 MRT 中移除；
  2. 如果指针引用的对象在 MRT 中且引用数大于 2，那么将其引用数减一；
  3. 如果指针引用的对象不在 MRT 中，那么这个对象原来的引用数为 1，将其记录到 ZCT 中。

根据以上规则，我们可以知道可以被回收的对象就是记录在 ZCT 中且不被任何其他局部变量引用的对象。

「优缺点」
延迟引用计数法最主要的优点就是减轻了引用频繁发生变化导致的计数器增减带来的负担。
其缺点也很显然：

• 垃圾不能马上得到回收，失去了可即刻回收垃圾这一大优点
• 依然没有解决循环引用的问题，要与跟踪垃圾收集器 (tracing garbage collector) 配合使用

---

除了延迟引用计数外，还有两类与采用延迟操作类似思想的优化方案：合并和缓存：

• 合并 - 许多引用计数操作都是临时性的、“不必要”的，通过在程序运行时仅跟踪对象在某一时段开始和结束时的状态，忽略中间过程引起的计数值变更，达到减少引用值频繁修改的目的。
• 缓存 - 将所有引用计数值增减操作缓冲起来以便后续进行处理，同时只有回收线程可以执行引用计数变更操作。缓冲引用计数关注的是何时执行变更，而不是是否执行变更。
  这三种方案的思想是相通的：都是将程序的执行划分为一系列时段 (epoch)，在同一时段内赋值器可以省略部分甚至所有的同步引用计数操作，或将其替换为非同步的写操作。这样，当个时段内的本地引用计数变更就不会暴露到全局了。

---

Sticky 引用计数法

前面有提到引用计数法的缺点之一就是计数器占用的空间太多。如果一个计数器采用 32 位，那么对于一个整体占用空间小的对象来说，计数器占比就太大了。
那如果使用较少位宽呢？比如一个 5 位的计数器，那这样计数器的最大值就只有 31，如果一个对象被引用的次数超过 31，计数器就溢出了。

针对计数器溢出的对象，我们可以有两种处理方法：

1. 什么都不做 - 不再增减计数器的值，什么都不做。不过这样的话，即使这个对象变成了垃圾，也不能将其回收。也就是说，白白浪费了空间。

2. 使用标记-清除算法进行管理 - 不过这个标记-清除算法跟我们之前提到的稍有不同：

   • 一开始把所有对象的计数器值设为 0（这样带来的一个优点是可以处理循环引用，循环引用的对象不会再被外界对象引用到，因此从根引用出发标记完后它们的引用数仍然为 0）
   • 不标记对象，而是对计数器进行增量操作

   • 为了对计数器进行增量操作，对活动对象进行了不止一次的搜索。（这样会导致算法比一般的标记-清除算法处理时间更长，降低了吞吐量）

     我们可以看一下伪码：

     mark_sweep_for_counter_overflow() {
         reset_all_ref_cnt()
         mark_phase()
         sweep_phase()
     }
     
     mark_phase() {
         for (r: roots) {
             mark_stack.push(r)
         }
     
         while (is_empty(mark_stack) == FALSE) {
             obj = mark_stack.pop()
             // 对计数器进行增量操作
             obj.ref_cnt++
             if (obj.ref_cnt == 1) {
                 for (child: obj.children) {
                     mark_stack.push(child)
                 }
             }
         }
     }
     
     sweep_phase () {
         cursor = $heap_start;
         while (cursor < $head_end) {
             if (cursor.ref_cnt == 0) {
                 reclaim(cursor)
             }
             cursor += cursor.size
         }
     }

---

1-bit 引用计数法

1-bit 引用计数法是 Sticky 引用计数法的一个极端例子，即计数器只有 1 位大小。
计数器只有 1 位，那还有什么意义？分分钟溢出给你看。然而，有研究者表明“几乎没有对象是被共有的，所有对象都能马上回收”。如果事实是这样，那么 1 位的计数器，采用 0 表示引用数为 1，用 1 表示引用数大于等于 2，也是能有效率地进行内存管理的。

W.R. Stoye、T.J.W Clark 和 A.C.Norman 在 Some Practical Methods for Rapid Combinator Reduction (published in LISP and Functional Programming 1984)* 提出了 1-bit 引用计数法。（下论文要付费，好贵贵，突然好怀念学生时代，虽然当时也没好好利用学校的资源）

他们三人提出让指针持有计数器。如何实现呢？通过在指针的某一位来标记引用对象的状态：

• 0 表示状态 UNIQUE，即引用数为1
• 1 表示状态 MULTIPLE，即引用数大于等于2

然后通过更新指针进行内存管理，只不过是通过复制指针的方式来更新指针：

copy_ptr(dest_ptr, src_ptr) {
    // 先尝试回收dest_ptr指向的对象
    delete_ptr(dest_ptr)
    // 复制指针
    *dest_ptr = *src_ptr
    // 更新指针的引用数标签
    set_multiple_tag(dest_ptr)
    if (tag(src_ptr) == UNIQUE) {
        set_multiple_tag(str_ptr)
    }
}

delete_ptr(ptr) {
    // 当指针的标签为UNIQUE，即引用数为1时，将对象回收
    if (tag(ptr) == UNIQUE) {
        reclaim(*ptr)
    }
}

「优缺点」
1-bit 引用计数法的优点是不容易出现高速缓存缺失，因为它不需要在更新计数器时读取要引用的对象，因此一定程度上避免了高速缓存缺失。另外就是不需要额外的给计数器留空间，节省了内存空间。
缺点就是要如果有大量计数器溢出的对象，会给堆造成巨大的负担，甚至很难保证分块。

（老实说，这个算法我自己还有点疑问，但是能找到的资料也比较少，看看之后能不能薅到原文的羊毛吧 /_\）

---

炎热的夏天令人心不在焉，导致这篇笔记整理得格外艰难，简直就像挤牙膏，明明内容也不多。(>﹏<)

---

参考资料

• 垃圾回收的算法与实现
• Reference Counting
• L. Peter Deutsch and Daniel G. Bobrow, An Efficient, Incremental, Automatic Garbage Collector, 1976