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