GC in C++前段時間看了一些關于GC的論文、書和源碼。源碼指的是Boehm的保守GC ，論文也主要是圍繞這個GC相關的算法，另外還包括一些survey和性能分析的論文。而其他關于GC的一些東西主要是從其他兩本書上看來，一本是謝之易老大翻譯的垃圾收集 ，目前唯一一本關于GC算法的書，還有就是仔細閱讀了C# via CLR 中關于.net GC的部分。原本想做個GC算法上的總結，但前幾天在實驗室做了個關于GC in C++的介紹，發現其他的一些關于GC的基本問題比算法更需要好好分析。 關于GC in C++，g9老大已經做了一篇漂亮的概述 。我想做的就是按我的邏輯做一下梳理，歡迎大家抄板磚，^_^。
第一個問題，為什么我們需要GC？ 或者說，在C++中，GC能給我們帶來什么。很多的時候，一說起GC，就陷入一場關于性能的討論。誠然，食堂賣飯mm（or JJ, or 阿姨, or 大媽, or 婆婆...）的pp程度對胃口有很大影響，但對于一個身心正常（if 花癡 or 別用用心者 then throw btException）且饑腸轆轆的人來說，優先考慮的肯定是口味和性價比。對于GC in C++來說，等同于口味和價格的應該是以下因素： 1. 比人肉管理更簡單、安全。對于人肉內存管理Meyers對其不安全性有了很多的描述 ，通常一個大的人肉C++程序，沒有資源泄露應該是不可能的吧。而C++的new/delete模式，對于很多非C++程序員來說還是非常復雜的。如果你 做的是一個二次開發平臺，未來的開發人員很多都是非C++程序員，逼著人家了解如此這般的內存管理模式，是不人道的，也是不安全。而如果是一個全GC的程 序，安全（前提是GC器是安全的...）和易用都是手到擒來的。 2. 可理解性更好。在人肉C++中，咱都需要付出大量的精力去檢查和編寫內存管理部分，new和delete混雜在代碼當中，稍有不慎，調你個半身不遂。特別 是類似于A * GetA()這樣的接口（delete or not），沒有文檔的幫助，幾乎是不可理解的（而文檔常常又跟不上要求）。而在GC的程序中，代碼更為清晰，接口也不會存在puzzle。 所以，在你決定是否使用GC之前，先考慮一下，你是否有以上兩點需求。如果你正撐的半死或者對ppmm的渴望超過了一切，那么忘了它吧，GC不是你 碗里的菜。如果，OK，這正是你所需要的。那么接下來考慮的才是GC這盤味道不錯的菜是否也秀色可餐、才貌雙全呢？是否有其他類似的菜也讓我蠢蠢欲動了。 換成地球人的語言就是說，GC的效率、可兼容性等等其他方面如何？有沒有其他的方案，也滿足上面兩點需求，并且在其他方面也表現不凡？
第二個問題，我們為什么害怕GC？ 拒絕GC的理由，往往不是以上兩個原因。之所以要詳細的說上面那些，是因為很多人在考慮下面的問題的時候，經常忘記了上面這些巨大的好處（Maybe...include me），而掉進了某個井中癡癡的望著天空。恩...這樣的井應該包括以下這些： 1. GC的效率低下 2. GC的內存占用率高 3. Stop-the-world的工作模式很可怕 4. 把內存管理這樣的大事交給GC不安全 5. 無法與人肉管理的代碼兼容 6. 內存回收不夠及時 7. 其他我不知道的... （排名不分先后^_^） 這些都是人們害怕，或拒絕使用GC的原因。如果考慮一個最最簡單的GC模型，可能以上這些問題都存在。但是，GC已經被研究了N多年，光GC in C++都被研究超過了20年。三日不見，當刮目相看，何況是如此多年，女大也該十八變了。 首要需要解決的問題應該就是分配效率。GC的分配性能一般都考量分攤性能，通常基于追蹤的垃圾收集算法，都會是分配快回收慢。基于縮并的（即可移動 的一種）內存分配，比如.net的GC分配都是常量級的損耗，而基于非移動的，由于有冗余，一般也不會慢。關鍵在于事后追蹤的時間會比較長。在Boehm 的GC中，很多的算法都是出于提高標記效率，這種提高不只是從算法復雜度上考慮（代齡可以看成是優化標記復雜度的做法），更多的是從缺頁率和cache miss率上來提高。在92年zorn對Boehm GC做的一篇評測中可以看到（現在的GC在分配效率、丟頁率和cache miss率上都應該會有更好的表現，但找不到相關paper×_×），哪怕保守GC分配效率也是非常出色的了。而云風前輩在網易游戲中的GC應用 ，可以看成是特定GC的設計之道（不能做通用庫用，但實現簡單），我相信這會有更好的效率表現。特別是隨著多核的普及，基于并發的GC 算法效率更是出類拔萃。所以，分配效率（當然，只能說在大部分的應用場合）不會成為拒絕的理由。 但我想內存占用率會成為一個問題（2、6其實是差不多的問題，占用率高主要就是預分配和延交還）。從zorn的那篇評測可以看到，Beohm GC在內存占用率方面是一般人肉分配器的一倍左右。其實，仔細思考一下GC的原理就可以理解，沒有內存的冗余，幾乎做不成GC的（分配一次起一次GC，還 算GC么？），當然操作系統有時也作冗余（查找表），但應該會比GC做的保守的多。盡管如此，但我覺得如此大的內存占用率是和Boehm GC的分配器相關，由于是用的Mark-Sweep（標記清掃，非移動的GC算法）算法，可能會出現內存空洞（一大塊內存被少量真實使用內存占據，其他部 分不能被不等大的對象使用），并且由于是對齊到2^n的邊界再分配，這里就可能會有約為50%的內存損失。因此，我想如果改善該內存分配器（我們有必要做 內存分配器嗎？當然，因為我們在托管堆上分配，操作系統已有的分配器再好，對我們也沒有幫助），應該有一定的內存占用率降低。并且，如果采用的是Mark -Compact（標記縮并算法，比如.net GC）不會有對齊的損失，冗余的內存塊可以更好滿足虛擬內存的模式（不用的放一起，用的放一起），這樣應該也會降低內存占用率。 Stop-the-world是大部分主流GC都會出現的情況（對，基于計數的GC不會有這個問題，但是...），在某些場合（高交互性？）可能會 成為一個大問題。個人覺得這也是一個不可避免的問題，就像你不可能用跑一百米的速度跑1w一樣（你100m跑2'？OK...算我沒說）。但是，大牛們做 了很多工作來降低這種停頓。在Boehm GC中，就有延遲清掃、并行、代齡等手段。而.net GC更把一次GC啟動的停頓的目標設在1ms，也就是一個缺頁的損失，不知道實測的情況是否能達到。如果能的話，我想大部分情況都可以忍受了吧。 內存交給GC安全么？恩，在C++中這是個問題。因為C++在運行期無法進行類型的識別，就這一條害得N多大牛一碗一碗的吐血的問題。Boehm為 此可以說是無招不用，但無論如何，在理論上都不可能杜絕GC犯錯的可能（除非有程序員的幫助^_^）。但我想，這年頭，最不安全的還是人本身吧*_^。 兼容性的問題。恩...一個大問題。先舉個例子（It's real...）。在項目中，有一部分內存是人肉分配，有另一部分是GC分配。當棧中一個非GC對象指向堆中一個非GC對象時，這個堆對象不會被掃描（因 為棧中對象所指地址GC不可識別），如果這個堆對象指向另外一個托管堆中的GC對象（并且沒有別人再引用），這個對象不會被Mark，也就是說GC起來會 把它給收了，這就導致可怕的結果（當...程序Game over了）。為了避免這種情況，最好的辦法是要保證所有對象并處于可追蹤或可回收的狀態。在源碼可改的狀況下，理論只要重載所有相關的分配器就可以了 （包括全局的，重載的，STL的...）。但有一個問題我想不清楚，如果是多根的情況（比如一個MFC程序，所有類派生自CObject），就是可以修改 源碼，這個問題也不好解決（CObject的分配器可關么？請教ing...），更不提其他源碼不受控的情況了（看看g9老大列舉的吧...但解決之道一 樣，保證處于兩個狀態下）。 最后，我們拿另一盤可選的菜，計數指針來比較一下。俗話說，不怕不識貨就怕貨比貨。其實把計數指針放在這做比較有點不公平，因為它不能提供GC能夠 提供的最基本的好處（味道有點酸酸的...），因為它易用性不足夠強（指針不是人，不會自覺的穿衣服...），也會把代碼搞亂。從效率上看，計數指針直接 Game Over，但從內存利用率和延遲性來看，計數指針會好一些。安全性上，計數指針還是依靠人；兼容性上，半斤對八兩。So，兩個東西不用拼得你死我活，你走 你的陽關道我過我的獨木橋就好（不過我一點多不覺得同時使用它們是一個好主意...）。
第三個問題，C++中需要GC么？ 至此我們可以總結一下。應用GC的好處是可以提供更安全的、更可理解的代碼，并且不需要付出太多額外的代價，內存管理也更為簡單。其缺點包含，可能會有的分配性能較低，內存占用率更多，停頓依然不可完全避免，還存在一些安全隱患，不是和老C++如此親密無間。 然后，我們需要在C++中用GC么。這分兩個步驟來回答，首先我們需要C++做一些項目，這些項目不適合用其他語言來做；另外，在這些項目中我們可以忍受上述缺點，并很需要上述優點。存在這樣的項目么？看一些g9老大的blog和Boehm GC的應用狀況吧。 大部分時候，我們把GC的應用局限在了做內存管理上，其實GC的使用方法很多。你可以在項目的某個部分用GC管理內存，你可以用GC作泄漏檢測器，甚至你可以用GC作Debugger。這樣一來，C++中就更需要GC了。
第四個問題，GC進C++0x有什么好處？ 看了上面的內容，這個問題基本成了廢話。我們在C++中用GC怕什么？上述那些缺點吧。GC進C++0x有什么好處？它能解決上述大部分缺點（效率、安全、兼容性），因為這些缺點本不屬于GC，只屬于GC in C++。
第五個問題，我們需要怎樣的GC進C++0x？ 大致看了一遍GC的Proposes，看的出來，老大們為了GC進C++0x花了很多力氣，有興趣的自己可以查看一下。個人感覺GC進C++0x可以從三個方面來考量。一個是庫，一個是編譯器，一個是語法支持。 我覺得GC庫是最基本的，Boehm GC算是一個標準，基于復制的庫也可以考察。但如果沒有任何編譯器層面的調整的話，所有的GC庫都還會存在上面那些問題。在編譯期層面上的支持，最可能的就像云風前輩設想的那樣， 提供一個編譯開關，當GC開啟的時候，將對象變為運行時可識別類型的，這將會完成保證GC（指純GC）的安全性，并大大提高效率（手動設置原子類也可以， 但這畢竟增加了編寫的負擔）。如果不存在和老代碼兼容，且只想搭建一個純GC的C++程序（或庫）的話，這是非常可行的（當然，會付出更多內存的代價）。 但最不理想的情況就是存在于人肉C++交互的情況，老大們想出了一堆關鍵字和使用方法其實都只針對這種情況（如果不存在這種情況，幾乎不用提供新的 關鍵字，且只需要擴展new和finalization相關的函數就好），當然這會在使用上帶來更為復雜的情況。但是，只要你不愿意，你可以不用GC，因 為一切都是可選的。 所以，我覺得目前GC進C++0x的方式還是很好的。大部分情況滿足需求，如果有少量與老家伙們交互的情況已經可以應付了，再如果有更復雜的情況出現，不使用GC，這個世界就還是很原來一樣了。
PS：Sutter老大說GC在C++0x的基本狀況是：
Garbage collection:
For C++0x, we're not going to add explicit support for garbage
collection, and only intend to find ways to remove blocking issues like
pointer hiding that make it difficult to add garbage collection in a
C++ implementation. In particular, the scope of this feature is
expected to be constrained as follows: 你覺得呢？
文獻列表：
[Boehm, 1992] A proposal for garbage collector safe C Compilation. [a] 解釋了為什么在C編譯器開啟優化時，保守垃圾收集為什么是不安全的。這種不安全主要來自于對指針的判定，編譯器有時會采取一些極端手段來處理指針，以達到 最優效率，導致指針的特征不明顯。文中還提出了避免了這種不安全需要注意的內容。在實際實現的時候用到了Blacklist的技術。 [Boehm, 2002] Bounding space usage of conservative garbage collectors. [a] 為了避免判定指針失誤，保守垃圾收集器需要用很大的空間來判定指針，為了將此利用率限定在一定范圍內，本文提出了弱健壯性的概念，即對指針的使用進行一定的限定從而可將利用率限定在一定范圍內，作者做出了數學證明。 [Boehm, 2000] Fast Multiprocessor Memory Allocation and Garbage Collection. [a] 對Boehm GC在多線程多處理器上的回收實現以及表現進行了詳盡的分析和比較。 [Boehm, 1988] Garbage collection in an uncooperative environment. [a] 對Boehm GC的基本算法，概念做了詳盡的介紹。 [Boehm, 1993] Space Efficient Conservative Garbage Collection. [a] 對如何進行高效的指針掃描和判定進行了分析，討論了可能出現的指針判定錯誤，已經采取的策略。 [Boehm, 1996] Simple garbage collector safety. [a] 討論了在編譯器層面上導致的垃圾回收不安全問題。 [Boehm, 2000] Reducing garbage collector cache misses. [a] 介紹Boehm GC中提高Cache命中率所采用的方法。 [Henderson, 2002] Accurate garbage collection in an uncooperative environment. [a] 在Boehm的GC為代表的保守GC中，需要遍歷棧和寄存器來判定根指針。而這種判定沒有任何的類型保證，存在判定失誤導致內存溢出的危險。為了避免這種 危險，本文從另一個角度出發，在編譯器生成C代碼的階段，為C代碼添加GC相關的信息，使得棧中的指針可以更精確的被辨識。 [Ellis, 1993] Safe, efficient garbage collection for C++. [a] 介紹了一種GC in C++的方法，并概述了一下之前的相關工作，比較詳盡。 [Wilson, 1992] Uniprocessor Garbage Collection Techniques. [a] 一篇Survey，介紹了幾種基本的垃圾回收算法，和漸進、代齡技術。 [Hertz, 2005] Garbage Collection Without Paging [a] 提出了減少分頁的垃圾回收算法。 [Berger, 2000] Hoard: A Scalable Memory Allocator for Multithreaded Applications. [a] 介紹一種多處理器多線程的內存分配器。 [Hertz, 2005] Quantifying the performance of garbage collection vs. explicit memory management. [a] 垃圾收集與人肉回收的性能比較。
|
|
|
