序章

在序章中，我們將對什么是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的值。