垃圾回收算法優缺點對比

GC之前

說明：該文中的GC算法講解不僅僅侷限於某種具體開發語言。

mutator

mutator 是 Edsger Dijkstra 、 琢磨出來的詞，有“改變某物”的意思。說到要改變什麼，那就是 GC 對象間的引用關係。不過光這麼說可能大家還是不能理解，其實用一句話概括的話，它的實體就是“應用程序”。這樣說就容易理解了吧。GC 就是在這個 mutator 內部精神飽滿地 工作著。

mutator 實際進行的操作有以下 2 種。

• 生成對象

• 更新指針

mutator 在進行這些操作時，會同時為應用程序的用戶進行一些處理(數值計算、瀏覽網頁、 編輯文章等)。隨著這些處理的逐步推進，對象間的引用關係也會“改變”。伴隨這些變化會 產生垃圾，而負責回收這些垃圾的機制就是 GC。

活動對象 / 非活動對象

我們將分配到內存空間中的對象中那些能通過 mutator 引用的對象稱為“活動對象”。反 過來，把分配到堆中那些不能通過程序引用的對象稱為“非活動對象”。

根

根(root)這個詞的意思是“根基”“根底”。在 GC 的世界裡，根是指向對象的指針的“起點” 部分。

這些都是能通過 mutator 直接引用的空間。

評價標準

評價 GC 算法的性能時，我們採用以下 4 個標準。

• 吞吐量

• 最大暫停時間

• 堆使用效率

• 訪問的局部性

其他信息（Java語言為例）：JVM解讀-GC（垃圾回收）

---

1 標記-清除法

優點

①實現簡單

說到 GC 標記 - 清除算法的優點，那當然要數算法簡單，實現容易了。

另外，如果算法實現簡單，那麼它與其他算法的組合也就相應地簡單。

②與保守式 GC 算法兼容

後面介紹的保守式 GC 算法中，對象是不能被移動的。因此保守式 GC 算法跟把 對象從現在的場所複製到其他場所的 GC 複製算法與標記 - 壓縮算法不兼容。

而 GC 標記 - 清除算法因為不會移動對象，所以非常適合搭配保守式 GC 算法。事實上，在很多采用保守式 GC 算法的處理程序中也用到了 GC 標記 - 清除算法。

缺點

①碎片化

在 GC 標記 - 清除算法的使用過程中會逐漸產生被細化的分塊，不久後就會導致無數的 小分塊散佈在堆的各處。我們稱這種狀況為碎片化(fragmentation)。眾所周知，Windows 的 文件系統也會產生這種現象。

image.png

②分配速度

GC 標記 - 清除算法中分塊不是連續的，因此每次分配都必須遍歷空閒鏈表，找到足夠 大的分塊。最糟的情況就是每次進行分配都得把空閒鏈表遍歷到最後。

另一方面，因為在 GC 複製算法和 GC 標記 - 壓縮算法中，分塊是作為一個連續的內存 空間存在的，所以沒必要遍歷空閒鏈表，分配就能非常高速地進行，而且還能在堆允許範圍 內分配很大的對象。

③與寫時複製技術不兼容

寫時複製技術(copy-on-write)是在 Linux 等眾多 UNIX 操作系統的虛擬存儲中用到的高速化方法。在 Linux 中複製進程，也就是使用 fork() 函數時，大部分內存空間都不會被複制。只是複製進程，就複製了所有內存空間的話也太說不過去了吧。因此，寫時復 制技術只是裝作已經複製了內存空間，實際上是將內存空間共享了。

在各個進程中訪問數據時，能夠訪問共享內存就沒什麼問題了。

然而，當我們對共享內存空間進行寫入時，不能直接重寫共享內存。因為從其他程序訪 問時，會發生數據不一致的情況。在重寫時，要複製自己私有空間的數據，對這個私有空間 進行重寫。複製後只訪問這個私有空間，不訪問共享內存。像這樣，因為這門技術是“在寫 入時進行復制”的，所以才被稱為寫時複製技術。

這樣的話，GC 標記 - 清除算法就會存在一個問題 — 與寫時複製技術不兼容。即使沒 重寫對象，GC 也會設置所有活動對象的標誌位，這樣就會頻繁發生本不應該發生的複製， 壓迫到內存空間。

2 引用計數的算法

優點

①可即刻回收垃圾

在引用計數法中，每個對象始終都知道自己的被引用數(就是計數器的值)。當被引用數 的值為 0 時，對象馬上就會把自己作為空閒空間連接到空閒鏈表。也就是說，各個對象在變成垃圾的同時就會立刻被回收。

另一方面，在其他的 GC 算法中，即使對象變成了垃圾，程序也無法立刻判別。只有當 分塊用盡後 GC 開始執行時，才能知道哪個對象是垃圾，哪個對象不是垃圾。也就是說，直 到 GC 執行之前，都會有一部分內存空間被垃圾佔用。

②最大暫停時間短

在引用計數法中，只有當通過 mutator 更新指針時程序才會執行垃圾回收。也就是說， 每次通過執行 mutator 生成垃圾時這部分垃圾都會被回收，因而大幅度地削減了 mutator 的最 大暫停時間。

③沒有必要沿指針查找

引用計數法和 GC 標記 - 清除算法不一樣，沒必要由根沿指針查找。減少沿指針查找的次數。

缺點

①計數器值的增減處理繁重

在引用計數法中，每當指針更新時，計數器的值都會隨之更新，因此值的增減處理必然會變得繁重。

②計數器需要佔用很多位

用於引用計數的計數器最大必須能數完堆中所有對象的引用數。

③實現煩瑣複雜

引用計數的算法本身很簡單，但事實上實現起來卻不容易。如果漏掉了某處，內存管理就無法正確 進行，就會產生 BUG。

④循環引用無法回收

兩個對象互相引用，所以各對象的計數器的值都是 1。但是這些對象 組並沒有被其他任何對象引用。因此想一併回收這兩個對象都不行，只要它們的計數器值都 是 1，就無法回收。

3 GC 複製算法

優點

①優秀的吞吐量

GC 標記 - 清除算法消耗的吞吐量是搜索活動對象(標記階段)所花費的時間和搜索整體 堆(清除階段)所花費的時間之和。

另一方面，因為 GC 複製算法只搜索並複製活動對象，所以跟一般的 GC 標記 - 清除算 法相比，它能在較短時間內完成 GC。也就是說，其吞吐量優秀。

尤其是堆越大，差距越明顯。GC 標記 - 清除算法在清除階段所花費的時間會不斷增加， 但 GC 複製算法就不會產生這種消耗。畢竟它消耗的時間是與活動對象的數量成比例的。

②可實現高速分配

GC 複製算法不使用空閒鏈表。這是因為分塊是一個連續的內存空間。比起 GC 標記 - 清除算法和引用計數法等使用空閒鏈表的分配，GC 複製算法明顯快得多。

③不會發生碎片化

基於算法性質，活動對象被集中安排在 From 空間的開頭對吧。像這 樣把對象重新集中，放在堆的一端的行為就叫作壓縮。在 GC 複製算法中，每次運行 GC 時 都會執行壓縮。

因此 GC 複製算法有個非常優秀的特點，就是不會發生碎片化。也就是說，可以安排分 塊允許範圍內大小的對象。

④與緩存兼容

在 GC 複製算法中有引用關係的對象會被安排在堆裡離彼此較近的位置。這種情況有一個優點，那就是 mutator 執行速度極快。這也是藉助壓縮來完成的，通過壓縮來把有引用關係的對 象安排在堆中較近的位置。

缺點

①堆使用效率低下

GC 複製算法把堆二等分，通常只能利用其中的一半來安排對象。也就是說，只有一半 堆能被使用。相比其他能使用整個堆的 GC 算法而言，可以說這是 GC 複製算法的一個重大的缺陷。

通過搭配使用 GC 複製算法和 GC 標記 - 清除算法可以改善這個缺點。

②不兼容保守式 GC 算法

GC 標記 - 清除算法有著跟保守式 GC 算法相兼容的優點。因 為 GC 標記 - 清除算法不用移動對象。

另一方面，GC 複製算法必須移動對象重寫指針，所以有著跟保守式 GC 算法不相容的 性質。

③遞歸調用函數

在這裡介紹的算法中，複製某個對象時要遞歸複製它的子對象。因此在每次進行復制的 時候都要調用函數，由此帶來的額外負擔不容忽視。大家都知道比起這種遞歸算法，迭代算 法更能高速地執行

此外，因為在每次遞歸調用時都會消耗棧，所以還有棧溢出的可能。

4 GC標記-壓縮算法

優點

①可有效利用堆

在 GC 標記 - 壓縮算法中會執行壓縮，和其他算法相比而言，堆利用效率高。

而且 GC 標記 - 壓縮算法不會出現 GC 複製算法那樣只能利用半個堆的情況。

另一方面，儘管 GC 標記 - 清除算法也能利用整個堆，但因為沒有壓縮的過程，所以會 產生碎片化，不能充分有效地利用堆。

缺點

①壓縮花費計算成本

在 GC 標記 - 清除算法中，清除階段也要搜索整個堆，不過搜索 1 次就夠了。但 GC 標記 - 壓縮算法要搜索 3 次，這樣就要花費約 3 倍的時間，這是一個相當巨大的缺陷，特別是堆越 大，所消耗的成本也就越大。

4 保守式 GC

什麼是保守式 GC

簡單來說，保守式 GC(Conservative GC)指的是“不能識別指針和非指針的 GC”。

優點

①語言處理程序不依賴於 GC

保守式 GC 的優點在於容易編寫語言處理程序。處理程序基本上不用在意 GC 就可以編 寫代碼。語言處理程序的實現者即使沒有意識到 GC 的存在，程序也會自己回收垃圾。因此 語言處理程序的實現要比準確式 GC 簡單。

缺點

①識別指針和非指針需要付出成本

②錯誤識別指針會壓迫堆

當存在貌似指針的非指針時，保守式 GC 會把被引用的對象錯誤識別為活動對象。如果 這個對象存在大量的子對象，那麼它們一律都會被看成活動對象。因為程序把已經死了的非 活動對象看成了活動對象，所以垃圾對象會嚴重壓迫堆。

③能夠使用的 GC 算法有限

5 分代垃圾回收

優點

①吞吐量得到改善

通過使用分代垃圾回收，可以改善 GC 所花費的時間(吞吐量)。正如 Ungar 所說的那樣:“據實驗表明，分代垃圾回收花費的時間是 GC 複製算法的 1/4。”可見分代垃圾 回收的導入非常明顯地改善了吞吐量。

另一方面，因為老年代 GC 很費時間，所以我們沒法縮短 mutator 的最大暫停時間。關 於使用分代垃圾回收來縮減 mutator 最大暫停時間的方法

缺點

①在部分程序中會起到反作用

對對象會活得很久的程序執行分代垃圾回收，就會產生以下兩個問題。

• 新生代GC所花費的時間增多

• 老年代GC頻繁運行

考慮到這兩點，恐怕我們沒法利用到分代垃圾回收的優點，或者就算利用到了，效果也 甚微。

6 增量式垃圾回收

優點

①縮短最大暫停時間

增量式垃圾回收不是一口氣運行 GC，而是和 mutator 交替運行的，因此不會長時間妨礙 到 mutator 的運行。

增量式垃圾回收適合那些比起提高吞吐量，更重視縮短最大暫停時間的應用程序。

②降低了吞吐量

想要優先提高吞吐量，最大暫停時間就會增加;想要優先縮短最大暫停時間， 吞吐量就會惡化。這兩者是一個權衡關係。至於要優先哪一方，則要根據應用程序而定。

參考文獻：《垃圾回收的算法與實現》

---

個人介紹：

高廣超：多年一線互聯網研發與架構設計經驗，擅長設計與落地高可用、高性能、可擴展的互聯網架構。

本文首發在 高廣超的簡書博客 轉載請註明！