前言
這是原來寫過的一篇文章，看到知乎的讀者比較多，故搬運到此處。
我們已經對虛幻4中的反射實作原理進行了一個簡單得講解，反射的用途非常多，其中一個就是用來做垃圾回收用的，我們這個系列就對虛幻4中的垃圾回收機制做一個講解。注：本系列文章對應的虛幻4版本是4.14.1
垃圾回收在計算機科學中，垃圾回收（garbage collection, 縮寫GC）是一種自動的記憶體管理機制。當一個電腦上的動态記憶體不需要時，就應該予以釋放，這種自動記憶體的資源管理，稱為垃圾回收。垃圾回收可以減少程式員的負擔，也能減少程式員犯錯的機會。最早起源于LISP語言。目前許多語言如Smalltalk、Java、C#、python和D語言等都支援垃圾回收。
下面我們簡單的介紹下垃圾回收常見的分類以及實作算法，我們并不會特别細緻的去講，如果讀者有興趣可以自行查找相關的書籍和文獻。推薦大家看下參考文獻中2的文章。
算法分類 引用計數GC和追蹤式GC引用計數式GC通過額外的計數來實時計算對單個對象的引用次數，當引用次數為0時回收對象。引用計數的GC是實時的。像微軟COM對象的加減引用值以及C++中的智能指針都是通過引用計數來實作GC的。
追蹤式GC算法在達到GC條件時（強制GC或者記憶體不夠用、到達GC間隔時間）通過掃描系統中是否有對象的引用來判斷對象是否存活，然後回收無用對象。
保守式GC和精确式GC精确式GC是指在回收過程中能準确得識别和回收每一個無用對象的GC方式，為了準确識别每一個對象的引用，通過需要一些額外的資料（比如虛幻中的屬性UProperty）。
保守式GC并不能準備識别每一個無用的對象（比如在32位程式中的一個4位元組的值，它是不能判斷出它是一個對象指針或者是一個數字的），但是能保證在不會錯誤的回收存活的對象的情況下回收一部分無用對象。保守式GC不需要額外的資料來支援查找對象的引用，它将所有的記憶體資料假定為指針，通過一些條件來判定這個指針是否是一個合法的對象。
搬遷式和非搬遷式搬遷式GC在GC過程中需要移動對象在記憶體中的位置，當然移動對象位置後需要将所有引用到這個對象的地方更新到新位置（有的通過句柄來實作、而有的可能需要修改所有引用記憶體的指針）。
非搬遷式GC跟搬遷式GC正好相關，在GC過程中不需要移動對象的記憶體位置。
實時和非實作GC實時GC是指不需要停止使用者執行的GC方式。而非實時GC則需要停止使用者程式的執行（stop the world）。
漸進式和非漸進式GC和實時GC一樣不需要中斷使用者程式運作，不同的地方在于漸進式GC不會在對象抛棄時立即回收占用的記憶體資源，而在GC達成一定條件時進行回收操作。
回收算法 引用計數式引用計數算法是即時的，漸近的，對于互動式和實時系統比較友好，因為它幾乎不會對使用者程式造成明顯的停頓
優點：
- 引用計數方法是漸進式的，它能及時釋放無用的對象，将記憶體管理的的開銷實時的分布在使用者程式運作過程中。
缺點：
- 引用計數方法要求修改一個對象引用時必須調整舊對象的引用計數和新對象的引用計數，這些操作增加了指針複制的成本，在總體開銷上而言通常比追蹤式GC要大。
- 引用計數要求額外的空間來儲存計數值，這通常要求架構和編譯器支援。
- 實際應用中很多對象的生命周期很短，頻繁的配置設定和釋放導緻記憶體碎片化嚴重。記憶體碎片意味着可用記憶體在總數量上足夠但由于不連續因而實際上不可用，同時增加記憶體配置設定的時間。
- 引用計數算法最嚴重的問題是環形引用問題（當然可以通過弱指針來解決）。
追蹤式GC算法通過遞歸的檢查對象的可達性來判斷對象是否存活，進而回收無用記憶體。
追蹤式的GC算法的關鍵在于準确并快速的找到所有可達對象，不可達的對象對于使用者程式來說是不可見的，是以清掃階段通常可以和使用者程式并行執行。下面主要讨論了算法的标記階段的實作。
标記清掃（Mark-Sweep）标記清掃式GC算法是後面介紹的追蹤式GC算法的基礎，它通過搜尋整個系統中對對象的引用來檢查對象的可達性，以确定對象是否需要回收。
分類：追蹤式，非實時，保守(非搬遷式)或者精确式(搬遷式) ，非漸進
優點：
- 相對于引用計數算法，完全不必考慮環形引用問題。
- 操縱指針時沒有額外的開銷。
- 與使用者程式完全分離。
缺點：
- 标記清掃算法是非實時的，它要求在垃圾收集器運作時暫停使用者程式運作，這對于實時和互動式系統的影響非常大。
- 基本的标記清掃算法通常在回收記憶體時會同時合并相鄰空閑記憶體塊，然而在系統運作一段時間後仍然難免會生成大量記憶體碎片，記憶體碎片意味着可用記憶體的總數量上足夠但實際上不可用，同時還會增加配置設定記憶體的時間，降低記憶體通路的效率。
- 保守式的标記清掃算法可能會将某些無用對象當做存活對象，導緻記憶體洩露。
使用者程式初始化時向系統預申請一塊記憶體，新的對象申請在此區域内配置設定, 使用者程式不需要主動釋放己配置設定的空間，當達到回收條件，或者使用者程式主動請求時開始收集記憶體。
标記清掃式GC算法（mark-sweep）分為兩個階段: 标記階段 和 清掃階段。
标記階段從根結點集合開始遞歸的标記所有可達對象。
根結點集合通常包括所有的全局變量，靜态變量以及棧區(注2)。這些資料可以被使用者程式直接或者間接引用到。
标記前：
标記後：
周遊所有對象，将沒有标記為可達的對象回收，并清理标記位。
保守式的标記清掃算法:
保守式的标記清掃算法缺少對象引用的記憶體資訊（事實上它本身就為了這些Uncooperative Environment設計的）,它假定所有根結點集合為指針，遞歸的将這些指針指向的記憶體堆區标記為可達,并将所有可達區域的記憶體資料假定為指針，重複上一步，最終識别出不可達的記憶體區域，并将這些區域回收。
保守式的GC算法可能導緻記憶體洩漏。由于保守式GC算法沒有必需的GC資訊，是以必須假設所有記憶體資料是一個指針，這很可能将一個非指針資料當作指針，比如将一個整型值當作一個指針，并且這個值碰巧在已經配置設定的堆區域位址範圍内，這将會導緻這部分記憶體被标記為可達，進而不能被回收。
保守式的GC不能确定一個記憶體上資料是否是一個指針，是以不能移動對象的位置。
實際應用：
保守式标記清掃GC算法： Boehm-Demers-Weiser 算法
精确式标記清掃算法：UE3, UE4等
由于我們并不是主要介紹GC算法的，是以接下來我們不打算對其它的GC算法進行細講，讀者可以參考參考文獻中第2篇文章或者看垃圾回收的算法與實作這本書，内容比較全面。
标記縮并有些情況下記憶體管理的性能瓶頸在配置設定階段，記憶體碎片增加了查找可用記憶體區域的開銷，标記縮并算法就是為了處理記憶體碎片問題而産生的。
分類：追蹤式，非實時，精确式，搬遷式，非漸進
節點複制節點複制GC通過将所有存活對象從一個區移動到另一個區來過濾非存活對象。
分類：追蹤式，非實時，精确式，搬遷式，非漸進
分代式GC（Generational Garbage Collection）在程式運作過程中，許多對象的生命周期是短暫的，配置設定不久即被抛棄。是以将記憶體回收的工作焦點集中在這些最有可能是垃圾的對象上，可以提高記憶體回收的效率，降低回收過程的開銷，進而減少對使用者程式的中斷。
分代式GC每次回收時通過掃描整個堆中的一部分而是不是全部來降低記憶體回收過程的開銷。
分類：追蹤式，非實時，精确式，搬遷式，非漸進
實際應用：Java, Ruby
漸進式GC漸進式GC要解決的問題是如何縮短自動記憶體管理引起的中斷，以降低對實時系統的影響。
漸進式GC算法基于分代式GC算法，它的核心在于在使用者程式運作過程中維護年輕分代的根結點集合。
分類：追蹤式，非實時，精确式，搬遷式，漸進式
實際應用：Java, Ruby
虛幻4 中的GC通過上面我們簡單的對GC分類和算法的講解，再結合虛幻4 的代碼，我們可以确定它的GC是追蹤式、非實時、精确式，非漸近、增量回收（時間片）。下面我們就從它的UML圖、執行流程以及部分代碼講起。
虛幻4中GC的入口是CollectGarbage()，讓我們來看一下它的函數原型以及定義
/**
從這段代碼中我們可以得到如下資訊，它是增量式的（bPerformFullPurge）,非實時的（gc 鎖），最後調用了CollectGarbageInternal來執行真正的垃圾回收操作。
CollectGarbageInternal流程通過看下面的流程圖，我們便可以知道虛幻4垃圾回收就是像我們上面所說的那樣，分為标記删除階段，隻不過它多了一個簇（cluster）和增量回收的，而增量回收是為了避免垃圾回收時導緻的卡頓的，提出簇的概念是為了提高回收的效率的。
虛幻4 中垃圾标記階段是通過FRealtimeGC類中的PerformReachabilityAnalysis()函數來完成标記的。
/**
我們可以看到，它首先會調用MarkObjectsAsUnreachable()來把所有不帶KeepFlags标記和EinternalObjectFlags::GarbageCollectionKeepFlags标記的對象全部标記為不可達，并把它們添加到ObjectsToSerialize中去。這個函數會判斷目前的FUObjectItem::GetOwnerIdnex()是否為0，如果為0那麼它就是一個普通物體也就意味着不在簇（cluster）中。把所有符合條件的對象标記為不可達後，然後會調用下面的代碼來進行可達性标記。
下面我們來詳細講解标記的過程，這裡會牽扯到我們前面提到的UProperty和UClass也就是我們需要利用反射資訊來進行可達性的标記。看上面的調用，有幾個比較重要的對象TFastReferenceCollector、FGCReferenceProcessor、以及FGCCollector，下面我們來分别介紹下下面幾個類。
TFastReferenceCollectorCollectReferences用于可達性分析，如果是單線程的話就調用ProcessObjectArray()周遊UObject的記号流（token stream ）來查找存在的引用，否則會建立幾個FCollectorTask來處理，最終調用的還是ProcessObjectArray()函數來處理。下面我們來仔細來講解一下這個函數。
它會周遊InObjectsToSerializeArray中的UObject對象，然後根據這個類的UClass拿到它的FGCReferenceTokenStream，如果是單線程且bAutoGenerateTokenSteram為true，且沒有産生token stream,那麼會調用AssembleReferenceTokenStream()來生成，代碼如下所示：
// Make sure that token stream has been assembled at this point as the below code relies on it.
然後它會根據目前的ReferenceTokenSteramIndex來擷取FGCReferenceInfo，然後根據它的類型來做相應的操作，代碼如下所示：
TokenStreamIndex
在這個處理的過程中，如果新加入的對象資料大于一定數量（MinDesiredObjectsPerSubTask）且是多線程處理，那麼就會按需建立一些新的TGraphTask<FCollectorTask>來并行處理引用問題，那麼這就是一個遞歸的過程了。具體的代碼讀者可以自行去閱讀，這裡就不展開去講了。
還記得我們前面一起提到的就是，反射資訊用于GC嗎？UClass::AssembleReferenceTokenStream()函數就是用生成記号流（token steam，其實就是記錄了什麼地方有UObject引用），它有一個CLASS_TokenStreamAssembled來儲存隻需要初始化一次。
這裡我們隻留一部分的代碼，讀者可以自行檢視AssembleReferenceTokenStream()的定義：
void
注意，我這裡省去了一些代碼，其它的大緻的邏輯就是如果沒有建立token stream或者要強制建立（需要清空ReferenceTokenSteam），那麼就會周遊自身的所有屬性，然後對每個UProperty調用EmitReferenceInfo()函數，它是一個虛函數，不同的UProperty會實作它，如果它有父類（GetSuperClass()），那麼就會調用父類的AssembleReferenceTokenStream()并把父類的添加到數組的前面，同時會處理GCRT_EndofStream的特殊情況，最後加上GCRT_EndOfStream到記号流裡面去，并設定CLASS_TokenStreamAssembled标記。
下面我們來看一個UObjectProperty::EmitReferenceInfo的實作，其它的UArrayProperty、UStructProperty等讀者可自行檢視。
/**
處理由TFastReferenceCollector查找到的UObject引用。
上面的流程圖中提到了簇的概念，那麼它是用來幹什麼的呢，我們上面說過它是為了提高GC性能的。我們接下來就來看下簇的概念。
下面我們來看一下UObject的繼承關系，其中跟Cluster相關的幾個函數在UObjectBaseUtility中，如下圖所示：
可以看到，它們都是虛函數，可以被重載，目前來看可以作為簇根（CanBeClusterRoot）的隻有UMaterial和UParticleSystem這兩個類，而基本上所有的類都可以在簇中（CanBeInCluster），而建立簇是通過CreateCluster來完成的，當然建立簇需要一定的條件，比如我們的CreateClusterFromPackage的函數定義為：
/** Looks through objects loaded with a package and creates clusters from them */
FPlatformProperties::RequiresCookedData()代表需要cook好的資料，是以編輯器模式下不會使用簇來GC。
接下來我們看一下CreateCluster()函數的定義：
void
可以看到它也使用了TFastReferenceCollector，隻不過這次的模闆參數為FClusterReferenceProssor和TCusterCollector，這裡我們就不展開去講了，讀者可以自行閱讀代碼。
FGCCollector這個類如下圖所示是繼承自FReferenceCollector，HandleObjectReference()和HandleObjectReferences()都調用了FGCReferenceProcessor的HandleObjectReference()方法來進行UObject的可達性分析。
FGCCollector的UML繼承關系圖如下所示：
前面，我們經過了标記過程，那些标記了不可達标記的物體可以進行删除了，為了減少卡頓，虛幻4加入了增量清除的概念（IncrementalPurgeGarbage()函數），就是一次删除隻占用固定的時間片，當然，如果是編譯器狀态或者是強制完全清除（比如下一次GC了，但是上一次增量清除還沒有完成，那麼就會強制清除）。
IncrementalPurgeGarbage()函數的大體流程如下圖所示：
還記得我們前面說的虛幻4使用簇來提高GC的效率嗎，下面是CollectGargageInternal函數中的一段，這個時候已經完成了可達性分析，代碼如下所示：
for
可以看到，如果UObject帶有EInternalObjectFlags::ClusterRoot且不可達，那麼它會直接把上面的UObject（Cluster->Objects）符合條件的進行銷毀，并且把目前簇删除掉。
總結到此為止，我們對虛幻4中的垃圾回收進行了大概的講解，知道了它的GC是追蹤式、非實時、精确式，非漸近、增量回收（時間片），先标記後回收的過程，為了提高效率和減少回收過程中的卡頓，可以做到并行标記和增量回收以及通過簇來提高回收的效率等。這篇文章隻能給你一個大概的了解，如果想要清楚其中的細節，看代碼是免不了的。另外中間有錯誤的地方，如果讀者發現也請指正。歡迎大家留言讨論。
參考文獻- https://zh.wikipedia.org/wiki/%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6_(%E8%A8%88%E7%AE%97%E6%A9%9F%E7%A7%91%E5%AD%B8)
- http://www.cnblogs.com/superjt/p/5946059.html