Cheney算法

Cheney算法，最初由C.J. Cheney在1970年ACM论文中描述，它是计算机软件系统中追踪垃圾回收的一种“停止并复制”方法^[1]。在这种方案中，堆被划分成相等的两半，在任何时刻都只有其中一个在使用中。进行垃圾回收的方式为，通过将存活对象从一个半空间（semispace）即“自”空间（from-space），复制到另一个半空间即“至”空间（to-space），它接着成为新堆，而整个旧堆一次性丢弃。

简介

Cheney算法收回如下项目：

在栈上的对象引用。检查在栈上的对象引用，对指向在“自”空间中对象的每个对象引用，选用下列两个动作之一：
- 如果这个对象仍未移动到“至”空间，则通过在“至”空间中创建完全相同的复件来移动它，并将这个“自”空间版本，替换为到“至”空间版本的转发指针（forwarding pointer）。接着更新对象引用，来提及在“至”空间中的新版本。
- 如果这个对象已经被移动到“至”空间，则简单的从“自”空间中的转发指针更新这个引用。
在“至”空间中的对象。垃圾回收器检查已经迁移到“至”空间的对象内所有对象引用，并在所引用的对象上进行上述两个动作。

一旦所有的“至”空间引用都已经检查并更新，垃圾回收完成。

算法不需要栈并只需要在“自”空间和“至”空间外部的两个指针：到在“至”空间中空闲空间开始处的指针，和到在“自”空间中需要检查的下一个字的指针。在这两个指针之间的数据，代表它仍需要做的工作。

转发指针（昵称“破碎的心”），只在垃圾回收进程中使用；在到已经处在“至”空间的对象（因此在“自”空间中有一个转发指针）的一个引用被找到的时候，通过更新其指针来匹配转发指针，这个引用就可以简单而快速的更新。

由于这种策略要穷尽所有的存活引用，和在所引用对象中的所有的引用，它被称为“广度优先”列表复制垃圾回收方案。

算法伪码

initialize() =
    tospace   = N/2
    fromspace = 0
    allocPtr  = fromspace
    scanPtr   = whatever -- only used during collection

allocate(n) =
    If allocPtr + n > fromspace + tospace
        collect()
    EndIf
    If allocPtr + n > fromspace + tospace
        fail “insufficient memory”
    EndIf
    o = allocPtr
    allocPtr = allocPtr + n
    return o

collect() =
    swap(fromspace, tospace)
    allocPtr = tospace
    scanPtr = tospace

    -- scan every root you've got
    ForEach root in the stack -- or elsewhere
        root = copy(root)
    EndForEach
    
    -- scan objects in the to-space (including objects added by this loop)
    While scanPtr < allocPtr
        ForEach reference r from o (pointed to by scanPtr)
            r = copy(r)
        EndForEach
        scanPtr = scanPtr + o.size() -- points to the next object in the to-space, if any
    EndWhile

copy(o) =
    If o has no forwarding address
        o' = allocPtr
        allocPtr = allocPtr + size(o)
        copy the contents of o to o'
        forwarding-address(o) = o'
    EndIf
    return forwarding-address(o)

半空间

Cheney算法基于了“半空间”（semispace）垃圾回收器，这是在它一年之前由R.R. Fenichel和J.C. Yochelson发表的^[2]。

引用

^ Cheney, C.J. A Nonrecursive List Compacting Algorithm. Communications of the ACM. November 1970, 13 (11): 677–678 [2022-11-09]. S2CID 36538112. doi:10.1145/362790.362798. （原始内容存档于2022-11-09）.
^ Fenichel, R.R.; Yochelson, Jerome C. A LISP garbage-collector for virtual-memory computer systems. Communications of the ACM. 1969, 12 (11): 611–612 [2022-11-09]. S2CID 36616954. doi:10.1145/363269.363280. （原始内容存档于2020-05-28）.

Byers, Rick. Garbage Collection Algorithms (PDF). Garbage Collection Algorithms. 2007, 12 (11): 3–4 [2022-11-09]. （原始内容存档 (PDF)于2015-12-05）.

[1] Cheney, C.J. A Nonrecursive List Compacting Algorithm. Communications of the ACM. November 1970, 13 (11): 677–678 [2022-11-09]. S2CID 36538112. doi:10.1145/362790.362798. （原始内容存档于2022-11-09）.

[2] Fenichel, R.R.; Yochelson, Jerome C. A LISP garbage-collector for virtual-memory computer systems. Communications of the ACM. 1969, 12 (11): 611–612 [2022-11-09]. S2CID 36616954. doi:10.1145/363269.363280. （原始内容存档于2020-05-28）.

[1]

[2]