算法篇

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復制算法等。