【USparkle專欄】如果你深懷絕技，愛“搞點研究”，樂于分享也博采眾長，我們期待你的加入，讓智慧的火花碰撞交織，讓知識的傳遞生生不息！

這是侑虎科技第1958篇文章，感謝作者南京周潤發(fā)供稿。歡迎轉(zhuǎn)發(fā)分享，未經(jīng)作者授權(quán)請勿轉(zhuǎn)載。如果您有任何獨到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群：793972859）

作者主頁：

https://www.zhihu.com/people/xu-chen-71-65

總覽

UE5的GC，相對UE4做了一些改動，但本質(zhì)沒變，依然是基于UObject的標(biāo)記清掃算法，許多改動都屬于優(yōu)化。

先看GC的各個階段：

• 遍歷所有Object，標(biāo)記為不可達(dá)

改動較少，增加了RefCount引用方式；更改了Unreachable Flag；增加了單獨的RootArray作為根集。

• 遍歷引用關(guān)系做可達(dá)性分析

改動較多，Batch模式的引用收集；UObject對ClassPrivate和Outer的引用從Token中移除；增加了引用收集的Debug模式。

• 清理不可達(dá)Object

差別不大，依然是分幀Purge，對每個UObject依次執(zhí)行BeginDestroy, Destroy, FinishDestroy。

除此之外，還有實驗性的Increment可達(dá)性分析模式，想完全避免可達(dá)性分析造成的一幀卡頓，算是一個最大的不同。

對于GC Cluster，變化不大。

另外還有一些其他Tips，比如IsPendingKill接口改成了IsGarbage；ObjectFlags增加了Reachable0，Reachable1，Reachable2等等。

文章中所使用的為UE5.7。

前篇：

一、加入引用計數(shù)機(jī)制

1. RefCounted Flag & RefCount

觀察InternalObjectFlags，發(fā)現(xiàn)多了一個叫RefCounted的Flag，說明UE的GC在標(biāo)記清掃的基礎(chǔ)上，又加入了引用計數(shù)機(jī)制，算是一個不小的改動。

引用計數(shù)是另一種GC方式，Python中就使用了，簡單概括為每個Object記錄自己被多少個其他Object引用了，當(dāng)發(fā)現(xiàn)引用計數(shù)為0時，就判定自己為垃圾。至于垃圾的清理，可以選擇為0時立即清理，也可以選擇之后一起清理，反正垃圾是不會再被重新引用到的。

enum class EInternalObjectFlags : int32
{
    None = 0,
    //...
    RefCounted UE_DEPRECATED(5.7, "Use GetRefCount() to determine if a refcount exists instead.") = 1 << 29, ///< Object currently has ref-counts associated with it.
    //...
};

但有了Flag還不夠，得給每個Object再定義一個RefCount屬性，記錄被引用的次數(shù)。UE5.7之前，在FUObjectItem中有一個專門的int32 RefCount屬性，但UE5.7開始把RefCount和Flags一起打包成了int64。Flag存在高32位里，RefCount存在低32位里。

這樣有個好處，RefCount通常用不了int32這么大，因此可以把更多位數(shù)給EInternalObjectFlags用，比如添加一些我們自定義的Flag，或者UE引擎自己擴(kuò)展。

2. 操作接口

添加RefCount：

void UObjectBase::AddRef() const
{
    FUObjectItem* ObjectItem = GUObjectArray.ObjectToObjectItem(this);
    ObjectItem->AddRef();
}

減去RefCount：

void UObjectBase::ReleaseRef() const
{
    FUObjectItem* ObjectItem = GUObjectArray.ObjectToObjectItem(this);
    ObjectItem->ReleaseRef();
}

獲取RefCount：

在引擎內(nèi)部代碼，比如GC過程中，才有獲取RefCount的需求，因此UObject上沒有獲取RefCount的接口，只有FUObjectItem上有。

FORCEINLINE int32 GetRefCount() const
{
    return RefCount;
}

哪些地方會給UObject加上引用計數(shù)？

引用計數(shù)管理UObject顯然更容易出錯，萬一AddRef/ReleaseRef不成對，就會造成UObject泄漏，引擎中目前也只有StrongObjectPtr使用了。而且是用了RAII模式，在構(gòu)造和析構(gòu)中操作RefCount，防止泄漏。StrongObjectPtr可以對一個UObject添加強(qiáng)引用，防止被GC，和AddToRoot類似。下面是StrongObjectPtr中操作的代碼：

FORCEINLINE_DEBUGGABLE void Reset(ObjectType* InNewObject)
{
    if (InNewObject)
    {
        if (Object == InNewObject)
        {
            return;
        }


         if (Object)
        {
            // UObject type is forward declared, ReleaseRef() is not known.
            // So move the implementation to the cpp file instead.
            UEStrongObjectPtr_Private::ReleaseUObject(Object);
        }
        InNewObject->AddRef();
        Object = InNewObject;
    }
    else
    {
        Reset();
    }
}

3. 為什么要使用引用計數(shù)管理UObject

一個原因可能是能減少可達(dá)性分析時間。

可達(dá)性分析階段需要遍歷Object間的所有引用關(guān)系，耗時正比于引用數(shù)量。

比如下圖，4個UObject相互引用，總共要遍歷10個引用關(guān)系。但假如都用引用計數(shù)管理，可以省略遍歷開銷，直接判定四個對象都可達(dá)。

但是理論上講，引用計數(shù)方式只是把遍歷開銷分?jǐn)偟搅诉\(yùn)行時維護(hù)引用計數(shù)的加減上。而且注意到上面例子其實是環(huán)形引用的情況，沒有外部引用情況下，四個UObject都該被判定為垃圾才對。因此一個完善的垃圾回收實現(xiàn)，不會只用引用計數(shù)，比如Python的FullGC就用的標(biāo)記-清掃算法，作為輔助。UE依然把標(biāo)記-清掃作為主GC流程，引用計數(shù)只是小小的輔助，但使用是絕對要注意。

另一個原因是單獨針對StrongObjectPtr的優(yōu)化。

StrongObjectPtr之前的實現(xiàn)是把包起來的UObject單獨放到一個大數(shù)組里，然后這個數(shù)組被一個FGCObject添加引用。這樣有個問題，當(dāng)數(shù)組元素很多時，添加需要遍歷全數(shù)組，判斷是否已添加過，而刪除時同樣需要遍歷全數(shù)組，找到元素并刪除，遍歷的時間很可觀。

4. RefCount如何影響可達(dá)性分析

其實RefCount等同于Root，觀察AddRef調(diào)用鏈，最終會執(zhí)行AddToRoot操作。

在第一步標(biāo)記所有UObject不可達(dá)后，會遍歷GRoots容器，把其中的UObject變成可達(dá)，那么RefCounted的Object也變成可達(dá)了。

二、可達(dá)性分析階段的優(yōu)化

1. FPrefetchingObjectIterator

首先介紹一個挺細(xì)節(jié)的ObjectIterator，基于經(jīng)驗做了Prefetch，盡量避免訪問Object的Outer和ClassPrivate造成的CacheMiss。整個可達(dá)性分析階段都充分應(yīng)用了Prefetch技術(shù)。

首先觀察下面代碼，會遍歷一組UObject，然后分別訪問它們的Class和Outer：

FORCEINLINE_DEBUGGABLE void ProcessObjects(DispatcherType& Dispatcher, TConstArrayView 

 CurrentObjects 
)
{
    for (FPrefetchingObjectIterator It(CurrentObjects); It.HasMore(); It.Advance())
    {
        UObject* CurrentObject = It.GetCurrentObject();
        UClass* Class = CurrentObject->GetClass();
        UObject* Outer = CurrentObject->GetOuter();
        //...
    }
}

這樣必然會導(dǎo)致讀Object內(nèi)存操作，相比讀CPU Cache肯定是更慢的。粗略估計，訪問內(nèi)存的延遲是60ns，而訪問CPU L1 Cache的延遲是1ns，當(dāng)中相差不少。

既然已經(jīng)知道要訪問這么多Object的ClassPrivate和Outer屬性，那么能不能提前把它們讀取到CPU Cache中，加快訪問速度？這就是FPrefetchingObjectIterator做的事情，使用了操作系統(tǒng)的Prefetch接口，異步的提出一個預(yù)讀請求，不需要當(dāng)場等待內(nèi)容返回到CPU Cache，CPU可以繼續(xù)執(zhí)行后面指令。

FPrefetchingObjectIterator迭代器在++時，會Prefetch后面第六個的Outer和ClassPrivate的Schema，以及后面第16個的Class。這些數(shù)字都是經(jīng)驗值，既需要保證訪問到這塊內(nèi)存時，其已經(jīng)被加載到了CPU Cache，又不能Prefetch太多，從而擠占CPU Cache。

示意圖如下：

2. 基于Batch的Object引用收集

Batch

UE4怎么做的：

給定一個待分析可達(dá)性的Objects數(shù)組，會不斷遍歷其引用，做廣度優(yōu)先搜索，最終遍歷完所有可達(dá)的UObject，完成任務(wù)。其中碰到StructArray結(jié)構(gòu)時，還會形成類似遞歸的情況，處理代碼更復(fù)雜些。整個過程由一個大的ProcessObjectArray函數(shù)實現(xiàn)，總共有600+行。

UE5的Batch：

UE5使用了Batch的遍歷方式，首先把ProcessObjectArray邏輯拆成多個函數(shù)，函數(shù)邏輯精簡，最長不超過90行，對CPU指令Cache更友好，然后多個函數(shù)形成執(zhí)行流；大概500個Object作為一個Batch，依次經(jīng)過這些執(zhí)行流，更少的數(shù)據(jù)量對應(yīng)更少的內(nèi)存使用量，讓CPU Cache足夠應(yīng)對；另外每段處理函數(shù)邏輯變簡單后，可以更容易地使用上面提到的Prefetch技術(shù)做Cache預(yù)取，進(jìn)一步提升效率。

Schema

首先，UE5加入了Schema的概念，其實就是UE4里的TokenStream，記錄Object帶引用的各成員地址偏移，以及成員類型。

ProcessObjectArray

下面是ProcessObjectsArray的主要流程，首先執(zhí)行ProcessObjects，收集引用到Dispatcher，Dispatcher的具體類型為BatchedDispatcher。CurrentObjects處理完后，再嘗試從全部的ObjectsToSerialize數(shù)組中取出BlockSize數(shù)量的UObject，繼續(xù)執(zhí)行ProcessObjects做引用收集。如果ObjectsToSerialize也空了，就執(zhí)行FlushWork，把引用到的UObject都添加到ObjectsToSerialize中繼續(xù)。

這樣就能把標(biāo)記階段分成多個Pass，每個Pass處理一點Object，流程示意圖如下：

ProcessObjects

ProcessObjects用于收集CurrentObjects的所有引用，F(xiàn)PrefetchingObjectIterator已在上面提過。注意到這里把Class和Outer的處理單獨提出來了，UE4還是在正常的Schema里處理它們�？赡苁强紤]到Class和Outer是每個UObject必備的引用，提出來統(tǒng)一處理能減小Schema大小。

VisitMembers函數(shù)是真正的處理Schema里定義的各種引用，包括UPROPERTY引用單個Object，TArray 數(shù)組引用等等，這里只給出單個Object引用和StructArray引用兩個常見例子。

VisitStructArray只會把StructArray緩存到對應(yīng)容器中，后面Flush時再處理：

FORCEINLINE_DEBUGGABLE void QueueStructArray(FSchemaView Schema, uint8* Data, int32 Num)
{
    StructBatcher.PushStructArray(Schema, Data, Num);
}

ImmutableReference & KillableReference

注意到對于單個UObject的引用，分了ImmutableReference和KillableReference(FMutableReference)，其實只有UObject對Class和Outer的引用屬于Immutable，其他都屬于Killable。這對UE4而言并沒有提出新的內(nèi)容，只是老內(nèi)容包裝成了新概念。

比如有如下代碼，想強(qiáng)制刪除B，但B又是A的屬性，被引用了

A->Prop = B;

B->MarkAsGarbage();

對于Class和Outer引用，非常強(qiáng)力，強(qiáng)到能阻止對B的強(qiáng)刪，讓B繼續(xù)以Garbage的形式存在。

對于普通的KillableReference，無法阻止，同時A->Prop屬性會變成nullptr。

因此查看它們的初始化方式，F(xiàn)MutableReference是存儲了指向?qū)傩缘闹羔槨?/p>

// Retains address of reference to allow killing it
struct FMutableReference { UObject** Object; };
struct FImmutableReference { UObject* Object; };

FlushWork

依次處理StructArray和其他Object引用，主要工作就是遍歷各種Array。

FORCEINLINE_DEBUGGABLE void FlushWork(DispatcherType& Dispatcher)
{
    if constexpr (DispatcherType::bBatching)
    {
        if (Dispatcher.FlushToStructBlocks())
        {
            ProcessStructs(Dispatcher);
        }


         Dispatcher.FlushQueuedReferences();
    }
}

最終通過HandleValidReference函數(shù)，把UObject標(biāo)記為可達(dá)，并插入到ObjectsToSerialize數(shù)組中，以待后續(xù)遍歷。

三、配套Debug功能的完善

1. gc.history協(xié)助找泄露

其中一個比較實用的功能是可以記錄下上次GC過程中，每個對象被誰引用了，方便排查UObject泄露問題。

看個例子，假如有如下代碼：

FActorSpawnParameters SpawnParameters;
SpawnParameters.Name = TEXT("TestObject123");
APawn* TestPawn = GetWorld()->SpawnActor 

 (SpawnParameters); 

USceneComponent* TempObject = NewObject 

 (TestPawn, USceneComponent::StaticClass()); 

TempObject->RegisterComponent();
{
    TStrongObjectPtr 

   
StrongPtr(TempObject);
    TestPawn->Destroy();
    CollectGarbage(GARBAGE_COLLECTION_KEEPFLAGS, true);
    TempObject->MarkAsGarbage();
}


 GEngine->Exec(GetWorld(), TEXT("OBJ Refs Name=TestObject123"));

在有StrongObjectPtr的情況下，即使MarkAsGarbage，這次GC也是刪不掉TempObject和TestPawn的，在嚴(yán)格的邏輯下，算是UObject泄露。Obj Refs的輸出也印證了：

LogReferenceChain: (Garbage) Pawn /Game/UEDPIE_0_Zoo.Zoo:PersistentLevel.TestObject123 is not currently reachable. Try using GC history to debug transient leaks with 'gc.historysize 1'

輸出中只能看到UObject泄露了，但打印Obj Refs時，引用現(xiàn)場已經(jīng)沒了，不知道為什么泄露。過去，要調(diào)試這個泄露，得先記下Object地址，再去GC下數(shù)據(jù)斷點，再對Flags下斷點等等操作，非常麻煩。

現(xiàn)在UE5加了HistorySize的Debug功能，會對上次GC存儲Snapshot，之后再輸出。

首先通過如下控制臺指令開啟：

gc.ForceEnableGCProcessor
gc.Historysize 1

然后把Exec代碼改成：

FReferenceChainSearch::FindAndPrintStaleReferencesToObject(TestPawn, EPrintStaleReferencesOptions::Log);

接著就能從GC History中獲取到歷史GC引用了，快速定位到泄露原因，非常方便：

LogLoad: Old Pawn /Game/UEDPIE_0_Zoo.Zoo:PersistentLevel.TestObject123 not cleaned up by GC! Garbage object SceneComponent /Game/UEDPIE_0_Zoo.Zoo:PersistentLevel.TestObject123.SceneComponent_0 was previously being referenced by NULL:
 (refcounted<1>) (Garbage)  SceneComponent /Game/UEDPIE_0_Zoo.Zoo:PersistentLevel.TestObject123.SceneComponent_0
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     ^ This reference is preventing the old Pawn from being GC'd ^
 -> UObject* UObject::Outer = (Garbage)  Pawn /Game/UEDPIE_0_Zoo.Zoo:PersistentLevel.TestObject123

2. 實現(xiàn)原理

UE5中，新增了用于Debug的TDebugReachabilityProcessor，在可達(dá)性分析階段，當(dāng)?shù)谝淮伪闅v到一個Object時，把當(dāng)前路徑記錄下來即可。

四、增量式可達(dá)性分析

1. 為什么要做增量式可達(dá)性分析

增量式的垃圾回收，目前還是Experimental階段，個人感覺有點意義不明。

Documentation | Epic Developer Community

https://dev.epicgames.com/documentation/en-us/unreal-engine/incremental-garbage-collection-in-unreal-engine

一個典型例子是Lua虛擬機(jī)實現(xiàn)，采用了黑白灰三色標(biāo)記，UE的實現(xiàn)也比較類似。

開啟方式：

DefaultEngine.ini加入下面配置：

[ConsoleVariables]
gc.AllowIncrementalReachability=1 ; enables Incremental Reachability Analysis
gc.AllowIncrementalGather=1 ; enables Incremental Gather Unreachable Objects
gc.IncrementalReachabilityTimeLimit=0.002 ; sets the soft time limit to 2ms

為什么有必要把可達(dá)性分析階段改成增量式的？

GC耗時可以分成三個部分：所有UObject先標(biāo)記不可達(dá)，可達(dá)性分析，銷毀垃圾。其中，銷毀垃圾本身是分幀的，不會造成卡頓。前兩個部分過去不能分幀，而可達(dá)性分析階段是耗時主要部分，通常超過第一部分十倍，如果游戲希望維持60幀或更高幀率運(yùn)行，這絕對會是一個阻礙。為了緩解這個卡頓，UE很早就提出了Cluster優(yōu)化方案，現(xiàn)在又進(jìn)一步提出了增量GC方案。

為什么之前可達(dá)性分析不能分幀執(zhí)行？

考慮這樣的場景，假如可達(dá)性分析要多幀完成，在中間執(zhí)行了A.XX = B語句，使A引用到B，但A已經(jīng)完成了可達(dá)性分析，UE識別不到這個新加的引用。那么B就有可能被錯誤當(dāng)成垃圾回收掉。

可是這是官方文檔的解釋，但個人感覺不太符合正常使用場景，還沒想通。不妨把B分成下面兩種情況：

1. B在這次GC開始前已創(chuàng)建，如果此時B沒有其他引用了，那么代碼里又是如何獲取到B的？存裸指針當(dāng)然可以，但本身也是不規(guī)范的做法。

2. B在這次GC開始后才創(chuàng)建，但新創(chuàng)建UObject默認(rèn)是Reachable的，不會被這次GC刪除。這點和Lua是有區(qū)別的，因為Lua里Object創(chuàng)建后默認(rèn)不可達(dá)。

這個也許和增量回收還處于Experimental有關(guān)，邏輯還不成熟，不妨順著UE思路繼續(xù)往下看實現(xiàn)。

2. Write Barrier

解決這種問題還是要靠Write Barrier。得益于UE5中把裸指針替換為TObjectPtr，使得A.XX = B這種語句能被捕獲到了。

TObjectPtr會在Operator =函數(shù)里做檢查，如果發(fā)現(xiàn)正在GC，就會立即把B作為可達(dá)對象，加到全局GReachableObjects或GReachableClusters鏈表中。

之后以GReachableObjects為例，在可達(dá)性分析的PerformReachabilityAnalysisPass函數(shù)開頭，會首先把GReachableObjects容器中的Object作為InitialObjects，當(dāng)成初始可達(dá)對象，然后繼續(xù)做可達(dá)性分析遍歷。

這只是TObjectPtr的處理，我們也會定義些自定義邏輯，然后使用AddReferenceObjects函數(shù)添加引用，這就不太好處理了。

3. 如何實現(xiàn)分幀

回顧之前的ProcessObjectsArray函數(shù)，已經(jīng)實現(xiàn)了Batch形式的Object遍歷，每趟處理500個Object，那么分幀也是比較方便實現(xiàn)的。這一段TimeLimit邏輯控制了每幀可以花費多少時間做可達(dá)性分析，超過了就給下一幀繼續(xù)執(zhí)行，會從CollectGarbage入口進(jìn)來。

既然分幀，就要保留當(dāng)前GC進(jìn)度，要知道還有哪些Object需要遍歷。這些信息就存儲在Context.InitialObjects數(shù)組里。因為可達(dá)性分析階段是多線程執(zhí)行的，因此每個線程都有自己的Context。

其實不僅可達(dá)性分析階段做了增量式處理，后面的收集不可達(dá)對象階段也支持了增量執(zhí)行。只是耗時本身不高，邏輯也更簡單，進(jìn)度保留在Context中即可。

開啟增量GC后的Trace如下，可以看到實現(xiàn)了分幀，但還不能做到完美的Timelimit分幀：

五、其他Tips

1. ReachabilityFlag0, ReachabilityFlag1

UE5在標(biāo)記所有Object不可達(dá)時，不再遍歷所有Object并設(shè)置UnReachable標(biāo)記，而是交替使用兩種ReachabilityFlag，同時依然有UnReachableFlag，用來表示真正的不可達(dá)Object：

ReachabilityFlag0 = 1 << 14, ///< One of the flags used by Garbage Collector to determine UObject's reachability state
ReachabilityFlag1 = 1 << 15, ///< One of the flags used by Garbage Collector to determine UObject's reachability state
ReachabilityFlag2 = 1 << 16, ///< One of the flags used by Garbage Collector to determine UObject's reachability state


 Unreachable = 1 << 28, ///< Object is not reachable on the object graph.

交替兩個ReachabilityFlag代碼如下：

FORCEINLINE static void SwapReachableAndMaybeUnreachable()
{
    // It's important to lock the global UObjectArray so that the flag swap doesn't occur while a new object is being created
    // as we set the GReachableObjectFlag on all newly created objects
    GUObjectArray.LockInternalArray();

     Swap(ReachableObjectFlag, MaybeUnreachableObjectFlag);

     // Maintain the old flag variables for backwards compatibility
    PRAGMA_DISABLE_DEPRECATION_WARNINGS
    UE::GC::GReachableObjectFlag = ReachableObjectFlag;
    UE::GC::GMaybeUnreachableObjectFlag = MaybeUnreachableObjectFlag;
    PRAGMA_ENABLE_DEPRECATION_WARNINGS

     GUObjectArray.UnlockInternalArray();
}

如此能實現(xiàn)這一幀F(xiàn)lag0表示可達(dá)，F(xiàn)lag1表示可能不可達(dá)，下一幀反過來，下下一幀再反過來。

然后一次GC結(jié)束后，PostCollectGarbageImpl，GatherUnreachableObjects會遍歷所有UObject，把依然有MaybeUnreachableObjectFlag的Object視為垃圾，標(biāo)記上Unreachable Flag。

遍歷完成后，插入到專門儲存待清理對象的GUnreachableObjects數(shù)組中。

2. MarkAsGarbage取代MarkAsPendingKill

UE4對于強(qiáng)刪的Object，比如Actor，會MarkAsPendingKill，UE5把接口改成了MarkAsGarbage：

inline void MarkAsGarbage()
{
    check(!IsRooted());

     AtomicallySetFlags(RF_MirroredGarbage);
    GUObjectArray.IndexToObject(InternalIndex)->SetGarbage();

     // If we explicitly marked the object as garbage, remove the async flag so it's visible to the GC
    AtomicallyClearInternalFlags(EInternalObjectFlags::Async);
}

對應(yīng)的IsPendingKill判斷也改成了IsValid：

inline bool UKismetSystemLibrary::IsValid(const UObject* Object)
{
    return ::IsValid(Object);
}

文末，再次感謝南京周潤發(fā)的分享， 作者主頁：https://www.zhihu.com/people/xu-chen-71-65， 如果您有任何獨到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群： 793972859 ）。

近期精彩回顧