垃圾回收算法優缺點對比
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 的運行。
增量式垃圾回收適合那些比起提高吞吐量,更重視縮短最大暫停時間的應用程序。
②降低了吞吐量
想要優先提高吞吐量,最大暫停時間就會增加;想要優先縮短最大暫停時間, 吞吐量就會惡化。這兩者是一個權衡關係。至於要優先哪一方,則要根據應用程序而定。
參考文獻:《垃圾回收的算法與實現》
個人介紹:
高廣超:多年一線互聯網研發與架構設計經驗,擅長設計與落地高可用、高性能、可擴展的互聯網架構。
本文首發在 高廣超的簡書博客 轉載請註明!
閱讀更多 互聯網技術棧 的文章