5.3  存储分配和垃圾回收

在第 5.4节中，我们将展示如何将Scheme求值器实现为一台寄存器计算机。为了简化讨论，我们将假设我们的寄存器计算机可以配备一个列表结构内存，其中操作列表结构数据的基本操作都是原语。当一个人专注于Scheme解释器中的控制机制时，假设这样一个内存的存在是一个有用的抽象，但这并不能反映当代计算机中实际基本数据操作的现实情况。为了更完整地了解Lisp系统是如何运作的，我们必须研究如何以与传统计算机内存兼容的方式来表示列表结构。

在实现列表结构时有两个考虑。第一个纯粹是表示问题：如何仅使用典型计算机内存的存储和寻址能力来表示Lisp序对的"盒子和指针"结构。第二个问题涉及随着计算的进行对内存的管理。Lisp系统的运作关键依赖于持续创建新数据对象的能力。这些对象既包括被解释的Lisp过程显式创建的对象，也包括解释器本身创建的结构，如环境和参数列表。尽管在具有无限快速可寻址内存的计算机上，持续创建新数据对象不会造成问题，但计算机内存只有有限的大小（可惜的是）。因此，Lisp系统提供了自动存储分配设施来支持无限内存的假象。当一个数据对象不再需要时，分配给它的内存被自动回收并用于构造新的数据对象。有各种技术来提供这种自动存储分配。我们在本节中将讨论的方法称为垃圾回收。

5.3.1  Memory as Vectors

传统的计算机内存可以被想象成一个由小格子组成的数组，每个小格子都可以包含一条信息。每个小格子都有一个唯一的名字，称为它的地址或位置。典型的内存系统提供两种基本操作：一种是从指定位置获取存储的数据，另一种是将新数据赋给指定位置。内存地址可以递增，以支持对某些格子集合的顺序访问。更一般地，许多重要的数据操作要求将内存地址视为数据，这些数据可以存储在内存位置中并在机器寄存器中操作。列表结构的表示就是这种地址运算的一个应用。

为了对计算机内存建模，我们使用一种称为向量的新型数据结构。抽象地说，向量是一种复合数据对象，其各个元素可以通过整数索引以与索引无关的时间量进行访问。⁵为了描述内存操作，我们使用两个用于操作向量的基本Scheme过程：

• (vector-ref <vector> <n>) 返回向量的第n个元素。

• (vector-set! <vector> <n> <value>) 将向量的第n个元素设置为指定的值。

例如，如果v是一个向量，那么(vector-ref v 5)获取向量v中的第五个条目，而(vector-set! v 5 7)将向量v中第五个条目的值改为7。⁶ 对于计算机内存，这种访问可以通过使用地址运算来实现，将指定向量在内存中起始位置的基地址与指定向量特定元素偏移量的索引结合起来。

Representing Lisp data

我们可以使用向量来实现列表结构内存所需的基本序对结构。让我们假设计算机内存被分为两个向量：the-cars和the-cdrs。我们将如下表示列表结构：指向一个序对的指针是指向这两个向量的一个索引。序对的car是具有指定索引的the-cars中的条目，序对的cdr是具有指定索引的the-cdrs中的条目。我们还需要一种表示非序对对象（如数字和符号）的方法，以及一种区分不同类型数据的方法。有多种方法可以实现这一点，但它们都归结为使用类型化指针，也就是说，扩展"指针"的概念以包含数据类型信息。⁷数据类型使系统能够区分指向序对的指针（由"序对"数据类型和指向内存向量的索引组成）和指向其他类型数据的指针（由其他数据类型和用于表示该类型数据的内容组成）。两个数据对象如果它们的指针相同，则被认为是相同的（eq?）。⁸图 5.14说明了使用这种方法来表示列表((1 2) 3 4)，其盒子和指针图也一并显示。我们使用字母前缀来表示数据类型信息。因此，指向索引为5的序对的指针记作p5，空列表由指针e0表示，指向数字4的指针记作n4。在盒子和指针图中，我们在每个序对的左下角标明了存储该序对car和cdr的向量索引。the-cars和the-cdrs中的空白位置可能包含其他列表结构的部分（这里不关心）。

图 5.14:  列表((1 2) 3 4)的盒子和指针表示与内存向量表示。

指向数字的指针，例如n4，可能由指示数值数据类型的类型信息和数字4的实际表示组成。⁹为了处理那些太大而无法在分配给单个指针的固定空间内表示的数字，我们可以使用一种独特的大数数据类型，其指针指向一个列表，其中存储了该数字的各个部分。¹⁰

一个符号可以被表示为一个类型化指针，该指针指向构成该符号打印表示形式的一个字符序列。这个序列由Lisp读取器在输入中首次遇到该字符串时构造。由于我们希望符号的两个实例被eq?识别为"相同"的符号，并且我们希望eq?只是一个简单的指针相等性测试，我们必须确保如果读取器两次看到相同的字符串，它使用相同的指针（指向相同的字符序列）来表示这两个出现。为了实现这一点，读取器维护一个表，传统上称为obarray（符号表），其中包含它曾经遇到过的所有符号。当读取器遇到一个字符串并即将构造一个符号时，它会检查obarray以查看是否曾经见过相同的字符串。如果没有，它就使用这些字符构造一个新符号（一个指向新字符序列的类型化指针），并将此指针输入到obarray中。如果读取器之前见过该字符串，它就返回存储在obarray中的符号指针。这种用唯一指针替换字符串的过程称为intern符号。

Implementing the primitive list operations

根据上述表示方案，我们可以将寄存器计算机的每个"基本"列表操作替换为一个或多个基本向量操作。我们将使用两个寄存器the-cars和the-cdrs来标识内存向量，并假设vector-ref和vector-set!可作为基本操作使用。我们还假设指针上的数值运算（例如递增指针、使用序对指针索引向量或两个数相加）只使用类型化指针的索引部分。

例如，我们可以让寄存器计算机支持以下指令

(assign <reg₁> (op car) (reg <reg₂>))

(assign <reg₁> (op cdr) (reg <reg₂>))

如果我们分别将它们实现为

(assign <reg₁> (op vector-ref) (reg the-cars) (reg <reg₂>))

(assign <reg₁> (op vector-ref) (reg the-cdrs) (reg <reg₂>))

而指令

(perform (op set-car!) (reg <reg₁>) (reg <reg₂>))

(perform (op set-cdr!) (reg <reg₁>) (reg <reg₂>))

被实现为

(perform
 (op vector-set!) (reg the-cars) (reg <reg₁>) (reg <reg₂>))

(perform
 (op vector-set!) (reg the-cdrs) (reg <reg₁>) (reg <reg₂>))

Cons通过分配一个未使用的索引并将cons的参数存储在该索引位置的the-cars和the-cdrs中来执行。我们假设有一个特殊的寄存器free，它始终持有一个包含下一个可用索引的序对指针，并且我们可以递增该指针的索引部分来找到下一个空闲位置。¹¹ 例如，指令

(assign <reg₁> (op cons) (reg <reg₂>) (reg <reg₃>))

被实现为以下向量操作序列：¹²

(perform
 (op vector-set!) (reg the-cars) (reg free) (reg <reg₂>))
(perform
 (op vector-set!) (reg the-cdrs) (reg free) (reg <reg₃>))
(assign <reg₁> (reg free))
(assign free (op +) (reg free) (const 1))

eq?操作

(op eq?) (reg <reg₁>) (reg <reg₂>)

简单地测试寄存器中所有字段的相等性，而 像pair?、null?、symbol?和number?这样的谓词只需检查类型字段。

Implementing stacks

虽然我们的寄存器计算机使用栈，但我们在这里不需要做任何特殊处理，因为栈可以基于列表来建模。栈可以是一个保存值的列表，由特殊寄存器the-stack指向。因此，(save <reg>)可以被实现为

(assign the-stack (op cons) (reg <reg>) (reg the-stack))

类似地，(restore <reg>)可以被实现为

(assign <reg> (op car) (reg the-stack))
(assign the-stack (op cdr) (reg the-stack))

而(perform (op initialize-stack))可以被实现为

(assign the-stack (const ()))

这些操作可以进一步展开为上面给出的向量操作。然而，在传统的计算机体系结构中，将栈分配为一个单独的向量通常更有利。这样，栈的压入和弹出可以通过递增或递减该向量的索引来实现。

练习 5.20.  画出由以下代码产生的列表结构的盒子和指针表示以及内存向量表示（如图 5.14所示）：

(define x (cons 1 2))
(define y (list x x))

其中free指针初始为p1。free的最终值是什么？哪些指针表示x和y的值？

练习 5.21.  为以下过程实现寄存器计算机。假设列表结构内存操作可作为机器原语使用。

a. 递归的count-leaves:

(define (count-leaves tree)
  (cond ((null? tree) 0)
        ((not (pair? tree)) 1)
        (else (+ (count-leaves (car tree))
                 (count-leaves (cdr tree))))))

b. 带显式计数器的递归count-leaves:

(define (count-leaves tree)
  (define (count-iter tree n)
    (cond ((null? tree) n)
          ((not (pair? tree)) (+ n 1))
          (else (count-iter (cdr tree)
                            (count-iter (car tree) n)))))
  (count-iter tree 0))

练习 5.22.  第 3.3.1节的练习 3.12 展示了一个append过程（将两个列表连接起来形成一个新列表）和一个append!过程（将两个列表拼接在一起）。请设计一个寄存器计算机来实现这些过程中的每一个。假设列表结构内存操作可作为基本操作使用。

5.3.2  Maintaining the Illusion of Infinite Memory

第 5.3.1节中概述的表示方法解决了实现列表结构的问题，前提是我们拥有无限的内存。在真实的计算机上，我们最终会用完用于构造新序对的空闲空间。¹³ 然而，在典型计算中生成的大部分序对只用于保存中间结果。在访问了这些结果之后，这些序对不再需要——它们变成了垃圾。例如，计算

(accumulate + 0 (filter odd? (enumerate-interval 0 n)))

构造了两个列表：枚举列表和过滤枚举的结果列表。当累积完成后，这些列表不再需要，已分配的内存可以被回收。如果我们能够定期收集所有的垃圾，并且如果这能以大约与我们构造新序对相同的速率回收内存，那么我们就保持了存在无限内存的假象。

为了回收序对，我们必须有一种方法来确定哪些已分配的序对是不需要的（从它们的内容不再能影响计算未来的意义上说）。我们将要研究的实现这一目的的方法称为垃圾回收。垃圾回收基于这样一个观察：在Lisp解释过程中的任何时刻，唯一能影响计算未来的对象是那些可以从当前在机器寄存器中的指针出发，通过一系列car和cdr操作到达的对象。¹⁴任何无法这样访问的内存单元都可以被回收。

有许多执行垃圾回收的方法。我们在这里将要研究的方法称为停止-复制。其基本思想是将内存分为两半："工作内存"和"空闲内存"。当cons构造序对时，它在工作内存中分配这些序对。当工作内存满时，我们通过定位工作内存中所有有用的序对并将它们复制到空闲内存中的连续位置来执行垃圾回收。（有用的序对是通过从机器寄存器开始追踪所有car和cdr指针来定位的。）由于我们不复制垃圾，因此很可能会有额外的空闲内存可用于分配新序对。此外，工作内存中没有任何东西是需要的，因为其中所有有用的序对都已被复制。因此，如果我们交换工作内存和空闲内存的角色，就可以继续处理；新序对将被分配在新的工作内存（即原先的空闲内存）中。当这个内存满时，我们可以将有用的序对复制到新的空闲内存（即原先的工作内存）中。¹⁵

Implementation of a stop-and-copy garbage collector

我们现在使用寄存器计算机语言来更详细地描述停止-复制算法。我们将假设有一个名为root的寄存器，它包含一个指向某个结构的指针，该结构最终指向所有可访问的数据。这可以通过在开始垃圾回收之前将所有机器寄存器的内容存储在一个由root指向的预分配列表中来实现。¹⁶我们还假设，除了当前的工作内存之外，还有可用的空闲内存供我们复制有用的数据。当前工作内存由基地址在名为the-cars和the-cdrs的寄存器中的向量组成，而空闲内存在名为new-cars和new-cdrs的寄存器中。

当当前工作内存中的空闲单元用尽时，即当cons操作试图将free指针递增到超出内存向量末尾时，就会触发垃圾回收。当垃圾回收过程完成时，root指针将指向新内存，所有从root可访问的对象都将被移动到新内存中，并且free指针将指示新内存中可以分配新序对的下一个位置。此外，工作内存和新内存的角色将会互换——新序对将被构建在新内存中，从free指示的位置开始，而（先前的）工作内存将作为下一次垃圾回收的新内存可用。 图 5.15显示了垃圾回收前后内存的布局。

图 5.15:  垃圾回收过程对内存的重新配置。

垃圾回收过程的状态通过维护两个指针来控制：free和scan。它们被初始化为指向新内存的开头。算法首先将由root指向的序对重定位到新内存的开头。该序对被复制，root指针被调整指向新位置，并且free指针被递增。此外，序对的旧位置被标记以表明其内容已被移动。这种标记方式如下：在car位置，我们放置一个特殊标签，表明这是一个已被移动的对象。（这样的对象传统上称为破碎的心。）¹⁷在cdr位置，我们放置一个转发地址，指向该对象被移动到的位置。

在重定位根之后，垃圾回收器进入其基本循环。在算法的每一步，scan指针（最初指向已重定位的根）指向一个已被移动到新内存但它的car和cdr指针仍指向旧内存中的对象的序对。这些对象各自被重定位，然后scan指针被递增。为了重定位一个对象（例如，我们正在扫描的序对的car指针所指示的对象），我们检查该对象是否已经被移动（通过该对象car位置是否存在broken-heart标签来判断）。如果该对象尚未被移动，我们将其复制到free指示的位置，更新free，在对象的旧位置设置一个broken heart，并更新指向该对象的指针（在此例中是正在扫描的序对的car指针）以指向新位置。如果该对象已被移动，则其转发地址（在broken heart的cdr位置找到）将被替换到正在扫描的序对的指针中。最终，所有可访问的对象都将被移动和扫描，此时scan指针将赶上free指针，过程终止。

我们可以将停止-复制算法指定为寄存器计算机的一系列指令。重定位对象的基本步骤由一个名为relocate-old-result-in-new的子程序完成。该子程序从名为old的寄存器中获取其参数——指向要重定位的对象的指针。它重定位指定的对象（在此过程中递增free），将指向重定位后对象的指针放入名为new的寄存器中，并通过分支到存储在relocate-continue寄存器中的入口点返回。为了开始垃圾回收，我们在初始化free和scan之后调用这个子程序来重定位root指针。当root的重定位完成后，我们将新指针安装为新的root，并进入垃圾回收器的主循环。

begin-garbage-collection
  (assign free (const 0))
  (assign scan (const 0))
  (assign old (reg root))
  (assign relocate-continue (label reassign-root))
  (goto (label relocate-old-result-in-new))
reassign-root
  (assign root (reg new))
  (goto (label gc-loop))

在垃圾回收器的主循环中，我们必须确定是否还有更多的对象需要扫描。我们通过测试scan指针是否与free指针重合来实现这一点。如果指针相等，那么所有可访问的对象都已被重定位，我们就分支到gc-flip，它负责清理工作，以便我们可以继续被中断的计算。如果仍然有待扫描的序对，我们就调用重定位子程序来重定位下一个序对的car（通过将car指针放入old中）。relocate-continue寄存器被设置为使子程序返回后更新car指针。

gc-loop
  (test (op =) (reg scan) (reg free))
  (branch (label gc-flip))
  (assign old (op vector-ref) (reg new-cars) (reg scan))
  (assign relocate-continue (label update-car))
  (goto (label relocate-old-result-in-new))

在update-car处，我们修改正在扫描的序对的car指针，然后继续重定位该序对的cdr。当该重定位完成后，我们返回到update-cdr。在重定位并更新cdr之后，我们就完成了对该序对的扫描，因此继续执行主循环。

update-car
  (perform
   (op vector-set!) (reg new-cars) (reg scan) (reg new))
  (assign old (op vector-ref) (reg new-cdrs) (reg scan))
  (assign relocate-continue (label update-cdr))
  (goto (label relocate-old-result-in-new))

update-cdr
  (perform
   (op vector-set!) (reg new-cdrs) (reg scan) (reg new))
  (assign scan (op +) (reg scan) (const 1))
  (goto (label gc-loop))

子程序relocate-old-result-in-new按如下方式重定位对象：如果要重定位的对象（由old指向）不是一个序对，那么我们返回指向该对象的相同指针（在new中），不做更改。（例如，我们可能正在扫描一个car是数字4的序对。如果我们如第 5.3.1节所述用n4表示car，那么我们希望"重定位"后的car指针仍然是n4。）否则，我们必须执行重定位。如果要重定位的序对的car位置包含一个broken-heart标签，那么该序对实际上已经被移动了，所以我们检索转发地址（从broken heart的cdr位置）并在new中返回它。如果old中的指针指向一个尚未移动的序对，那么我们将该序对移动到新内存中的第一个空闲单元（由free指向），并通过在旧位置存储broken-heart标签和转发地址来设置broken heart。 Relocate-old-result-in-new使用寄存器oldcr 来保存由old指向的对象的car或cdr。¹⁸

relocate-old-result-in-new
  (test (op pointer-to-pair?) (reg old))
  (branch (label pair))
  (assign new (reg old))
  (goto (reg relocate-continue))
pair
  (assign oldcr (op vector-ref) (reg the-cars) (reg old))
  (test (op broken-heart?) (reg oldcr))
  (branch (label already-moved))
  (assign new (reg free)) ; 序对的新位置
  ;; 更新free指针。
  (assign free (op +) (reg free) (const 1))
  ;; 将car和cdr复制到新内存。
  (perform (op vector-set!)
           (reg new-cars) (reg new) (reg oldcr))
  (assign oldcr (op vector-ref) (reg the-cdrs) (reg old))
  (perform (op vector-set!)
           (reg new-cdrs) (reg new) (reg oldcr))
  ;; 构造broken heart。
  (perform (op vector-set!)
           (reg the-cars) (reg old) (const broken-heart))
  (perform
   (op vector-set!) (reg the-cdrs) (reg old) (reg new))
  (goto (reg relocate-continue))
already-moved
  (assign new (op vector-ref) (reg the-cdrs) (reg old))
  (goto (reg relocate-continue))

在垃圾回收过程的最后，我们通过交换指针来互换旧内存和新内存的角色：交换the-cars与new-cars，以及the-cdrs与new-cdrs。这样，下次内存耗尽时，我们就准备好执行另一次垃圾回收了。

gc-flip
  (assign temp (reg the-cdrs))
  (assign the-cdrs (reg new-cdrs))
  (assign new-cdrs (reg temp))
  (assign temp (reg the-cars))
  (assign the-cars (reg new-cars))
  (assign new-cars (reg temp))