读书笔记

垃圾回收的算法与实现(2)

引用计数算法

分配

新分配的对象 ref 为1

1
2
3
4
def newObj(size):
    obj = malloc(size)
    obj.ref = 1
    return obj

使用

1
2
def assign(obj):
    obj.ref ++

回收

1
2
3
4
def free(obj):
    obj.ref --
    if obj.ref == 0:
        freeObj(obj)

评价

  • 垃圾回收快。
  • 最大暂停时间短。
  • 引用计数增减有一定消耗，占用一定的大小。
  • 循环引用无法释放。

优化

  1. 延迟引用计数法

    说白了，就是分配释放的时候，使用数据结构来保存下来，之后一并回收。

  2. Sticky引用计数

    1. 固定的计数位长度。
    2. 如果计数超过了最大，则该对象的引用计数不再改变。
    3. 用标记-清除算法管理对象。
      • 将所有对象的ref清零。
      • 扫描所有对象，增加ref。
      • 清除ref为0的数据。

  3. 1位引用计数法

    计数位为1的Sticky引用计数法。
    0 代表引用数为1，1 代表引用数多于1。

  4. 部分标记-清除算法

    用两位bit位来标记存在的状态，可以不用扫全部的对象

部分标记-清除算法

标记位

2位标记位
1. black（绝对不是垃圾的对象） 
2. white（绝对是垃圾的对象）
3. gray（搜索完毕的对象）
4. hatch（可能是循环垃圾的对象）

回收

曾经没减引用的对象，都被认为是可能为循环对象，染色为灰色。

1
2
3
4
5
6
def free(obj):
    if obj.ref == 0:
        delete(obj)
    elif obj.color != HATCH:
        obj.color = HATCH
        hatch_queue.push(obj)

分配

所有分配的对象，标记为都为黑色
不足以分配的时候，会尝试回收内存

1
2
3
4
5
6
7
8
9
10
def new_obj(size):
    obj = pickup_chunk(size)
    if obj is NULL:
        obj.color = BLACK
        obj.ref = 1
        return obj
    if not hatch_queue.empty():
        scan_hatch_queue()
        return new_obj(size)
    return NULL

遍历灰色的对象，尝试开始收集对象。

1
2
3
4
5
6
7
8
def scan_hatch_queue():
    obj = hatch.pop()
    if obj.color == HATCH:
        paint_gray(obj)
        scan_gray(obj)
        collect_white(obj)
    elif not hatch_queue.empty():
        scan_hatch_queue()

将对象自身所引用的对象的引用计数-1，循环所有子对象，如果有循环引用，则该对象的引用计数将会被减为1.

1
2
3
4
5
6
def paint_pray(obj):
    if obj.color in [BLACK, HATCH]:
        obj.color = GRAY
        for child in obj.childs:
            child.ref --
            paint_gray(child)

遍历对象，将引用计数不为0的，即非循环引用的对象还原为黑色，否则，设置为白色

1
2
3
4
5
6
7
8
def scan_gray(obj):
    if obj.color == GRAY:
        if obj.ref > 0:
            print_black(obj)
        else:
            obj.color = WHITE
            for child in obj.childs:
                scan_gray(child)

还原为黑色的过程中，增加对引用对象的计数

1
2
3
4
5
6
def paint_black(obj):
    obj.color = BLACK
    for child in obj.childs:
        child.ref ++
        if child.color != BLACK:
            paint_black(child)

将白色对象进行回收，并回收其子对象

1
2
3
4
5
6
def collect_white(obj):
    if obj.color == WHITE:
        obj.color = BLACK
        for child in obj.childs:
            collect_white(child)
    delete(obj)