序章

在序章中，我们将对什么是GC、GC的历史、学习GC的目的进行简要说明。此外还将说明阅读本书时的注意事项。

GC的定义

GC是Garbage Collection的简称，中文称为“垃圾回收”。

垃圾的回收

Garbage Collection的Garbage，也就是“垃圾”，具体指的是什么呢？

在现实世界中，说到垃圾，指的就是那些不读的书、不穿的衣服等。这种情况下的“垃圾”指的是“自己不用的东西”。

在GC中，“垃圾”的定义也是如此。GC把程序不用的内存空间视为垃圾。关于“垃圾”的详细介绍，我们会在1.5节进行阐述。

GC要做两件事

GC要做的有两件事。

1．找到内存空间里的垃圾

2．回收垃圾，让程序员能再次利用这部分空间

满足这两项功能的程序就是GC。

GC的好处

GC到底会给程序员带来怎样的好处呢？

没有GC的世界

在没有GC的世界里，程序员必须自己手动进行内存管理，必须清楚地确保必要的内存空间，释放不要的内存空间。

程序员在手动进行内存管理时，申请内存尚不存在什么问题，但在释放不要的内存空间时，就必须一个不漏地释放。这非常地麻烦。

如果忘记释放内存空间，该内存空间就会发生内存泄露，即无法被使用，但它又会持续存在下去。如果将发生内存泄露的程序放着不管，总有一刻内存会被占满，甚至还可能导致系统崩溃。

另外，在释放内存空间时，如果忘记初始化指向释放对象的内存空间的指针，这个指针就会一直指向释放完毕的内存空间。因为这个指针没有指向有效的内存空间，处于一种悬挂的状态，所以我们称其为“悬垂指针”（dangling pointer）。如果在程序中错误地引用了悬垂指针，就会产生无法预期的BUG。此外，悬垂指针也会导致严重的安全漏洞。

更有甚者，还可能会出现错误释放了使用中的内存空间的情况。一旦错误释放了使用中的内存空间，下一次程序使用此空间时就会发生故障。大多数情况下会发生段错误，运气不好的话还可能引发恶性BUG。

上述这样与内存相关的BUG，其共通之处在于“难以确定BUG的原因”。我们都知道，与内存相关的BUG的潜在场所和BUG出现的场所在位置上（或者是时间上）不一致，所以很难确定BUG的原因。

有GC的世界

为了省去上述手动内存管理的麻烦，人们钻研开发出了GC。如果把内存管理交给计算机，程序员就不用去想着释放内存了。

在手动内存管理中，程序员要判断哪些是不用的内存空间（垃圾），留意内存空间的寿命。但只要有GC在，这一切都可以交给GC来做。

有了GC，程序员就不用再去担心因为忘了释放内存等而导致BUG，从而大大减轻了负担。也不用再去头疼费事的内存管理。GC能让程序员告别恼人的内存管理，把精力集中在更本质的编程工作上。

GC的历史

GC是一门古老的技术

据笔者所知，GC因为Java的发布而一举成名，所以很多人可能会认为GC是最近才有的技术。不过GC有着非常久远的历史，最初的GC算法是John McCarthy在1960年发布的。

GC标记-清除算法

John McCarthy身为Lisp之父和人工智能之父，是一名非常有名的黑客，事实上他同时也是GC之父（多么伟大的黑客啊）。

1960年，McCarthy在其论文 [1]中首次发布了GC算法。

当然，当时还没有Garbage Collection这个词。证据就在这篇论文的脚注之中，如下所示。

给人感觉很青涩呢。

在这篇论文中发布的算法，就是现在我们所说的GC标记-清除算法。

引用计数法

1960年，George E. Collins在论文 [6]中发布了叫作引用计数的GC算法。

当时Collins可能没有注意到，引用计数法有个缺点，就是它不能回收“循环引用”。Harold McBeth [26]在1963年指出了这个缺点。

GC复制算法

1963年，也有“人工智能之父”之称的Marvin L. Minsky在论文 [7]中发布了复制算法。

GC复制算法把内存分成了两部分，这篇论文中将第二部分称为磁带存储空间。不得不说带有浓烈的时代色彩。

50年来，GC的根本都没有改变

从50年前GC算法首次发布以来，众多研究者对其进行了各种各样的研究，因此许多GC算法也得以发布。

但事实上，这些算法只不过是把前文中提到的三种算法进行组合或应用。也可以这么说，1963年GC复制算法诞生时，GC的根本性内容就已经完成了。

未知的第四种算法

现在为世人所知的GC算法，不过是从之前介绍的三种基本算法中衍生出来的产物。

本书中除了细致介绍这些基本的GC算法，还会介绍应用到它们的GC算法。把这些算法全看完后，请跟笔者一起，就GC的课题进行思考。

也许发现全新的第四种基本算法的人，就是你。

为什么我们现在要学GC

为什么我们现在有必要学习GC的原理？有以下几个原因。

GC——存在即合理

现在我们使用的多数编程语言都搭载有GC。以下是几个具体的例子。

· Lisp

· Java

· Ruby

· Python

· Perl

· Haskell

大家有没有使用过其中的某种编程语言呢？如果使用过，当时应该也在不知不觉中获得了GC带来的好处。

对编程语言来说，GC就是一个无名英雄，默默地做着贡献。打个比方，天鹅在水面优雅地游动时，实际上脚蹼却在水下拼命地划着水。GC也是如此。在由编程语言构造的美丽的源代码这片水下，GC在拼命地将垃圾回收再利用。

如上所述，GC是语言处理程序中非常重要的一部分，相当于树荫。应该有很多人感觉“GC帮忙回收垃圾是理所当然”的吧？

GC基本上是高负载处理，需要花费一定的时间。打个比方，当编写像动作游戏这样追求即时性的程序时，就必须尽量压低GC导致的最大暂停时间。如果因为GC导致玩家频繁卡顿，相信谁都会想摔手柄。碰到这种应用，我们就需要选择最大暂停时间较短的GC算法了。

再打个比方，对音乐和动画这样类似于编码应用的程序来说，GC的最大暂停时间就不那么重要了。更为重要的是，我们必须选择一个整体处理时间更短的算法。

笔者深信，事先知道“这个GC算法有这样的特征，所以它适合这个应用”对程序员来说很有价值。

如果我们不理所当然地去利用GC，而是去了解其内部情况，自己来评价GC算法，那么自身的编程水平就一定会得到提高吧。

多种多样的处理程序的实现

近年来，随着编程语言的发展，燃起了一股发布语言处理程序的势头，这些语言处理程序都搭载有不同的GC算法。作为语言处理程序的关键功能，很多人将采用了优秀的GC算法作为一大卖点。

GC性能在语言处理程序的性能评价中也是一大要素。为了正确评价GC的性能，对GC算法的理解是不可或缺的。

留意内存空间的用法

应该有不少人是通过使用搭载GC的编程语言来学习编程的吧。本书的作者之一中村也是如此，他最初接触的编程语言是Java。

可以说在用Java语言编写程序时完全不用留意内存空间的用法。当然这也是多亏了GC，这是好事，但太不留心也会招致麻烦。

例如，有时会出现无意中把内存空间挥霍一空的情况。比如在循环中生成一些没用的对象等。

这是因为没有把握好编程语言背后的内存管理的概念。

本书中以具体的编程语言为例，来说明编程语言中所使用的内存空间的结构，以及GC的运行。通过阅读本书，我们就能在编程中留意内存空间的用法了。

不会过时的技术

GC自1960年发布以来，一直在吸引着顶尖工程师们的目光。笔者确信，只要计算机构造不发生根本性的改变，GC就是一门不会过时的技术。对程序员来说，比起学习日新月异的最新技术，学习GC这样的古典技术不是更幸福吗？

更何况，GC很有趣

说实话，其实笔者自己学习GC的时候，并没有想过上述这些略复杂的事情。现在回过头觉得学了GC真好，也只是因为它具备前面那些优点而已。

为什么当初要学GC呢？对笔者而言，之所以会学习GC的算法和实现，纯粹是觉得有趣。

笔者小时候就喜欢拆点什么东西，看看里面是怎样的。电视机、收音机、红白机什么的都拆了个遍。平时也喜欢研究那些看似理所当然地在运转的机器，看看它们的内部如何。笔者至今都还记得看到其内部时的快感，以及了解其构造时的感动。

或许学习GC也差不多是这样。对笔者来说，研究GC这种理所当然存在的东西，看看它的内部，这是一件非常刺激的事。

本书中饱含了笔者在看到GC的内部时生出的“感动”。读完本书后，相信你心中的疑问——“为什么要学GC? ”也一定会转化成感动，发自内心地认为“GC真有趣！”。

读者对象

本书由两部分构成。

1．算法篇

2．实现篇

在“算法篇”中，我们没有必要去详细了解特定的编程语言，你只要能用任何一种语言编程，就能往下读“算法篇”。

阅读“实现篇”需要具备C和C++的知识。只要会用C的函数指针、C++的模板，阅读“实现篇”就没有什么障碍。关于GC算法的知识，读完本书的“算法篇”就相当够用了。

另一方面，对于“实现篇”中涉及的各种编程语言，最好有一定程度的了解，那样阅读起来会比较轻松。关于本书涉及的编程语言，在本书的“附录”部分中略有介绍。

本书中的符号

图中的箭头

本书的插图中会出现各种各样的箭头。关于本书中主要使用的箭头，请参考图1。

箭头（a）表示引用关系，用于从根到对象的引用等。

箭头（b）表示赋值操作和转移操作，用于给变量赋值、复制对象、转移对象等。

箭头（c）表示处理流程，用于流程图和函数调用等。

箭头（d）表示时间的经过。

箭头（e）表示继承关系，主要会在“实现篇”的类图中出现。

伪代码

为了帮助读者理解GC算法，本书采用伪代码进行解说。关于用到的伪代码，本书后文中会对其表示法进行说明。

本书用到的伪代码，其基本语法跟一般编程语言很像。因此读者可以直观地理解本书中出现的众多伪代码。

命名规则

变量以及函数都用小写字母表示（例：obj）。常量都用大写字母表示（例：COPIED）。另外，本书采用下划线连接两个及两个以上的单词（例：free_list、update_ptr()、HEAP_SIZE）。

空指针和真假值

设真值为TRUE，假值为FALSE。拥有真假值的变量var的否定为！var。

除此之外，本书用NULL表示没有指向任何地址的指针。

函数

本书采用与一般编程语言相同的描述方法来定义函数。例如，我们将以arg1、arg2为参数的函数func()定义如下。

1  func(arg1, arg2){
2     ...
3  }

当我们以整数100和200为实参调用该函数时，即为func(100,200)。

缩进

我们将缩进也算作语法的一部分。例如像下面这样，用缩进表示if语句的作用域。

1  if(test == TRUE)
2     a = 1
3     b = 2
4     c = 3
5  d = 4

在上面的例子中，只有当test为真的时候，才会执行第2行到第4行。第5行与test的值没有关系，所以一定会被执行。此外，我们把缩进长度设为两个空格。

指针

在GC算法中，指针是不可或缺的。我们用星号（*）访问指针所引用的内存空间。例如我们把指针ptr指向的对象表示为*ptr。

域

我们可以用obj.field访问对象obj的域field。例如，我们要想在对象girl的各个域name、age、job中分别代入值，可按如下书写。

1  girl.name = "Hanako"
2  girl.age = 30
3  girl.job = "lawyer"

for循环

我们在给整数增量的时候使用for循环。例如用变量sum求1到10的和时，代码如下所示。

1  sum = 0
2  for(i : 1..10)
3     sum += i

for循环也用来访问数组元素。例如，想把函数do_something()应用在数组array中包含的所有元素中时，我们可以用for(变量：集合)的形式来按顺序访问全部元素。

1  for(obj : array)
2     do_something(obj)

当然，也可以像下面这样把index作为下标（整数N是数组array的长度）。和C语言等编程语言一样，数组的下标都从0开始。

1  for(index : 0..(N-1))
2     do_something(array[index])

栈与队列

GC中经常用到栈和队列等数据结构。栈是一种将后进入的数据先取出的数据结构，即FILO（First-In Last-Out）。与其相反，队列是将先进入的数据先取出的数据结构，即FIFO（First-In First-Out）。

我们分别用push()函数和pop()函数将数据压栈（push）和出栈（pop）。用push(stack, obj)向栈stack中压入对象obj。用pop(stack)从stack中取出数据，并将此数据作为返回值。另外，我们用is_full(stack)检查stack是否为满，用is_empty(stack)检查stack是否为空，并返回真假值。

另一方面，我们用enqueue()函数和dequeue()函数来向队列内添加（enqueue）以及取出（dequeue）数据，用enqueue(queue, data)来向队列queue中添加数据data，用dequeue(queue)来从queue取出并返回数据。

特殊的函数

除了以上介绍的函数之外，我们还有两个在伪代码中出现的特殊函数。

首先是copy_data()函数，它是复制内存区域的函数。我们用copy_data(ptr1, ptr2, size)把size个字节的数据从指针ptr2指向的内存区域复制到ptr1指向的内存区域。这个函数跟C语言中的memcpy()函数用法相同。

swap()函数是替换两个变量值的函数。我们用swap(var1, var2)来替换变量var1和变量var2的值。