算法篇

1 学习GC之前

本章中将为各位说明GC中的基本概念。

1.1 对象/头/域

对象这个词，在不同的使用场合其意思各不相同。比如，在面向对象编程中，它指“具有属性和行为的事物”，然而在GC的世界中，对象表示的是“通过应用程序利用的数据的集合”。

对象配置在内存空间里。GC根据情况将配置好的对象进行移动或销毁操作。因此，对象是GC的基本单位。本书中的所有“对象”都表示这个含义。

一般来说，对象由头（header）和域（field）构成。我们下面将对其逐一说明。

1.1.1 头

我们将对象中保存对象本身信息的部分称为“头”。头主要含有以下信息。

· 对象的大小

· 对象的种类

如果不清楚对象的大小和种类，就会发生问题，例如无法判别内存中存储的对象的边界。因此头对GC来说非常重要。

此外，头中事先存有运行GC所需的信息。然而根据GC算法的不同，信息也不同。

比如将在第2章中介绍的GC标记-清除算法，就是在对象的头部中设置1个flag（标志位）来记录对象是否已标记，从而管理各个对象。

因为任何GC算法中都会用到对象大小和种类的信息，所以本书就不专门在图中将其标记出来了。另一方面，我们会将标志位等算法特有的信息作为对象的一部分明确写出。

1.1.2 域

我们把对象使用者在对象中可访问的部分称为“域”。可以将其想成C语言中结构体的成员，这样就很简单了吧。对象使用者会引用或替换对象的域值。另一方面，对象使用者基本上无法直接更改头的信息。

域中的数据类型大致分为以下2种。

· 指针

· 非指针

指针是指向内存空间中某块区域的值。用C语言和C++语言编程过的读者对它应该很熟悉了吧。即使是像Java这样语言使用者没有明确用到指针的编程语言，语言处理程序内部也用到了指针。关于指针，我们在1.2节中再详细介绍。

非指针指的是在编程中直接使用值本身。数值、字符以及真假值都是非指针。

在对象内部，头之后存在1个及1个以上的域。在“算法篇”中，对象、头以及域的关系如图1.1所示。

为了更简单地向大家说明，我们事先把“算法篇”中域的大小全设成1个字。

此外在伪代码中，可以用obj.field1、obj.field2……来从头按顺序访问对象obj的各个域。

1.2 指针

通过GC，对象会被销毁或保留。这时候起到关键作用的就是指针。因为GC是根据对象的指针指向去搜寻其他对象的。另一方面，GC对非指针不进行任何操作。

在这里有两点需要我们注意。

首先，要注意语言处理程序是否能判别指针和非指针。要判别指针和非指针需要花费一定的功夫，关于这一点我们会在第6章详细说明。除第6章之外，在“算法篇”的各个章节中，我们都以GC可判别对象各域中的值是指针还是非指针为前提进行解说。

另一点是指针要指向对象的哪个部分。指针如果指向对象首地址以外的部分，GC就会变得非常复杂。在大多数语言处理程序中，指针都默认指向对象的首地址。因为存在这个制约条件，不仅是GC，就连语言处理程序的其他各种处理都变得简单了。因此我们在“算法篇”中也以此条件为前提。

在“算法篇”中，对象和指针的关系如图1.2所示。

在此我们把图1.2中的B和C称为A的子对象。对某个对象的子对象进行某项处理是GC的基本操作。在“算法篇”的伪代码部分，我们用children(obj)获取指向对象obj的子对象的指针数组。使用这个children()函数，我们可以把遍历子对象的操作写得简单一些。打个比方，我们假设执行了以下代码来处理图1.2的情况。

1   for(child : children(A))
2     func(*child)

此时，对象B、C依次作为实参调用func()函数。

1.3 mutator

mutator是Edsger Dijkstra [15]琢磨出来的词，有“改变某物”的意思。说到要改变什么，那就是GC对象间的引用关系。不过光这么说可能大家还是不能理解，其实用一句话概括的话，它的实体就是“应用程序”。这样说就容易理解了吧。GC就是在这个mutator内部精神饱满地工作着。

mutator实际进行的操作有以下2种。

· 生成对象

· 更新指针

mutator在进行这些操作时，会同时为应用程序的用户进行一些处理（数值计算、浏览网页、编辑文章等）。随着这些处理的逐步推进，对象间的引用关系也会“改变”。伴随这些变化会产生垃圾，而负责回收这些垃圾的机制就是GC。

1.4 堆

堆指的是用于动态（也就是执行程序时）存放对象的内存空间。当mutator申请存放对象时，所需的内存空间就会从这个堆中被分配给mutator。

GC是管理堆中已分配对象的机制。在开始执行mutator前，GC要分配用于堆的内存空间。一旦开始执行mutator，程序就会按照mutator的要求在堆中存放对象。等到堆被对象占满后，GC就会启动，从而分配可用空间。如果不能分配足够的可用空间，一般情况下我们就要扩大堆。

然而，为了让读者能更容易理解，在“算法篇”中我们把堆的大小固定为常量HEAP_SIZE，不会进行扩大。此外，我们把$heap_start定为指向堆首地址的指针，把$heap_end定为指向堆末尾下一个地址的指针。也就是说，$heap_end等于$heap_start + HEAP_SIZE。

此外，本书中将如图所示的堆的左侧设为内存的低地址，右侧设为高地址。

HEAP_SIZE、$heap_start和$heap_end的关系如图1.3所示。

1.5 活动对象/非活动对象

我们将分配到内存空间中的对象中那些能通过mutator引用的对象称为“活动对象”。反过来，把分配到堆中那些不能通过程序引用的对象称为“非活动对象”。也就是说，不能通过程序引用的对象已经没有人搭理了，所以死掉了。死掉的对象（即非活动对象）我们就称为“垃圾”。

这里需要大家注意的是：死了的对象不可能活过来。因为就算mutator想要重新引用（复活）已经死掉的对象，我们也没法通过mutator找到它了。

因此，GC会保留活动对象，销毁非活动对象。当销毁非活动对象时，其原本占据的内存空间会得到解放，供下一个要分配的新对象使用。

1.6 分配

分配（allocation）指的是在内存空间中分配对象。当mutator需要新对象时，就会向分配器（allocator）申请一个大小合适的空间。分配器则在堆的可用空间中找寻满足要求的空间，返回给mutator。

像Java和Ruby这些配备了GC的编程语言在生成实例时，会在内部进行分配。另一方面，因为C语言和C++没有配备GC，所以程序员要使用malloc()函数和new运算符等进行手动分配。

然而，当堆被所有活动对象占满时，就算运行GC也无法分配可用空间。这时候我们有以下两种选择。

1．销毁至今为止的所有计算结果，输出错误信息

2．扩大堆，分配可用空间

之前在1.4节中也讲过，为了让本书的“算法篇”更易懂，这里我们选择第1个选项。我们将在伪代码中用allocation_fail()函数进行第1项的处理。

不过，在现实的执行环境中选择第2项会更贴合实际。因为我们必须尽可能地避免因内存不足造成的程序停止。在内存空间大小没有特殊限制的情况下，应该扩大堆。

1.7 分块

分块（chunk）在GC的世界里指的是为利用对象而事先准备出来的空间。

初始状态下，堆被一个大的分块所占据。

然后，程序会根据mutator的要求把这个分块分割成合适的大小，作为（活动）对象使用。活动对象不久后会转化为垃圾被回收。此时，这部分被回收的内存空间再次成为分块，为下次被利用做准备。也就是说，内存里的各个区块都重复着分块→活动对象→垃圾（非活动对象）→分块→……这样的过程。

1.8 根

根（root）这个词的意思是“根基”“根底”。在GC的世界里，根是指向对象的指针的“起点”部分。

这些都是能通过mutator直接引用的空间。举个例子，请看下面的伪代码。

1   $obj = Object.new
2   $obj.field1 = Object.new

在这里$obj是全局变量。首先，我们在第1行分配一个对象（对象A），然后把$obj代入指向这个对象的指针。在第2行我们也分配一个对象（对象B），然后把$obj.field1代入指向这个对象的指针。在执行完第2行后，全局变量空间及堆如图1.5所示。

在这里我们可以使用$obj直接从伪代码中引用对象A，也就是说A是活动对象。此外，因为可以通过$obj经由对象A引用对象B，所以对象B也是活动对象。因此GC必须保护这些对象。

GC把上述这样可以直接或间接从全局变量空间中引用的对象视为活动对象。

与全局变量空间相同，我们也可以通过mutator直接引用调用栈（call stack）和寄存器。也就是说，调用栈、寄存器以及全局变量空间都是根。

但在这里我们必须注意一点，那就是GC在一般情况下无法严谨地判断寄存器和调用栈中的值是指针还是非指针。关于这一点会在第6章详细说明。为了判断根中的指针，我们需要下点功夫。

在这里介绍怎么去判断未免太费口舌。所以在“算法篇”，我们先暂定“GC可以严谨判断根中的指针和非指针”。这跟1.2节的前提相同。

在“算法篇”中，根如图1.6所示。

此外，我们将伪代码中有根的指针数组表示为$roots。也就是说，像下面这样编写，就能依次把所有由根引用的对象作为func()函数的参数。

1   for(r : $roots)
2     func(*r)

1.9 评价标准

评价GC算法的性能时，我们采用以下4个标准。

· 吞吐量

· 最大暂停时间

· 堆使用效率

· 访问的局部性

下面我们逐一进行说明。

1.9.1 吞吐量

从一般意义上来讲，吞吐量（throughput）指的是“在单位时间内的处理能力”，这点在GC的世界中也不例外。

请参照图1.7的示例。

在mutator整个执行过程中，GC一共启动了3次，我们把花费的时间分别设为A、B、C。也就是说，GC总共花费的时间为（A+B+C）。另一方面，我们前面提到过，以GC为对象的堆大小是HEAP_SIZE。也就是说，在大小为HEAP_SIZE的堆进行内存管理，要花费的时长为（A+B+C）。因此，这种情况下GC的吞吐量为HEAP_SIZE/（A+B+C）。

当然，人们通常都喜欢吞吐量高的GC算法。然而判断各算法吞吐量的好坏时不能一概而论。

打个比方，众所周知GC复制算法和GC标记-清除算法相比，活动对象越少吞吐量越高。这是因为GC复制算法只检查活动对象，而GC标记-清除算法则会检查所有的活动和非活动对象。

然而，随着活动对象的增多，各GC算法表现出的吞吐量也会相应地变化。极端情况下，甚至会出现GC标记-清除算法比GC复制算法表现的吞吐量更高的情况。

也就是说，即便是同一GC算法，其吞吐量也是受mutator的动作左右的。评价GC算法的吞吐量时，有必要把mutator的动作也考虑在内。

1.9.2 最大暂停时间

本书“算法篇”中介绍的所有GC算法，都会在GC执行过程中令mutator暂停执行。最大暂停时间指的是“因执行GC而暂停执行mutator的最长时间”。这么说可能比较难理解，请再看一遍图1.7。最大暂停时间是A～C的最大值，也就是B。

那么，我们在何种情况下需要重视此种指标呢？

典型例子是两足步行的机器人。如果在其步行过程中启动GC，我们对机器人的控制就会暂时中断，直到GC执行完毕方可重启。也就是说，在这期间机器人完全不能运作。很显然，机器人会摔倒。

再举个例子，Web浏览器会如何呢？如果在浏览Web网页的时候发生GC，浏览器就会看似卡住，带给用户心理负担。像Web浏览器这样的GUI应用，大多数都是以人机交互为前提的，所以我们不希望执行过程中长时间受到GC的影响。

这种情况下就需要缩短最大暂停时间。然而不管尝试哪种GC算法，我们都会发现较大的吞吐量和较短的最大暂停时间不可兼得。所以应根据执行的应用所重视的指标的不同，来分别采用不同的GC算法。

1.9.3 堆使用效率

根据GC算法的差异，堆使用效率也大相径庭。左右堆使用效率的因素有两个。

一个是头的大小，另一个是堆的用法。

首先是头的大小。在堆中堆放的信息越多，GC的效率也就越高，吞吐量也就随之得到改善。但毋庸置疑，头越小越好。因此为了执行GC，需要把在头中堆放的信息控制在最小限度。

其次，根据堆的用法，堆使用效率也会出现巨大的差异。举个例子，GC复制算法中将堆二等分，每次只使用一半，交替进行，因此总是只能利用堆的一半。相对而言，GC标记-清除算法和引用计数法就能利用整个堆。

撇开这个不说，因为GC是自动内存管理功能，所以过量占用堆就成了本末倒置。与吞吐量和最大暂停时间一样，堆使用效率也是GC算法的重要评价指标之一。

然而，堆使用效率和吞吐量，以及最大暂停时间不可兼得。简单地说就是：可用的堆越大，GC运行越快；相反，越想有效地利用有限的堆，GC花费的时间就越长。

1.9.4 访问的局部性

PC上有4种存储器，分别是寄存器、缓存、内存、辅助存储器。它们之间有着如图1.8所示的层级关系。

众所周知，越是可实现高速存取的存储器容量就越小。毫无疑问，我们都希望尽可能地利用较高速的存储器，但由于高速的存储器容量小，因此通常不可能把所有要利用的数据都放在寄存器和缓存里。一般我们会把所有的数据都放在内存里，当CPU访问数据时，仅把要使用的数据从内存读取到缓存。与此同时，我们还将它附近的所有数据都读取到缓存中，从而压缩读取数据所需要的时间。

另一方面，具有引用关系的对象之间通常很可能存在连续访问的情况。这在多数程序中都很常见，称为“访问的局部性”。考虑到访问的局部性，把具有引用关系的对象安排在堆中较近的位置，就能提高在缓存中读取到想利用的数据的概率，令mutator高速运行。想深入了解访问的局部性的读者，请参考《计算机组成与设计：硬件、软件接口》[29]。

有些GC算法会根据引用关系重排对象，例如在第4章中提到的GC复制算法等。