引用计数
GC 原本是一种“释放怎么都无法被引用的对象的机制”。那么人们自然而然地就会 想到,可以让所有对象事先记录下“有多少程序引用自己”。让各对象知道自己的“人气指 数”,从而让没有人气的对象自己消失,这就是引用计数法(Reference Counting),它是 George E. Collins 于 1960 年钻研出来的[1]。
引用计数是 GC 算法中最简单也最容易实现的一种,它和标记清除方式差不多是在同一时间发明出来的,第一个 JS 版本大概是 90 年代初的事情。
基本原理
引用计数法中引入了一个概念,那就是“计数器”。计数器表示的是对象的人气指数, 也就是有多少程序引用了这个对象(被引用数)。
图1 引用计数法中的对象
当引用发生增减时对计数进行更新。引用计数的增减,一般发生在变量赋值、对象内容更新、函数结束(局部变量不再被引用)等时间点。当一个对象的引用计数变为 0 时,则说明它将来不会再被引用,因此可以释放相应的内存空间。
结合图片来看一下 update_ptr()
[2] 函数执行时的情况。请看图 2(a)。初始状态下从 根引用 A 和 C,从 A 引用 B。A 持有唯一指向 B 的指针,假设现在将该指针更新到了 C,请看图 2(b)。
图2 update_ptr() 函数执行时的情况
通过以上的更新,B 的计数器值变成了 0,因此 B 被回收了。且 B 连接上了空闲链表, 能够再被利用了。又因为新形成了由 A 指向 C 的指针,所以 C 的计数器的值增量为 2。
优点
可立即回收,效率最高
在引用计数法中,每个对象始终都知道自己的被引用数(就是计数器的值)。当被引用数的值为 0 时,对象马上就会把自己作为空闲空间连接到空闲链表。也就是说,各个对象在变成垃圾的同时就会立刻被回收。要说这有什么意义,那就是内存空间不会被垃圾占领。垃圾全部都已连接到空闲链表,能作为分块再被利用。
另一方面,在其他的 GC 算法中,即使对象变成了垃圾,程序也无法立刻判别。只有当分块用尽后 GC 开始执行时,才能知道哪个对象是垃圾,哪个对象不是垃圾。也就是说,直到 GC 执行之前,都会有一部分内存空间被垃圾占用。
没有必要沿指针查找
最大暂停时间短
缺点
循环引用无法回收
图3 循环引用对象
像上述这样,因为两个对象互相引用,所以各对象的计数器的值都是 1。但是这些对象 组并没有被其他任何对象引用。因此想一并回收这两个对象都不行,只要它们的计数器值都 是 1,就无法回收。像这样在两个及两个以上的对象互相循环引用形成对象组的情况下,即 使这些对象组都成了垃圾,程序也无法将它们回收,有可能造成内存泄漏。
引用计数的策略是跟踪记录每个值被使用的次数,当声明了一个 变量并将一个引用类型赋值给该变量的时候这个值的引用次数就加 1,如果该变量的值变成了另外一个,则这个值得引用次数减 1,当这个值的引用次数变为 0 的时 候,说明没有变量在使用,这个值没法被访问了,因此可以将其占用的空间回收,这样垃圾回收器会在运行的时候清理掉引用次数为 0 的值占用的空间。
计数器需要占用很多位
用于引用计数的计数器最大必须能数完堆中所有对象的引用数。打个比方,假如我们用的是 32 位机器,那么就有可能要让 2 的 32 次方个对象同时引用一个对象。考虑到这种情况, 就有必要确保各对象的计数器有 32 位大小。也就是说,对于所有对象,必须留有 32 位的空间。这就害得内存空间的使用效率大大降低了。打比方说,假如对象只有 2 个域,那么其计数器就占了它整体的 1/3。
实现烦琐复杂
引用计数的算法本身很简单,但事实上实现起来却不容易。
改良
尽管引用计数法有很多缺点,但引用计数法并不是一个“完全没法用”的算法。事实上,很多处理系统和应用都 在使用引用计数法,那是因为引用计数法只要稍加改良,就会变得非常具有实用性了。