Categories
程式開發

深入理解JVM垃圾回收算法- 複製算法


通常來說,在整個程序的運行過程中,垃圾回收只會佔用很小一部分時間,賦值器的執行會佔用更多的時間,因此,內存分配速度的快慢將直接決定整個程序的性能。很明顯,前面提到的標記-清理算法並不是一個很好的範例,雖然它的算法簡單且實現容易,但存在很嚴重的內存碎片化問題,會嚴重影響內存的分配速度。

标记-整理算法可以根除碎片问题,而且分配速度也很快,但在垃圾回收过程中会进行多次堆遍历,进而显著增加了回收时间。

本文將介紹第三種基本的垃圾回收算法:半區復制算法。回收器在整個過程中通過複製的方式來進行堆整理,從而提升內存分配速度,且回收過程中只需對存活對象便利一次,其最大的缺點是堆的可用空間降低了一半。

複製算法是一種典型的以空間換時間的算法。

實現原理

在復制算法中,回收器將堆空間劃分為兩個大小相等的半區(semispace),分別是來源空間(fromspace) 和目標空間(tospace)。在進行垃圾回收時,回收器將存活對像從來源空間複製到目標空間,複製結束後,所有存活對象緊密排佈在目標空間一端,最後將來源空間和目標空間互換。半區復制算法的概要如下圖所示。

深入理解JVM垃圾回收算法- 複製算法 1

深入理解JVM垃圾回收算法- 複製算法 2

接下來看下代碼如何實現?主要流程很簡單,有一個free 指針指向TOSPACE的起點,從根節點開始遍歷,將根節點及其引用的子節點全部複製到TOSPACE,每複製一個對象,就把free 指針向後移動相應大小的位置,最後交換FROMSPACE和TOSPACE,大致可用如下代碼描述:

collect() {
// 变量前面加*表示指针
// free指向TOSPACE半区的起始位置
*free = *to_start;
for(root in Roots) {
copy(*free, root);
}
// 交换FROMSPACE和TOSPACE
swap(*from_start,*to_start);
}

核心函數copy 的實現如下所示:

copy(*free,obj) {
// 检查obj是否已经复制完成
// 这里的tag仅是一个逻辑上的域
if(obj.tag != COPIED) {
// 将obj真正的复制到free指向的空间
copy_data(*free,obj);
// 给obj.tag贴上COPIED这个标签
// 即使有多个指向obj的指针,obj也不会被复制多次
obj.tag = COPIED;
// 复制完成后把对象的新地址存放在老对象的forwarding域中
obj.forwarding = *free;
// 按照obj的长度将free指针向前移动
*free += obj.size;

// 递归调用copy函数复制其关联的子对象
for(child in getRefNode(obj.forwarding)) {
*child = copy(*free,child);
}
}
return obj.forwarding;
}

在這段代碼中需要注意兩個問題,其一是tag=COPIED 只是一個邏輯上的概念,用來區分對像是否已經完成複制,以確保即使這個對像被多次引用,也僅會復制一次;另外一個問題則是forwarding 域,forwarding指針在前面已經多次提到過,主要是用來保存對象移動後的新地址,比如在標記整理算法中,對象移動後需要遍歷更新對象的引用關係,就需要使用forwarding指針來查找其移動後的地址,而在復制算法中,其作用類似,如果遇到已復製完成的對象,直接通過forwarding域把對象的新地址返回即可。整個複制算法的基本致流程如下圖所示。

深入理解JVM垃圾回收算法- 複製算法 3

接下來用一個詳細的示例看看複製算法的大致流程。堆中對象的關係如下圖所示,其中free指針指向TOSPACE的起點位置。

深入理解JVM垃圾回收算法- 複製算法 4

首先,從根節點出發,找到它直接引用的對象B和E,其中對象B首先被複製到TOSPACE。 B被複製後的堆的關係如下圖所示。

深入理解JVM垃圾回收算法- 複製算法 5

這裡將B被複製後生成的對象成為B’,而原來的對象B中tag 域已經打上複製完成的標籤,而forwarding指針也存放著B’的地址。

對象B複製完成後,它引用的對象A還在FROMSPACE裡,接下來就會把對象A複製到TOSPACE中。

深入理解JVM垃圾回收算法- 複製算法 6

接下來複製從根引用的對象E,以及其引用對象B,不過因為B已經復製完成,所以只需要把從E指向B的指針換成指向B’的指針即可。

深入理解JVM垃圾回收算法- 複製算法 7

最後只要把FROMSPACE和TOSPACE互換,GC就結束了。 GC結束時堆的狀態如下圖所示。

深入理解JVM垃圾回收算法- 複製算法 8

在這兒,程序的搜索順序是按B、A、E的順序搜索對象的,即以深度優先算法來搜索的。

算法評價

複製算法主要有如下優勢:

吞吐量高:整個GC算法只搜索並複制存活對象,尤其是堆越大,差距越明顯,畢竟它消耗的時間只是與活動對像數量成正比。可實現高速分配:由於GC完成後空閒空間是一個連續的內存塊,在內存分配時,只要申請空間小於空閒內存塊,只需要移動free指針即可。相較於標記-清理算法使用空閒鍊錶的分配方式,複製算法明顯快得多,畢竟要在空閒鍊錶中找到合適大小的內存怎麼都得遍歷這個鍊錶。無碎片:沒啥好說的。與緩存兼容:可以回顧一下前面說的局部性原理,由於所有存活對像都緊密的排佈在內存裡,非常有利於CPU的高速緩存。

相較於前面的兩種GC算法,其劣勢主要有亮點:

堆空間利用率低:複製算法把堆一分為二,只有一半能被使用,內存利用率極低,這也是複制算法的最大缺陷。遞歸調用函數:複製某個對象時要遞歸複製它引用的對象,相較於迭代算法,遞歸的效率更低,而且有棧空間溢出的風險。

Cheney 複製算法

Cheney算法是用來解決如何遍歷引用關係圖並將存活對象移動到TOSPACE的算法,它使用迭代算法來代替遞歸。

還是以一個簡單的例子來看看Cheney算法的執行過程,首先還是初始狀態,在前面的例子上做了一點改動,同時有兩個指針指向TOSPACE的起點位置。

深入理解JVM垃圾回收算法- 複製算法 9

首先複製所有從根節點直接引用的對象,在這兒就是複制B和E。

深入理解JVM垃圾回收算法- 複製算法 10

這時,與根節點直接引用的對像都已經復製完畢,scan 仍然指向TOSPACE的起點,free 從起點向前移動了B和E個長度。

接下來,scan 和free 繼續向前移動,scan 的每次移動都意味著對已完成複制對象的搜索,而free 的向前移動則意味著新的對象複製完成。

還是以例子來說,在B和E完成複制以後,接著開始復制與B關聯的所有對象,這裡是A和C。

深入理解JVM垃圾回收算法- 複製算法 11

在復制A和C時,free 向前移動,等A和C複製完成以後,scan向前移動B個長度到E。接著,繼續掃描E引用的對象B,發現B已經完成複制,則scan 向前移動E個長度,free 保持不動。由於對象A沒有引用任何對象,還是scan 向前移動A個長度,free 保持不動。

深入理解JVM垃圾回收算法- 複製算法 12

接下來,繼續複製C的關聯對象D,完成D的複制以後,發現scan 和free 相遇了,則結束複製。

深入理解JVM垃圾回收算法- 複製算法 13

最後仍然是FROMSPACE和TOSPACE互換,GC結束。

代碼實現只需要在之前的代碼上稍做修改,即可:

collect() {
// free指向TOSPACE半区的起始位置
*scan = *free = *to_start;
// 复制根节点直接引用的对象
for(root in Roots) {
copy(*free, root);
}
// scan开始向前移动
// 首先获取scan位置处对象所引用的对象
// 所有引用对象复制完成后,向前移动scan
while(*scan != *free) {
for(child in getRefObject(scan)) {
copy(*free, child);
}
*scan += scan.size;
}
swap(*from_start,*to_start);
}

而copy 函數也不再包含遞歸調用,僅僅是完成複制功能:

copy(*free,obj) {
if(!is_pointer_to_heap(obj.forwarding,*to_start)) {
// 将obj真正的复制到free指向的空间
copy_data(*free,obj);
// 复制完成后把对象的新地址存放在老对象的forwarding域中
obj.forwarding = *free;
// 按照obj的长度将free指针向前移动
*free += obj.size;
}
return obj.forwarding;
}

對於is_pointer_to_heap(obj.forwarding,*to_start),如果obj.forwarding 是指向TOSPACE的指針,則返回TRUE,否則返回FALSE。這裡沒有使用tag 來區分對像是否已經完成複制,而是直接判斷obj.forwarding 指針,如果obj.forwarding 不是指針或者沒有指向TOSPACE,那麼就認為它沒有完成複制,否則就說明已經完成複制。

通過代碼可以看出,Cheney算法採用的是廣度優先算法。熟悉算法的同學可能知道,廣度優先搜索算法是需要一個先進先出的隊列來輔助的,但這兒並沒有隊列。實際上scan 和free 之間的堆變成了一個隊列,scan左邊是已經搜索完的對象,右邊是待搜索對象。 free 向前移動,隊列就會追加對象,scan 向前移動,都會有對像被取出並進行搜索,這樣一來,就滿足了先入先出隊列的條件。

下面是一個廣度優先遍曆算法的典型實現,大家可以用作對比,加深理解。

void BFS(List roots) {
// 已经被访问过的元素
List visited = new ArrayList();
// 用队列存放依次要遍历的元素
Queue queue = new LinkedList();

for (node in roots) {
visited.add(node);
process(node);
queue.offer(node);
}

while (!queue.isEmpty()) {
Node currentNode = queue.poll();
if (!visited.contains(currNode)) {
visited.add(currentNode);
process(node);
for (child in getChildren(node)) {
queue.offer(node);
}
}
}
}

對比之前的算法,Cheney算法的優點是使用迭代算法代替遞歸,避免了棧的消耗和可能的棧溢出風險,特別是拿堆空間用作隊列來實現廣度優先遍歷,非常巧妙。而缺點則是,相互引用的對象並不是相鄰的,就沒辦法充分利用緩存。注意,這裡不是說,Cheney算法無法兼容緩存,只是相較於前一種算法來說,沒有那麼好而已。

最後

複製算法還有挺多變種的,這裡沒辦法一一列舉,更多內容可以閱讀參考資料中的兩本書籍。

複製算法的最大缺陷就是堆空間利用率低,因此大多數場景下,都是與其他算法搭配使用;並且我們也不是真的會把堆空間一分為二,而是根據實際情況,合理的劃分。就比如,可以把堆空間分成10份,拿出2份空間分別作為From空間和To空間,用來執行複制算法,而剩下的8分則搭配使用標記-清理算法。

是不是又想到了JVM的新生代和老年代的區域劃分,嗯,原因就是我們所講的內容。

深入理解JVM系列的第13篇,完整目錄請移步:深入理解JVM系列文章目錄

封面圖:克里斯托弗·高爾

參考資料

垃圾回收算法手冊:自動內存管理的藝術

垃圾回收的算法與實現