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]。

引用

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）.

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